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 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, NodeCountingPath path) {
087 if (node == null) {
088 throw new IllegalArgumentException();
089 }
090 this.node = node;
091 this.path = path;
092 if (path != null) {
093 this.cost = 1 + path.cost;
094 } else {
095 this.cost = 1;
096 }
097 }
098
099
100
101 // Specified by Path interface.
102 public NodeCountingPath extend(WeightedNode node) {
103 return new NodeCountingPath(node, this);
104 }
105
106 // Specified by Path interface.
107 public double cost() {
108 return cost;
109 }
110
111 // Specified by Path interface (which extends Iterable)
112 public Iterator<WeightedNode> iterator() {
113 // reverse the linked list, so that elements are returned in order
114 // from start to end of the path.
115 List<WeightedNode> accumulator = new LinkedList<WeightedNode>();
116 for (NodeCountingPath cur = this; cur!=null; cur = cur.path) {
117 accumulator.add(0, cur.end());
118 }
119 return accumulator.iterator();
120 }
121
122 /**
123 * @return a string representation of this.
124 **/
125 public String toString() {
126 StringBuilder sb = new StringBuilder();
127 sb.append("[NodeCountingPath: ");
128 boolean first=true;
129 for (WeightedNode wn : this) {
130 if (first) first = false;
131 else sb.append(", ");
132 sb.append(wn);
133 }
134 sb.append("]");
135 return sb.toString();
136 }
137
138 /**
139 * @return true iff o is a NodeCountingPath and o.elements is the
140 * same sequence as this.elements
141 **/
142 @Override
143 public boolean equals(Object o) {
144 if (!(o instanceof NodeCountingPath))
145 return false;
146 return this.equals((NodeCountingPath) o);
147 }
148
149 /**
150 * @return true iff wnp.elements is the same sequence as this.elements
151 **/
152 public boolean equals(NodeCountingPath wnp) {
153 return (wnp != null) &&
154 this.node.equals(wnp.node) &&
155 (this.path == null ? wnp.path==null : this.path.equals(wnp.path));
156 }
157
158 /**
159 * @return a valid hashcode for this.
160 **/
161 public int hashCode() {
162 return node.hashCode() + (this.path==null ? 0 : 13 * path.hashCode());
163 }
164
165
166 /**
167 * Compares the cost of this path to the given path.
168 * @return the value 0 if the cost of this path is equal to the
169 * cost of the given path; a value less than 0 if this.cost is
170 * less than p.cost; and a value greater than 0 if this.cost
171 * is greater than p.cost.
172 * @see java.lang.Comparable#compareTo
173 */
174 public int compareTo(Path<?,?> p) {
175 return Double.compare(this.cost(), p.cost());
176 }
177
178 /**
179 * Return the end of this path
180 */
181 public WeightedNode end() {
182 return node;
183 }
184 }