001: //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/trunk/src/org/deegree/io/rtree/RTree.java $
002: //
003: //RTree implementation.
004: //Copyright (C) 2002-2004 Wolfgang Baer - WBaer@gmx.de
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; either
009: //version 2.1 of the License, or (at your option) any later version.
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: //You should have received a copy of the GNU Lesser General Public
017: //License along with this library; if not, write to the Free Software
018: //Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
019:
020: package org.deegree.io.rtree;
021:
022: import java.io.Serializable;
023: import java.util.Arrays;
024: import java.util.Enumeration;
025: import java.util.Stack;
026: import java.util.Vector;
027:
028: /**
029: * <br>
030: * Implementation of a R-Tree after the algorithms of Antonio Guttman. With nearest neighbour search
031: * after algorithm of Cheung & Fu <br>
032: *
033: * @author Wolfgang Baer - WBaer@gmx.de
034: * @author last edited by: $Author: apoth $
035: *
036: * @version $Revision: 6813 $, $Date: 2007-05-04 06:41:50 -0700 (Fri, 04 May 2007) $
037: */
038: public class RTree implements Serializable {
039:
040: private PageFile file;
041:
042: /**
043: * Creates an empty R-Tree with a memory-mapped pagefile (MemoryPageFile) and an empty root node
044: *
045: * @param dimension -
046: * dimension of the data to store
047: * @param maxLoad -
048: * maximum load of a node
049: * @throws RTreeException
050: */
051: public RTree(int dimension, int maxLoad) throws RTreeException {
052: this .file = new MemoryPageFile();
053:
054: try {
055: file.initialize(dimension, maxLoad + 1);
056: Node rootNode = new LeafNode(0, this .file);
057: file.writeNode(rootNode);
058: } catch (PageFileException e) {
059: e.fillInStackTrace();
060: throw new RTreeException(
061: "PageFileException in constructor occured");
062: }
063: }
064:
065: /**
066: * Creates an empty R-Tree with a persistent pagefile (PersistentPageFile) and an empty root
067: * node.
068: *
069: * @param dimension -
070: * dimension of the data to store
071: * @param maxLoad -
072: * maximum load of a node
073: * @param fileName -
074: * name of the rtree file
075: * @throws RTreeException
076: */
077: public RTree(int dimension, int maxLoad, String fileName)
078: throws RTreeException {
079: try {
080: this .file = new PersistentPageFile(fileName);
081: this .file.initialize(dimension, maxLoad + 1);
082:
083: Node rootNode = new LeafNode(0, this .file);
084: file.writeNode(rootNode);
085: } catch (PageFileException e) {
086: e.fillInStackTrace();
087: throw new RTreeException(
088: "PageFileException in constructor occured");
089: }
090: }
091:
092: /**
093: * Creates an R-Tree from an EXISTING persistent pagefile (PersistentPageFile).
094: *
095: * @param fileName -
096: * name of the existing rtree file
097: * @throws RTreeException
098: */
099: public RTree(String fileName) throws RTreeException {
100:
101: this .file = new PersistentPageFile(fileName);
102: try {
103: this .file.initialize(-999, -999);
104: } catch (PageFileException e) {
105: e.fillInStackTrace();
106: throw new RTreeException(
107: "PageFileException in constructor occured");
108: }
109: }
110:
111: /**
112: * Searches all entries in the R-Tree whose HyperBoundingBoxes intersect with the given.
113: *
114: * @param box -
115: * given test HyperBoundingBox
116: * @return Object[] - Array with retrieved Objects
117: * @throws RTreeException
118: */
119: public Object[] intersects(HyperBoundingBox box)
120: throws RTreeException {
121: if (box.getDimension() != file.getDimension())
122: throw new IllegalArgumentException(
123: "HyperBoundingBox has wrong dimension "
124: + box.getDimension() + " != "
125: + file.getDimension());
126:
127: Vector<Object> v = new Vector<Object>(100);
128: // calls the real search method
129: try {
130: intersectsSearch(file.readNode(0), v, box);
131: } catch (PageFileException e) {
132: e.fillInStackTrace();
133: throw new RTreeException(
134: "PageFileException RTree.search() - readNode()");
135: }
136:
137: return v.toArray();
138: }
139:
140: /**
141: * Searches all entries in the R-Tree whose HyperBoundingBoxes contain the given.
142: *
143: * @param box -
144: * given test HyperBoundingBox
145: * @return Object[] - Array with retrieved Objects
146: * @throws RTreeException
147: */
148: public Object[] contains(HyperBoundingBox box)
149: throws RTreeException {
150: if (box.getDimension() != file.getDimension())
151: throw new IllegalArgumentException(
152: "HyperBoundingBox has wrong dimension");
153:
154: Vector<Object> v = new Vector<Object>(100);
155: try {
156: containsSearch(file.readNode(0), v, box);
157: } catch (PageFileException e) {
158: e.fillInStackTrace();
159: throw new RTreeException(
160: "PageFileException RTree.search() - readNode() ");
161: }
162:
163: return v.toArray();
164: }
165:
166: // private method for contains search
167: private void containsSearch(Node node1, Vector<Object> v,
168: HyperBoundingBox box) {
169: if (node1 instanceof LeafNode) {
170: LeafNode node = (LeafNode) node1;
171:
172: for (int i = 0; i < node.getUsedSpace(); i++) {
173: // if box is contained put into Vector
174: if (node.hyperBBs[i].contains(box))
175: v.addElement(node.getData(i));
176: }
177: return;
178: }
179: NoneLeafNode node = (NoneLeafNode) node1;
180:
181: // node is no Leafnode - so search all entries for overlapping
182: for (int i = 0; i < node.getUsedSpace(); i++) {
183: if (node.hyperBBs[i].contains(box))
184: containsSearch((Node) node.getData(i), v, box);
185: }
186: }
187:
188: // private method for intersects search
189: private void intersectsSearch(Node node1, Vector<Object> v,
190: HyperBoundingBox box) {
191: if (node1 instanceof LeafNode) {
192: LeafNode node = (LeafNode) node1;
193:
194: for (int i = 0; i < node.getUsedSpace(); i++) {
195: if (node.hyperBBs[i].overlaps(box))
196: v.addElement(node.getData(i));
197: }
198: return;
199: }
200:
201: NoneLeafNode node = (NoneLeafNode) node1;
202:
203: for (int i = 0; i < node.getUsedSpace(); i++) {
204: if (node.hyperBBs[i].overlaps(box))
205: intersectsSearch((Node) node.getData(i), v, box);
206: }
207: }
208:
209: /**
210: * Inserts the given Object associated with the given HyperBoundingBox object into the R-Tree.
211: *
212: * @param obj -
213: * Object to insert
214: * @param box -
215: * associated HyperBoundingBox
216: * @return boolean - true if successfull
217: * @throws RTreeException
218: */
219: public boolean insert(Object obj, HyperBoundingBox box)
220: throws RTreeException {
221:
222: try {
223: Node[] newNodes = new Node[] { null, null };
224: // Find position for new record
225: LeafNode node;
226: node = chooseLeaf(file.readNode(0), box);
227:
228: // Add record to leaf node
229:
230: if (node.getUsedSpace() < (file.getCapacity() - 1)) {
231: node.insertData(obj, box);
232: file.writeNode(node);
233: } else {
234: // invoke SplitNode
235: node.insertData(obj, box);
236: file.writeNode(node);
237: newNodes = splitNode(node);
238: }
239:
240: if (newNodes[0] != null) {
241: adjustTree(newNodes[0], newNodes[1]);
242: } else {
243: adjustTree(node, null);
244: }
245: } catch (PageFileException e) {
246: e.fillInStackTrace();
247: throw new RTreeException("PageFileException occured");
248: }
249:
250: return true;
251: }
252:
253: // algorithm to split a full node
254: private Node[] splitNode(Node node) throws PageFileException {
255:
256: // new node
257: Node newNode = null;
258: // temp help node
259: Node helpNode = null;
260:
261: // compute the start entries
262: int[] seeds = pickSeeds(node);
263:
264: if (node instanceof LeafNode) {
265: newNode = new LeafNode(this .file);
266: helpNode = new LeafNode(node.getPageNumber(), this .file);
267: } else {
268: newNode = new NoneLeafNode(-1, this .file);
269: helpNode = new NoneLeafNode(node.getPageNumber(), this .file);
270: }
271:
272: // write the new node to pagefile
273: file.writeNode(newNode);
274:
275: node.counter = 0;
276: node.unionMinBB = HyperBoundingBox.getNullHyperBoundingBox(file
277: .getDimension());
278:
279: // insert the start entries
280: helpNode.insertData(node.getData(seeds[0]), node
281: .getHyperBoundingBox(seeds[0]));
282: newNode.insertData(node.getData(seeds[1]), node
283: .getHyperBoundingBox(seeds[1]));
284:
285: // mark the inserted entries - first build a marker array
286: boolean[] marker = new boolean[file.getCapacity()];
287: for (int i = 0; i < file.getCapacity(); i++)
288: marker[i] = false;
289:
290: // mark them
291: marker[seeds[0]] = true;
292: marker[seeds[1]] = true;
293:
294: int doneCounter = file.getCapacity() - 2;
295:
296: // do until all entries are put into one of the groups or until
297: // one group has so less entries that the remainder must be given to that group
298: while (doneCounter > 0) {
299: int[] entry;
300: entry = pickNext(node, marker, helpNode, newNode);
301: doneCounter--;
302: if (entry[0] == 1)
303: helpNode.insertData(node.getData(entry[1]), node
304: .getHyperBoundingBox(entry[1]));
305: else
306: newNode.insertData(node.getData(entry[1]), node
307: .getHyperBoundingBox(entry[1]));
308:
309: if ((file.getMinimum() - helpNode.getUsedSpace()) == doneCounter) {
310:
311: for (int i = 0; i < file.getCapacity(); i++)
312: if (marker[i] == false)
313: helpNode.insertData(node.getData(i), node
314: .getHyperBoundingBox(i));
315: break;
316: }
317:
318: if ((file.getMinimum() - newNode.getUsedSpace()) == doneCounter) {
319:
320: for (int i = 0; i < file.getCapacity(); i++)
321: if (marker[i] == false)
322: newNode.insertData(node.getData(i), node
323: .getHyperBoundingBox(i));
324: break;
325: }
326: }
327:
328: // put the entries from the temp node to current node
329: for (int x = 0; x < helpNode.getUsedSpace(); x++)
330: node.insertData(helpNode.getData(x), helpNode
331: .getHyperBoundingBox(x));
332:
333: file.writeNode(node);
334: file.writeNode(newNode);
335:
336: return new Node[] { node, newNode };
337: }
338:
339: // picks the first to entries for the new nodes - returns the index of the entries
340: private int[] pickSeeds(Node node) {
341:
342: double max = 0.0;
343: int e1 = 0;
344: int e2 = 0;
345:
346: // walks through all combinations and takes
347: // the combination with the largest area enlargement
348: for (int i = 0; i < file.getCapacity(); i++)
349: for (int j = 0; j < file.getCapacity(); j++) {
350: if (i != j) {
351: double d = (node.getHyperBoundingBox(i))
352: .unionBoundingBox(
353: node.getHyperBoundingBox(j))
354: .getArea()
355: - node.getHyperBoundingBox(i).getArea()
356: - node.getHyperBoundingBox(j).getArea();
357: if (d > max) {
358: max = d;
359: e1 = i;
360: e2 = j;
361: }
362: }
363: }
364:
365: return new int[] { e1, e2 };
366: }
367:
368: // int[0] = group, int[1] = entry
369: private int[] pickNext(Node node, boolean[] marker, Node group1,
370: Node group2) {
371:
372: double d0 = 0;
373: double d1 = 0;
374: double diff = -1;
375: double max = -1;
376: int entry = 99;
377: int group = 99;
378:
379: for (int i = 0; i < file.getCapacity(); i++) {
380: if (marker[i] == false) {
381: d0 = group1.getUnionMinBB().unionBoundingBox(
382: node.getHyperBoundingBox(i)).getArea()
383: - group1.getUnionMinBB().getArea();
384:
385: d1 = group2.getUnionMinBB().unionBoundingBox(
386: node.getHyperBoundingBox(i)).getArea()
387: - group2.getUnionMinBB().getArea();
388: diff = Math.abs(d0 - d1);
389: if (diff > max) {
390: if (d0 < d1)
391: group = 1;
392: else
393: group = 2;
394: max = diff;
395: entry = i;
396: }
397: if (diff == max) {
398: if (d0 < d1)
399: group = 1;
400: else
401: group = 2;
402: max = diff;
403: entry = i;
404: }
405: }
406: }
407:
408: marker[entry] = true;
409: return new int[] { group, entry };
410: }
411:
412: // searches the leafnode with LeastEnlargment criterium for insert
413: private LeafNode chooseLeaf(Node node, HyperBoundingBox box) {
414:
415: if (node instanceof LeafNode) {
416: return (LeafNode) node;
417: }
418: NoneLeafNode node1 = (NoneLeafNode) node;
419: int least = node1.getLeastEnlargement(box);
420: return chooseLeaf((Node) node1.getData(least), box);
421:
422: }
423:
424: /**
425: * Queries the nearest neighbour to given search HyperPoint
426: *
427: * @param point -
428: * search point
429: * @return double[] - Place 0 = Distance, Place 1 = data number (must be cast to int)
430: * @throws RTreeException
431: */
432: public double[] nearestNeighbour(HyperPoint point)
433: throws RTreeException {
434: try {
435: return nearestNeighbour(file.readNode(0), point,
436: new double[] { Double.POSITIVE_INFINITY, -1.0 });
437: } catch (PageFileException e) {
438: e.fillInStackTrace();
439: throw new RTreeException(
440: "PageFileException - nearestNeighbour - readNode(0)");
441: }
442: }
443:
444: // private method for nearest neighbour query
445: private double[] nearestNeighbour(Node node, HyperPoint point,
446: double[] temp) {
447:
448: if (node instanceof LeafNode) {
449: // if mindist this < tempDist
450: for (int i = 0; i < node.getUsedSpace(); i++) {
451: double dist = node.getHyperBoundingBox(i)
452: .minDist(point);
453: if (dist < temp[0]) {
454: // then this = nearest Neighbour - update tempDist
455: temp[1] = ((LeafNode) node).data[i];
456: temp[0] = dist;
457: }
458: }
459:
460: } else {
461: // inner class ABL
462: class ABL implements Comparable {
463:
464: Node node;
465:
466: double minDist;
467:
468: /**
469: * @param node
470: * @param minDist
471: */
472: public ABL(Node node, double minDist) {
473: this .node = node;
474: this .minDist = minDist;
475: }
476:
477: public int compareTo(Object obj) {
478: ABL help = (ABL) obj;
479: if (this .minDist < help.minDist)
480: return -1;
481:
482: if (this .minDist > help.minDist)
483: return 1;
484: return 0;
485: }
486: }
487:
488: // generate ActiveBranchList of node
489: ABL[] abl = new ABL[node.getUsedSpace()];
490:
491: for (int i = 0; i < node.getUsedSpace(); i++) {
492: Node help = (Node) node.getData(i);
493: abl[i] = new ABL(help, help.getUnionMinBB().minDist(
494: point));
495: }
496:
497: // sort activebranchlist
498: Arrays.sort(abl);
499:
500: for (int i = 0; i < abl.length; i++) {
501: // apply heuristic 3
502: if (abl[i].minDist <= temp[0]) {
503: temp = nearestNeighbour(abl[i].node, point, temp);
504: }
505: }
506: }
507:
508: return temp;
509: }
510:
511: /**
512: * Closes the rtree.
513: *
514: * @throws RTreeException -
515: * if an error occures.
516: */
517: public void close() throws RTreeException {
518: try {
519: file.close();
520: } catch (PageFileException e) {
521: e.fillInStackTrace();
522: throw new RTreeException("PageFileException - close()");
523: }
524: }
525:
526: /**
527: * Deletes an entry from the RTree.
528: *
529: * @param box -
530: * HyperBoundingBox of the entry to deleted
531: * @param objID -
532: * Integer value of Object-ID to be deleted
533: * @return boolean - true if successfull
534: * @throws RTreeException
535: */
536: public boolean delete(HyperBoundingBox box, int objID)
537: throws RTreeException {
538:
539: Vector<Object> v = new Vector<Object>(100);
540: try {
541: findLeaf(file.readNode(0), box, objID, v);
542: } catch (PageFileException e) {
543: e.fillInStackTrace();
544: throw new RTreeException("PageFileException - delete()");
545: }
546:
547: if (v.size() < 1)
548: return false;
549:
550: if (v.size() == 1) {
551:
552: LeafNode leaf = (LeafNode) v.elementAt(0);
553:
554: for (int i = 0; i < leaf.getUsedSpace(); i++) {
555: if (leaf.getHyperBoundingBox(i).equals(box)
556: && leaf.data[i] == objID) {
557: leaf.deleteData(i);
558:
559: try {
560: file.writeNode(leaf);
561: } catch (PageFileException e) {
562: e.fillInStackTrace();
563: throw new RTreeException(
564: "PageFileException - delete()");
565: }
566: }
567: }
568:
569: Stack<Object> stack = new Stack<Object>();
570: try {
571: condenseTree(leaf, stack);
572: } catch (PageFileException e) {
573: e.fillInStackTrace();
574: throw new RTreeException(
575: "PageFileException - condenseTree()");
576: }
577:
578: while (!stack.empty()) {
579:
580: Node node = (Node) stack.pop();
581:
582: if (node instanceof LeafNode) {
583: for (int i = 0; i < node.getUsedSpace(); i++)
584: this .insert(((LeafNode) node).getData(i),
585: ((LeafNode) node)
586: .getHyperBoundingBox(i));
587: } else {
588: for (int i = 0; i < node.getUsedSpace(); i++)
589: stack.push(((NoneLeafNode) node).getData(i));
590: }
591:
592: try {
593: file.deleteNode(node.pageNumber);
594: } catch (PageFileException e) {
595: e.fillInStackTrace();
596: throw new RTreeException(
597: "PageFileException - delete() - deleteNode(0)");
598: }
599: }
600: }
601:
602: return true;
603: }
604:
605: /**
606: * Deletes all entries from the R-Tree with given HyperBoundingBox
607: *
608: * @param box -
609: * HyperBoundingBox
610: * @return boolean - true if successfull
611: * @throws RTreeException
612: */
613: public boolean delete(HyperBoundingBox box) throws RTreeException {
614:
615: Vector<Object> v = new Vector<Object>(100);
616: try {
617: findLeaf(file.readNode(0), box, v);
618: } catch (PageFileException e) {
619: e.fillInStackTrace();
620: throw new RTreeException("PageFileException - delete()");
621: }
622:
623: if (v.size() < 1)
624: return false;
625:
626: LeafNode leaf;
627:
628: for (Enumeration en = v.elements(); en.hasMoreElements();) {
629:
630: leaf = (LeafNode) en.nextElement();
631:
632: for (int i = 0; i < leaf.getUsedSpace(); i++) {
633: if (leaf.getHyperBoundingBox(i).equals(box)) {
634: leaf.deleteData(i);
635:
636: try {
637: file.writeNode(leaf);
638: } catch (PageFileException e) {
639: e.fillInStackTrace();
640: throw new RTreeException(
641: "PageFileException - delete()");
642: }
643: }
644: }
645:
646: Stack<Object> stack = new Stack<Object>();
647: try {
648: condenseTree(leaf, stack);
649: } catch (PageFileException e) {
650: e.fillInStackTrace();
651: throw new RTreeException(
652: "PageFileException - condenseTree()");
653: }
654:
655: while (!stack.empty()) {
656:
657: Node node = (Node) stack.pop();
658:
659: if (node instanceof LeafNode) {
660: for (int i = 0; i < node.getUsedSpace(); i++)
661: this .insert(((LeafNode) node).getData(i),
662: ((LeafNode) node)
663: .getHyperBoundingBox(i));
664: } else {
665: for (int i = 0; i < node.getUsedSpace(); i++)
666: stack.push(((NoneLeafNode) node).getData(i));
667: }
668:
669: try {
670: file.deleteNode(node.pageNumber);
671: } catch (PageFileException e) {
672: e.fillInStackTrace();
673: throw new RTreeException(
674: "PageFileException - delete() - deleteNode(0)");
675: }
676: }
677: }
678:
679: return true;
680: }
681:
682: /**
683: * Retrieves all entries with the given HyperBoundingBox.
684: *
685: * @param box -
686: * HyperBoundingBox
687: * @return Object[] - array with retrieved objects
688: * @throws RTreeException
689: */
690: public Object[] find(HyperBoundingBox box) throws RTreeException {
691: if (box.getDimension() != file.getDimension())
692: throw new IllegalArgumentException(
693: "HyperBoundingBox has wrong dimension");
694:
695: Vector<Object> v = new Vector<Object>(100);
696: // ruft die eigentliche suche auf
697: try {
698: findSearch(file.readNode(0), v, box);
699: } catch (PageFileException e) {
700: e.fillInStackTrace();
701: throw new RTreeException(
702: "PageFileException RTree.search() - readNode()");
703: }
704:
705: return v.toArray();
706: }
707:
708: // F�hrt die eigentliche Suche durch - Aufruf von search(HyperBoundingBox box)
709: private void findSearch(Node node1, Vector<Object> v,
710: HyperBoundingBox box) {
711: if (node1 instanceof LeafNode) {
712: LeafNode node = (LeafNode) node1;
713:
714: for (int i = 0; i < node.getUsedSpace(); i++) {
715: // wenn eintraege enthalten diese in Vechtor aufnehmen;
716: if (node.hyperBBs[i].equals(box))
717: v.addElement(node.getData(i));
718: }
719: return;
720: }
721:
722: NoneLeafNode node = (NoneLeafNode) node1;
723:
724: // node ist kein LeafNode
725: // alle eintrraege auf �berlappung durchsuchen
726: for (int i = 0; i < node.getUsedSpace(); i++) {
727: // wenn enthalten rekursiv search mit diesem node aufrufen
728: if (node.hyperBBs[i].contains(box)) {
729: findSearch((Node) node.getData(i), v, box);
730: }
731: }
732:
733: }
734:
735: // Retrieves all leaf nodes regardless of the id
736: private void findLeaf(Node node, HyperBoundingBox box,
737: Vector<Object> v) {
738: if (node instanceof LeafNode) {
739: for (int i = 0; i < node.getUsedSpace(); i++) {
740: if (node.getHyperBoundingBox(i).equals(box))
741: v.addElement(node);
742: }
743: } else {
744: for (int i = 0; i < node.getUsedSpace(); i++) {
745: if (node.getHyperBoundingBox(i).overlaps(box))
746: findLeaf((Node) node.getData(i), box, v);
747: }
748: }
749: }
750:
751: // Retrieves all leaf nodes with correct box and id
752: private void findLeaf(Node node, HyperBoundingBox box, int objID,
753: Vector<Object> v) {
754: if (node instanceof LeafNode) {
755: for (int i = 0; i < node.getUsedSpace(); i++) {
756: if (((LeafNode) node).data[i] == objID
757: && node.getHyperBoundingBox(i).equals(box))
758: v.addElement(node);
759: }
760: } else {
761: for (int i = 0; i < node.getUsedSpace(); i++) {
762: if (node.getHyperBoundingBox(i).overlaps(box))
763: findLeaf((Node) node.getData(i), box, objID, v);
764: }
765: }
766: }
767:
768: // condenses the tree after remove of some entries
769: private void condenseTree(Node n, Stack<Object> stack)
770: throws PageFileException {
771: if (!n.isRoot()) {
772:
773: Node p = n.getParent();
774: if (n.getUsedSpace() < file.getMinimum()) {
775: p.deleteData(n.place);
776: stack.push(n);
777: } else {
778: p.hyperBBs[n.place] = n.getUnionMinBB();
779: p.updateNodeBoundingBox();
780: }
781:
782: file.writeNode(p);
783:
784: condenseTree(p, stack);
785: } else {
786: if (n.getUsedSpace() == 1 && (n instanceof NoneLeafNode)) {
787:
788: Node kind = (Node) n.getData(0);
789: Node newRoot = null;
790: if (kind instanceof LeafNode) {
791: newRoot = new LeafNode(0, this .file);
792: for (int i = 0; i < kind.getUsedSpace(); i++)
793: newRoot.insertData(kind.getData(i), kind
794: .getHyperBoundingBox(i));
795: } else {
796: newRoot = new NoneLeafNode(0, this .file);
797: for (int i = 0; i < kind.getUsedSpace(); i++)
798: newRoot.insertData(kind.getData(i), kind
799: .getHyperBoundingBox(i));
800: }
801:
802: file.writeNode(newRoot);
803: }
804: }
805: }
806:
807: // adjustes the Tree with the correct bounding boxes and
808: // propagates needed splits upwards
809: private void adjustTree(Node n1, Node n2) throws PageFileException {
810: // if n2 = null - only adjust boundingboxes
811: // if n2 != null a split occured - maybe propagate split
812:
813: if (n1.isRoot()) {
814:
815: // if n2 != null we need a new Root node - Root Split
816: if ((n2 != null) && n1.isRoot()) {
817:
818: // Node must be written from page number 0 (root number) to other
819: n1.setPageNumber(-1);
820: int pagenumber;
821:
822: pagenumber = file.writeNode(n1);
823:
824: for (int x = 0; x < n1.getUsedSpace(); x++) {
825: Object obj = n1.getData(x);
826:
827: if (obj instanceof Node) {
828: Node node = (Node) obj;
829: node.parentNode = pagenumber;
830: file.writeNode(node);
831: }
832:
833: obj = null;
834: }
835:
836: NoneLeafNode newRoot = new NoneLeafNode(0, this .file);
837:
838: newRoot.insertData(n1, n1.getUnionMinBB());
839: newRoot.insertData(n2, n2.getUnionMinBB());
840: newRoot.parentNode = 0;
841:
842: file.writeNode(newRoot);
843: }
844:
845: return;
846: }
847:
848: // adjust the bounding boxes in the parents for Node n1
849: NoneLeafNode p = (NoneLeafNode) n1.getParent();
850: p.hyperBBs[n1.place] = n1.getUnionMinBB();
851: p.unionMinBB = (p.getUnionMinBB()).unionBoundingBox(n1
852: .getUnionMinBB());
853:
854: file.writeNode(p);
855:
856: // propagate adjustment upwards
857: if (n2 == null) {
858: adjustTree(p, null);
859: } else {
860: // as there occured a split - the second node has to be inserted
861: Node[] newNodes = new Node[] { null, null };
862: if (p.getUsedSpace() < (file.getCapacity() - 1)) {
863: // new split must happen
864: p.insertData(n2, n2.getUnionMinBB());
865: file.writeNode(p);
866: newNodes[0] = p;
867: } else {
868: p.insertData(n2, n2.getUnionMinBB());
869: file.writeNode(p);
870: newNodes = splitNode(p);
871: }
872:
873: adjustTree(newNodes[0], newNodes[1]);
874: }
875: }
876: }
|