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.structure.opt;
018:
019: import java.io.IOException;
020: import java.io.ObjectInputStream;
021: import java.io.ObjectOutputStream;
022: import java.util.ArrayList;
023: import java.util.Iterator;
024: import java.util.List;
025:
026: import org.geotools.graph.structure.DirectedEdge;
027: import org.geotools.graph.structure.DirectedNode;
028: import org.geotools.graph.structure.Edge;
029: import org.geotools.graph.structure.Node;
030:
031: /**
032: * Optimized implementation of DirectedNode. The following optimizations
033: * reduce space and increase performance. <BR>
034: * <UL>
035: * <LI>In and Out edge adjacency list stored as arrays of exact size.</LI>
036: * <LI>Support from removing edges is removed</LI>
037: * <LI>The related component iterators iterates over the underlying edge
038: * arrays of the node instread of newly created collections.
039: * </UL>
040: * Using an optimized directed node requires that the size of the in and out
041: * edge adjacency lists be known before its creation.
042: *
043: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
044: * @see DirectedNode
045: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/structure/opt/OptDirectedNode.java $
046: */
047: public class OptDirectedNode extends OptGraphable implements
048: DirectedNode {
049:
050: /** in edge adjacency list **/
051: transient private DirectedEdge[] m_in;
052:
053: /** out edge adjacency list **/
054: transient private DirectedEdge[] m_out;
055:
056: /**
057: * Constructs a new OptDirectedNode. This constructor does not create
058: * the edge adjacency arrays for the node.
059: *
060: */
061: public OptDirectedNode() {
062: this (0, 0);
063: }
064:
065: /**
066: * Constructs a new OptDirectedNode.
067: *
068: * @param indegree Number of in adjacenct edges to the node.
069: * @param outdegree Number of out adjacent edges to the node.
070: */
071: public OptDirectedNode(int indegree, int outdegree) {
072: super ();
073: m_in = new DirectedEdge[indegree];
074: m_out = new DirectedEdge[outdegree];
075: }
076:
077: /**
078: * Not supported.
079: *
080: * @throws UnsupportedOperationException
081: */
082: public void add(Edge e) {
083: throw new UnsupportedOperationException(getClass().getName()
084: + "#add(Edge)");
085: }
086:
087: /**
088: * @see DirectedNode#addIn(DirectedEdge)
089: */
090: public void addIn(DirectedEdge e) {
091: for (int i = 0; i < m_in.length; i++) {
092: if (m_in[i] == null) {
093: m_in[i] = e;
094: return;
095: }
096: }
097: }
098:
099: /**
100: * @see DirectedNode#addOut(DirectedEdge)
101: */
102: public void addOut(DirectedEdge e) {
103: for (int i = 0; i < m_out.length; i++) {
104: if (m_out[i] == null) {
105: m_out[i] = e;
106: return;
107: }
108: }
109: }
110:
111: /**
112: * Unsupported Operation.
113: *
114: * @throws UnsupportedOperationException
115: */
116: public void remove(Edge e) {
117: throw new UnsupportedOperationException(getClass().getName()
118: + "#remove(Edge)");
119: }
120:
121: /**
122: * Unsupported Operation.
123: *
124: * @throws UnsupportedOperationException
125: */
126: public void removeIn(DirectedEdge e) {
127: throw new UnsupportedOperationException(getClass().getName()
128: + "#removeIn(DirectedEdge)");
129: }
130:
131: /**
132: * Unsupported Operation.
133: *
134: * @throws UnsupportedOperationException
135: */
136: public void removeOut(DirectedEdge e) {
137: throw new UnsupportedOperationException(getClass().getName()
138: + "#removeOut(DirectedEdge)");
139: }
140:
141: /**
142: * @see Node#getEdge(Node)
143: */
144: public Edge getEdge(Node other) {
145: Edge e = getInEdge((DirectedNode) other);
146: if (e == null)
147: e = getOutEdge((DirectedNode) other);
148: return (e);
149: }
150:
151: /**
152: * @see DirectedNode#getInEdge(DirectedNode)
153: */
154: public Edge getInEdge(DirectedNode other) {
155: for (int i = 0; i < m_in.length; i++) {
156: if (m_in[i].getInNode().equals(other))
157: return (m_in[i]);
158: }
159: return (null);
160: }
161:
162: /**
163: * @see DirectedNode#getOutEdge(DirectedNode)
164: */
165: public Edge getOutEdge(DirectedNode other) {
166: ArrayList edges = new ArrayList();
167:
168: for (int i = 0; i < m_out.length; i++) {
169: if (m_out[i].getOutNode().equals(other))
170: return (m_out[i]);
171: }
172:
173: return (null);
174: }
175:
176: /**
177: * @see Node#getEdges(Node)
178: */
179: public List getEdges(Node other) {
180: List l = getInEdges((DirectedNode) other);
181: l.addAll(getOutEdges((DirectedNode) other));
182:
183: return (l);
184: }
185:
186: /**
187: * @see DirectedNode#getInEdges(DirectedNode)
188: */
189: public List getInEdges(DirectedNode other) {
190: ArrayList edges = new ArrayList();
191:
192: for (int i = 0; i < m_in.length; i++) {
193: if (m_in[i].getInNode().equals(other))
194: edges.add(m_in[i]);
195: }
196:
197: return (edges);
198: }
199:
200: /**
201: * @see DirectedNode#getOutEdges(DirectedNode)
202: */
203: public List getOutEdges(DirectedNode other) {
204: ArrayList edges = new ArrayList();
205:
206: for (int i = 0; i < m_out.length; i++) {
207: if (m_out[i].getOutNode().equals(other))
208: edges.add(m_out[i]);
209: }
210:
211: return (edges);
212: }
213:
214: /**
215: * @see Node#getEdges()
216: */
217: public List getEdges() {
218: ArrayList edges = new ArrayList();
219: for (int i = 0; i < m_in.length; i++)
220: edges.add(m_in[i]);
221: for (int i = 0; i < m_out.length; i++)
222: edges.add(m_out[i]);
223:
224: return (edges);
225: }
226:
227: /**
228: * Returns the in adjacency edge array of the node.
229: *
230: * @return An array of in edges for the node.
231: */
232: public DirectedEdge[] getInEdgeArray() {
233: return (m_in);
234: }
235:
236: /**
237: * @see DirectedNode#getInEdges()
238: */
239: public List getInEdges() {
240: ArrayList edges = new ArrayList();
241:
242: for (int i = 0; i < m_in.length; i++) {
243: edges.add(m_in[i]);
244: }
245: return (edges);
246: }
247:
248: /**
249: * Returns the out adjacency edge array of the node.
250: *
251: * @return An array of out edges for the node.
252: */
253: public DirectedEdge[] getOutEdgeArray() {
254: return (m_out);
255: }
256:
257: /**
258: * @see DirectedNode#getOutEdges()
259: */
260: public List getOutEdges() {
261: ArrayList edges = new ArrayList();
262:
263: for (int i = 0; i < m_out.length; i++) {
264: edges.add(m_out[i]);
265: }
266: return (edges);
267: }
268:
269: /**
270: * @see Node#getDegree()
271: */
272: public int getDegree() {
273: return (m_in.length + m_out.length);
274: }
275:
276: /**
277: * Sets the in degree of the node. This method builds the in edge adjacency
278: * list of the node.
279: *
280: * @param indegree The in degree / size of in edge array of the node.
281: */
282: public void setInDegree(int indegree) {
283: m_in = new DirectedEdge[indegree];
284: }
285:
286: /**
287: * @see DirectedNode#getInDegree()
288: */
289: public int getInDegree() {
290: return (m_in.length);
291: }
292:
293: /**
294: * Sets the out degree of the node. This method builds the out edge adjacency
295: * list of the node.
296: *
297: * @param outdegree The out degree / size of out edge array of the node.
298: */
299: public void setOutDegree(int outdegree) {
300: m_out = new DirectedEdge[outdegree];
301: }
302:
303: /**
304: * @see DirectedNode#getOutDegree()
305: */
306: public int getOutDegree() {
307: return (m_out.length);
308: }
309:
310: /**
311: * This iterator iterates over the underlying edge arrays of the node.
312: *
313: * @see org.geotools.graph.structure.Graphable#getRelated()
314: */
315: public Iterator getRelated() {
316: return (new RelatedIterator(RelatedIterator.BOTH));
317: }
318:
319: /**
320: * This iterator iterates over the underlying in edge array of the node.
321: *
322: * @see org.geotools.graph.structure.DirectedGraphable#getInRelated()
323: */
324: public Iterator getInRelated() {
325: return (new RelatedIterator(RelatedIterator.IN));
326: }
327:
328: /**
329: * This iterator iterates over the underlying out edge array of the node.
330: */
331: public Iterator getOutRelated() {
332: return (new RelatedIterator(RelatedIterator.OUT));
333: }
334:
335: /**
336: * Overrides the default deserialization operation. Since edge adjacency
337: * lists of Nodes are not written out upon serialization, they must be
338: * recreated upon deserialization.
339: *
340: * @param in Object input stream containing serialized objects.
341: *
342: * @throws IOException
343: * @throws ClassNotFoundException
344: */
345: private void readObject(ObjectInputStream in) throws IOException,
346: ClassNotFoundException {
347:
348: in.defaultReadObject();
349:
350: //read the degree of the node
351: setInDegree(in.readInt());
352: setOutDegree(in.readInt());
353: }
354:
355: /**
356: * Overrides the default serialization operation. Since edge adjacency
357: * lists of Nodes are not written out upon serialization, all the information
358: * needed to recreate them must be written to the object stream as well. Since
359: * the edge list is not written out, and the node does not store its degree
360: * explicitly, it must be written to the output stream.
361: *
362: * @param in Object output stream containing serialized objects.
363: *
364: * @throws IOException
365: * @throws ClassNotFoundException
366: */
367: private void writeObject(ObjectOutputStream out) throws IOException {
368:
369: out.defaultWriteObject();
370:
371: //write the degree of the node to the output stream
372: out.writeInt(getInDegree());
373: out.writeInt(getOutDegree());
374: }
375:
376: /**
377: * Iterator used to iterate over related nodes.
378: *
379: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
380: *
381: */
382: public class RelatedIterator implements Iterator {
383:
384: /** in iteration mode **/
385: public static final int IN = 0;
386:
387: /** out iteration mode **/
388: public static final int OUT = 1;
389:
390: /** both iteration mode **/
391: public static final int BOTH = 2;
392:
393: /** iteration mode **/
394: private int m_mode;
395:
396: /** iteration index **/
397: private int m_index;
398:
399: /**
400: * Constructs a new iterator.
401: *
402: * @param mode Iteration mode.
403: */
404: public RelatedIterator(int mode) {
405: m_mode = mode;
406: m_index = 0;
407: }
408:
409: /**
410: * Not supported.
411: *
412: * @throws UnsupportedOperationException
413: */
414: public void remove() {
415: throw new UnsupportedOperationException(getClass()
416: .getName()
417: + "#remove()");
418: }
419:
420: /**
421: * Determines if there are any more related nodes to return.
422: *
423: * @see Iterator#hasNext()
424: */
425: public boolean hasNext() {
426: switch (m_mode) {
427: case IN:
428: return (m_index < m_in.length);
429:
430: case OUT:
431: return (m_index < m_out.length);
432:
433: case BOTH:
434: return (m_index < m_in.length + m_out.length);
435: }
436: return (false);
437: }
438:
439: /**
440: * Returns the next related node.
441: *
442: * @see Iterator#next()
443: */
444: public Object next() {
445:
446: switch (m_mode) {
447: case IN:
448: return (m_in[m_index++].getInNode());
449:
450: case OUT:
451: return (m_out[m_index++].getOutNode());
452:
453: case BOTH:
454: return (m_index < m_in.length ? m_in[m_index++]
455: .getInNode() : m_out[m_index++ - m_in.length]
456: .getOutNode());
457: }
458: return (null);
459: }
460: }
461: }
|