    001    //$HeadURL: https://svn.wald.intevation.org/svn/deegree/base/branches/2.4_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    }