Reputation: 41
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
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:
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. isSimilar()
on the first and second pair.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
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
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
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
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