comparing two generic objects if the one is "greater" or "smaller"

Question

I want to generate a binary tree with key - value pairs in their nodes.

In my binary tree I want to implement nodes at the beginning with an insert method, which implements a new left node if the key is smaller than the key of the current node. Then if there is already a left node it will check again for it. The same logic follows for right/greater node inserts.

I wrote my code first using the int type because it's way easier for me to test my code before I use generics (new topic for me). It worked when using int but I an unsure how to compare two generics with themselves by using "<" or ">".

public ListCell<Type> checkKey(Type key, ListCell<Type> checkCell) {
    ListCell<Type> newCell = null;
    if (key < checkCell.key && checkCell.left != null) {
        ...
    }
    ...
}

I don't know if it's worth saying but I'm creating my binary tree with a selfcoded list. Above you can see my current checks but i can't compare my given key now with checkCell.key because of them not being numbers.

So my general question is how to compare the keys in generics if they are "smaller" or "greater" than the other for my implementation in a binary tree.

Thanks in advance

Answer 1

You would need to ensure that your generic type implemented the Comparable interface, and then use the compareTo method instead. Java does not support overloading the > operator (or any operator overloading, for that matter).

As per the documents, compareTo:

Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

An example (that you'll have to map on to your exact code), assuming that key is your item you will store in your node, and checkCell.key is your node

int compareResult = key.compareTo(checkCell.key);
if (key < 0) { // it goes on the left }
else if (key == 0) { // it is the same }
else { // it goes on the right }

In your compareTo method you need to decide what fields in your class determine it's "ordering". For example, if you have a size and priority field, you might do:

@Override public int compareTo(Type other) {
  final int BEFORE = -1;
  final int EQUAL = 0;
  final int AFTER = 1;

  if (this == other) return EQUAL;

  if (this.size < other.size) return BEFORE;
  else if (this.size > other.size) return AFTER;
  else { // size is equal, so test priority
    if (this.priority < other.priority) return BEFORE;
    else if (this.priority > other.priority) return AFTER;
  }
  return EQUAL;
}