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