Java comparing generic types

Question

In Java, I wrote a Binary Search Tree class that adds nodes using recursion. Now I want to generalize it using Generics so I can learn more about them.

public class GBinNode<T> {
    T item;
    GBinNode<T> left;
    GBinNode<T> right;

public GBinNode(T newItem) {
    item = newItem;
    left = null;
    right = null;
    }
public GBinNode(T it, GBinNode<T> le, GBinNode<T> ri) {
    item = it;
    left = le;
    right = ri;
    }
public String toString() {
    return item.toString()+" ";
    }
}

My function to add nodes is in the following class

public class GBinTree<T extends Comparable <T>> {
  GBinNode<T> add(T item, GBinNode<T> bn) {
    if (bn==null) {
        return new GBinNode<T>(item, null, null);
    }
    if (item < bn.item) {        // ERROR HERE
        bn.left = add( item, bn.left);
    }
    else {
        bn.right = add( item, bn.right);
    }
    return bn;
}

public void toString(GBinNode<T> root) {
    GBinNode<T> curr = root;
    if (curr == null)
        return;
    else {
        toString(curr.left);
        System.out.println(curr.toString());    // inorder traversal
        toString(curr.right);
    }
}

The main class has the following code to kick things off. I'm using strings, but the data type could be some complex type.

GBinTree<String> bt = new GBinTree<String>();
    GBinNode<String> root = null;
    root = bt.add("Calex", root);
    root = bt.add("Ealex", root);
    root = bt.add("Balex", root);
    root = bt.add("Dalex", root);       
    bt.toString(root);

I started to use the Comparable interface but then how do I write the CompareTo() function? I don't know what type T will be? The error I got was "The operator < is undefined for the argument type(s) T, T".

Searching for a solution, one answer was Comparing generic types Java:

class Element<T extends Comparable<T>>

I don't understand where this should go, and how it's different from the class implementing Comparable. The only place I know the type is in the main class, so should the compareTo() be there? I looked at making GBinTree an interface, but got confused whether that was the right track? Any help would be appreciated.

for best results use <T extends Comparable<? super T>>

newacct
– newacct

2013-12-27 20:47:16 +00:00
Commented Dec 27, 2013 at 20:47 — newacct
– newacct, Commented Dec 27, 2013 at 20:47
Please check this post I hope it meets your expectation.

Prabu R
– Prabu R

2020-08-25 20:52:43 +00:00
Commented Aug 25, 2020 at 20:52 — Prabu R
– Prabu R, Commented Aug 25, 2020 at 20:52

Sotirios Delimanolis · Accepted Answer · 2019-03-19 18:11:04Z

43

You cannot overload operators in Java. The < operator only applies to primitive (or numeric) types, not reference types. Since T is a type variable that represents a reference type, you cannot use < on variables of type T. You have to use

if (item.compareTo(bn.item) < 0)

check the value returned and decide to do what you wish with it.

You don't know what the type T will be but you know that it will be a type that implements Comparable and therefore implements the compareTo() method.

edited Mar 19, 2019 at 18:11

answered Dec 27, 2013 at 0:26

Sotirios Delimanolis

281k62 gold badges718 silver badges744 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Dennis Meng Over a year ago

A side note on that last paragraph for OP's benefit: Basically, you as the person implementing GBinNode<T extends Comparable<T>> are not responsible for implementing compareTo, it's the job of whoever is using your code to make sure that whatever T is, it already has that method implemented. Otherwise, the code won't even compile.

user2483498 · Accepted Answer · 2017-06-27 07:01:31Z

3

You can use this simple approach
for data greater than root.getData = 1, for data equals root.getData = 0,for data lesser than root.getData = -1

public class BST<E extends Number & Comparable<? super E>>{
    void add(){
    ...
    if(data.compareTo(root.getData()) == 1)
    ...
}

answered Jun 27, 2017 at 7:01

user2483498

393 bronze badges

Comments

JPG · Accepted Answer · 2022-02-12 11:08:07Z

0

Came across this problem when writing generic sorting. Best solution that i came up with is to add a Comparator to the argument of sorting function and use the compare method. You will have to override the compare(T o1,To2) method at/before function call while creating new Comparator<T>() , T to be replaced by the desired type.

answered Feb 12, 2022 at 11:08

JPG

1

Comments

Destroy666 · Accepted Answer · 2023-05-26 21:55:37Z

To address the issue and make your GBinTree class work with generics, you need to make a few modifications. Here's an updated version of your code:

public class GBinNode<T extends Comparable<T>> {
    T item;
    GBinNode<T> left;
    GBinNode<T> right;

    public GBinNode(T newItem) {
        item = newItem;
        left = null;
        right = null;
    }

    public GBinNode(T it, GBinNode<T> le, GBinNode<T> ri) {
        item = it;
        left = le;
        right = ri;
    }

    public String toString() {
        return item.toString() + " ";
    }
}

public class GBinTree<T extends Comparable<T>> {
    GBinNode<T> add(T item, GBinNode<T> bn) {
        if (bn == null) {
            return new GBinNode<T>(item, null, null);
        }
        if (item.compareTo(bn.item) < 0) {
            bn.left = add(item, bn.left);
        } else {
            bn.right = add(item, bn.right);
        }
        return bn;
    }

    public void toString(GBinNode<T> root) {
        if (root == null)
            return;
        else {
            toString(root.left);
            System.out.println(root.toString()); // inorder traversal
            toString(root.right);
        }
    }

    public static void main(String[] args) {
        GBinTree<String> bt = new GBinTree<String>();
        GBinNode<String> root = null;
        root = bt.add("Calex", root);
        root = bt.add("Ealex", root);
        root = bt.add("Balex", root);
        root = bt.add("Dalex", root);
        bt.toString(root);
    }
}

Here are the changes made:

In the GBinNode class, the generic type T is now restricted to implement the Comparable interface using T extends Comparable<T>. This allows you to use the compareTo method for comparing items in the tree.

In the GBinTree class, the add method uses item.compareTo(bn.item) instead of the < operator for comparison. This ensures that the comparison is done using the compareTo method of the generic type T.

The toString method in the GBinTree class now checks for root == null before performing traversal. This prevents errors when the tree is empty.

With these changes, you can now create a GBinTree object with any type that implements the Comparable interface, including custom types. The compareTo method is automatically available for comparisons within the add method.

Note: I also removed the space in the toString method of GBinNode class to align with the standard toString format.

Collectives™ on Stack Overflow

Java comparing generic types

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related