001: package org.geotools.caching.quatree;
002:
003: import com.vividsolutions.jts.geom.Envelope;
004:
005: import org.geotools.caching.FeatureCache;
006: import org.geotools.caching.FeatureCacheException;
007: import org.geotools.caching.QueryTracker;
008: import org.geotools.caching.spatialindex.spatialindex.Region;
009: import org.geotools.caching.util.FilterSplitter;
010: import org.geotools.caching.util.IndexUtilities;
011:
012: import org.geotools.data.DataStore;
013: import org.geotools.data.FeatureListener;
014: import org.geotools.data.FeatureReader;
015: import org.geotools.data.Query;
016: import org.geotools.data.Transaction;
017: import org.geotools.data.store.EmptyFeatureCollection;
018:
019: import org.geotools.feature.AttributeType;
020: import org.geotools.feature.Feature;
021: import org.geotools.feature.FeatureCollection;
022: import org.geotools.feature.FeatureType;
023:
024: import org.geotools.filter.spatial.BBOXImpl;
025:
026: import org.opengis.filter.Filter;
027:
028: import java.io.IOException;
029:
030: import java.util.ArrayList;
031: import java.util.Iterator;
032: import java.util.Set;
033: import java.util.Stack;
034:
035: public class QuadTreeFeatureCache implements FeatureCache, QueryTracker {
036: private final DataStore ds;
037: private final FeatureType type;
038: protected QuadTree tree;
039: protected int capacity;
040:
041: // == Contructors ===================
042: public QuadTreeFeatureCache(DataStore ds, FeatureType type,
043: int capacity) throws FeatureCacheException {
044: this .ds = ds;
045: this .type = type;
046: this .capacity = capacity;
047:
048: try {
049: this .tree = new QuadTree(IndexUtilities.toRegion(ds
050: .getFeatureSource(type.getTypeName()).getBounds()));
051: } catch (IOException e) {
052: throw new FeatureCacheException(e);
053: }
054: }
055:
056: // == FeatureCache interface ===================
057: public void clear() {
058: // TODO Auto-generated method stub
059: }
060:
061: public void evict() {
062: // TODO Auto-generated method stub
063: }
064:
065: public Feature get(String id) throws FeatureCacheException {
066: // TODO Auto-generated method stub
067: return null;
068: }
069:
070: public void put(Feature f) {
071: // TODO Auto-generated method stub
072: }
073:
074: public void putAll(FeatureCollection fc, Filter f) {
075: // TODO Auto-generated method stub
076: }
077:
078: public Feature remove(String id) {
079: // TODO Auto-generated method stub
080: return null;
081: }
082:
083: public int size() {
084: // TODO Auto-generated method stub
085: return 0;
086: }
087:
088: public Filter[] splitFilter(Filter f) {
089: //TODO: move to AbstractFeatureCache
090: //TODO: remove from interface ; this shoud not be public
091: Filter[] filters = new Filter[3];
092: FilterSplitter splitter = new FilterSplitter();
093: f.accept(splitter, null);
094:
095: Filter sr = splitter.getSpatialRestriction();
096: assert ((sr == Filter.INCLUDE) || sr instanceof BBOXImpl);
097:
098: Filter missing = match(sr);
099: Filter cached;
100:
101: if (missing == sr) {
102: cached = Filter.EXCLUDE;
103: } else {
104: cached = sr;
105: }
106:
107: filters[SPATIAL_RESTRICTION_CACHED] = cached;
108: filters[SPATIAL_RESTRICTION_MISSING] = missing;
109: filters[OTHER_RESTRICTIONS] = splitter.getOtherRestriction();
110:
111: return filters;
112: }
113:
114: // == FeatureStore interface =================
115: public Set addFeatures(FeatureCollection collection)
116: throws IOException {
117: // TODO Auto-generated method stub
118: return null;
119: }
120:
121: public Transaction getTransaction() {
122: // TODO Auto-generated method stub
123: return null;
124: }
125:
126: public void modifyFeatures(AttributeType[] type, Object[] value,
127: Filter filter) throws IOException {
128: // TODO Auto-generated method stub
129: }
130:
131: public void modifyFeatures(AttributeType type, Object value,
132: Filter filter) throws IOException {
133: // TODO Auto-generated method stub
134: }
135:
136: public void removeFeatures(Filter filter) throws IOException {
137: // TODO Auto-generated method stub
138: }
139:
140: public void setFeatures(FeatureReader reader) throws IOException {
141: // TODO Auto-generated method stub
142: }
143:
144: public void setTransaction(Transaction transaction) {
145: // TODO Auto-generated method stub
146: }
147:
148: public void addFeatureListener(FeatureListener listener) {
149: // TODO Auto-generated method stub
150: }
151:
152: public Envelope getBounds() throws IOException {
153: // TODO Auto-generated method stub
154: return null;
155: }
156:
157: public Envelope getBounds(Query query) throws IOException {
158: // TODO Auto-generated method stub
159: return null;
160: }
161:
162: public int getCount(Query query) throws IOException {
163: // TODO Auto-generated method stub
164: return 0;
165: }
166:
167: public DataStore getDataStore() {
168: return ds;
169: }
170:
171: public FeatureCollection getFeatures() throws IOException {
172: // TODO Auto-generated method stub
173: return null;
174: }
175:
176: /* (non-Javadoc)
177: * @see org.geotools.data.FeatureSource#getFeatures(org.geotools.data.Query)
178: * TODO: move to AbstractFeatureCache
179: */
180: public FeatureCollection getFeatures(Query query)
181: throws IOException {
182: if ((query.getTypeName() != null)
183: && (query.getTypeName() != type.getTypeName())) {
184: return new EmptyFeatureCollection(getSchema());
185: }
186:
187: return getFeatures(query.getFilter());
188: }
189:
190: public FeatureCollection getFeatures(Filter filter)
191: throws IOException {
192: // TODO Auto-generated method stub
193: return null;
194: }
195:
196: public FeatureType getSchema() {
197: return type;
198: }
199:
200: public void removeFeatureListener(FeatureListener listener) {
201: // TODO Auto-generated method stub
202: }
203:
204: // == QueryTracker interface ==============
205: public Filter match(Filter f) {
206: if (!(f instanceof BBOXImpl)) {
207: return f;
208: }
209:
210: BBOXImpl bbox = (BBOXImpl) f;
211: Region r = new Region(new double[] { bbox.getMinX(),
212: bbox.getMinY() }, new double[] { bbox.getMaxX(),
213: bbox.getMaxY() });
214: ValidTileVisitor v = new ValidTileVisitor();
215: tree.containmentQuery(r, v);
216:
217: if (v.isCovered) {
218: // we do not need extra data
219: return Filter.EXCLUDE;
220: } else {
221: // find missing tiles
222:
223: /* v2 */
224: register(f);
225: v = new ValidTileVisitor();
226: tree.containmentQuery(r, v);
227:
228: Stack regions = new Stack();
229: match(r, v.lastNode, regions);
230:
231: /* v1
232: Stack regions = new Stack() ;
233: if (v.lastNode == null) {
234: // Query is bigger than the known part of the universe
235: Region unknown = intersection(r, (Region) tree.root.getShape()) ;
236: regions.push(unknown) ;
237: match(r, tree.root, regions) ;
238: } else {
239: match(r, v.lastNode, regions) ;
240: }*/
241: }
242:
243: return null;
244: }
245:
246: protected void match(final Region r, Node current, Stack s) {
247: if (current.isLeaf()) {
248: // we have no data
249: // we must get corresponding normalized region from DataStore
250: Region normalized = normalize(r, current);
251: // add region to stack of regions to retrieve
252: s.push(normalized);
253: } else {
254: for (int i = 0; i < current.getChildrenCount(); i++) {
255: Node child = current.getSubNode(i);
256:
257: if (child.getShape().intersects(r)) {
258: if (!child.isValid()) {
259: match(r, child, s);
260: }
261: }
262: }
263:
264: // is that the right place to do that ?
265: // s = groupRegions(s) ;
266: }
267: }
268:
269: protected Stack groupRegions(Stack s) {
270: Stack r = new Stack();
271:
272: while (!s.isEmpty()) {
273: Region r1 = (Region) s.pop();
274:
275: for (Iterator it = s.iterator(); it.hasNext();) {
276: Region r2 = (Region) it.next();
277:
278: if (r1.intersects(r2)) {
279: it.remove();
280: r1 = r1.combinedRegion(r2);
281: }
282: }
283:
284: r.push(r1);
285: }
286:
287: return r;
288: }
289:
290: protected static Region normalize(final Region r, final Node node) {
291: Region noderegion = (Region) node.getShape();
292: Region inter = intersection(r, noderegion);
293: int level = node.getLevel();
294:
295: while (level > 0) {
296: Region[] splits = Node.splitBounds(noderegion,
297: QuadTree.SPLITRATIO);
298:
299: //Region[] splits1 = Node.splitBounds(splits[0], QuadTree.SPLITRATIO) ;
300: //Region[] splits2 = Node.splitBounds(splits[1], QuadTree.SPLITRATIO) ;
301: if (splits[0].contains(inter)) {
302: splits = Node.splitBounds(splits[0],
303: QuadTree.SPLITRATIO);
304:
305: if (splits[0].contains(inter)) {
306: noderegion = splits[0];
307: level--;
308: } else if (splits[1].contains(inter)) {
309: noderegion = splits[1];
310: level--;
311: } else {
312: break;
313: }
314: } else if (splits[1].contains(inter)) {
315: splits = Node.splitBounds(splits[1],
316: QuadTree.SPLITRATIO);
317:
318: if (splits[0].contains(inter)) {
319: noderegion = splits[0];
320: level--;
321: } else if (splits[1].contains(inter)) {
322: noderegion = splits[1];
323: level--;
324: } else {
325: break;
326: }
327: } else {
328: break;
329: }
330: }
331:
332: return noderegion;
333: }
334:
335: protected static Region intersection(final Region r1,
336: final Region r2) {
337: double xmin = (r1.getLow(0) > r2.getLow(0)) ? r1.getLow(0) : r2
338: .getLow(0);
339: double ymin = (r1.getLow(1) > r2.getLow(1)) ? r1.getLow(1) : r2
340: .getLow(1);
341: double xmax = (r1.getHigh(0) < r2.getHigh(0)) ? r1.getHigh(0)
342: : r2.getHigh(0);
343: double ymax = (r1.getHigh(1) < r2.getHigh(1)) ? r1.getHigh(1)
344: : r2.getHigh(1);
345:
346: return new Region(new double[] { xmin, ymin }, new double[] {
347: xmax, ymax });
348: }
349:
350: public Query match(Query q) {
351: // TODO Auto-generated method stub
352: return null;
353: }
354:
355: public void register(Query q) {
356: // TODO Auto-generated method stub
357: }
358:
359: public void register(Filter f) {
360: if (f instanceof BBOXImpl) {
361: BBOXImpl bbox = (BBOXImpl) f;
362: Region r = new Region(new double[] { bbox.getMinX(),
363: bbox.getMinY() }, new double[] { bbox.getMaxX(),
364: bbox.getMaxY() });
365: tree.insertData(null, r, 0);
366: }
367: }
368:
369: public void unregister(Query q) {
370: // TODO Auto-generated method stub
371: }
372:
373: public void unregister(Filter f) {
374: // TODO Auto-generated method stub
375: // intersectionQuery
376: // for each node, invalidate entry
377: // push node in stack
378: // while stack not empty
379: // get node from stack
380: // if four invalid quadrants, make node an invalid leaf
381: }
382: }
|