CODEWITHSUNDEEP
javagenericsbinary-search-treecomparablecompareto
Stefan Sprenger
Stefan Sprenger

Reputation: 1080

Java Generics Comparable | implement compareTo

I'm facing a problem with java generics. My plan is to implement a binary search tree (key & value) with generics with total ordering. I started by creating this KeyValPair and faced the problem of getting the right compareTo method.

public class KeyValPair <V extends Comparable<V>>
        implements Comparable<KeyValPair<V>>{

    private int key;
    private V value;
    private KeyValPair<V> leftchild;
    private KeyValPair<V> rightchild;

    public KeyValPair(int k,V v){
        key=k;
        value=v;
    }

    public Comparable<?> getKey(){
        return key;
    }

    public Comparable<?> getValue(){
        return value;
    }

    public void setRightChild(KeyValPair<V> r){
        rightchild=r;
    }

    public KeyValPair<V> getRightChild(KeyValPair<V> r){
        return rightchild;
    }

    public void setLeftChild(KeyValPair<V> l){
        leftchild=l;
    }

    public KeyValPair<V> getLeftChild(KeyValPair<V> l){
        return leftchild;
    }

    @Override
    public int compareTo(KeyValPair<V> toComp) {
        if(this.getValue().compareTo(toComp.getValue())>0){
            return -1;
        }else if(this.getValue().compareTo(toComp.getValue())==0){
            return 0;
        }else{
            return 1;
        }
    }

}

The if sentences in compareTo are not acceppted and I think it's because of the fact that I overrode the compareTo, but how should I compare generics?

Also tried Comparable instead of K with same result.

Best Regards

EDIT: What compiler says: Multiple markers at this line - The method compareTo(capture#1-of ?) in the type Comparable is not applicable for the arguments (Comparable) - Line breakpoint:KeyValPair [line: 39] - compareTo(KeyValPair)

EDIT2:

UPDATED CODE:

public class KeyValPair{

private int key;
private Comparable<?> value;
private KeyValPair leftchild;
private KeyValPair rightchild;

public KeyValPair(int k,Comparable<?> v){
    key=k;
    value=v;
}

public Comparable<?> getKey(){
    return key;
}

public Comparable<?> getValue(){
    return value;
}

public void setRightChild(KeyValPair r){
    rightchild=r;
}

public KeyValPair getRightChild(KeyValPair r){
    return rightchild;
}

public void setLeftChild(KeyValPair l){
    leftchild=l;
}

public KeyValPair getLeftChild(KeyValPair l){
    return leftchild;
}

}

Now i updated the code of the KEYVALPAIR, but if i test it with my BST Class with method adder as example:

private void adder(KeyValPair current,KeyValPair toInsert) {
    if(toInsert.getValue().compareTo(current.getValue())>0){
        //dosomething
    }
}

it throws: The method compareTo(capture#2-of ?) in the type Comparable is not applicable for the arguments (Comparable)

SOLUTION:

I solved it by putting KEYVALPAIR as inner class to BST and use V extends Comparable. Works now, thanks for your help.

Upvotes: 0

Views: 3069

Answers (2)

zapl
zapl

Reputation: 63955

You don't need to cast key or value to comparable since V is required to be comparable already. Doing so just makes it harder to use your class because now you have just a Comparable instead of usable values or keys.

public int getKey() {
    return key;
}

public V getValue() {
    return value;
}

@Override
public int compareTo(KeyValPair<V> toComp) {
    return -this.getValue().compareTo(toComp.getValue());
}

You should also consider to relax the requirement that V must implement Comparable<V>

class KeyValPair<V extends Comparable<? super V>>

would allow e.g. classes like Apple extends Fruit implements Comparable<Fruit> - those can still be ordered if they are comparable to super types.

Upvotes: 2

Adam Arold
Adam Arold

Reputation: 30528

Your problem here is that you are required to compare V to an other V and you don't have the slightest idea about its runtime type.

It can be a String or an Integer and you obviously don't compare them the same way.

So I think that your KeyValPair should not implement Comparable since its members (V instances) are already doing so: <V extends Comparable<V>>.

If you want some comparison you can simply do something like:

leftChild.getValue().compareTo(rightChild.getValue());

getValue() should also return Comparable<V>, the wildcard is not necessary.

Upvotes: 0

Related Questions