001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2002, Refractions Reserach Inc.
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.graph.path;
018:
019: import java.util.ArrayList;
020: import java.util.Collection;
021: import java.util.Collections;
022: import java.util.Iterator;
023: import java.util.List;
024:
025: import org.geotools.graph.structure.Edge;
026: import org.geotools.graph.structure.Node;
027:
028: /**
029: * Represents a walk in a graph. A <B>walk</B> W is defined as an ordered set
030: * of nodes that two adjacenct nodes in the set share
031: * an edge. More precisley: <BR>
032: * <BR>
033: * G = {N,E}
034: * W = { n(i) in N | (n(i-1),n(i)) in E }
035: *
036: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
037: *
038: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/path/Walk.java $
039: */
040: public class Walk extends ArrayList implements NodeSequence {
041:
042: private List m_edges;
043:
044: //TODO: DOCUMENT ME!
045: public Walk() {
046:
047: }
048:
049: //TODO: DOCUMENT ME!
050: public Walk(Collection nodes) {
051: super (nodes);
052: }
053:
054: /**
055: * A valid walk is one in which each pair of adjacent nodes in the sequence
056: * share an edge. Note,
057: */
058: public boolean isValid() {
059: //if edges were calculated successfly it is a valid walk
060: return (getEdges() != null);
061: }
062:
063: /**
064: * Calculates the edges in the walk. If the edges of the walk cannot be
065: * calculated (due to an invalid walk), null is returned, otherwise the
066: * list of edges is returned.
067: *
068: * @return The edges of the walk, otherwise null if the edges cannot be
069: * calculated.
070: */
071: public List getEdges() {
072: //calculate edges
073: if (m_edges == null) {
074: m_edges = buildEdges();
075: }
076:
077: return (m_edges);
078: }
079:
080: /**
081: * Adds a node to the walk. Adding a node clears the edge list which will be
082: * recalculated on the next call to getEdges().
083: *
084: * @param node Node to add to the walk.
085: */
086: public boolean add(Node node) {
087: m_edges = null;
088: return (super .add(node));
089: }
090:
091: //TODO DOCUMENT ME!
092: public void add(int index, Object element) {
093: super .add(index, element);
094: m_edges = null;
095: }
096:
097: //TODO DOCUMENT ME!
098: public boolean add(Object o) {
099: return (add((Node) o));
100: }
101:
102: //TODO DOCUMENT ME!
103: public boolean addAll(Collection c) {
104: m_edges = null;
105: return (super .addAll(c));
106: }
107:
108: public boolean addAll(int index, Collection c) {
109: m_edges = null;
110: return (super .addAll(index, c));
111: }
112:
113: public boolean addEdge(Edge e) {
114: //append edge to end of path, path must be empty, or last node in path
115: // must be a node of the edge
116:
117: //save current edge list
118: List edges = getEdges();
119:
120: if (isEmpty()) {
121: //add both nodes
122: add(e.getNodeA());
123: add(e.getNodeB());
124: } else {
125: //walk is not empty, check to see if the last node is related to the edge
126: Node last = getLast();
127:
128: if (last.equals(e.getNodeA())) {
129: add(e.getNodeB());
130: } else if (last.equals(e.getNodeB())) {
131: add(e.getNodeA());
132: } else
133: return (false);
134: }
135:
136: //the addition of nodes resets the internal edge list so it must be rebuilt.
137: // In the case that an edge shares both of its nodes with another edge
138: // it is possible for the list to be rebuilt properly (ie. not contain
139: // the edge being added). To rectify this situation, a backup copy of the
140: // edge list is saved before the addition, the addition performed, the
141: // edge explicitly added to the backup edge list, and the internal
142: // edge list replaced by the modified backup
143: edges.add(e);
144: m_edges = edges;
145:
146: return (true);
147: }
148:
149: public void addEdges(Collection edges) {
150: for (Iterator itr = edges.iterator(); itr.hasNext();) {
151: Edge e = (Edge) itr.next();
152: addEdge(e);
153: }
154: }
155:
156: /**
157: * Removes a node from the walk. Removing a node clears the edge list which
158: * will be recalculated on the next call to getEdges().
159: *
160: * @param node Node to remove from the walk.
161: */
162: public void remove(Node node) {
163: super .remove(node);
164: m_edges = null;
165: }
166:
167: public Object remove(int index) {
168: m_edges = null;
169: return (super .remove(index));
170: }
171:
172: public boolean remove(Object o) {
173: m_edges = null;
174: return (super .remove(o));
175: }
176:
177: public boolean removeAll(Collection c) {
178: m_edges = null;
179: return (super .removeAll(c));
180: }
181:
182: /**
183: * Determines if the walk is closed. A closed walk is one in which the
184: * first and last nodes are the same.
185: *
186: * @return True if closed, otherwise false.
187: */
188: public boolean isClosed() {
189: if (isEmpty() || !isValid())
190: return (false);
191: return (get(0).equals(get(size() - 1)));
192: }
193:
194: /**
195: * @see NodeSequence#getFirst()
196: */
197: public Node getFirst() {
198: return ((Node) get(0));
199: }
200:
201: /**
202: * @see NodeSequence#getLast()
203: */
204: public Node getLast() {
205: return ((Node) get(size() - 1));
206: }
207:
208: /**
209: * Internal method for building the edge set of the walk. This method
210: * calculated the edges upon every call.
211: *
212: * @return The list of edges for the walk, or null if the edge set could
213: * not be calculated due to an invalid walk.
214: */
215: protected List buildEdges() {
216: ArrayList edges = new ArrayList();
217:
218: for (int i = 1; i < size(); i++) {
219: Node prev = (Node) get(i - 1);
220: Node curr = (Node) get(i);
221:
222: Edge e = curr.getEdge(prev);
223:
224: if (e != null)
225: edges.add(e);
226: else
227: return (null);
228: }
229:
230: return (edges);
231: }
232:
233: /**
234: * Reverses the path.
235: */
236: public void reverse() {
237: Collections.reverse(this );
238: m_edges = null;
239: }
240:
241: /**
242: * Truncates the path at the specified index. Nodes in the path whose
243: * index is >= the specified index are removed.
244: *
245: * @param index The index of first node to be removed.
246: */
247: public void truncate(int index) {
248: removeRange(index, size());
249: m_edges = null;
250: }
251:
252: /**
253: * Returns an iterator that iterates over the path in reverse. The iterator
254: * does not support the remove operation.
255:
256: * @return the reverse iterator.
257: */
258: public Iterator riterator() {
259: return (new Iterator() {
260: int m_index = size() - 1;
261:
262: public void remove() {
263: throw new UnsupportedOperationException(
264: "Path iterator does not support remove()");
265: }
266:
267: public boolean hasNext() {
268: return (m_index > -1);
269: }
270:
271: public Object next() {
272: return (get(m_index--));
273: }
274: });
275: }
276:
277: //TODO: DOCUMENT ME!!!
278: public Path duplicate() {
279: return (new Path(this ));
280: }
281:
282: public boolean equals(Object other) {
283: if (other instanceof Walk)
284: return (equals((Walk) other));
285: return (false);
286: }
287:
288: public boolean equals(Walk other) {
289: if (other.size() == size()) {
290: //make a node by node comparision
291: Iterator this nodes = iterator();
292: Iterator othernodes = other.iterator();
293:
294: while (this nodes.hasNext()) {
295: Node this node = (Node) this nodes.next();
296: Node othernode = (Node) othernodes.next();
297:
298: if (!this node.equals(othernode))
299: return (false);
300: }
301: return (true);
302: }
303: return (false);
304: }
305:
306: public int hashCode() {
307: int hash = 7;
308: hash = 31 * hash + getFirst().hashCode();
309: hash = 31 * hash + getLast().hashCode();
310: return (hash);
311: }
312:
313: }
|