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() < 021 * p2.cost()</tt>, then for all nodes <tt>n</tt>, we must have that 022 * <tt>p1.extend(n).cost() < 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<N></tt>. Then the <tt>extend</tt> 030 * function would be defined as returning a <tt>Path<N></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