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.impl;
017:
018: import com.vividsolutions.jts.geom.Coordinate;
019: import com.vividsolutions.jts.geom.Envelope;
020: import com.vividsolutions.jts.geom.Geometry;
021: import com.vividsolutions.jts.geom.GeometryFactory;
022: import com.vividsolutions.jts.geom.LinearRing;
023: import com.vividsolutions.jts.geom.Polygon;
024: import com.vividsolutions.jts.geom.impl.CoordinateArraySequence;
025:
026: import org.geotools.caching.QueryTracker;
027:
028: import org.geotools.data.DefaultQuery;
029: import org.geotools.data.Query;
030:
031: import org.geotools.filter.FilterFactoryImpl;
032: import org.geotools.filter.spatial.BBOXImpl;
033:
034: import org.geotools.index.Data;
035: import org.geotools.index.DataDefinition;
036: import org.geotools.index.LockTimeoutException;
037: import org.geotools.index.TreeException;
038: import org.geotools.index.rtree.*;
039: import org.geotools.index.rtree.memory.MemoryPageStore;
040:
041: import org.opengis.filter.Filter;
042: import org.opengis.filter.FilterFactory;
043:
044: import java.util.HashMap;
045: import java.util.Iterator;
046: import java.util.List;
047:
048: /** First implementation of QueryTracker to handle BBox queries.
049: * Stores the extent of queries in a R-tree,
050: * so this tracker can tell what areas are already covered by previous queries.
051: * Can compute a rough approximation of the complementary area needed to cover a new query.
052: * Uses spatial index from org.geotools.index.rtree, and keeps tree in memory.
053: *
054: * Currently, does handle only queries made of a BBoxFilter.
055: *
056: * @task handle queries made a up of a _spatial filter_ and an _attribute filter_
057: * Use FilterVisitor ?
058: * @task should tree have a size limit ? for the time being, we rely a the cache eviction strategy,
059: * and hope for the best. We should easily be able to store thousands query envelopes.
060: *
061: * @author Christophe Rousson, SoC 2007, CRG-ULAVAL
062: *
063: */
064: public class SpatialQueryTracker implements QueryTracker {
065: /**
066: * We need to feed the tree with some data.
067: * What we store is the hashCode of the envelope of queries.
068: */
069: private static DataDefinition df = createDataDefinition();
070:
071: /**
072: * The R-tree to keep track of queries bounds.
073: */
074: private RTree tree = createTree();
075:
076: /**
077: * A map to store queries bounds.
078: * As these are stored in the R-tree, why do we have to store these in another place ?
079: * Well, when we search the tree, we get data, not the envelope of data.
080: * Other R-tree implementation might do a better job.
081: *
082: */
083: private final HashMap map = new HashMap();
084:
085: /**
086: * We will use this instance of FilterFactory to build new queries.
087: */
088: private final FilterFactory filterFactory = new FilterFactoryImpl();
089:
090: /* (non-Javadoc)
091: * @see org.geotools.caching.QueryTracker#clear()
092: */
093: public void clear() {
094: try {
095: map.clear();
096: tree.close();
097: tree = createTree();
098: } catch (TreeException e) {
099: // TODO Auto-generated catch block
100: e.printStackTrace();
101: }
102: }
103:
104: public Query match(Query q) {
105: return new DefaultQuery(q.getTypeName(), match(q.getFilter()));
106: }
107:
108: /* (non-Javadoc)
109: * @see org.geotools.caching.QueryTracker#match(org.geotools.data.Query)
110: */
111: public Filter match(Filter f) {
112: if (!accepts(f)) {
113: return f;
114: }
115:
116: BBOXImpl bb = (BBOXImpl) f;
117:
118: try {
119: Envelope env = new Envelope(bb.getMinX(), bb.getMaxX(), bb
120: .getMinY(), bb.getMaxY());
121: Geometry searchArea = getRectangle(env);
122:
123: // find matches in R-tree
124: List results = tree.search(env);
125:
126: // seems we know nothing about the requested area ... we have to process the whole query.
127: if (results.size() == 0) {
128: return f;
129: }
130:
131: // at least part of the requeted area falls within the "known world"
132: for (Iterator i = results.iterator(); i.hasNext();) {
133: Data d = (Data) i.next();
134: Envelope e = (Envelope) map.get(d.getValue(0));
135: Polygon rect = getRectangle(e);
136:
137: // searchArea within the "known world".
138: // We actually don't need any other data.
139: if (rect.contains(searchArea)) {
140: return Filter.EXCLUDE;
141: }
142:
143: // remove known area from search area ...
144: searchArea = searchArea.difference(rect);
145: }
146:
147: // searchArea may be some really complex geometry, with holes and patches.
148: // get back to the envelope, to build a new query.
149: Envelope se = searchArea.getEnvelopeInternal();
150: Filter newbb = filterFactory.bbox(bb.getPropertyName(), se
151: .getMinX(), se.getMinY(), se.getMaxX(), se
152: .getMaxY(), bb.getSRS());
153:
154: return newbb;
155: } catch (TreeException e) {
156: // TODO Auto-generated catch block
157: e.printStackTrace();
158: } catch (LockTimeoutException e) {
159: // TODO Auto-generated catch block
160: e.printStackTrace();
161: }
162:
163: return f;
164: }
165:
166: public void register(Query q) {
167: register(q.getFilter());
168: }
169:
170: /* (non-Javadoc)
171: * @see org.geotools.caching.QueryTracker#register(org.geotools.data.Query)
172: */
173: public void register(Filter f) {
174: if (accepts(f)) {
175: BBOXImpl bb = (BBOXImpl) f;
176:
177: try {
178: Envelope env = new Envelope(bb.getMinX(), bb.getMaxX(),
179: bb.getMinY(), bb.getMaxY());
180: Data d = new Data(df);
181: Integer key = new Integer(env.hashCode());
182: d.addValue(key);
183: map.put(key, env);
184: tree.insert(env, d);
185: } catch (TreeException e) {
186: // TODO Auto-generated catch block
187: e.printStackTrace();
188: } catch (LockTimeoutException e) {
189: // TODO Auto-generated catch block
190: e.printStackTrace();
191: }
192: }
193: }
194:
195: public void unregister(Query q) {
196: unregister(q.getFilter());
197: }
198:
199: /* (non-Javadoc)
200: * @see org.geotools.caching.QueryTracker#unregister(org.geotools.data.Query)
201: */
202: public void unregister(Filter f) {
203: if (accepts(f)) {
204: BBOXImpl bb = (BBOXImpl) f;
205: Envelope env = new Envelope(bb.getMinX(), bb.getMaxX(), bb
206: .getMinY(), bb.getMaxY());
207: unregister(env);
208: }
209: }
210:
211: public void unregister(Envelope env) {
212: try {
213: List results = tree.search(env);
214:
215: for (Iterator i = results.iterator(); i.hasNext();) {
216: Data d = (Data) i.next();
217: Envelope e = (Envelope) map.get(d.getValue(0));
218: tree.delete(e);
219: map.remove(d.getValue(0));
220: }
221: } catch (TreeException e) {
222: // TODO Auto-generated catch block
223: e.printStackTrace();
224: } catch (LockTimeoutException e) {
225: // TODO Auto-generated catch block
226: e.printStackTrace();
227: }
228: }
229:
230: /**
231: * @param q
232: * @return
233: */
234: private boolean accepts(Filter f) {
235: if (f instanceof BBOXImpl) {
236: return true;
237: } else {
238: return false;
239: }
240: }
241:
242: /** R-tree used to track queries.
243: * R-tree is mapped in memory.
244: *
245: * @return
246: */
247: private static RTree createTree() {
248: try {
249: PageStore ps = new MemoryPageStore(df, 8, 4,
250: PageStore.SPLIT_QUADRATIC);
251: RTree tree = new RTree(ps);
252:
253: return tree;
254: } catch (TreeException e) {
255: throw (RuntimeException) new RuntimeException()
256: .initCause(e);
257: }
258: }
259:
260: /** Type of data to feed in the tree.
261: * Holds one interger, which represents the hashCode of the envelope stored in the tree.
262: *
263: * @return
264: */
265: private static DataDefinition createDataDefinition() {
266: DataDefinition df = new DataDefinition("US-ASCII");
267: df.addField(Integer.class);
268:
269: return df;
270: }
271:
272: /** Envelope -> Polygon convenience function.
273: *
274: * @param e an envelope
275: * @return a Rectangle that has the same shape as e
276: */
277: private static Polygon getRectangle(Envelope e) {
278: Coordinate[] coords = new Coordinate[] {
279: new Coordinate(e.getMinX(), e.getMinY()),
280: new Coordinate(e.getMaxX(), e.getMinY()),
281: new Coordinate(e.getMaxX(), e.getMaxY()),
282: new Coordinate(e.getMinX(), e.getMaxY()),
283: new Coordinate(e.getMinX(), e.getMinY()) };
284: CoordinateArraySequence seq = new CoordinateArraySequence(
285: coords);
286: LinearRing ls = new LinearRing(seq, new GeometryFactory());
287: Polygon ret = new Polygon(ls, null, new GeometryFactory());
288:
289: return ret;
290: }
291: }
|