001: /*
002: * GeoTools - OpenSource mapping toolkit
003: * http://geotools.org
004: * (C) 2003-2006, GeoTools Project Managment Committee (PMC)
005: * (C) 2002, Centre for Computational Geography
006: *
007: * This library is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU Lesser General Public
009: * License as published by the Free Software Foundation;
010: * version 2.1 of the License.
011: *
012: * This library is distributed in the hope that it will be useful,
013: * but WITHOUT ANY WARRANTY; without even the implied warranty of
014: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015: * Lesser General Public License for more details.
016: */
017: package org.geotools.index.rtree;
018:
019: import com.vividsolutions.jts.geom.Envelope;
020: import org.apache.velocity.runtime.exception.NodeException;
021: import org.opengis.filter.Filter;
022: import org.geotools.filter.Filters;
023: import org.geotools.index.Data;
024: import org.geotools.index.DataDefinition;
025: import org.geotools.index.Lock;
026: import org.geotools.index.LockTimeoutException;
027: import org.geotools.index.TreeException;
028: import org.geotools.index.UnsupportedFilterException;
029: import java.util.ArrayList;
030: import java.util.Collection;
031: import java.util.Iterator;
032: import java.util.List;
033: import java.util.logging.Level;
034: import java.util.logging.Logger;
035:
036: /**
037: * DOCUMENT ME!
038: *
039: * @author Tommaso Nolli
040: * @source $URL: http://svn.geotools.org/geotools/tags/2.4.1/modules/plugin/shapefile/src/main/java/org/geotools/index/rtree/RTree.java $
041: */
042: public class RTree {
043: private Logger logger = org.geotools.util.logging.Logging
044: .getLogger("org.geotools.index.rtree");
045: private PageStore store;
046:
047: public RTree(PageStore store) throws TreeException {
048: this .store = store;
049: }
050:
051: /**
052: * Gets this index bounding box
053: *
054: * @return An Envelope
055: *
056: * @throws TreeException DOCUMENT ME!
057: */
058: public Envelope getBounds() throws TreeException {
059: this .checkOpen();
060:
061: Node root = this .store.getRoot();
062:
063: return (root == null) ? null : root.getBounds();
064: }
065:
066: /**
067: * DOCUMENT ME!
068: *
069: * @param filter
070: *
071: *
072: * @throws TreeException
073: * @throws UnsupportedFilterException
074: */
075: public Envelope getBounds(Filter filter) throws TreeException,
076: UnsupportedFilterException {
077: this .checkOpen();
078:
079: FilterConsumer fc = new FilterConsumer();
080: Filters.accept(filter, fc);
081:
082: Envelope env = fc.getBounds();
083:
084: if (env == null) {
085: throw new UnsupportedFilterException("Filter not supported");
086: }
087:
088: Node root = this .store.getRoot();
089:
090: return env.contains(root.getBounds()) ? root.getBounds() : this
091: .getBoundsInternal(env, root);
092: }
093:
094: /*
095: public Envelope getBounds(Envelope env) {
096:
097: }
098: */
099:
100: /**
101: * DOCUMENT ME!
102: *
103: * @param query
104: * @param node
105: *
106: * @return DOCUMENT ME!
107: *
108: * @throws TreeException
109: */
110: private Envelope getBoundsInternal(final Envelope query,
111: final Node node) throws TreeException {
112: Envelope result = null;
113: Entry entry = null;
114:
115: for (int i = 0; i < node.getEntriesCount(); i++) {
116: entry = node.getEntry(i);
117:
118: if (entry.getBounds().intersects(query)) {
119: if (node.isLeaf()) {
120: if (result == null) {
121: result = new Envelope(entry.getBounds());
122: } else {
123: result.expandToInclude(entry.getBounds());
124: }
125: } else {
126: this .getBoundsInternal(query, this .store.getNode(
127: entry, node));
128: }
129: }
130: }
131:
132: return result;
133: }
134:
135: public DataDefinition getDataDefinition() {
136: return this .store.getDataDefinition();
137: }
138:
139: /**
140: * Performs a search on this <code>RTree</code>
141: *
142: * @param query the query <code>Envelope</code>
143: *
144: * @return a <code>Collection</code> of <code>Data</code>
145: *
146: * @throws TreeException DOCUMENT ME!
147: * @throws LockTimeoutException DOCUMENT ME!
148: */
149: public List search(Envelope query) throws TreeException,
150: LockTimeoutException {
151: // Aquire a read lock
152: Lock lock = this .store.getReadLock();
153: List ret = null;
154:
155: try {
156: ret = this .search(query, lock);
157: } finally {
158: // Release the lock
159: this .store.releaseLock(lock);
160: }
161:
162: return ret;
163: }
164:
165: /**
166: * Performs a search on this <code>RTree</code>
167: *
168: * @param filter a <code>Filter</code>
169: *
170: * @return a <code>Collection</code> of <code>Data</code>
171: *
172: * @throws TreeException
173: * @throws UnsupportedFilterException DOCUMENT ME!
174: * @throws LockTimeoutException DOCUMENT ME!
175: */
176: public List search(Filter filter) throws TreeException,
177: UnsupportedFilterException, LockTimeoutException {
178: // Aquire a read lock
179: Lock lock = this .store.getReadLock();
180: List ret = null;
181:
182: try {
183: FilterConsumer fc = new FilterConsumer();
184: Filters.accept(filter, fc);
185:
186: if (fc.getBounds() != null) {
187: ret = this .search(fc.getBounds(), lock);
188: } else {
189: throw new UnsupportedFilterException(
190: "Not a valid filter");
191: }
192: } finally {
193: // Release the lock
194: this .store.releaseLock(lock);
195: }
196:
197: return ret;
198: }
199:
200: /**
201: * Performs a search on the index
202: *
203: * @param query The query <code>Envelope</code>
204: * @param lock A <code>Lock</code> on the index
205: *
206: * @return A <code>Collection</code> of <code>Data</code>
207: *
208: * @throws TreeException
209: * @throws LockTimeoutException
210: */
211: private List search(Envelope query, Lock lock)
212: throws TreeException, LockTimeoutException {
213: long start = System.currentTimeMillis();
214: this .checkOpen();
215:
216: ArrayList matches = new ArrayList();
217:
218: Node root = this .store.getRoot();
219: this .searchNode(query, root, matches);
220:
221: if (logger.isLoggable(Level.FINEST)) {
222: logger.log(Level.FINEST, matches.size()
223: + " Data objects retrieved in "
224: + (System.currentTimeMillis() - start) + "ms.");
225: }
226:
227: return matches;
228: }
229:
230: /**
231: * DOCUMENT ME!
232: *
233: * @param query
234: * @param node
235: * @param matches
236: *
237: * @throws TreeException
238: */
239: private void searchNode(final Envelope query, final Node node,
240: final ArrayList matches) throws TreeException {
241: Entry entry = null;
242:
243: for (int i = 0; i < node.getEntriesCount(); i++) {
244: entry = node.getEntry(i);
245:
246: if (entry.getBounds().intersects(query)) {
247: if (node.isLeaf()) {
248: matches.add(entry.getData());
249: } else {
250: searchNode(query, this .store.getNode(entry, node),
251: matches);
252: }
253: }
254: }
255: }
256:
257: /**
258: * DOCUMENT ME!
259: *
260: * @param bounds
261: * @param data
262: *
263: * @throws TreeException
264: * @throws LockTimeoutException
265: */
266: public void insert(Envelope bounds, Data data)
267: throws TreeException, LockTimeoutException {
268: if (!data.isValid()) {
269: throw new TreeException("Invalid data supplied!");
270: }
271:
272: // Aquire a write lock
273: Lock lock = this .store.getWriteLock();
274:
275: try {
276: this .insert(lock, new Entry(bounds, data));
277: } finally {
278: // Release the lock
279: this .store.releaseLock(lock);
280: }
281: }
282:
283: /**
284: * DOCUMENT ME!
285: *
286: * @param lock
287: * @param entry
288: *
289: * @throws TreeException
290: */
291: private void insert(Lock lock, Entry entry) throws TreeException {
292: this .checkOpen();
293:
294: // Get the right leaf
295: Node leaf = this .chooseLeaf(this .store.getRoot(), entry);
296:
297: leaf.addEntry(entry);
298:
299: if (leaf.getEntriesCount() <= this .store.getMaxNodeEntries()) {
300: // If leaf has room add to it
301: leaf.save();
302: this .adjustTree(leaf, null);
303: } else {
304: // Overflow...
305: Node[] split = this .splitNode(leaf);
306: this .adjustTree(split[0], split[1]);
307: }
308: }
309:
310: /**
311: * DOCUMENT ME!
312: *
313: * @param node
314: * @param newEntry
315: *
316: *
317: * @throws TreeException DOCUMENT ME!
318: */
319: private Node chooseLeaf(Node node, Entry newEntry)
320: throws TreeException {
321: if (node.isLeaf()) {
322: return node;
323: }
324:
325: Collection entries = node.getEntries();
326:
327: // Find the best Entry
328: Entry best = null;
329: Envelope env = null;
330: double lastArea = Double.POSITIVE_INFINITY;
331: double currentArea = 0d;
332: double w = 0;
333: double h = 0;
334: double nw = 0;
335: double nh = 0;
336:
337: Entry element = null;
338:
339: for (Iterator iter = entries.iterator(); iter.hasNext();) {
340: element = (Entry) iter.next();
341:
342: currentArea = this .getAreaIncrease(element.getBounds(),
343: newEntry.getBounds());
344:
345: if (currentArea < lastArea) {
346: lastArea = currentArea;
347: best = element;
348: } else if ((currentArea == lastArea)
349: && (this .getEntryArea(best) > this
350: .getEntryArea(element))) {
351: best = element;
352: }
353: }
354:
355: // Now best is the best Entry
356: return this
357: .chooseLeaf(this .store.getNode(best, node), newEntry);
358: }
359:
360: /**
361: * DOCUMENT ME!
362: *
363: * @param node
364: *
365: *
366: * @throws TreeException
367: */
368: private Node[] splitNode(Node node) throws TreeException {
369: Collection entriesTmp = node.getEntries();
370:
371: Entry[] e = (Entry[]) entriesTmp.toArray(new Entry[entriesTmp
372: .size()]);
373: Entry[] firsts = null;
374:
375: if (this .store.getSplitAlgorithm() == PageStore.SPLIT_QUADRATIC) {
376: firsts = this .quadraticPickSeeds(e);
377: } else {
378: firsts = this .linearPickSeeds(e);
379: }
380:
381: ArrayList entries = new ArrayList(e.length - 2);
382:
383: for (int i = 0; i < e.length; i++) {
384: if (!e[i].equals(firsts[0]) && !e[i].equals(firsts[1])) {
385: entries.add(e[i]);
386: }
387: }
388:
389: // Clear the node in order to reuse it
390: node.clear();
391:
392: Node newNode = this .store.getEmptyNode(node.isLeaf());
393:
394: Node[] ret = new Node[] { node, newNode };
395: ret[0].addEntry(firsts[0]);
396: ret[1].addEntry(firsts[1]);
397:
398: Entry toAssign = null;
399: double d1 = 0d;
400: double d2 = 0d;
401: int pointer = -1;
402:
403: while (true) {
404: if (entries.size() == 0) {
405: break;
406: } else {
407: /* If the remaining elements are not enough
408: * for reaching the minNodeElements of a group
409: * or are just right to reach it, add all entries
410: * to the group
411: */
412: if ((ret[0].getEntriesCount() + entries.size()) <= this .store
413: .getMinNodeEntries()) {
414: for (int i = 0; i < entries.size(); i++) {
415: ret[0].addEntry((Entry) entries.get(i));
416: }
417:
418: break;
419: }
420:
421: if ((ret[1].getEntriesCount() + entries.size()) <= this .store
422: .getMinNodeEntries()) {
423: for (int i = 0; i < entries.size(); i++) {
424: ret[1].addEntry((Entry) entries.get(i));
425: }
426:
427: break;
428: }
429: }
430:
431: toAssign = null;
432:
433: if (this .store.getSplitAlgorithm() == PageStore.SPLIT_QUADRATIC) {
434: toAssign = this .quadraticPickNext(ret, entries);
435: } else {
436: toAssign = this .linearPickNext(ret, entries);
437: }
438:
439: d1 = this .getAreaIncrease(ret[0].getBounds(), toAssign
440: .getBounds());
441: d2 = this .getAreaIncrease(ret[1].getBounds(), toAssign
442: .getBounds());
443:
444: if (d1 < d2) {
445: pointer = 0;
446: } else if (d1 > d2) {
447: pointer = 1;
448: } else {
449: // If areas increase are the same, smallest wins
450: d1 = this .getEnvelopeArea(ret[0].getBounds());
451: d2 = this .getEnvelopeArea(ret[1].getBounds());
452:
453: if (d1 < d2) {
454: pointer = 0;
455: } else if (d1 > d2) {
456: pointer = 1;
457: } else {
458: /* If areas are the same the one with less
459: * entries wins
460: */
461: if (ret[0].getEntriesCount() < ret[1]
462: .getEntriesCount()) {
463: pointer = 0;
464: } else {
465: pointer = 1;
466: }
467: }
468: }
469:
470: ret[pointer].addEntry(toAssign);
471:
472: entries.remove(toAssign);
473: }
474:
475: ret[0].save();
476: ret[1].save();
477:
478: return ret;
479: }
480:
481: /**
482: * Returns the 2 new <code>Node</code>s
483: *
484: * @param entries
485: *
486: */
487: private Entry[] quadraticPickSeeds(Entry[] entries) {
488: Entry[] ret = new Entry[2];
489: Envelope env = null;
490: double actualD = 0d;
491: double choosedD = Double.NEGATIVE_INFINITY;
492:
493: // Foreach pair of entries...
494: for (int i = 0; i < (entries.length - 1); i++) {
495: env = new Envelope(entries[i].getBounds());
496:
497: for (int j = i + 1; j < entries.length; j++) {
498: env.expandToInclude(entries[j].getBounds());
499:
500: // find the inefficency of groupping together
501: actualD = this .getAreaDifference(env, entries[i],
502: entries[j]);
503:
504: // Choose the pair with the largest area
505: if (actualD > choosedD) {
506: choosedD = actualD;
507: ret[0] = entries[i];
508: ret[1] = entries[j];
509: }
510: }
511: }
512:
513: return ret;
514: }
515:
516: private Entry[] linearPickSeeds(Entry[] entries) {
517: //TODO Implement
518: return null;
519: }
520:
521: /**
522: * DOCUMENT ME!
523: *
524: * @param nodes
525: * @param entries
526: *
527: */
528: private Entry quadraticPickNext(Node[] nodes, ArrayList entries) {
529: Entry ret = null;
530: double[] d = new double[] { 0d, 0d };
531:
532: double diff = 0d;
533: double maxDiff = Double.NEGATIVE_INFINITY;
534: Envelope e = null;
535:
536: for (int i = 0; i < entries.size(); i++) {
537: e = ((Entry) entries.get(i)).getBounds();
538: d[0] = this .getAreaIncrease(nodes[0].getBounds(), e);
539: d[1] = this .getAreaIncrease(nodes[1].getBounds(), e);
540:
541: diff = Math.abs(d[0] - d[1]);
542:
543: if (diff > maxDiff) {
544: maxDiff = diff;
545: ret = (Entry) entries.get(i);
546: }
547: }
548:
549: return ret;
550: }
551:
552: /**
553: * DOCUMENT ME!
554: *
555: * @param nodes
556: * @param entries
557: *
558: */
559: private Entry linearPickNext(Node[] nodes, ArrayList entries) {
560: //TODO implement
561: return null;
562: }
563:
564: /**
565: * DOCUMENT ME!
566: *
567: * @param node1
568: * @param node2
569: *
570: * @throws TreeException
571: */
572: private void adjustTree(Node node1, Node node2)
573: throws TreeException {
574: Node n = node1;
575: Node nn = node2;
576:
577: Node p = null;
578: Entry e = null;
579:
580: while (true) {
581: if (n.equals(this .store.getRoot())) {
582: if (nn != null) {
583: Node newRoot = this .store.getEmptyNode(false);
584:
585: e = this .store.createEntryPointingNode(n);
586: newRoot.addEntry(e);
587:
588: e = this .store.createEntryPointingNode(nn);
589: newRoot.addEntry(e);
590:
591: newRoot.save();
592: this .store.setRoot(newRoot);
593:
594: n.setParent(newRoot);
595: nn.setParent(newRoot);
596:
597: n.save();
598: nn.save();
599: } else {
600: // Force root save...
601: this .store.setRoot(n);
602: }
603:
604: break;
605: }
606:
607: p = n.getParent();
608: e = p.getEntry(n);
609: e.setBounds(new Envelope(n.getBounds()));
610:
611: if (nn != null) {
612: Entry e2 = this .store.createEntryPointingNode(nn);
613:
614: p.addEntry(e2);
615:
616: if (p.getEntriesCount() > this .store
617: .getMaxNodeEntries()) {
618: Node[] split = this .splitNode(p);
619: n = split[0];
620: nn = split[1];
621:
622: // splitNodes saves the 2 nodes before returning
623: } else {
624: // No more to check
625: p.save();
626:
627: nn = null;
628: n = p;
629: }
630: } else {
631: p.save();
632: n = p;
633: }
634: }
635: }
636:
637: /**
638: * Deletes the entry with the specified <code>Envelope</code> as its bounds.<br>
639: * If more than one entry exists with the same bounds, then subsequent
640: * calls to <code>delete</code> are needed to remove all this elements.
641: *
642: * @param env The <code>Envelope</code>
643: *
644: * @throws TreeException
645: * @throws LockTimeoutException DOCUMENT ME!
646: */
647: public void delete(Envelope env) throws TreeException,
648: LockTimeoutException {
649: this .checkOpen();
650:
651: // Aquire a write lock
652: Lock lock = this .store.getWriteLock();
653:
654: try {
655: Node node = this .findLeaf(this .store.getRoot(), env);
656:
657: if (node == null) {
658: throw new TreeException(
659: "No node found with the supplied envelope: "
660: + env);
661: }
662:
663: Entry e = null;
664:
665: for (int i = 0; i < node.getEntriesCount(); i++) {
666: e = node.getEntry(i);
667:
668: if (e.getBounds().equals(env)) {
669: this .doDelete(lock, node, e);
670:
671: break;
672: }
673: }
674: } finally {
675: // Release the lock
676: this .store.releaseLock(lock);
677: }
678: }
679:
680: /**
681: * DOCUMENT ME!
682: *
683: * @param lock
684: * @param node
685: * @param entry
686: *
687: * @throws TreeException
688: */
689: private void doDelete(Lock lock, Node node, Entry entry)
690: throws TreeException {
691: node.removeEntry(entry);
692: node.save();
693:
694: Collection toRemove = this .condenseTree(node);
695:
696: Node root = this .store.getRoot();
697:
698: if ((root.getEntriesCount() == 1) && !root.isLeaf()) {
699: root = this .store.getNode(root.getEntry(0), root);
700: this .store.setRoot(root);
701: }
702:
703: Collection entries = new ArrayList();
704: Iterator iter = toRemove.iterator();
705:
706: while (iter.hasNext()) {
707: this .free((Node) iter.next(), entries);
708: }
709:
710: // Reinsert orphaned entries
711: Entry e = null;
712:
713: for (Iterator iterator = entries.iterator(); iterator.hasNext();) {
714: e = (Entry) iterator.next();
715: this .insert(lock, e);
716: }
717: }
718:
719: /**
720: * Frees a non leaf Node
721: *
722: * @param node The Node to free
723: * @param entries A <code>Collection</code> used to store Node Entry
724: *
725: * @throws TreeException DOCUMENT ME!
726: */
727: private void free(final Node node, final Collection entries)
728: throws TreeException {
729: if (node.isLeaf()) {
730: entries.addAll(node.getEntries());
731: } else {
732: for (int i = 0; i < node.getEntriesCount(); i++) {
733: this .free(this .store.getNode(node.getEntry(i), node),
734: entries);
735: }
736: }
737:
738: this .store.free(node);
739: }
740:
741: /**
742: * Closes this index and the associated <code>PageStore</code>
743: *
744: * @throws TreeException
745: */
746: public void close() throws TreeException {
747: this .store.close();
748: this .store = null;
749: }
750:
751: /**
752: * Checks to see if the index is open
753: *
754: * @throws TreeException If the index is closed
755: */
756: private void checkOpen() throws TreeException {
757: if (this .store == null) {
758: throw new TreeException("The index is closed!");
759: }
760: }
761:
762: /**
763: * Finds the first leaf node that contains the element with the supplied
764: * envelope
765: *
766: * @param node Starting node
767: * @param envelope <code>Envelope</code> to search
768: *
769: * @return The <code>Node</code> that contains the element
770: *
771: * @throws TreeException
772: */
773: private Node findLeaf(Node node, Envelope envelope)
774: throws TreeException {
775: Node ret = null;
776: Entry entry = null;
777:
778: for (int i = 0; i < node.getEntriesCount(); i++) {
779: entry = node.getEntry(i);
780:
781: if (node.isLeaf()) {
782: if (entry.getBounds().equals(envelope)) {
783: ret = node;
784: }
785: } else {
786: if (entry.getBounds().contains(envelope)) {
787: ret = this .findLeaf(
788: this .store.getNode(entry, node), envelope);
789: }
790: }
791:
792: if ((ret != null) && ret.isLeaf()) {
793: break;
794: }
795: }
796:
797: return ret;
798: }
799:
800: /**
801: * DOCUMENT ME!
802: *
803: * @param node
804: *
805: *
806: * @throws TreeException
807: */
808: private Collection condenseTree(Node node) throws TreeException {
809: ArrayList removed = new ArrayList();
810:
811: if (node.equals(this .store.getRoot())) {
812: return removed;
813: }
814:
815: Node parentNode = node.getParent();
816: Entry parentEntry = parentNode.getEntry(node);
817:
818: if (node.getEntriesCount() < this .store.getMinNodeEntries()) {
819: removed.add(node);
820: parentNode.removeEntry(parentEntry);
821: } else {
822: parentEntry.setBounds(node.getBounds());
823: }
824:
825: parentNode.save();
826:
827: if (this .store.getRoot().equals(parentNode)) {
828: this .store.setRoot(parentNode);
829: }
830:
831: removed.addAll(this .condenseTree(parentNode));
832:
833: return removed;
834: }
835:
836: /**
837: * Gets the area of an <code>Entry</code>
838: *
839: * @param e The <code>Entry</code>
840: *
841: * @return the area
842: */
843: private double getEntryArea(Entry e) {
844: return this .getEnvelopeArea(e.getBounds());
845: }
846:
847: private double getEnvelopeArea(Envelope env) {
848: return env.getWidth() * env.getHeight();
849: }
850:
851: private double getAreaIncrease(Envelope orig, Envelope add) {
852: double ret = 0d;
853:
854: // The old values
855: Envelope env = new Envelope(orig);
856: double w = env.getWidth();
857: double h = env.getHeight();
858:
859: // Expand the envelope
860: env.expandToInclude(add);
861:
862: // Check area delta
863: double nw = env.getWidth();
864: double nh = env.getHeight();
865:
866: ret += ((nw - w) * nh); // new height
867: ret += ((nh - h) * w); // old width
868:
869: return ret;
870: }
871:
872: private double getAreaDifference(Envelope env, Entry e1, Entry e2) {
873: return this .getEnvelopeArea(env) - this .getEntryArea(e1)
874: - this .getEntryArea(e2);
875: }
876:
877: /**
878: * @see java.lang.Object#toString()
879: */
880: public String toString() {
881: Node root = this .store.getRoot();
882:
883: String ret = null;
884:
885: try {
886: ret = this .dump(root, 0);
887: } catch (TreeException e) {
888: e.printStackTrace();
889: }
890:
891: return ret;
892: }
893:
894: private String dump(Node node, int indent) throws TreeException {
895: StringBuffer spc = new StringBuffer();
896:
897: for (int i = 0; i < indent; i++) {
898: spc.append(" ");
899: }
900:
901: StringBuffer ret = new StringBuffer();
902: ret.append(spc);
903: ret.append("Node: ").append(node.getBounds());
904: ret.append(System.getProperty("line.separator"));
905:
906: spc.append(" ");
907:
908: for (int i = 0; i < node.getEntriesCount(); i++) {
909: ret.append(spc).append(node.getEntry(i)).append(
910: System.getProperty("line.separator"));
911:
912: if (!node.isLeaf()) {
913: ret.append(this .dump(this .store.getNode(node
914: .getEntry(i), node), indent + 1));
915: }
916: }
917:
918: return ret.toString();
919: }
920: }
|