I am trying to create a hybrid list that uses Binary Search Trees for various functions. The class tries to implement List< E >. To index, these trees use comparison to decide whether data should be placed in the left or right child of the parent. This is done using a Comparator variable set by the Constructor:
private Comparator<E> comparator; // method for ordering the tree
This ensures that type E will be comparable in some way. The problem however is in how the List Interface declared its abstract functions. For example:
public boolean contains(Object o);
Normally, I would assume that the parameter is comparable and then use a recursive lookup method on the tree, but because the parameter is Object, I cannot make that assumption.
I have tried to ensure that it is of type E by doing the following:
if (o instanceof E) {}
but it does not work and gives me this suggestion:
Cannot perform instanceof check against type parameter E.
Use its erasure Object instead since further generic type information will be erased at runtime
Any ideas on how to solve this?
Edit:
This is how the class is instantiated:
TreeCollection<Integer> c = new TreeCollection<>(
new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
There's no perfect answer for your situation. There's a kind of conflict between the Comparator, where correct use is enforced by compile-time generics, and the .contains() method, whose contract depends on .equals(), which takes any type of object (there is no compile-time constraint), and whose logic must be based on runtime information. This problem is also faced by TreeSet.
The whole point of your data structure is lookup is O(log n), so you cannot go through every element and check; instead, you must go down the binary search tree, by comparing the given value to the elements using the comparator. But since the given element is any type of object, we don't know the comparator can take it. I think the best solution is just to cast it to E and assume that your comparator can take it. If the object is not an instance of E, the comparator will probably throw ClassCastException somehow, and you can just let that exception pass up to the user. TreeSet takes this approach -- the documentation for TreeSet.contains() says that it throws ClassCastException when the specified object cannot be compared with the elements in the set.
Although this makes .contains() less general, it avoids breaking the contract of Collection.contains(), because in the case where someone gives us an object to .contains() that our comparator cannot compare, the correct answer could be true or false according to the contract, but we can't determine that efficiently; so instead of returning something that might be wrong, we throw an exception, which is allowed in the contract.