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