Max Johnson
Max Johnson

Reputation: 41

How to compare lists in java with a method other than .equals()

I want to compare two lists of objects. I want a method that will return a collection of the equal objects (intersections) of the lists. However, the type of object in these lists uses a method other than .equals() to be compared (.isSimilar). Is there a streamlined and efficient way to go about this?

Upvotes: 4

Views: 2342

Answers (5)

einpoklum
einpoklum

Reputation: 132310

Please avoid changing the semantics of equals(), both for lists and for items...

Anyway, I think you might like to use Guava's functional idioms:

  • Define an Iterable<Pair<T,T>>-implementing class constructed with a pair of List<T>, with the iteration proceeding from one pair of corresponding elements to the next.
  • Create a predicate on pairs which uses isSimilar() on the first and second pair.
  • Use Iterables.any(theIterableYouCreated, thePredicateYouCreated).

Don't have a pair class already? See here. Also, you'll need to handle the case of different lengths, which you can do before constructing the iterator; or you could do it some other way.

Upvotes: 1

Joni
Joni

Reputation: 111389

The built-in methods all use the standard equals method to see if two objects are equal; none will use your custom isSimilar method.

Luckily it's easy to program the logic for computing the intersection yourself: go through the elements in the first list, and add it to the intersection if it exists in the second list.

List<YourObject> intersection = new ArrayList<YourObject>();
for (YourObject a: list1) for (YourObject b: list2) {
    if (a.isSimilarTo(b)) {
        intersection.add(a);
        break;
    }
}

Computational complexity: if first list has n items and second list has m items this algorithm makes potentially O(nm) comparisons. If the lists were sorted or if a different data structure could be used (for example a hash table) the complexity could be reduced to O(n+m).

On the other hand, you can create a wrapper class for your objects and that uses the isSimilar method for equality:

final class YourObjectWrapper {
    YourObject value;
    public boolean equals(Object o) {
        return o instanceof YourObjectWrapper
                   ? value.isSimilarTo(((YourObjectWrapper) o).value) 
                   : false;
    }
    // don't forget to override hashCode
}

If you fill your lists with these wrapper objects you can use built-in methods like retainAll.

Upvotes: 4

Nir Alfasi
Nir Alfasi

Reputation: 53565

You can work around the isSimilar() issue either by setting equals() to call isSimilar() in the item class or by using a class that extends one of List implementations and there you should override the method contains() to use isSimilar() instead of equals().

Upvotes: 1

Joop Eggen
Joop Eggen

Reputation: 109613

No solution present. I take it that you cannot sort the lists (similarity). Hence you need to compare every element from one list with all of the others to see whether no similar is found, in order to reject it. N x M, quadratic complexity.

Upvotes: 0

BlackHatSamurai
BlackHatSamurai

Reputation: 23513

The efficient streamlined way to do this is to write you own method for this. That said, this would be a simple method, where you compare the two objects and if they are equal you add them to a list, or other collection.

Upvotes: 0

Related Questions