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.Envelope;
019:
020: import org.geotools.caching.FeatureCache;
021: import org.geotools.caching.FeatureCacheException;
022: import org.geotools.caching.spatialindex.rtree.Index;
023: import org.geotools.caching.spatialindex.rtree.Leaf;
024: import org.geotools.caching.spatialindex.rtree.RTree;
025: import org.geotools.caching.spatialindex.spatialindex.IData;
026: import org.geotools.caching.spatialindex.spatialindex.IEntry;
027: import org.geotools.caching.spatialindex.spatialindex.INode;
028: import org.geotools.caching.spatialindex.spatialindex.INodeCommand;
029: import org.geotools.caching.spatialindex.spatialindex.IQueryStrategy;
030: import org.geotools.caching.spatialindex.spatialindex.IVisitor;
031: import org.geotools.caching.spatialindex.spatialindex.Region;
032: import org.geotools.caching.spatialindex.spatialindex.SpatialIndex;
033: import org.geotools.caching.spatialindex.storagemanager.MemoryStorageManager;
034: import org.geotools.caching.spatialindex.storagemanager.PropertySet;
035: import org.geotools.caching.util.FilterSplitter;
036:
037: import org.geotools.data.DataStore;
038: import org.geotools.data.DataUtilities;
039: import org.geotools.data.FeatureListener;
040: import org.geotools.data.FeatureReader;
041: import org.geotools.data.Query;
042: import org.geotools.data.Transaction;
043: import org.geotools.data.store.EmptyFeatureCollection;
044:
045: import org.geotools.feature.AttributeType;
046: import org.geotools.feature.DefaultFeatureCollection;
047: import org.geotools.feature.Feature;
048: import org.geotools.feature.FeatureCollection;
049: import org.geotools.feature.FeatureIterator;
050: import org.geotools.feature.FeatureType;
051: import org.geotools.feature.SchemaException;
052:
053: import org.geotools.filter.FilterFactoryImpl;
054: import org.geotools.filter.spatial.BBOXImpl;
055:
056: import org.opengis.filter.Filter;
057: import org.opengis.filter.FilterFactory;
058:
059: import java.io.IOException;
060:
061: import java.util.ArrayList;
062: import java.util.HashMap;
063: import java.util.Hashtable;
064: import java.util.Iterator;
065: import java.util.List;
066: import java.util.Set;
067:
068: /** An implementation of FeatureCache :
069: * <ul><li>with in memory storage
070: * <li>uses a RTree to index features
071: * <li>uses a SpatialQueryTracker to track query bounds
072: * </ul>
073: *
074: * @param ds the DataStore to cache
075: * @param t the FeatureType
076: *
077: * TODO: add constructor InMemoryFeatureCache(FeatureStore)
078: *
079: * @author Christophe Rousson, SoC 2007, CRG-ULAVAL
080: *
081: */
082: public class InMemoryFeatureCache implements FeatureCache {
083: protected Transaction transaction = Transaction.AUTO_COMMIT;
084: protected final DataStore ds;
085: protected final HashMap store;
086: protected final Hashtable nodes;
087: protected final FeatureType type;
088: protected final SpatialQueryTracker tracker;
089: protected final RTree index;
090: protected int capacity;
091: protected int cacheReads = 0;
092: protected int storeReads = 0;
093: protected int evictions = 0;
094:
095: /** Create a new InMemoryFeatureCache
096: *
097: * @param ds the source DataStore for features
098: * @param t FeatureType to cache
099: * @throws FeatureCacheException if DataStore does not have type t, or if IOException occurs
100: */
101: public InMemoryFeatureCache(DataStore ds, FeatureType t,
102: int capacity) throws FeatureCacheException {
103: FeatureType dstype = null;
104:
105: try {
106: dstype = ds.getSchema(t.getTypeName());
107: } catch (IOException e) {
108: throw (FeatureCacheException) new FeatureCacheException()
109: .initCause(e);
110: }
111:
112: if ((dstype == null) || !dstype.equals(t)) {
113: throw new FeatureCacheException(new SchemaException(
114: "Datastore does not have type " + t.getTypeName()));
115: }
116:
117: this .ds = ds;
118: this .type = t;
119: this .store = new HashMap();
120: this .nodes = new Hashtable();
121: this .tracker = new SpatialQueryTracker();
122: this .capacity = capacity;
123:
124: PropertySet ps = new PropertySet();
125: ps.setProperty("TreeVariant", new Integer(
126: SpatialIndex.RtreeVariantLinear));
127: ps.setProperty("LeafCapacity", new Integer(capacity / 10));
128:
129: MemoryStorageManager sm = new MemoryStorageManager();
130: this .index = new RTree(ps, sm);
131: this .index.addDeleteNodeCommand(new INodeCommand() {
132: public void execute(INode n) {
133: nodes.remove(new Integer(n.getIdentifier()));
134: }
135: });
136: this .index.addReadNodeCommand(new INodeCommand() {
137: public void execute(INode n) {
138: NodeCacheEntry entry = (NodeCacheEntry) nodes
139: .get(new Integer(n.getIdentifier()));
140:
141: if (entry == null) {
142: entry = new NodeCacheEntry(n);
143: nodes.put(new Integer(n.getIdentifier()), entry);
144: }
145:
146: entry.hit();
147: }
148: });
149: this .index.addWriteNodeCommand(new INodeCommand() {
150: public void execute(INode n) {
151: NodeCacheEntry entry = new NodeCacheEntry(n);
152: nodes.put(new Integer(n.getIdentifier()), entry);
153: }
154: });
155: }
156:
157: public void clear() {
158: throw new UnsupportedOperationException();
159: }
160:
161: public void evict() {
162: //System.out.println("before = " + store.size()) ;
163: //System.out.println(index.getStatistics()) ;
164: EvictionQueryStrategy strategy = new EvictionQueryStrategy();
165: index.queryStrategy(strategy);
166: strategy.doDelete();
167:
168: //System.out.println("after = " + store.size()) ;
169: //System.out.println(index.getStatistics()) ;
170: //System.out.println("======================") ;
171: }
172:
173: /* (non-Javadoc)
174: * @see org.geotools.caching.FeatureCache#get(java.lang.String)
175: */
176: public Feature get(String id) throws FeatureCacheException {
177: /*SimpleFeatureCacheEntry entry = (SimpleFeatureCacheEntry) store.get(id) ;
178: Feature f = null ;*/
179: Feature f = (Feature) store.get(id);
180:
181: if (f == null) {
182: Filter filter = new FilterFactoryImpl().createFidFilter(id);
183:
184: try {
185: FeatureCollection fc = getFeatures(filter);
186:
187: if (fc.size() > 0) {
188: FeatureIterator it = fc.features();
189: f = it.next();
190: }
191: } catch (IOException e) {
192: throw (FeatureCacheException) new FeatureCacheException()
193: .initCause(e);
194: }
195:
196: /*} else {
197: f = (Feature) entry.getValue() ; */
198: }
199:
200: return f;
201: }
202:
203: /**
204: * @param id
205: * @return
206: */
207: public Feature peek(String id) {
208: /*SimpleFeatureCacheEntry entry = (SimpleFeatureCacheEntry) store.get(id) ;
209: if (entry == null) {
210: return null ;
211: } else {
212: return (Feature) entry.getValue() ;
213: }*/
214: return (Feature) store.get(id);
215: }
216:
217: /** Transform a JTS Envelope to a Region
218: *
219: * @param e JTS Envelope
220: * @return
221: */
222: protected static Region toRegion(final Envelope e) {
223: Region r = new Region(
224: new double[] { e.getMinX(), e.getMinY() },
225: new double[] { e.getMaxX(), e.getMaxY() });
226:
227: return r;
228: }
229:
230: public void put(Feature f) {
231: if (store.containsKey(f.getID())) {
232: return;
233: }
234:
235: //store.put(f.getID(), new SimpleFeatureCacheEntry(f));
236: store.put(f.getID(), f);
237:
238: Region r = toRegion(f.getBounds());
239: index.insertData(f.getID().getBytes(), r, f.getID().hashCode());
240: }
241:
242: public void putAll(FeatureCollection fc, Filter f) {
243: if (fc.size() > capacity) {
244: return;
245: }
246:
247: tracker.register(f);
248:
249: FeatureIterator it = fc.features();
250:
251: while (it.hasNext()) {
252: if (store.size() >= capacity) {
253: evict();
254: }
255:
256: put(it.next());
257: }
258:
259: it.close();
260: }
261:
262: public Feature remove(String id) {
263: Feature f = peek(id);
264:
265: if (f == null) {
266: return null;
267: }
268:
269: index.deleteData(toRegion(f.getBounds()), f.getID().hashCode());
270: store.remove(id);
271:
272: return f;
273: }
274:
275: public int size() {
276: return store.size();
277: }
278:
279: public Filter[] splitFilter(Filter f) {
280: Filter[] filters = new Filter[3];
281: FilterSplitter splitter = new FilterSplitter();
282: f.accept(splitter, null);
283:
284: Filter sr = splitter.getSpatialRestriction();
285:
286: /*if (f instanceof BBOXImpl) {
287: Filter missing = tracker.match(sr);
288: Filter cached;
289: if (missing.equals(f)) {
290: cached = Filter.EXCLUDE;
291: } else {
292: cached = f;
293: }
294: filters[SPATIAL_RESTRICTION_CACHED] = cached;
295: filters[SPATIAL_RESTRICTION_MISSING] = missing;
296: filters[OTHER_RESTRICTIONS] = Filter.INCLUDE;
297: } else {
298: filters[SPATIAL_RESTRICTION_CACHED] = Filter.EXCLUDE;
299: filters[SPATIAL_RESTRICTION_MISSING] = f;
300: filters[OTHER_RESTRICTIONS] = Filter.INCLUDE;
301: }*/
302: assert ((sr == Filter.INCLUDE) || sr instanceof BBOXImpl);
303:
304: //System.out.println(sr.getClass()) ;
305: Filter missing = tracker.match(sr);
306: Filter cached;
307:
308: if (missing == sr) {
309: cached = Filter.EXCLUDE;
310: } else {
311: cached = sr;
312: }
313:
314: filters[SPATIAL_RESTRICTION_CACHED] = cached;
315: filters[SPATIAL_RESTRICTION_MISSING] = missing;
316: filters[OTHER_RESTRICTIONS] = splitter.getOtherRestriction();
317:
318: return filters;
319: }
320:
321: public Set addFeatures(FeatureCollection collection)
322: throws IOException {
323: throw new UnsupportedOperationException();
324: }
325:
326: public Transaction getTransaction() {
327: // TODO Auto-generated method stub
328: return transaction;
329: }
330:
331: public void modifyFeatures(AttributeType[] type, Object[] value,
332: Filter filter) throws IOException {
333: throw new UnsupportedOperationException();
334: }
335:
336: public void modifyFeatures(AttributeType type, Object value,
337: Filter filter) throws IOException {
338: throw new UnsupportedOperationException();
339: }
340:
341: public void removeFeatures(Filter filter) throws IOException {
342: throw new UnsupportedOperationException();
343: }
344:
345: public void setFeatures(FeatureReader reader) throws IOException {
346: throw new UnsupportedOperationException();
347: }
348:
349: public void setTransaction(Transaction transaction) {
350: if (transaction == null) {
351: throw new IllegalArgumentException(
352: "Transaction cannot be null, did you mean Transaction.AUTO_COMMIT?");
353: }
354:
355: this .transaction = transaction;
356: }
357:
358: public void addFeatureListener(FeatureListener listener) {
359: // TODO Auto-generated method stub
360: }
361:
362: public Envelope getBounds() throws IOException {
363: // TODO Auto-generated method stub
364: return getDataStore().getFeatureSource(type.getTypeName())
365: .getBounds();
366: }
367:
368: public Envelope getBounds(Query query) throws IOException {
369: return getDataStore().getFeatureSource(type.getTypeName())
370: .getBounds(query);
371: }
372:
373: public int getCount(Query query) throws IOException {
374: // may be we should return -1 if this is too expensive, or an estimate ?
375: return getDataStore().getFeatureSource(type.getTypeName())
376: .getCount(query);
377: }
378:
379: public DataStore getDataStore() {
380: return ds;
381: }
382:
383: public FeatureCollection getFeatures() throws IOException {
384: return getFeatures(Filter.INCLUDE);
385: }
386:
387: public FeatureCollection getFeatures(Query query)
388: throws IOException {
389: if ((query.getTypeName() != null)
390: && (query.getTypeName() != type.getTypeName())) {
391: return new EmptyFeatureCollection(getSchema());
392: }
393:
394: return getFeatures(query.getFilter());
395: }
396:
397: public FeatureCollection getFeatures(Filter filter)
398: throws IOException {
399: Filter[] filters = splitFilter(filter);
400: FeatureCollection fromCache = loadFromCache(filters[SPATIAL_RESTRICTION_CACHED]);
401:
402: //System.out.println("from cache = " + fromCache.size()) ;
403: //fromCache.subCollection(filters[OTHER_RESTRICTIONS]) ;
404: //System.out.println("from cache = " + fromCache.size()) ;
405: cacheReads += fromCache.size();
406:
407: FilterFactory ff = new FilterFactoryImpl();
408: Filter missing = filters[SPATIAL_RESTRICTION_MISSING];
409:
410: if (missing != Filter.EXCLUDE) {
411: FeatureCollection fromStore = loadFromStore(ff.and(missing,
412: filters[OTHER_RESTRICTIONS]));
413: //tracker.register(missing);
414: putAll(fromStore, missing);
415: //System.out.println("from store = " + fromStore.size()) ;
416: storeReads += fromStore.size();
417: fromCache.addAll(fromStore);
418:
419: //System.out.println("Added data to cache") ;
420: }
421:
422: return fromCache;
423: }
424:
425: protected FeatureCollection loadFromStore(Filter f)
426: throws IOException {
427: FeatureCollection c = ds.getFeatureSource(type.getTypeName())
428: .getFeatures(f);
429:
430: //System.out.println(index.getStatistics()) ;
431: return c;
432: }
433:
434: protected FeatureCollection loadFromCache(Filter f) {
435: if (f == Filter.EXCLUDE) {
436: return new DefaultFeatureCollection("cached", type);
437: } else {
438: final List features = new ArrayList();
439: BBOXImpl bb = (BBOXImpl) f;
440: Region r = new Region(new double[] { bb.getMinX(),
441: bb.getMinY() }, new double[] { bb.getMaxX(),
442: bb.getMaxY() });
443: index.intersectionQuery(r, new IVisitor() {
444: public void visitData(final IData d) {
445: String id = new String(d.getData());
446: features.add(peek(id));
447:
448: //System.out.println("Data = " + d.getIdentifier() + " fid = " + get(id)) ;
449: }
450:
451: public void visitNode(final INode n) {
452: NodeCacheEntry e = (NodeCacheEntry) nodes
453: .get(new Integer(n.getIdentifier()));
454:
455: if (e == null) {
456: e = new NodeCacheEntry(n);
457: nodes.put(new Integer(n.getIdentifier()), e);
458:
459: //System.out.println("created node " + n.getIdentifier()) ;
460: }
461:
462: e.hit();
463:
464: //System.out.println("hitted node " + n.getIdentifier()) ;
465: }
466: });
467:
468: return DataUtilities.collection((Feature[]) features
469: .toArray(new Feature[1]));
470: }
471: }
472:
473: public FeatureType getSchema() {
474: return type;
475: }
476:
477: public void removeFeatureListener(FeatureListener listener) {
478: throw new UnsupportedOperationException();
479: }
480:
481: public int getCacheReads() {
482: return cacheReads;
483: }
484:
485: public int getStoreReads() {
486: return storeReads;
487: }
488:
489: public int getEvictions() {
490: return evictions;
491: }
492:
493: class EvictionQueryStrategy implements IQueryStrategy {
494: Leaf leaf = null;
495:
496: public void getNextEntry(IEntry e, int[] nextEntry,
497: boolean[] hasNext) {
498: if (e instanceof Index) {
499: // TODO handle case there is no child
500: Index n = (Index) e;
501: NodeCacheEntry entry = (NodeCacheEntry) nodes
502: .get(new Integer(n.getChildIdentifier(0)));
503: long accessTime;
504:
505: if (entry == null) {
506: accessTime = System.currentTimeMillis();
507: } else {
508: accessTime = entry.getLastAccessTime();
509: }
510:
511: for (int i = 1; i < n.getChildrenCount(); i++) {
512: NodeCacheEntry next = (NodeCacheEntry) nodes
513: .get(new Integer(n.getChildIdentifier(i)));
514:
515: if ((next != null)
516: && (next.getLastAccessTime() < accessTime)) {
517: accessTime = next.getLastAccessTime();
518: entry = next;
519: }
520: }
521: assert (entry != null);
522: nextEntry[0] = ((INode) entry.getValue())
523: .getIdentifier();
524: hasNext[0] = true;
525:
526: return;
527: } else if (e instanceof Leaf) {
528: leaf = (Leaf) e;
529: /*for (int i = 0 ; i < leaf.getChildrenCount() ; i++ ) {
530: // can't do that cause read lock !
531: //index.deleteData(leaf.getChildShape(i), leaf.getChildIdentifier(i)) ;
532: System.out.println("Should delete data " + leaf.getChildIdentifier(i)) ;
533: }*/
534: hasNext[0] = false;
535: }
536: }
537:
538: public void doDelete() {
539: if (leaf != null) {
540: //System.out.println("deleting") ;
541: //index.deleteLeaf(leaf) ;
542: //index.deleteLeaf(node, leafIndex) ;
543: List ids = index.readLeaf(leaf);
544:
545: for (Iterator it = ids.iterator(); it.hasNext();) {
546: String id = (String) it.next();
547: remove(id);
548: evictions++;
549: }
550:
551: Region r = (Region) leaf.getShape();
552: Envelope e = new Envelope(r.getLow(0), r.getHigh(0), r
553: .getLow(1), r.getHigh(1));
554: tracker.unregister(e);
555: }
556: }
557: }
558: }
|