compareTo with objects returns a false while it is true

Question

I am trying to check whether my levelorder of my Binary Search Tree is equal to the other one. To do this, I tried to make a compareTo method. I only give equal values to the method, but it keeps on saying the condition is false. When I place breakpoints, I see that the values are still equal. I am probably not understanding it correctly. Does anyone know how to solve this?

Here is what I did, as you can see below, the compareTo returns a 1 instead of a 0:

import edu.princeton.cs.algs4.BST;
import java.util.*;

public class MyBST implements Comparable<MyBST>{

    private Object e;

    public MyBST(Object e){
        this.e = e;
    }

    private Object getE(){
        return e;
    }

    public static void main(String[] args) {

        int size = 4;

        Random r = new Random();
        Set<Integer> tes = new LinkedHashSet<>(size);
        Stack<Integer> stack = new Stack<>();

        while (tes.size() < size) {
            tes.add(r.nextInt(10));
        }

        System.out.println("possible combinations");
        Set<Stack<Integer>> combos = combos(tes, stack, tes.size());

        Object[] arr = combos.toArray();
        List<String> d = new ArrayList<>();
        for (Object s : arr) {
            String b = s.toString();
            b = b.replaceAll("\\[", "").replaceAll("\\]", "");
            d.add(b);
        }

        int index = 0;

        do {
            BST<String, Integer> bst1 = new BST<String, Integer>();
            BST<String, Integer> bst2 = new BST<String, Integer>();
            String key1 = d.get(index);
            String key2 = d.get(index);
            key1 = key1.replaceAll(" ", "");
            String[] m = key1.split(",");

            key2 = key2.replaceAll(" ", "");
            String[] n = key2.split(",");

            System.out.println("1e order");
            for (int j = 0; j < m.length; j++) {

                System.out.println(m[j]);
                bst1.put(m[j], 0);
            }

            System.out.println("2e order");
            for (int j = 0; j < n.length; j++) {

                System.out.println(n[j]);
                bst2.put(n[j], 0);
            }

            System.out.println("levelorder 1e BST");

            MyBST e = new MyBST(bst1.levelOrder());
            MyBST y = new MyBST(bst2.levelOrder());

            System.out.println(bst1.levelOrder());

            System.out.println("levelorder 2e BST");

            System.out.println(bst2.levelOrder());

            System.out.println(e.compareTo(y) + "\n");
            index++;
        } while (index < arr.length - 1);

    }
    public static Set<Stack<Integer>> combos(Set<Integer> items, Stack<Integer> stack, int size) {
        Set<Stack<Integer>> set = new HashSet<>();

        if (stack.size() == size) {
            set.add((Stack) stack.clone());
        }
        Integer[] itemz = items.toArray(new Integer[0]);
        for (Integer i : itemz) {
            stack.push(i);
            items.remove(i);
            set.addAll(combos(items, stack, size));
            items.add(stack.pop());
        }
        return set;
    }

    @Override
    public int compareTo(MyBST o) {
        if (this.e == o.e) {
            return 0;
        }
        else
            return 1;
    }
}

Here you can find the BST.java class: BST.java

And the output is something like:

The breakpoint at the compareTo method says:

Answer 1

When you're using the == operator you're actually checking to see if the references point to the same object in memory. From your debugging screenshot you can see that they are not. this.e points to object Queue@817 while o.e points to Queue@819.

Answer 2

If all you want to do is test for equality, then just override equals and hashCode. You can do it like this (rest of class omitted):

public class MyBST {  

   private Object e;
  
   public MyBST(Object e) {
        this.e = e;
    }

    public Object getE(){
        return e;
    }
    
    @Override
    public int hashCode() {
        return Objects.hashCode(e);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!(obj instanceof MyBST))
            return false;
        MyBST me = (MyBST) obj;
        if (e == null) {
            if (me.e != null)
                return false;
        } else if (!e.equals(me.e))
            return false;
        return true;
    }
}

Implementing Comparable is more involved since you need to check for less, equal, or greater than other instances of MyBST. Unfortunately, the only field in MyBST is an Object which does not tell you anything about its actual fields. So without specific fields with which to test you need to ensure that the Object you pass also implements Comparable. Then you can declare your class like this. Rest of class omitted.

It simply says that

• MyBST is comparable.
• And the object that is passed in the constructor is comparable.

class MyBST<T extends Comparable<? super T>> implements Comparable<MyBST<T>>{

    private T e;

    public MyBST(T e){
        this.e = e;
    }

    public T getE(){
        return e;
    }
    
    @Override
    public int compareTo(MyBST<T> o) {
        return e.compareTo(o.e);    
    }
}

The other alternative is to simply pass the actual object type and store it as such, not as Object. Then just implement Comparable in MyBST and use the appropriate fields of the passed object. Lets say the object was an Apple object, you could do this.

class Apple {
    String type;
    int weight;
}

class MyBST implements Comparable<MyBST> {
    
    private Apple apple;
    
    public MyBST(Apple apple) {
        this.apple = apple;
    }
    
    @Override
    public int compareTo(MyBST e) {
        // this could be different depending on how you wanted
        // to compare one apple to another. This comparison favors
        // type over weight.

        // check type - String class implements comparable
        int ret = apple.type.compareTo(e.apple.type);
        if (ret != 0) { 
            return ret;
        }
        
        // same type so check weight
        if (apple.weight < e.apple.weight) {
            return -1;
        }
        if (apple.weight > e.apple.weight) {
            return 1;
        }
        return 0;  // equals apples based on criteria
    }
}

Finally, you have this.

    private Object getE(){
        return e;
    }

A private getter is not usually very useful. Make it public.