Custom object comparator

Question

I will try to get right to the point.

I am having my custom Node objects, which have attribute Cost. I would want to sort those Node objects in ascending order by their attribute Cost.

I was able to do so using PriorityQueue<Node> = new PriorityQueue<Node>(10000, new NodeComparator());, but that way worked too slow for me, and now I am looking to do the same thing, only using TreeSet. Anyways, if my constructor looks like this TreeSet<Node> = new TreeSet<Node>(new NodeComparator());, the program seems to skip vast amount of Node objects, seemingly treating them as they are the same. Which they are not. I am assuming there might be some hashCode issues about, but I am not sure, and I don't know how to resolve it at this moment.

To be concise, I just want my Nodes in TreeSet to be ordered in ascending way by Cost attribute. Here is my NodeComparator class:

public class NodeComparator implements Comparator<Node> {

    @Override
    public int compare(Node n1, Node n2) {
        // TODO Auto-generated method stub
        if(n1.cost > n2.cost) return 1;
        else if(n1.cost < n2.cost) return -1;
        else return 0;
    }

}

And here is my Node class:

public class Node{

    public State state;
    public int cost;

    public Node(State s, int Cost){
        this.state = s;
        this.cost = Cost;
    }

    public State getState(){

        return this.state;
    }

    public int getCost(){
        return this.cost;
    }
}

I will provide you with my State class aswell.

public class State {

    public int lamp;

    public ArrayList<Integer> left;


    public State(ArrayList<Integer> Left, int Lamp){
        lamp = Lamp;
        left = Left;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + lamp;
        result = prime * result + ((left == null) ? 0 : left.hashCode());
        return result;
    }


    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        State other = (State) obj;
        if (lamp != other.lamp)
            return false;
        if (left == null) {
            if (other.left != null)
                return false;
        } else if (!left.equals(other.left))
            return false;
        return true;
    }
}

`Set` by default - eliminates duplicates. You need to override your `equals()` & `hashCode()` in your `Node` class. — Rahul, Mar 26 '13 at 11:21
check [this][1] out. You need to change your comparator. [1]: http://stackoverflow.com/questions/1470735/java-treeset-and-hashcode — Abhishek Agarwal, Mar 26 '13 at 11:54

Pshemo · Accepted Answer · 2013-03-26T11:48:21.363

5

TreeSet uses TreeMap to store values. Your problem is that TreeMap instead equals uses result of comparator to check if element is already in map. Because of that you need to include state of steate field in compare method like

@Override
public int compare(Node n1, Node n2) {
    // TODO Auto-generated method stub
    if(n1.cost > n2.cost) return 1;
    else if(n1.cost < n2.cost) return -1;
    else return ( n1.equals(n2)? 0 : 1);
}

edited Mar 26 '13 at 11:48

answered Mar 26 '13 at 11:43

Pshemo

122,468
25
185
269

1

The last `1` should be something like `(n1.hashCode() - n2.hashCode())` – Joop Eggen Mar 26 '13 at 11:47
Yes, you are right. It works that way, but it doesn't really resolve my initial problem of speed, since that way is 30% slower even then it was using PriorityQueue. Any advice on that? Maybe better implementation of NodeComparator (for example which compares hash values in some way) in combination with TreeMap would give the proper result. – Whizzil Mar 26 '13 at 11:52
@Whizzil Sorry, no idea of how you can improve it. – Pshemo Mar 26 '13 at 12:12
@JoopEggen Why so? `hashCode` may return the same value for two unequal objects -> problem postponed. Check `System.identityHashCode()` instead. – steffen May 09 '16 at 11:27
@steffen hasty comment on my side – Joop Eggen May 09 '16 at 12:25

score 1 · Answer 2 · answered Mar 26 '13 at 11:25

1

Set by default eliminates duplicates. You need to override your equals() & hashCode() in your Node class.

answered Mar 26 '13 at 11:25

Rahul

44,383
11
84
103

I tried that, but the problem persists. That way, it only goes through 620 Nodes, and using PriorityQueue it goes through 136000 Nodes. Not sure why. And I have overriden equals() nad hashCode() in my State class, that might do aswell. – Whizzil Mar 26 '13 at 11:36

Custom object comparator

2 Answers2