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;
    }
}

Solution 1

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);
}

Solution 2

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

Comments

[Whizzil]

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.

[Joop Eggen]

The last 1 should be something like (n1.hashCode() - n2.hashCode())

[Whizzil]

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.

[Pshemo]

@Whizzil Sorry, no idea of how you can improve it.

[steffen]

@JoopEggen Why so? hashCode may return the same value for two unequal objects -> problem postponed. Check System.identityHashCode() instead.

[Joop Eggen]

@steffen hasty comment on my side