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.traverse.basic;
018:
019: import org.geotools.graph.structure.Graph;
020: import org.geotools.graph.structure.GraphVisitor;
021: import org.geotools.graph.structure.Graphable;
022: import org.geotools.graph.traverse.GraphIterator;
023: import org.geotools.graph.traverse.GraphTraversal;
024: import org.geotools.graph.traverse.GraphWalker;
025:
026: /**
027: * A basic implementation of GraphTraversal.
028: *
029: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
030: *
031: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/traverse/basic/BasicGraphTraversal.java $
032: */
033: public class BasicGraphTraversal implements GraphTraversal {
034:
035: /** the graph being iterated over **/
036: private Graph m_graph;
037:
038: /** the walker being iterated over the graph **/
039: private GraphWalker m_walker;
040:
041: /** the iterator specifying the order in which to visit components of
042: the graph during the traversal **/
043: private GraphIterator m_iterator;
044:
045: /**
046: * Constrcuts a new graph traversal.
047: *
048: * @param graph The graph being traversed.
049: * @param walker The walker being traversed over the components of the graph.
050: * @param iterator The iterator specifying the order in which to visit
051: * components of the graph.
052: */
053: public BasicGraphTraversal(Graph graph, GraphWalker walker,
054: GraphIterator iterator) {
055: m_graph = graph;
056: m_walker = walker;
057: setIterator(iterator);
058: }
059:
060: /**
061: * @see GraphTraversal#setGraph(Graph)
062: */
063: public void setGraph(Graph graph) {
064: m_graph = graph;
065: }
066:
067: /**
068: * @see GraphTraversal#getGraph()
069: */
070: public Graph getGraph() {
071: return (m_graph);
072: }
073:
074: /**
075: * Sets the iterator and intializes it.
076: *
077: * @see GraphIterator#init(Graph)
078: * @see GraphTraversal#setIterator(GraphIterator)
079: */
080: public void setIterator(GraphIterator iterator) {
081: m_iterator = iterator;
082: m_iterator.setTraversal(this );
083: m_iterator.init(m_graph, this );
084: }
085:
086: /**
087: * @see GraphTraversal#getIterator()
088: */
089: public GraphIterator getIterator() {
090: return (m_iterator);
091: }
092:
093: /**
094: * @see GraphTraversal#setWalker(GraphWalker)
095: */
096: public void setWalker(GraphWalker walker) {
097: m_walker = walker;
098: }
099:
100: /**
101: * @see GraphTraversal#getWalker()
102: */
103: public GraphWalker getWalker() {
104: return (m_walker);
105: }
106:
107: /**
108: * Resets the visited flag and counts of all nodes of the graph.
109: *
110: * @see GraphTraversal#init()
111: */
112: public void init() {
113: //initialize the nodes of the graph
114: m_graph.visitNodes(new GraphVisitor() {
115: public int visit(Graphable component) {
116: component.setVisited(false);
117: component.setCount(0);
118: return (0);
119: }
120: });
121: }
122:
123: /**
124: * Upon each iteration of the traversal, a component is returned from the
125: * iterator and passed to the visitor. The traversal interprets the return
126: * codes from the walker and performs the following actions. <BR>
127: * <BR>
128: * <TABLE border="1" width="60%" style="font-family:Arial;font-size=10pt">
129: * <TH width="20%">Code</TH>
130: * <TH width="40%">Action Performed</TH>
131: * <TR>
132: * <TD align="center">CONTINUE</TD>
133: * <TD>The traversal instructs the iterator to continue and starts the
134: * next stage of iteration.</TD>
135: * </TR>
136: * <TR>
137: * <TD align="center">SUSPEND</TD>
138: * <TD>The traversal instructs the iterator to continue but does not start
139: * the next stage of iteration, returning from traverse().</TD>
140: * </TR>
141: * <TR>
142: * <TD align="center">KILL_BRANCH</TD>
143: * <TD>The traversal instructs the iterator to kill the current branch
144: * and starts the next stage of iteration.</TD>
145: * </TR>
146: * <TR>
147: * <TD align="center">STOP</TD>
148: * <TD>The traversal does not instruct the iterator to continue and
149: * does not start the next of iteration, returning from traverse()
150: * </TD>
151: * </TR>
152: * </TABLE>
153: *
154: * @see GraphTraversal#traverse()
155: */
156: public void traverse() {
157: Graphable current;
158:
159: //get next component from iterator, null means stop
160: O: while ((current = m_iterator.next(this )) != null) {
161: setVisited(current, true);
162:
163: //pass the component to the visitor
164: switch (m_walker.visit(current, null)) {
165: case CONTINUE:
166: //signal iterator to continue from this point and start next
167: // iteration of traversal
168: m_iterator.cont(current, this );
169: continue;
170:
171: case SUSPEND:
172: //signal iterator to continue from this point, but do not start
173: // next iteration
174: m_iterator.cont(current, this );
175: return;
176:
177: case KILL_BRANCH:
178: //signal iterator to kill branch at this point and start next
179: //iteration
180: m_iterator.killBranch(current, this );
181: continue;
182:
183: case STOP:
184: //stop traversal
185: break O;
186:
187: default:
188: //illegal return value from walker
189: throw new IllegalStateException(
190: "Unrecognized return value from GraphWalker");
191: }
192: }
193:
194: //traversal complete, signal to walker
195: m_walker.finish();
196: }
197:
198: public void setVisited(Graphable g, boolean visited) {
199: g.setVisited(visited);
200: }
201:
202: public boolean isVisited(Graphable g) {
203: return (g.isVisited());
204: }
205: }
|