001    package ps3.graph;
002    
003    import java.util.Iterator;
004    
005    /**
006     * <p>
007     * A Path models a sequence of nodes and the cost for travelling along such a
008     * sequence.
009     * </p>
010     *
011     * <p>
012     * Paths are immutable.
013     * </p>
014     *
015     * @specfield cost : double // cost of traversing this Path
016     * @specfield elements : sequence // the nodes in this Path
017     *
018     *
019     * <p> The cost of traversing a path must not decrease as the path is
020     * extended with new nodes.  Additionally, if <tt>p1.cost() &lt;
021     * p2.cost()</tt>, then for all nodes <tt>n</tt>, we must have that
022     * <tt>p1.extend(n).cost() &lt; p2.extend(n).cost()</tt> </p>
023     *
024     * <p>
025     * The first generic argument (<tt>N</tt>) is the type of nodes in the path.
026     * The second generic argument (<tt>P</tt>) should be the name of the
027     * implementing class itself (see WeightedNodePath for an example). Why is this
028     * second argument necessary? Imagine that this interface was defined as
029     * <tt>public interface Path&lt;N&gt;</tt>. Then the <tt>extend</tt>
030     * function would be defined as returning a <tt>Path&lt;N&gt;</tt>. But this
031     * is not specific enough; for example, the extend method on WeightedNodePath
032     * could return a NodeCountingPath, or vice versa! The second generic
033     * argument lets us force the implementing class to define an extend method that
034     * returns an element of the same type.
035     * </p>
036     */
037    public interface Path<N, P extends Path<N,P>>
038        extends Iterable<N>, Comparable<Path<?, ?>> {
039    
040        // Producers
041    
042        /**
043         * Creates an extended path by adding a new node to its end.
044         * @requires n != null &&
045                     n is a valid node type for this particular path
046                     implementation
047         * @return a new Path p such that
048         *       p.elements = this.elements + [ n ]
049         *    && p.cost >= this.cost
050         **/
051        P extend(N n);
052    
053        // Observers
054    
055        /** @return this.cost **/
056        double cost();
057    
058        /** @return the end of the path **/
059        N end();
060    
061        /**
062         * @return an Iterator over the elements in the path in order from
063         *         start to end.
064         */
065        public Iterator<N> iterator();
066    
067    } // Path