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.Edge;
027: import org.geotools.graph.structure.Node;
028:
029: /**
030: * Optimized implementation of Node. The following optimizations reduce space
031: * and improve performance.<BR>
032: * <UL>
033: * <LI>Edge adjacency list stored as array of predetermined size.</LI>
034: * <LI>Removing support for removing edges from the nodes ajdacency list.</LI>
035: * <LI>The related component iterator iterates over the underlying edge
036: * array of the node instread of a newly created collection.
037: * </UL>
038: * Using an optimized node requires that the degree of the node be known before
039: * the node is built.
040: *
041: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
042: * @see Node
043: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/extension/graph/src/main/java/org/geotools/graph/structure/opt/OptNode.java $
044: */
045: public class OptNode extends OptGraphable implements Node {
046:
047: /** edge adjacency list **/
048: private Edge[] m_edges;
049:
050: /**
051: * Constructs a new OptimizedNode. This constructor does not build the
052: * adjacency array for the node.
053: */
054: public OptNode() {
055: this (0);
056: }
057:
058: /**
059: * Constructs a new Optimized Node with a known degree.
060: *
061: * @param degree The degree of the node.
062: */
063: public OptNode(int degree) {
064: super ();
065: m_edges = new Edge[degree];
066: }
067:
068: /**
069: * @see Node#add(Edge)
070: */
071: public void add(Edge e) {
072: for (int i = 0; i < m_edges.length; i++) {
073: if (m_edges[i] == null) {
074: m_edges[i] = e;
075: return;
076: }
077: }
078: }
079:
080: /**
081: * Not supported.
082: *
083: * @throws UnsupportedOperationException
084: *
085: * @see Node#remove(Edge)
086: */
087: public void remove(Edge e) {
088: throw new UnsupportedOperationException(getClass().getName()
089: + "#remove(Edge)");
090: }
091:
092: /**
093: * @see Node#getEdge(Node)
094: */
095: public Edge getEdge(Node other) {
096: for (int i = 0; i < m_edges.length; i++) {
097: if (m_edges[i].getNodeA().equals(this )
098: && m_edges[i].getNodeB().equals(other)
099: || m_edges[i].getNodeB().equals(this )
100: && m_edges[i].getNodeA().equals(other))
101: return (m_edges[i]);
102: }
103: return (null);
104: }
105:
106: /**
107: * @see Node#getEdges(Node)
108: */
109: public List getEdges(Node other) {
110: ArrayList edges = new ArrayList();
111: for (int i = 0; i < m_edges.length; i++) {
112: if (m_edges[i].getNodeA().equals(this )
113: && m_edges[i].getNodeB().equals(other)
114: || m_edges[i].getNodeB().equals(this )
115: && m_edges[i].getNodeA().equals(other))
116: edges.add(m_edges[i]);
117: }
118: return (edges);
119: }
120:
121: /**
122: * Returns the edge adjacency list of the node as an array.
123: *
124: * @return An array containing edges adjacent to the node.
125: */
126: public Edge[] getEdgeArray() {
127: return (m_edges);
128: }
129:
130: /**
131: * @see Node#getEdges()
132: */
133: public List getEdges() {
134: ArrayList edges = new ArrayList();
135:
136: for (int i = 0; i < m_edges.length; i++) {
137: edges.add(m_edges[i]);
138: }
139:
140: return (edges);
141: }
142:
143: /**
144: * Sets the degree of the node. This method build the edge adjacency array
145: * for the node.
146: *
147: * @param degree The degree of the node / size of edge adjacency array.
148: */
149: public void setDegree(int degree) {
150: m_edges = new Edge[degree];
151: }
152:
153: /**
154: * @see Node#getDegree()
155: */
156: public int getDegree() {
157: return (m_edges.length);
158: }
159:
160: /**
161: * This iterator iterates over the underlying edge array of the node.
162: *
163: * @see org.geotools.graph.structure.Graphable#getRelated()
164: */
165: public Iterator getRelated() {
166: return (new RelatedIterator(this ));
167: }
168:
169: /**
170: * Overrides the default deserialization operation. Since edge adjacency
171: * lists of Nodes are not written out upon serialization, they must be
172: * recreated upon deserialization.
173: *
174: * @param in Object input stream containing serialized objects.
175: *
176: * @throws IOException
177: * @throws ClassNotFoundException
178: */
179: private void readObject(ObjectInputStream in) throws IOException,
180: ClassNotFoundException {
181:
182: in.defaultReadObject();
183:
184: //read degree from object stream and recreate edge list
185: setDegree(in.readInt());
186: }
187:
188: /**
189: * Overrides the default serialization operation. Since edge adjacency
190: * lists of Nodes are not written out upon serialization, all the information
191: * needed to recreate them must be written to the object stream as well. Since
192: * the edge list is not written out, and the node does not store its degree
193: * explicitly, it must be written to the output stream.
194: *
195: * @param in Object output stream containing serialized objects.
196: *
197: * @throws IOException
198: * @throws ClassNotFoundException
199: */
200: private void writeObject(ObjectOutputStream out) throws IOException {
201:
202: out.defaultWriteObject();
203:
204: //store degree in object stream
205: out.writeInt(getDegree());
206: }
207:
208: /**
209: * An iterator used to iterate over related nodes.
210: *
211: * @author Justin Deoliveira, Refractions Research Inc, jdeolive@refractions.net
212: *
213: */
214: public class RelatedIterator implements Iterator {
215:
216: /** index of iterator **/
217: private byte m_index = 0;
218: private OptNode m_node;
219:
220: public RelatedIterator(OptNode node) {
221: m_node = node;
222: }
223:
224: /**
225: * Not supported.
226: *
227: * @throws UnsupportedOperationException
228: */
229: public void remove() {
230: throw new UnsupportedOperationException(getClass()
231: .getName()
232: + "#remove()");
233: }
234:
235: /**
236: * Determines if there are any more related nodes to return.
237: *
238: * @see Iterator#hasNext()
239: */
240: public boolean hasNext() {
241: return (m_index < m_edges.length);
242: }
243:
244: /**
245: * Returns the next related node.
246: *
247: * @see Iterator#next()
248: */
249: public Object next() {
250: Edge e = m_edges[m_index++];
251: return (e.getNodeA().equals(m_node) ? e.getNodeB() : e
252: .getNodeA());
253: }
254: }
255: }
|