001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2002-2006, GeoTools Project Managment Committee (PMC)
005: *
006: * This library is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU Lesser General Public
008: * License as published by the Free Software Foundation;
009: * version 2.1 of the License.
010: *
011: * This library is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * Lesser General Public License for more details.
015: */
016: package org.geotools.caching.quatree;
017:
018: import org.geotools.caching.spatialindex.spatialindex.INode;
019: import org.geotools.caching.spatialindex.spatialindex.IShape;
020: import org.geotools.caching.spatialindex.spatialindex.Region;
021:
022: import org.geotools.feature.Feature;
023: import org.geotools.feature.FeatureCollection;
024: import org.geotools.feature.FeatureIterator;
025:
026: import java.util.ArrayList;
027: import java.util.Arrays;
028: import java.util.List;
029:
030: public class Node implements INode {
031: private Region bounds;
032: protected NodeCacheEntry entry;
033: protected int numShapes;
034: protected int[] shapesId;
035: protected byte[][] shapesData;
036: protected List subNodes;
037: protected Node parent;
038: protected boolean visited = false;
039: protected boolean childrenVisited = false;
040: protected int id;
041: protected int level;
042:
043: // Constructors
044:
045: /** Constructor : creates a new node descending from another node.
046: *
047: * @param s envelope of new node
048: * @param id of new node
049: * @param parent node
050: */
051: protected Node(Region s, int id, Node parent) {
052: this .bounds = s;
053: this .id = id;
054: this .parent = parent;
055: this .subNodes = new ArrayList();
056: this .numShapes = 0;
057: this .shapesId = new int[4];
058: Arrays.fill(shapesId, -1);
059: this .shapesData = new byte[4][];
060: this .entry = new NodeCacheEntry(this );
061:
062: if (parent == null) {
063: this .level = 0;
064: } else {
065: this .level = parent.level - 1;
066: }
067: }
068:
069: /** Constructor : creates a root node.
070: * Supplied level parameter indicates the maximum height of the tree.
071: *
072: * @param s envelope of new node
073: * @param id of new node
074: * @param maxDepth is the maximum height of the tree. Must be > 0.
075: */
076: protected Node(Region s, int id, int maxDepth) {
077: this (s, id, null);
078: this .level = maxDepth;
079: }
080:
081: // Interface
082: public int getChildIdentifier(int index)
083: throws IndexOutOfBoundsException {
084: return ((Node) subNodes.get(index)).getIdentifier();
085: }
086:
087: public IShape getChildShape(int index)
088: throws IndexOutOfBoundsException {
089: return ((Node) subNodes.get(index)).getShape();
090: }
091:
092: public int getChildrenCount() {
093: return subNodes.size();
094: }
095:
096: public int getLevel() {
097: return level;
098: }
099:
100: public boolean isIndex() {
101: return !isLeaf();
102: }
103:
104: public boolean isLeaf() {
105: return subNodes.isEmpty();
106: }
107:
108: public int getIdentifier() {
109: return id;
110: }
111:
112: public IShape getShape() {
113: return bounds;
114: }
115:
116: // Additional public methods, for our caching purpose
117:
118: /** Attach features to this node
119: *
120: * @param feature to attach to this node
121: */
122: public void attach(Feature f) {
123: this .entry.linkedFeatures.add(f);
124: }
125:
126: /** Attach a list of features to this node
127: *
128: * @param list of features
129: */
130: public void attach(FeatureCollection features) {
131: FeatureIterator it = features.features();
132:
133: try {
134: while (it.hasNext()) {
135: attach((Feature) it.next());
136: }
137: } finally {
138: features.close(it);
139: }
140: }
141:
142: /** Hit node, cause access statistics to be updated.
143: * Actually, hit associated NodeCacheEntry
144: */
145: public void hit() {
146: this .entry.hit();
147: }
148:
149: public boolean isValid() {
150: return this .entry.isValid();
151: }
152:
153: // Internal
154: protected Node getSubNode(int index) {
155: return (Node) subNodes.get(index);
156: }
157:
158: protected void addSubNode(Node n) {
159: subNodes.add(n);
160: }
161:
162: protected void split(double SPLITRATIO) {
163: assert (isLeaf());
164:
165: Region half1;
166: Region half2;
167: Region[] quads = new Region[4];
168: Region[] tmp = splitBounds(bounds, SPLITRATIO);
169: half1 = tmp[0];
170: half2 = tmp[1];
171: tmp = splitBounds(half1, SPLITRATIO);
172: quads[0] = tmp[0];
173: quads[1] = tmp[1];
174: tmp = splitBounds(half2, SPLITRATIO);
175: quads[2] = tmp[0];
176: quads[3] = tmp[1];
177:
178: for (int i = 0; i < 4; i++) {
179: addSubNode(new Node(quads[i], i, this ));
180: }
181: }
182:
183: /**
184: * Splits the specified Envelope
185: * @param in an Envelope to split
186: * @return an array of 2 Envelopes
187: */
188: public static Region[] splitBounds(Region in, double SPLITRATIO) {
189: Region[] ret = new Region[2];
190: double range;
191: double calc;
192:
193: if ((in.m_pHigh[0] - in.m_pLow[0]) > (in.m_pHigh[1] - in.m_pLow[1])) {
194: // Split in X direction
195: range = in.m_pHigh[0] - in.m_pLow[0];
196:
197: calc = in.m_pLow[0] + (range * SPLITRATIO);
198: ret[0] = new Region(in);
199: ret[0].m_pHigh[0] = calc;
200:
201: calc = in.m_pHigh[0] - (range * SPLITRATIO);
202: ret[1] = new Region(in);
203: ret[1].m_pLow[0] = calc;
204: } else {
205: // Split in Y direction
206: range = in.m_pHigh[1] - in.m_pLow[1];
207:
208: calc = in.m_pLow[1] + (range * SPLITRATIO);
209: ret[0] = new Region(in);
210: ret[0].m_pHigh[1] = calc;
211:
212: calc = in.m_pHigh[1] - (range * SPLITRATIO);
213: ret[1] = new Region(in);
214: ret[1].m_pLow[1] = calc;
215: }
216:
217: return ret;
218: }
219:
220: protected void insertData(byte[] data, int id) {
221: if (shapesId.length == numShapes) {
222: // increases storage size
223: int[] newIds = new int[shapesId.length * 2];
224: byte[][] newData = new byte[shapesData.length * 2][];
225: System.arraycopy(this .shapesId, 0, newIds, 0,
226: this .numShapes);
227: System.arraycopy(shapesData, 0, newData, 0, this .numShapes);
228: this .shapesId = newIds;
229: this .shapesData = newData;
230: }
231:
232: this .shapesId[numShapes] = id;
233: this .shapesData[numShapes] = data;
234: numShapes++;
235: }
236:
237: protected void deleteData(int index)
238: throws IndexOutOfBoundsException {
239: if ((index < 0) || (index > (numShapes - 1))) {
240: throw new IndexOutOfBoundsException("" + index);
241: }
242:
243: if (index < (numShapes - 1)) {
244: this .shapesId[index] = this .shapesId[numShapes - 1];
245: this .shapesData[index] = this .shapesData[numShapes - 1];
246: }
247:
248: this .shapesData[numShapes - 1] = null;
249: numShapes--;
250:
251: //if (numShapes == 0) {
252: // do we have to do something ?
253: //}
254: }
255:
256: public String toString() {
257: StringBuffer r = new StringBuffer();
258: r.append("Node ID=" + this .id + " ");
259: r.append("# of data=" + this .numShapes + " ");
260: r.append("MBR=" + this.bounds);
261:
262: return r.toString();
263: }
264: }
|