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