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