I want to implement a Heap based on an Array. However, this Heap is should be callable with an Array of either only elements that implement the Comparable interface or with an additional Comparator (so if no Comparator is given it is assumed every element can be compareTo with one another). Then I want to check for its validity. It doesn't work because the heapCondition for extends Comparable can not be called.
public class Heap <T>{
Object[] tree;
Comparator<T> comparator;
public <T extends Comparable<T>> Heap(T[] tree){
this.tree = tree;
}
public Heap(T[] tree, Comparator<T> comparator){
this.tree = tree;
this.comparator = comparator;
}
/**
* defines the heapCondition default is set so the Heap is a minHeap (parent is smaller than their children)
* @param parent parent node
* @param child child node
*/
public <T extends Comparable<T>> boolean heapCondition(T parent, T child){
return parent.compareTo(child) < 0;
}
public boolean heapCondition(T parent, T child){
if(comparator == null){
// go into the heap condition where to Comparable is assumed
heapCondition(parent,child);
}
return comparator.compare(parent,child) < 0;
}
/**
* @return boolean whether or not the current tree fulfills the Heap condition
*
*/
private boolean valid(){
for(int i = 0; 2*i+2 < tree.length; i++){
// returns false if the condition is not met for one of the children
return !(!heapCondition((T) tree[i], (T) tree[2*i+1]) || !heapCondition((T) tree[i],(T) tree[2*i+2]));
}
return true;
}
}
In your implementation Heap <T> and public <T extends Comparable<T>> boolean heapCondition are not the same Ts. The generic method creates other T and shadows T from the class definition. That's why your public boolean heapCondition can't call public <T ...> boolean heapCondition.
Actually, you can't require T to be Comparable in the case when Comparator == null and T to be any class otherwise. java.util.TreeMap implements something similar. It uses compareTo when Comparator == null. But this logic is done by using runtime casting and throwing ClassCastException when the object is not Comparable. Here is JavaDoc of java.util.TreeMap
/**
* Constructs a new, empty tree map, using the natural ordering of its
* keys. All keys inserted into the map must implement the {@link
* Comparable} interface. Furthermore, all such keys must be
* <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
* a {@code ClassCastException} for any keys {@code k1} and
* {@code k2} in the map. If the user attempts to put a key into the
* map that violates this constraint (for example, the user attempts to
* put a string key into a map whose keys are integers), the
* {@code put(Object key, Object value)} call will throw a
* {@code ClassCastException}.
*/
public TreeMap() {
comparator = null;
}
And here is getEntry implementation which casts elements to Comparable:
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
...
You need to remove all generics except for Heap <T> definition. Also, when your comparator == null, you're not returning the result, thus making infinite recursion. And in your valid method you're always returning after the first iteration.
Here is how your heap may look like.
class Heap<T> {
T[] tree;
Comparator<? super T> comparator;
public Heap(T[] tree) {
this.tree = tree;
this.comparator = null;
}
public Heap(T[] tree, Comparator<? super T> comparator) {
this.tree = tree;
this.comparator = comparator;
}
/**
* defines the heapCondition default is set so the Heap is a minHeap (parent is smaller than their children)
*
* @param parent parent node
* @param child child node
*/
public boolean heapConditionComparable(T parent, T child) {
@SuppressWarnings("unchecked")
Comparable<? super T> comparableParent = (Comparable<? super T>) parent;
return comparableParent.compareTo(child) < 0;
}
public boolean heapCondition(T parent, T child) {
if (comparator == null) {
// go into the heap condition where to Comparable is assumed
return heapConditionComparable(parent, child);
}
return comparator.compare(parent, child) < 0;
}
/**
* @return boolean whether or not the current tree fulfills the Heap condition
*/
boolean valid() {
for (int i = 0; i < (tree.length - 2) / 2; ++i) {
// returns false if the condition is not met for one of the children
if (!(!heapCondition(tree[i], tree[2 * i + 1]) || !heapCondition(tree[i], tree[2 * i + 2]))) {
return false;
}
}
return true;
}
}