Best way to deal with some classes implementing comparable and some not in a Binary search tree

Question

I am looking for suggestions on how to handle some possible elements implementing comparable and some not.

I am currently trying to do it like this

class BinaryTree<E> { 
  private Comparator<E> comparator;
  public <T extends Comparable<E>>() BinaryTree() {
    comparator = (T a, T b) -> a.compareTo(b)
  }


  public BinaryTree(Comparator<E> comparator) { 
    this.comparator = comparator
  }
}

//rest of the class (add, remove etc)

And then the comparator variable is used. I cant get it to compile tho.

If you get compiler errors, your question should include copies of those errors. — Old Dog Programmer, Aug 14 '23 at 18:37
How does java's own library do it? There's no mention of Comparable in the [API method declarations](https://docs.oracle.com/javase/8/docs/api/java/util/TreeSet.html), if you didn't provide a comparator and the element is not comparable, it blows up with a ClassCastException at runtime. — teapot418, Aug 14 '23 at 18:55

score 1 · Answer 1 · answered Aug 14 '23 at 19:47

Just check and see if a comparator has been provided. If so, use it. Otherwise, presume that the objects implement it. The downside is that if the objects don't implement it you will get a runtime exception instead of a compiler error.

class BinaryTree<E> {

    private Comparator<E> comparator = null;

  
    public BinaryTree() {
    }
    
    public BinaryTree(Comparator<E> myComparator) {
          this.comparator = myComparator;
    }
    
    public void traverse() {
        if (comparator != null) {
            //use it
        } else {
            // compare Objects presuming they implement comparable.
        }
    }
}

Chaosfire · Answer 2 · 2023-08-15T09:23:58.290

Normally this use case is handled by casting. See TreeSet for example. One way to do it would be like this:

public BinaryTree() {
  this((e1, e2) -> ((Comparable<E>) e1).compareTo(e2));
}

Naturally, this will throw ClassCastException at runtime, if you try to add elements, which do not implement Comparable.

I would do it with a static factory method. Like this you can declare the type variable to be bound as a subclass of Comparable:

public class BinaryTree<E> {
  
  private Comparator<E> comparator;

  public static <T extends Comparable<T>> BinaryTree<T> fromComparable() {
    return new BinaryTree<>(Comparable::compareTo);
  }

  public BinaryTree(Comparator<E> comparator) { 
    this.comparator = comparator;
  }
}

The compiler now won't allow you to create a BinaryTree with non-comparable elements:

BinaryTree<Integer> tree1 = BinaryTree.fromComparable(); //compiles succesfully
BinaryTree<NonComparableClass> tree2 = BinaryTree.fromComparable(); //compilation error

Best way to deal with some classes implementing comparable and some not in a Binary search tree

2 Answers2