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 com.vividsolutions.jts.geom.Envelope;
019:
020: import junit.framework.Test;
021: import junit.framework.TestCase;
022: import junit.framework.TestSuite;
023:
024: import org.geotools.caching.Generator;
025: import org.geotools.caching.spatialindex.spatialindex.IData;
026: import org.geotools.caching.spatialindex.spatialindex.INode;
027: import org.geotools.caching.spatialindex.spatialindex.IVisitor;
028: import org.geotools.caching.spatialindex.spatialindex.Region;
029:
030: import org.geotools.feature.Feature;
031: import org.geotools.feature.FeatureType;
032:
033: import java.io.PrintStream;
034:
035: import java.util.ArrayList;
036: import java.util.HashMap;
037: import java.util.Iterator;
038: import java.util.List;
039: import java.util.Stack;
040: import java.util.logging.Level;
041: import java.util.logging.Logger;
042:
043: public class QuadTreeTest extends TestCase {
044: protected FeatureType type;
045: protected List data;
046: protected QuadTree tree;
047:
048: protected List createDataSet(int numberOfData) {
049: //System.out.println("=== Creating Data Set");
050: Generator gen = new Generator(1000, 1000);
051: type = gen.getFeatureType();
052:
053: List ret = new ArrayList();
054:
055: for (int i = 0; i < numberOfData; i++) {
056: ret.add(gen.createFeature(i));
057: }
058:
059: return ret;
060: }
061:
062: protected void setUp() {
063: data = createDataSet(2000);
064: tree = new QuadTree(new Region(new double[] { 0d, 0d },
065: new double[] { 1000d, 1000d }));
066: }
067:
068: public static Test suite() {
069: return new TestSuite(QuadTreeTest.class);
070: }
071:
072: public void testInsertData() {
073: for (Iterator it = data.iterator(); it.hasNext();) {
074: Feature f = (Feature) it.next();
075: tree.insertData(f.getID().getBytes(), toRegion(f
076: .getBounds()), f.hashCode());
077: }
078: }
079:
080: public void testCountQuery() {
081: testInsertData();
082:
083: CountingVisitor v1 = new CountingVisitor();
084: tree.intersectionQuery(new Region(new double[] { 0d, 0d },
085: new double[] { 1000d, 1000d }), v1);
086: //System.out.println("Nodes = " + v1.nodes + " ; Data = " + v1.data) ;
087: // some data overlap in the tree, so we may count more than actual
088: assertTrue(v1.data >= 2000);
089:
090: CountingVisitor v2 = new CountingVisitor();
091: tree.intersectionQuery(new Region(new double[] { 0d, 0d },
092: new double[] { 1000d, 1000d }), v2);
093: //System.out.println("Nodes = " + v2.nodes + " ; Data = " + v2.data) ;
094: assertEquals(v1.data, v2.data);
095: assertEquals(v2.nodes, v2.nodes);
096: }
097:
098: public void testIntersectionQuery() {
099: testInsertData();
100:
101: YieldingVisitor v = new YieldingVisitor();
102: long start = System.currentTimeMillis();
103: tree.intersectionQuery(new Region(new double[] { 0d, 0d },
104: new double[] { 1000d, 1000d }), v);
105:
106: long q1 = System.currentTimeMillis() - start;
107: assertEquals(2000, v.yields.size());
108: v = new YieldingVisitor();
109: start = System.currentTimeMillis();
110: tree.intersectionQuery(new Region(new double[] { 250d, 250d },
111: new double[] { 500d, 500d }), v);
112:
113: long q2 = System.currentTimeMillis() - start;
114: assertTrue(v.yields.size() < 2000);
115:
116: /* Runtime context may cause this to fail ...
117: but this is what we expect of an index */
118:
119: // assertTrue(q2 < q1) ;
120: if (q2 >= q1) {
121: org.geotools.util.logging.Logging.getLogger(
122: "org.geotools.caching.quadtree").log(Level.SEVERE,
123: "Index not fast as expected.");
124: }
125: }
126:
127: public void testContainementQuery() {
128: Region r = new Region(new double[] { 10, 15 }, new double[] {
129: 15, 20 });
130: tree.insertData(null, r, 0);
131:
132: NodeEnvelopeVisitor v = new NodeEnvelopeVisitor();
133: tree.containmentQuery(r, v);
134: assertTrue(v.lastNode.getShape().contains(r));
135: }
136:
137: public void testMaximumDepth() {
138: Region r = new Region(new double[] { 0d, 0d }, new double[] {
139: 1000d, 1000d });
140: int height = 5;
141: tree = new QuadTree(r, height);
142: testInsertData();
143:
144: LevelCountVisitor v = new LevelCountVisitor();
145: tree.intersectionQuery(r, v);
146: assertTrue((height + 1) >= v.getNumLevels());
147: assertEquals(height, v.getMaxLevel());
148: assertTrue(0 <= v.getMinLevel());
149:
150: //printTree(tree, System.out) ;
151: }
152:
153: public void testRootExpansion() {
154: // expanding in all possible directions
155: expandTree(410d, 510d);
156: expandTree(250d, 300d);
157: expandTree(410d, 300d);
158: expandTree(250d, 510d);
159: }
160:
161: protected void expandTree(double x, double y) {
162: assertTrue((x >= 0) && (x <= 1000));
163: assertTrue((y >= 0) && (y <= 1000));
164:
165: double xmin = 300d;
166: double ymin = 400d;
167: double xmax = 350d;
168: double ymax = 450d;
169: Region r = new Region(new double[] { xmin, ymin },
170: new double[] { xmax, ymax });
171: tree = new QuadTree(r);
172:
173: double nxmin = (x < xmin) ? x : xmin;
174: double nxmax = (x > xmax) ? x : xmax;
175: double nymin = (y < ymin) ? y : ymin;
176: double nymax = (y > ymax) ? y : ymax;
177: tree.insertData(null, new Region(new double[] { xmin, ymin },
178: new double[] { xmax, ymax }), 1);
179: tree.insertData(null, new Region(new double[] { nxmin, nymin },
180: new double[] { nxmax, nymax }), 2);
181:
182: CountingVisitor v = new CountingVisitor();
183: tree.intersectionQuery(new Region(new double[] { 0d, 0d },
184: new double[] { 1000d, 1000d }), v);
185: //printTree(tree, System.out) ;
186: assertEquals(2, v.data);
187: }
188:
189: // Test Utilities
190:
191: /** Transform a JTS Envelope to a Region
192: *
193: * @param e JTS Envelope
194: * @return
195: */
196: protected static Region toRegion(final Envelope e) {
197: Region r = new Region(
198: new double[] { e.getMinX(), e.getMinY() },
199: new double[] { e.getMaxX(), e.getMaxY() });
200:
201: return r;
202: }
203:
204: protected void printTree(final QuadTree t, final PrintStream out) {
205: t.queryStrategy(new QueryStrategy() {
206: Stack nodes = new Stack();
207:
208: public Node getNextNode(Node current, boolean[] hasNext) {
209: out.println("@level " + current.getLevel() + " : "
210: + current);
211:
212: for (int i = 0; i < current.getChildrenCount(); i++) {
213: nodes.add(0, current.getSubNode(i));
214: }
215:
216: if (!nodes.isEmpty()) {
217: hasNext[0] = true;
218:
219: return (Node) nodes.pop();
220: } else {
221: hasNext[0] = false;
222:
223: return null;
224: }
225: }
226: });
227: }
228:
229: class CountingVisitor implements IVisitor {
230: int data = 0;
231: int nodes = 0;
232:
233: public void visitData(IData d) {
234: data++;
235:
236: //System.out.println(new String(d.getData())) ;
237: }
238:
239: public void visitNode(INode n) {
240: nodes++;
241: }
242: }
243:
244: class YieldingVisitor implements IVisitor {
245: HashMap yields = new HashMap();
246:
247: public void visitData(IData d) {
248: yields.put(new String(d.getData()), null);
249: }
250:
251: public void visitNode(INode n) {
252: // do nothing
253: }
254: }
255:
256: class NodeEnvelopeVisitor implements IVisitor {
257: INode lastNode = null;
258:
259: public void visitData(IData d) {
260: // TODO Auto-generated method stub
261: }
262:
263: public void visitNode(INode n) {
264: lastNode = n;
265: }
266: }
267:
268: class LevelCountVisitor implements IVisitor {
269: int minLevel = -1;
270: int maxLevel = -1;
271:
272: public void visitData(IData d) {
273: // TODO Auto-generated method stub
274: }
275:
276: public void visitNode(INode n) {
277: if (maxLevel == -1) {
278: minLevel = n.getLevel();
279: maxLevel = minLevel;
280: } else if (minLevel > n.getLevel()) {
281: minLevel = n.getLevel();
282: }
283: }
284:
285: public int getNumLevels() {
286: return maxLevel - minLevel + 1;
287: }
288:
289: public int getMaxLevel() {
290: return maxLevel;
291: }
292:
293: public int getMinLevel() {
294: return minLevel;
295: }
296: }
297: }
|