root/trunk/SearchNode.java

//
//  SearchNode.java
//  Pathways
//
//  Created by Andres J. Tack on 1/9/05.
//  Copyright 2005 __MyCompanyName__. All rights reserved.
//

// Searchnode holds everything we "mark" on a node - it's costs, it's parent,
// and which list it's part of.  There is no explicit closed list, instead,
// if the searchnode exists, look at its isOpen property to see whether it's
// open or closed.  This avoids costly TreeSet membership tests, in favor of
// cheaper membership tests on a HashMap.

class SearchNode implements Comparable {

        public SearchNode(Node n) {
                node = n;
                f = h = g = Cost.ZERO;
        }

        // TreeSet, a SortedSet, will use this to maintain its ordering
        public int compareTo(Object o) {
                // XXX NOTE UGLY HACK!!!
                // We are using a TreeMap that indexes on Cost as the basis for
                // our open list.  Maps can't have multiple values for one key,
                // so if two nodes have the same f-cost, they will overwrite
                // each other in the open list, which is obviously bad.
                //
                // The correct way to fix this would be to implement a special
                // OpenList class, which would maintain a treemap that maps
                // costs to linked lists of possibly multiple nodes.  This
                // would probably be bad for performance.
                //
                // Instead, we will cause SearchNode to violate the general
                // contract of compareTo, given in the Java docs, that
                // (x.compareTo(y) > 0 == y.compareTo(x) < 0).  By ensuring that
                // SearchNodes are never equal, they will never overwrite each
                // other in the open list, and the performance should still
                // be good.  The main loop also includes tests to ensure
                // that this has worked.

                // Sane version:
                //return f.compareTo(((SearchNode)o).f);

                // Evil version:
                if(f.compareTo(((SearchNode)o).f) <= 0) return -1;
                else return 1; // never return 0
        }

        // only for debugging purposes
        public String toString() {
                String ret = new String();
                ret += "Node " + node.id + " f:" + f + " g:" + g + " h:" + h;
                return ret;
        }

        // which node we refer to
        public final Node node;

        // where we came from, useful for backtracking to determine the path
        public Edge parent;
        // the f, h, and g costs used in the algorithm
        public Cost f, h, g;
        // is the node on the open list?  otherwise, it's closed
        public boolean isOpen;
}