001 package ps3.graph;
002
003 import java.util.*;
004
005 /**
006 * A NodeCountingPath characterizes a path of WeightedNodes. The cost
007 * for a path is the number of WeightedNodes it contains; the cost of the
008 * WeightedNodes are ignored.<p>
009 *
010 * A NodeCountingPath is immutable. A new NodeCountingPath is returned through
011 * the extend path operation. <p>
012 *
013 * <p>The main purpose of this class is to illustrate that there can be multiple
014 * implementations of Paths of WeightedNodes.</p>
015 *
016 * Specfields inherited from Path:
017 *
018 * @specfield cost : double // cost of traversing this path.
019 * @specfield elements : sequence // sequence of nodes in this path.
020 *
021 **/
022
023 public class NodeCountingPath implements Path<WeightedNode, NodeCountingPath> {
024
025 // The representation invariant describes what invariants hold for
026 // the concrete representation.
027 //
028 // RepInvariant:
029 // RI(c) =
030 // (c.node != null) &&
031 // (c.path == null) ==> (c.cost == 1) &&
032 // (c.path != null) ==> (c.cost == 1 + c.path.cost)
033 //
034
035 //
036 // Abstraction Function:
037 //
038 // The abstract state is given in terms of the specfields of the
039 // Path interface, namely the cost and elements of a path.
040 //
041 // The AF uses two helper functions, which map a concrete state
042 // 'c' to the abstract state.
043 //
044 // AF(c) = < ncpcost(c), ncpelms(c) >
045 // (Maps c to ncp cost and ncp elements abstract fields recursively)
046 //
047 // ncpcost(c) = c.cost
048 // ncpelms(c) = / [c.node] if (c.path == null)
049 // \ ncpelms(c.path) + [c.node] if (c.path != null)
050 //
051 // (Note that [c.node] appears at the *end* not the *start* of the
052 // path sequence.)
053 //
054 // To make the AF(c) clearer, we could also write the following:
055 // AF(c) = < cost, elements > where
056 // cost = c.cost
057 // elements = [c.node] if c.path == null
058 // [c.node] + c.path.elements if c.path != null
059 //
060
061 /** The WeightedNode at the end of the path. */
062 private final WeightedNode node;
063 /** A NodeCountingPath which, when extended with 'node' at the end,
064 * is equal to this. May be null iff this path has only 1 element. */
065 private final /*@Nullable*/ NodeCountingPath path;
066 /** The cost of this NodeCountingPath (that is, its length). */
067 private final int cost;
068
069
070 /**
071 * Constructs a NodeCountingPath containing one node.
072 *
073 * @requires node != null
074 * @effects Creates a new NodeCountingPath which originates at
075 * <code>node</code>.
076 **/
077 public NodeCountingPath(WeightedNode node) {
078 this(node, null);
079 }
080
081 /**
082 * @requires node != null
083 * @effects Creates a new NodeCountingPath 'res' such that
084 * res.elements = path.elements + [ node ]
085 **/
086 private NodeCountingPath(WeightedNode node,
087 /*@Nullable*/ NodeCountingPath path) {
088 if (node == null) {
089 throw new IllegalArgumentException();
090 }
091 this.node = node;
092 this.path = path;
093 if (path != null) {
094 this.cost = 1 + path.cost;
095 } else {
096 this.cost = 1;
097 }
098 }
099
100
101
102 // Specified by Path interface.
103 public NodeCountingPath extend(WeightedNode node) {
104 return new NodeCountingPath(node, this);
105 }
106
107 // Specified by Path interface.
108 public double cost() {
109 return cost;
110 }
111
112 // Specified by Path interface (which extends Iterable)
113 public Iterator<WeightedNode> iterator() {
114 // reverse the linked list, so that elements are returned in order
115 // from start to end of the path.
116 List<WeightedNode> accumulator = new LinkedList<WeightedNode>();
117 for (NodeCountingPath cur = this; cur!=null; cur = cur.path) {
118 accumulator.add(0, cur.end());
119 }
120 return accumulator.iterator();
121 }
122
123 /**
124 * @return a string representation of this.
125 **/
126 public String toString() {
127 StringBuilder sb = new StringBuilder();
128 sb.append("[NodeCountingPath: ");
129 boolean first=true;
130 for (WeightedNode wn : this) {
131 if (first) first = false;
132 else sb.append(", ");
133 sb.append(wn);
134 }
135 sb.append("]");
136 return sb.toString();
137 }
138
139 /**
140 * @return true iff o is a NodeCountingPath and o.elements is the
141 * same sequence as this.elements
142 **/
143 @Override
144 public boolean equals(/*@Nullable*/ Object o) {
145 if (!(o instanceof NodeCountingPath))
146 return false;
147 return this.equals((NodeCountingPath) o);
148 }
149
150 /**
151 * @return true iff wnp.elements is the same sequence as this.elements
152 **/
153 public boolean equals(NodeCountingPath wnp) {
154 return (wnp != null) &&
155 this.node.equals(wnp.node) &&
156 (this.path == null ? wnp.path==null : this.path.equals(wnp.path));
157 }
158
159 /**
160 * @return a valid hashcode for this.
161 **/
162 public int hashCode() {
163 return node.hashCode() + (this.path==null ? 0 : 13 * path.hashCode());
164 }
165
166
167 /**
168 * Compares the cost of this path to the given path.
169 * @return the value 0 if the cost of this path is equal to the
170 * cost of the given path; a value less than 0 if this.cost is
171 * less than p.cost; and a value greater than 0 if this.cost
172 * is greater than p.cost.
173 * @see java.lang.Comparable#compareTo
174 */
175 public int compareTo(Path<?,?> p) {
176 return Double.compare(this.cost(), p.cost());
177 }
178
179 /**
180 * Return the end of this path
181 */
182 public WeightedNode end() {
183 return node;
184 }
185 }