CODEWITHSUNDEEP
javasortingarraylist
jackthehipster
jackthehipster

Reputation: 1018

Sorted List in Java with elements of same value but different identity

I know there are dozens of questions similar to this one, but I couldn't find an answer to my specific problem. Sorry if I missed it - please tell me where to look if it exists!

The problem seems very common to me: I need a list of objects that is sorted by some property of the object, and only have each object once in the list. Specifically, I am implementing A* path finding and need the open list sorted by the F-values of the nodes.

What I tried was using a TreeSet with a Comparator that compares the f-values of two Nodes, like this:

public class NodeFComparator implements Comparator<Node> {

    @Override
    public int compare(Node arg0, Node arg1) {
        return (arg0.getF() - arg1.getF());
    }

}

Class Node is looking like this :

public class Node {

    PathableMap parentmap;
    Point coord;    // coordinates on the map
    private Node parent;    // parent node: used by astar to backtrace shortest path

    (etc etc)

    /*
     * F-value of a node is the sum of the distance from start + distance to target.
     * The nodes are searched in the order of that value.
     */
    public int getF() {
        return getG() + getH();
    }

    @Override
    public int hashCode() {
        final int prime = 65537;
        return prime * coord.x + coord.y;
    }

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

}

The problem with this solution seems to be that if two different nodes have the same f-value (which happens all the time), in other words the comparator returns 0, the TreeSet seems to treat that as Node1 == Node2 and doesn't add the second node to the list or does some other weird thing because my openlist misses nodes that should be there.

So the only way I can think of doing this with the existing classes is to use a simple ArrayList and sort it each time I append a Node to it.

Is there really no collection class in Java or Apache Commons that:

I'm puzzled.

Upvotes: 0

Views: 2409

Answers (4)

David Conrad
David Conrad

Reputation: 16359

Don't use a set if you want to have elements that compare equal (in this case, that have the same f-value). The A* algorithm is typically defined with respect to a priority queue, and as of Java 5 there is a PriorityQueue implementation provided in the Java collections API:

import java.util.PriorityQueue;

. . .

PriorityQueue nodes = new PriorityQueue<Node>(new NodeFComparator());

Upvotes: 3

nitnamby
nitnamby

Reputation: 414

If the compare method is not consistent with equals implementation you got be careful which collection classes you got to use. TreeSet is not a good choice here. One alternative would be look at Multimap implementations in Guava library https://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap

Upvotes: 0

tbodt
tbodt

Reputation: 16987

Just change your comparator a little:

public class NodeFComparator implements Comparator<Node> {
    @Override
    public int compare(Node arg0, Node arg1) {
        int result = arg0.getF() - arg1.getF();
        if (result == 0)
            return arg0.hashCode() - arg1.hashCode();
        return result;
    }
}

This will return correct results for nodes with different f-values, and when the nodes have the same f-values, they will be compared by their hash codes. You could use any other unique property other than the hash code for this, but I chose hash codes because they are almost unique and every object has them.

Upvotes: 2

ktm5124
ktm5124

Reputation: 12123

You're right, you can use ArrayList instead of TreeSet, since it won't remove items that are duplicates (according to the comparator that you pass it).

You can add your Nodes to an ArrayList, and when you're ready to sort it, invoke the method from the Collections class,

Collections.sort(myList, myComparator)

Upvotes: 2

Related Questions