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    }