basic-r-tree.h

Go to the documentation of this file.

#ifndef _H_BASIC_R_TREE
#define _H_BASIC_R_TREE

#include "r-tree.h"

//template < typename bb_type > Pending...
class Basic_R_tree : public R_tree< Basic_R_tree > {

  protected:

        typedef vector< Basic_R_tree* >::const_iterator childIterator;
        
        typedef vector< BB_container* >::const_iterator elemIterator;
        
        Basic_R_tree *chooseLeaf( Basic_R_tree *v, const BB_type bb ) const;

        Basic_R_tree *handleOverflow( Basic_R_tree *node, BB_container *element );

        void linearSplitElements( vector< BB_container* > oldItems, BB_container *newItem, vector< BB_container* > *set_one, vector< BB_container* > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension );

        void linearSplitNodes( vector< Basic_R_tree * > oldItems, Basic_R_tree *newItem, vector< Basic_R_tree* > *set_one, vector< Basic_R_tree* > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension );

        void quadraticSplitElements( vector< BB_container* > oldItems, BB_container *newItem, vector< BB_container* > *set_one, vector< BB_container* > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension );

        void quadraticSplitNodes( vector< Basic_R_tree* > oldItems, Basic_R_tree *newItem, vector< Basic_R_tree* > *set_one, vector< Basic_R_tree* > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension );

        Basic_R_tree *insert( Basic_R_tree *node );

        Basic_R_tree *buildNode( vector< BB_container* > input, BB_type *newMbr ) const;
        
        Basic_R_tree *buildNode( vector< Basic_R_tree* > input, BB_type *newMbr ) const;

        void reinsert( vector< Basic_R_tree* > s );
        
        void reinsert( Basic_R_tree* walk, Basic_R_tree* at );

        Basic_R_tree *handleOverflow( Basic_R_tree *node );

        Basic_R_tree *makeNewRoot( Basic_R_tree *child );

        void setChildren( vector< Basic_R_tree* > newChildren, BB_type *newMbr );
        
        /*
         *  Sets a collection of bb_containers to be the elements of this node.
         *
         *  @param newElements The collection of new elements.
         *  @param newMbr The minimum bounding rectangle of newElements
         *
         */
        //void setElements( vector< BB_container* > newElements, BB_type *newMbr );

        void removeChild( Basic_R_tree *toRemove );

        Basic_R_tree *remove( Basic_R_tree *node, BB_container *element );


  public:

        Basic_R_tree() : R_tree< Basic_R_tree >() {}
        
        Basic_R_tree( R_tree_props *props ) : R_tree< Basic_R_tree >( props ) {}
                
        virtual Basic_R_tree *remove( BB_container *element );

        virtual Basic_R_tree *getRoot();

        virtual const Basic_R_tree *getRoot() const;

        virtual Basic_R_tree *insert( BB_container *element );

        virtual Basic_R_tree *search( BB_container *element );

};


Basic_R_tree *Basic_R_tree::remove( Basic_R_tree *node, BB_container *element ) {
#ifdef _DEBUG
        cout << "Entering remove(node, element)" << endl; fflush( stdout );
#endif
        vector< BB_container* >::iterator it = node->elements.begin();
        vector< Basic_R_tree* > s;
                
        //first erase the element
        for ( ; it!=node->elements.end(); it++ ) {
                if ( (*it)->getID() == element->getID() ) {
                        node->elements.erase( it );
                }
        }
                
        //check for underflows
        Basic_R_tree *walk = node;
        while ( !( walk->isRoot() ) ) {
                Basic_R_tree *par = walk->parent;
        
                if ( walk->isLeaf() ) {
                        if ( walk->elements.size() < properties->minimum ) {
                                //underflow detected, store node
                                s.push_back( walk );
                                //remove node
                                par->removeChild( walk );
                                //update MBR
                                par->updateMBRNode();
                        }
                } else {
                        if ( walk->children.size() < properties->minimum ) {
                                s.push_back( walk );
                                par->removeChild( walk );
                                par->updateMBRNode();
                        }
                }
                        
                //check parent
                walk = par;
        }
                
        //re-insert all at root
        walk->reinsert( s );

#ifdef _DEBUG
        cout << "Almost exitting remove(node, element) -- rootcheck" << endl; fflush( stdout );
#endif
        //check for degenerate root
        if ( walk->children.size() == 1 ) {

                Basic_R_tree *temp = walk->children[0];
                walk->elements = temp->elements;
                walk->children = temp->children;
                walk->mbr = temp->mbr;
                walk->properties = temp->properties; //actually kind of useless
                delete temp;
        
#ifdef _DEBUG
                cout << "Exitting remove(node, element) -- root fixed" << endl; fflush( stdout );
#endif

                return walk;
        }
#ifdef _DEBUG
        cout << "Exitting remove(node, element) -- no degenerate root" << endl; fflush( stdout );
#endif

        return walk;
}

void Basic_R_tree::removeChild( Basic_R_tree *toRemove ) {

#ifdef _DEBUG
        cout << "Entering removeChild" << endl; fflush( stdout );
#endif

        vector< Basic_R_tree* >::iterator it = this->children.begin();
        for ( ; it!=this->children.end(); it++ ) {
                if ( ( *it ) == toRemove )
                        this->children.erase( it );
        }
        
#ifdef _DEBUG
        cout << "Exitting removeChild" << endl; fflush( stdout );
#endif

}

void Basic_R_tree::setChildren( vector< Basic_R_tree* > newChildren, BB_type *newMbr ) {

        if ( newChildren.size() == 1 ) {
                if ( newChildren[0]->isLeaf() )
                        this->setElements( newChildren[0]->elements, &( newChildren[0]->mbr ) );
                else
                        this->setChildren( newChildren[0]->children, &( newChildren[0]->mbr ) );
                newChildren[0]->children.clear();
                newChildren[0]->elements.clear();
                delete newChildren[0];
                return;
        }

#ifdef _DEBUG
        cout << "Entering setChildren; replacing with " << newChildren.size() << " children." << endl; fflush( stdout );
        cout << "\tClearing old children..." << endl; fflush( stdout );
#endif

        this->children.clear();
                
#ifdef _DEBUG
        cout << "\tInitialising iterator..." << endl; fflush( stdout );
#endif

        childIterator it = newChildren.begin();

#ifdef _DEBUG
        cout << "\tLooping..." << endl; fflush( stdout );
#endif

        for( ; it!=newChildren.end(); it++ ) {

#ifdef _DEBUG
                cout << "\tSetting parent..." << endl; fflush( stdout );
#endif

                (*it)->parent = this;

#ifdef _DEBUG
                cout << "\t" << this->children.size() << " Children, pushing back another child..." << endl; fflush( stdout );
                cout << "\tChild mbr: " << (*(*it)).mbr << endl; fflush( stdout );
                cout << "\tChild adress: " << (*it) << endl; fflush( stdout );
#endif

                this->children.push_back( (*it) );
                        
#ifdef _DEBUG
                cout << "\tPush back successful" << endl; fflush( stdout );
#endif

        }

#ifdef _DEBUG
        cout << "\tClearing elements..." << endl; fflush( stdout );
#endif
                
        this->elements.clear();
        
#ifdef _GREATER_CHECK
 #ifdef _DEBUG
        cout << "\tLocal height estimate: " << getLocalHeightEstimate() << endl;
 #endif
#endif

#ifdef _DEBUG
        cout << "\tSetting MBR..." << endl; fflush( stdout );
#endif

        if ( newMbr != 0 )
                mbr = BB_type( newMbr );

#ifdef _DEBUG
        cout << "Exitting setChildren" << endl; fflush( stdout );
#endif

}

/*void Basic_R_tree::setElements( vector< BB_container* > newElements, BB_type *newMbr ) {

#ifdef _DEBUG
        cout << "Entering setElements" << endl; fflush( stdout );
#endif

        this->elements.clear();
        vector< BB_container* >::iterator it = newElements.begin();
        for( ; it!=newElements.end(); it++ ) {
#ifdef _DEBUG
                cout << "Adding element " << endl << *(*it) << endl; fflush( stdout );
#endif
                this->elements.push_back( *it );
        }
        
        this->children.clear();
        
        mbr = BB_type( newMbr );

#ifdef _GREATER_CHECK
        checkInvariants();
#endif
        
#ifdef _DEBUG
        cout << "Exitting setElements" << endl; fflush( stdout );
#endif

}*/

Basic_R_tree *Basic_R_tree::makeNewRoot( Basic_R_tree *child ) {
        
#ifdef _DEBUG
        cout << "Entering makeNewRoot" << endl; fflush( stdout );
#endif

#ifndef _HP
        if (!this->isRoot()) {
                cerr << "makeNewRoot called on non-root node!" << endl;
                exit(1);
        }
#endif

        Basic_R_tree *newRoot = new Basic_R_tree( properties );

#ifdef _GREATER_CHECK
 #ifdef _DEBUG
        cout << "\tLocal children depth: " << getLocalHeightEstimate() << endl;
        cout << "\tReal depth: " << getHeightEstimate() << endl;
 #endif
#endif

        newRoot->children.push_back( this );

#ifdef _GREATER_CHECK
 #ifdef _DEBUG
        cout << "\tNew child children depth: " << child->getLocalHeightEstimate() << endl;
        cout << "\tReal depth: " << child->getHeightEstimate() << endl;
 #endif
#endif

        newRoot->children.push_back( child );
        this->parent = newRoot;
        child->parent = newRoot;
        newRoot->updateMBRLocal();

#ifdef _GREATER_CHECK
 #ifdef _DEBUG
        cout << "\tRoot check: " << endl; fflush( stdout );
 #endif
        newRoot->checkInvariants();
#endif

#ifdef _DEBUG
        cout << "Exitting makeNewRoot" << endl; fflush( stdout );
#endif

        return newRoot;
}
        
void Basic_R_tree::reinsert( vector< Basic_R_tree* > s ) {

#ifdef _DEBUG
        cout << "Entering re-insert" << endl; fflush( stdout );
#endif

        childIterator it = s.begin();
        for ( ; it!=s.end(); it++ ) {
                
                Basic_R_tree *node = *it;
                if ( node->isLeaf() ) {
                        vector< BB_container* >::iterator itp = node->elements.begin();
                        for( ; itp != node->elements.end(); itp++ )
                                insert( *itp );
                } else {
                        //non leaf. take the naive approach (for now), and just reinsert
                        //all stored elements instead of adding the internal node at some
                        //position at the appropiate height, as in [GUT84], page 51.
                        
                        Basic_R_tree* walk = (*it);
                        reinsert( walk, this );
                        
                        /*Basic_R_tree::Iterator itr = node->begin();
                        for ( ; itr != node->end(); ++itr )
                                insert( *itr );*/
                }
                        
        }
        
#ifdef _DEBUG
        cout << "Exitting re-insert" << endl; fflush( stdout );
#endif

}

void Basic_R_tree::reinsert( Basic_R_tree* walk, Basic_R_tree* at ) {
        if ( walk->isLeaf() ) {
                elemIterator it = this->elements.begin();
                for( ; it!=this->elements.end(); it++ )
                        at->insert( *it );
        } else {
                childIterator it = this->children.begin();
                for( ; it!=this->children.end(); it++ )
                        reinsert( *it, at );
        }
}

Basic_R_tree *Basic_R_tree::buildNode( vector< BB_container* > input, BB_type *newMbr ) const {
        
#ifdef _DEBUG
        cout << "Entering buildNode, the polytope version" << endl; fflush( stdout );
#endif

        Basic_R_tree *ret = new Basic_R_tree( properties );
        
        vector< BB_container* >::iterator it = input.begin();
        for( ; it!=input.end(); it++ ) {
                ret->elements.push_back( *it );
        }
        
        ret->mbr = BB_type( newMbr );
                
#ifdef _DEBUG
        cout << "Exitting buildNode, the polytope version" << endl; fflush( stdout );
#endif

        return ret;
}

Basic_R_tree *Basic_R_tree::buildNode( vector< Basic_R_tree* > input, BB_type *newMbr ) const {
        
#ifdef _DEBUG
        cout << "Entering buildNode, the R-tree node version" << endl; fflush( stdout );
#endif

        Basic_R_tree *ret = new Basic_R_tree( properties );
                
        //ret.children.add( input.begin(), input.end() );
        for ( unsigned int i=0; i<input.size(); i++ ) {
                ret->children.push_back(  input[ i ] );
                ret->children[ i ]->parent = ret;
        }
        
        if ( newMbr!= 0 )
                ret->mbr = BB_type( newMbr );

#ifdef _DEBUG
        cout << "Exitting buildNode, the R-tree node version" << endl; fflush( stdout );
#endif

        return ret;
}

Basic_R_tree *Basic_R_tree::handleOverflow( Basic_R_tree *node ) {
#ifdef _DEBUG
        cout << "Entering handleOverflow, the Basic_R_tree node version" << endl; fflush( stdout );
#endif

        //set splits
        vector< Basic_R_tree* > set_one;
        vector< Basic_R_tree* > set_two;
        BB_type *mbr_one = new BB_type();
        BB_type *mbr_two = new BB_type();

        //build item nodes
        vector< Basic_R_tree* > oldItems;

#ifdef _DEBUG
        cout << "\tCurrent node at: " << this << ", children are at: ";
#endif

        for( unsigned int i=0; i<this->children.size(); i++ ) {

#ifdef _DEBUG
                cout << this->children[i] << " ";
#endif

                oldItems.push_back( this->children[ i ] );
        }

#ifdef _DEBUG
        cout << endl;
#endif
        
        this->children.clear();
                
        //actual splitting
        switch( SPLIT_STRATEGY ) {
                case LINEAR_SPLIT:
                        linearSplitNodes( oldItems, node, &set_one, &set_two, mbr_one, mbr_two, node->mbr.getDimension() ); 
                        break;
                case QUADRATIC_SPLIT:
                        quadraticSplitNodes( oldItems, node, &set_one, &set_two, mbr_one, mbr_two, node->mbr.getDimension() ); 
                        break;
                case EXPONENTIAL_SPLIT:
                        cerr << "x^Split not yet implemented! " << endl; exit(1);
                        break;
                default:
                        cerr << "No valid split strategy selected! (r-tree.h)" << endl;
                        exit(1);
        }
                
        //node building
        Basic_R_tree *child_one = buildNode( set_one, mbr_one ); //note this takes into account mbr

#ifdef _GREATER_CHECK
 #ifdef _DEBUG
        cout << "child_one local depth: " << child_one->getLocalHeightEstimate() << endl;
 #endif
#endif

        setChildren( set_two, mbr_two ); //note this takes into account mbr

        //delete temporary mbrs
        delete mbr_one;
        delete mbr_two;

        //insert the new node
        if ( this->isRoot() ) {

#ifdef _DEBUG
        cout << "Exitting handleOverflow, the Basic_R_tree node version, calling makeNewRoot" << endl; fflush( stdout );
#endif

                return makeNewRoot( child_one ); //takes into account MBR

        } else {

#ifdef _DEBUG
        cout << "Exitting handleOverflow, the Basic_R_tree node version, calling parent->insert" << endl; fflush( stdout );
#endif

                return this->parent->insert( child_one ); //takes into account MBR
        }
}

Basic_R_tree *Basic_R_tree::insert( Basic_R_tree *node ) {

#ifdef _DEBUG
        cout << "Entering insert, the R-tree node version" << endl; fflush( stdout );
        cout << "Inserting " << node << " at " << this << endl;
#endif

#ifndef _HP
        if ( this->isLeaf() ) {
                cerr << "\tTrying to add internal node to a leaf node!" << endl;
                exit(1);
        }
#endif
                
        if ( full() ) {

#ifdef _DEBUG
        cout << "Exitting insert, the R-tree node version; calling handleOverflow( node )" << endl; fflush( stdout );
#endif

                return handleOverflow( node ); //should also handle MBR updates

        } else {

                this->children.push_back( node );
                node->parent = this;

#ifdef _DEBUG
                cout << "Exitting insert, the R-tree node version" << endl; fflush( stdout );
#endif
#ifdef _GREATER_CHECK
                updateMBR();
 #ifdef _DEBUG
                cout << "\tChecking current subtree" << endl; fflush( stdout );
 #endif
                checkEntireTreeRecursive();

                if ( this->isRoot() ) {
 #ifdef _DEBUG
                        cout << "\tNOT checking parent tree recursively; we are at root." << endl; fflush( stdout );
 #endif
                } else {
 #ifdef _DEBUG
                        cout << "\tOK, checking parents' " << this->parent << " subtree" << endl; fflush( stdout );
 #endif
                        this->parent->checkEntireTreeRecursive();
                }
 #ifdef _DEBUG
                cout << "\tOK, checking entire tree" << endl; fflush( stdout );
 #endif
                checkEntireTree();
 #ifdef _DEBUG
                cout << "Even exitted with entire tree check" << endl; fflush( stdout );
 #endif
#else
                updateMBR(); //propagates upward
#endif
                return getRoot();
        }
}

void Basic_R_tree::quadraticSplitElements( vector< BB_container* > oldItems, BB_container *newItem, vector< BB_container* > *set_one, vector< BB_container* > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension ) {
        
        //add new item to the back of the old ones
        oldItems.push_back( newItem );

#ifndef _HP
        if( oldItems.size() < 2 ) {
                cerr << "Too few elements passed to quadraticSplit!" << endl;
                exit(1);
        }
#endif
        
        //find largest dead space combo
        unsigned int i = 0;
        unsigned int j = 1;
        unsigned int a = i;
        unsigned int b = j;
        double dead = deadSpace( *oldItems[i], *oldItems[j] );
        
        for ( ; i<oldItems.size(); i++ ) {
                for ( ; j<oldItems.size(); j++ ) {
                        if ( i!=j ) {
                                double tempdead = deadSpace( *oldItems[i], *oldItems[j] );
                                if ( dead < tempdead ) {
                                        dead = tempdead;
                                        a = i;
                                        b = j;
                                }
                        }
                }
        }
        
        //add those two to two different sets and erase them from oldItems
        BB_type *set_one_mbr = new BB_type( oldItems[a] );
        BB_type *set_two_mbr = new BB_type( oldItems[b] );
        set_one->push_back( oldItems[a] );
        set_two->push_back( oldItems[b] );
        
        if ( b > a ) {
                oldItems.erase( oldItems.begin() + b );
                oldItems.erase( oldItems.begin() + a );
        } else {
                oldItems.erase( oldItems.begin() + a );
                oldItems.erase( oldItems.begin() + b );
        }

        //remember the volume used in set one
        double volumeInOne = Current_Metric::Volume( *set_one_mbr );
        double volumeInTwo = Current_Metric::Volume( *set_two_mbr );
        
        //add the remaining objects
        while ( !oldItems.empty() ) {
        
                //check for minimum constraint
                if ( properties->minimum - set_one->size() == oldItems.size() ) {
                        //all remaining entries must be added to set one, otherwise the min
                        //requirement will not be met.
                        for ( unsigned int i=0 ; i<oldItems.size(); i++ ) {
                                set_one->push_back( oldItems[ i ] );
                                (*set_one_mbr).unite( oldItems[ i ] );
                                //*set_one_mbr = set_one_mbr->unite( *oldItems[ i ] );
                                
#ifdef _DEBUG_LINEAR_SPLIT
                                cout << "\t Adding to set one (forced): " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        }
                        break;
                } else if ( oldItems.size() == properties->minimum - set_two->size() ) {
                        //likewise for set two
                        for ( unsigned int i=0 ; i<oldItems.size(); i++ ) {
                                set_two->push_back( oldItems[ i ] );
                                (*set_two_mbr).unite( oldItems[ i ] ); 
                                //*set_two_mbr = set_two_mbr->unite( *oldItems[ i ] );

#ifdef _DEBUG_LINEAR_SPLIT
                                cout << "\t Adding to set two (forced): " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        }
                        break;                  
                }
        
        
                for ( unsigned int k=0; k<oldItems.size(); k++ ) {
                
                        //calculate dead spaces
                        double curVol = Current_Metric::Volume( *( oldItems[ k ] ) );
                        double da = Current_Metric::Volume( set_one_mbr->unionWith( *(oldItems[ k ]) ) ) - volumeInOne - curVol;
                        double db = Current_Metric::Volume( set_two_mbr->unionWith( *(oldItems[ k ]) ) ) - volumeInTwo - curVol;
                        double p = -1;
                
                        if ( db < da ) {
                                double diff = da - db;
                                if ( diff > p ) {
                                        p = diff;
                                        a = k;
                                        b = k;
                                }
                        } else {
                                double diff = db - da;
                                if ( diff > p ) {
                                        p = diff;
                                        a = k;
                                        b = k+1;
                                }
                        }
                }
                
                //now we have at a the elements which would cause the largest MBR difference
                //add this element to the appropiate set
                if ( a == b ) {
                        //only the case if db < da for element a
                        //so add a to set two
                        volumeInTwo += Current_Metric::Volume( *oldItems[ a ] );
                        set_two->push_back( oldItems[a] );
                        (*set_two_mbr).unite( oldItems[ a ] );
                        //*set_two_mbr = set_two_mbr->unite( *oldItems[a] );
                } else {
                        //add to set one
                        volumeInOne += Current_Metric::Volume( *oldItems[ a ] );
                        set_one->push_back( oldItems[ a ] );
                        (*set_one_mbr).unite( oldItems[ a ] );
                        //*set_one_mbr = set_one_mbr->unite( *oldItems[a] );
                }

                //erase item
                oldItems.erase( oldItems.begin() + a );
        }
        
        mbr_one->become( set_one_mbr ); delete set_one_mbr;
        mbr_two->become( set_two_mbr ); delete set_two_mbr;
        
}

void Basic_R_tree::quadraticSplitNodes( vector< Basic_R_tree* > oldItems, Basic_R_tree *newItem, vector< Basic_R_tree* > *set_one, vector< Basic_R_tree* > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension ) {
        
        //add new item to the back of the old ones
        oldItems.push_back( newItem );

#ifndef _HP
        if( oldItems.size() < 2 ) {
                cerr << "Too few elements passed to quadraticSplit!" << endl;
                exit(1);
        }
#endif
        
        //find largest dead space combo
        unsigned int i = 0;
        unsigned int j = 1;
        unsigned int a = i;
        unsigned int b = j;
        double dead = deadSpace( oldItems[i]->mbr, oldItems[j]->mbr );
        
        for ( ; i<oldItems.size(); i++ ) {
                for ( ; j<oldItems.size(); j++ ) {
                        if ( i!=j ) {
                                double tempdead = deadSpace( oldItems[i]->mbr, oldItems[j]->mbr );
                                if ( dead < tempdead ) {
                                        dead = tempdead;
                                        a = i;
                                        b = j;
                                }
                        }
                }
        }
        
        //add those two to two different sets and erase them from oldItems
        BB_type *set_one_mbr = new BB_type( &( oldItems[a]->mbr ) );
        BB_type *set_two_mbr = new BB_type( &( oldItems[b]->mbr ) );
        set_one->push_back( oldItems[a] );
        set_two->push_back( oldItems[b] );
        
        if ( b > a ) {
                oldItems.erase( oldItems.begin() + b );
                oldItems.erase( oldItems.begin() + a );
        } else {
                oldItems.erase( oldItems.begin() + a );
                oldItems.erase( oldItems.begin() + b );
        }

        //remember the volume used in set one
        double volumeInOne = Current_Metric::Volume( *set_one_mbr );
        double volumeInTwo = Current_Metric::Volume( *set_two_mbr );
        
        //add the remaining objects
        while ( !oldItems.empty() ) {
        
                //check for minimum constraint
                if ( properties->minimum - set_one->size() == oldItems.size() ) {
                        //all remaining entries must be added to set one, otherwise the min
                        //requirement will not be met.
                        for ( unsigned int i=0 ; i<oldItems.size(); i++ ) {
                                set_one->push_back( oldItems[ i ] );
                                (*set_one_mbr).unite( &( oldItems[ i ]->mbr ) );
                                //*set_one_mbr = set_one_mbr->unite( oldItems[ i ]->mbr );
                                
#ifdef _DEBUG_LINEAR_SPLIT
                                cout << "\t Adding to set one (forced): " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        }
                        break;
                } else if ( oldItems.size() == properties->minimum - set_two->size() ) {
                        //likewise for set two
                        for ( unsigned int i=0 ; i<oldItems.size(); i++ ) {
                                set_two->push_back( oldItems[ i ] );
                                (*set_two_mbr).unite( &( oldItems[ i ]->mbr ) );
                                //*set_two_mbr = set_two_mbr->unite( oldItems[ i ]->mbr );

#ifdef _DEBUG_LINEAR_SPLIT
                                cout << "\t Adding to set two (forced): " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        }
                        break;
                }
        
        
                for ( unsigned int k=0; k<oldItems.size(); k++ ) {
        
                        //calculate dead spaces
                        double curVol = Current_Metric::Volume( oldItems[ k ]->mbr );
                        double da = Current_Metric::Volume( set_one_mbr->unionWith( oldItems[ k ]->mbr ) ) - volumeInOne - curVol;
                        double db = Current_Metric::Volume( set_two_mbr->unionWith( oldItems[ k ]->mbr ) ) - volumeInTwo - curVol;
                        double p = -1;
                
                        if ( db < da ) {
                                double diff = da - db;
                                if ( diff > p ) {
                                        p = diff;
                                        a = k;
                                        b = k;
                                }
                        } else {
                                double diff = db - da;
                                if ( diff > p ) {
                                        p = diff;
                                        a = k;
                                        b = k+1;
                                }
                        }
                }

                //now we have at a the elements which would cause the largest MBR difference
                //add this element to the appropiate set
                if ( a == b ) {
                        //only the case if db < da for element a
                        //so add a to set two
                        volumeInTwo += Current_Metric::Volume( oldItems[ a ]->mbr );
                        set_two->push_back( oldItems[ a ] );
                        (*set_two_mbr).unite( &( oldItems[ a ]->mbr ) );
                        //*set_two_mbr = set_two_mbr->unite( oldItems[ a ]->mbr );
                } else {
                        //add to set one
                        volumeInOne += Current_Metric::Volume( oldItems[ a ]->mbr );
                        set_one->push_back( oldItems[ a ] );
                        (*set_one_mbr).unite( &( oldItems[ a ]->mbr ) );
                        //*set_one_mbr = set_one_mbr->unite( oldItems[ a ]->mbr );
                }
        
                //erase item
                oldItems.erase( oldItems.begin() + a );
                                
        }
        
        mbr_one->become( set_one_mbr ); delete set_one_mbr;
        mbr_two->become( set_two_mbr ); delete set_two_mbr;
        
}

void Basic_R_tree::linearSplitNodes( vector< Basic_R_tree* > oldItems, Basic_R_tree *newItem, vector< Basic_R_tree* > *set_one, vector< Basic_R_tree* > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension ) {
        
#ifdef _DEBUG
        cout << "Entering linearSplitNodes" << endl; fflush( stdout );
#endif

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t #oldItems = " << oldItems.size() << endl; fflush( stdout );
#endif
                
        vector<double> lowerBounds; lowerBounds.resize( dimension );
        vector<double> upperBounds; upperBounds.resize( dimension );
        vector<int> lowerElements; lowerElements.resize( dimension );
        vector<int> upperElements; upperElements.resize( dimension );

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Vectors set, entering dimension loop" << endl; fflush( stdout );
#endif
                
        //for each dimension
        for ( int i=0; i<dimension; i++ ) {
                //for each object to be stored, find the maximum on that dimension
                                                
#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Recording newItem MBR max coordinates" << endl; fflush( stdout );
#endif

                //note that suddenly, mbrs need to implement mins.. not generic!
                
                //initialise all to newItem
                lowerBounds[ i ] = newItem->mbr._mins[ i ];
                upperBounds[ i ] = newItem->mbr._mins[ i ];

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Initial lower bounds on current dimension: " << lowerBounds[ i ] << endl; fflush( stdout );
                cout << "\t Initial upper bounds on current dimension: " << upperBounds[ i ] << endl; fflush( stdout );
#endif
                lowerElements[ i ] = oldItems.size(); upperElements[ i ] = oldItems.size();
                
                for ( unsigned int j=0; j<oldItems.size(); j++ ) {
                        
#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Recording oldItems MBR max coordinates" << endl; fflush( stdout );
#endif
                        
#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Requesting minimum, j=" << j << "<" << oldItemsMBR.size() << " and i=" << i << endl; fflush( stdout );
#endif

                        double t = oldItems[ j ]->mbr._mins[ i ];

#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Minimum t=" << t << endl; fflush( stdout );
                        cout << "\t Done, going for if statement." << endl; fflush( stdout );
#endif

                        if ( t <= lowerBounds[ i ] ) {
                                lowerBounds[ i ] = t;
                                lowerElements[ i ] = j;
                        }
                                
#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Requesting maximum, j="<<j<<" and i=" << i << endl; fflush( stdout );
#endif
                        
#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Maximum t=" << t << endl; fflush( stdout );
                        cout << "\t Done, going for if statement." << endl; fflush( stdout );
#endif

                        if ( t > upperBounds[ i ] ) {
                                upperBounds[ i ] = t;
                                upperElements[ i ] = j;
                        }
                }

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Calculating difference" << endl; fflush( stdout );
#endif

                //store only the upper<>lower difference
                lowerBounds[ i ] = upperBounds[ i ] - lowerBounds[ i ];

        }

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Calculating maximum" << endl; fflush( stdout );
#endif

        //the below can be incorporated in the above loop
        //altough it shouldnt make that much difference
        //select the dimension with max difference
        int k=0; double t=lowerBounds[0];
        
#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Max = " << t << endl; fflush( stdout );
#endif

        for ( int i=1; i<dimension; i++ ) {

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Difference = " << lowerBounds[ i ] << endl; fflush( stdout );
#endif

                if ( lowerBounds[i] > t ) {
                        t=lowerBounds[i];
                        k=i;

#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Max = " << k << endl; fflush( stdout );
#endif

                }
        }

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Add everything to a single vector" << endl; fflush( stdout );
#endif

        //put all elements to be stored in a single vector
        oldItems.push_back( newItem );

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Add the first two items" << endl; fflush( stdout );
#endif
                
        //put the extreme 
        set_one->push_back( oldItems[ lowerElements[ k ] ] );
        set_two->push_back( oldItems[ upperElements[ k ] ] );
        
#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Construct the two set MBRs" << endl; fflush( stdout );
        cout << "\t Initially added extreme objects: " <<  oldItems[ lowerElements[ k ] ] << " and " <<  oldItems[ upperElements[ k ] ] << endl;
#endif

        //remember the MBRs of each set
        BB_type *set_one_mbr = new BB_type( &( oldItems[ lowerElements[ k ] ]->mbr ) );
        BB_type *set_two_mbr = new BB_type( &( oldItems[ upperElements[ k ] ]->mbr ) );

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Erasing the two already added items" << endl; fflush( stdout );
        cout << "\t Going to erase: " << (*(oldItems.begin() + lowerElements[ k ])) << endl;
        cout << "\t and: " << (*(oldItems.begin() + upperElements[ k ])) << endl;
#endif

        //erase the already added items
        oldItems.erase( oldItems.begin() + lowerElements[ k ] );
        
#ifndef _HP
        if ( lowerElements[ k ] == upperElements[ k ] ) {
                cerr << "Error: Linear split found two extreme elements to be the same!" << endl;
                cerr << set_one_mbr->toString() << endl;
                cerr << set_two_mbr->toString() << endl;
                exit( 1 );
        }
#endif
        
        if ( lowerElements[ k ] < upperElements[ k ] ) {
                oldItems.erase( oldItems.begin() + ( upperElements[ k ] - 1 ) );
        } else {
                oldItems.erase( oldItems.begin() + upperElements[ k ] );
        }
        
#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Adding the not yet added elements" << endl; fflush( stdout );
#endif

        //add the remaining entries
        while ( !oldItems.empty() ) {
        
                //check for minimum constraint
                if ( properties->minimum - set_one->size() == oldItems.size() ) {
                        //all remaining entries must be added to set one, otherwise the min
                        //requirement will not be met.
                        for ( unsigned int i=0 ; i<oldItems.size(); i++ ) {
                                set_one->push_back( oldItems[ i ] );
                                (*set_one_mbr).unite( &( oldItems[ i ]->mbr ) );
                                //*set_one_mbr = set_one_mbr->unite( oldItems[ i ]->mbr );
                                
#ifdef _DEBUG_LINEAR_SPLIT
                                cout << "\t Adding to set one (forced): " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        }
                        break;
                } else if ( oldItems.size() == properties->minimum - set_two->size() ) {
                        //likewise for set two
                        for ( unsigned int i=0 ; i<oldItems.size(); i++ ) {
                                set_two->push_back( oldItems[ i ] );
                                (*set_two_mbr).unite( &( oldItems[ i ]->mbr ) );
                                //*set_two_mbr = set_two_mbr->unite( oldItems[ i ]->mbr );

#ifdef _DEBUG_LINEAR_SPLIT
                                cout << "\t Adding to set two (forced): " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        }
                        break;                  
                }
        
#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Getting random number" << endl; fflush( stdout );
#endif

                //select randomly
                double rdm = ((double)rand()) / ((double)RAND_MAX + 1);
                unsigned int i = (int)(rdm * oldItems.size());

#ifndef _HP
                if ( i>=oldItems.size() ) {
                        cerr << "Random index number generated is too large!" << endl;
                        exit(1);
                }
#endif

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Calculating area enlargements" << endl; fflush( stdout );
#endif

                //calculate area enlargement
                double s = areaEnlargement( *set_one_mbr, oldItems[ i ]->mbr );
                double t = areaEnlargement( *set_two_mbr, oldItems[ i ]->mbr );

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Going for ifs" << endl; fflush( stdout );
#endif

                if ( s < t ) {
                        set_one->push_back( oldItems[ i ] );

#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Adding to set one: " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        //note the following code duplication, could be optimised
                        (*set_one_mbr).unite( &( oldItems[ i ]->mbr ) );
                        //*set_one_mbr = set_one_mbr->unite( oldItems[ i ]->mbr );
                } else {
                        set_two->push_back( oldItems[ i ] );

#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Adding to set two: " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        //note the following code duplication, could be optimised
                        (*set_two_mbr).unite( &( oldItems[ i ]->mbr ) );
                        //*set_two_mbr = set_two_mbr->unite( oldItems[ i ]->mbr );
                }       

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Going for erase" << endl; fflush( stdout );
                cout << "\t Erasing the just now added item" << endl; fflush( stdout );
                cout << "\t Going to erase: " << (*(oldItems.begin() + i )) << endl;
#endif

                //delete
#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Erasing item" << endl; fflush( stdout );
#endif


                oldItems.erase( oldItems.begin() + i );
                
        }

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "Propagating mbr changes" << endl; fflush( stdout );
#endif          
                
        mbr_one->become( set_one_mbr ); delete set_one_mbr;
        mbr_two->become( set_two_mbr ); delete set_two_mbr;
        
#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\tNumber of elements in set 1: " << set_one->size() << endl; fflush( stdout );
        cout << "\tSet one MBR: " << endl << set_one_mbr->toString();
        cout << "\tNumber of elements in set 2: " << set_two->size() << endl; fflush( stdout );
        cout << "\tSet two MBR: " << endl << set_two_mbr->toString();
#endif

#ifdef _DEBUG
        cout << "Exitting linearSplit" << endl; fflush( stdout );
#endif


}

void Basic_R_tree::linearSplitElements( vector< BB_container* > oldItems, BB_container *newItem, vector< BB_container* > *set_one, vector< BB_container* > *set_two, BB_type *mbr_one, BB_type *mbr_two, int dimension ) {

#ifdef _DEBUG
        cout << "Entering linearSplitElements" << endl; fflush( stdout );
#endif

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t #oldItems = " << oldItems.size() << endl; fflush( stdout );
#endif
                
        vector<double> lowerBounds; lowerBounds.resize( dimension );
        vector<double> upperBounds; upperBounds.resize( dimension );
        vector<int> lowerElements; lowerElements.resize( dimension );
        vector<int> upperElements; upperElements.resize( dimension );

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Vectors set, entering dimension loop" << endl; fflush( stdout );
#endif
                
        //for each dimension
        for ( int i=0; i<dimension; i++ ) {
                //for each object to be stored, find the maximum on that dimension
                                                
#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Recording newItem MBR max coordinates" << endl; fflush( stdout );
#endif

                //note that suddenly, mbrs need to implement mins.. not generic!
                
                //initialise all to newItem
                lowerBounds[ i ] = newItem->_mins[ i ];
                upperBounds[ i ] = newItem->_mins[ i ];

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Initial lower bounds on current dimension: " << lowerBounds[ i ] << endl; fflush( stdout );
                cout << "\t Initial upper bounds on current dimension: " << upperBounds[ i ] << endl; fflush( stdout );
#endif
                lowerElements[ i ] = oldItems.size(); upperElements[ i ] = oldItems.size();
                
                for ( unsigned int j=0; j<oldItems.size(); j++ ) {
                        
#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Recording oldItems MBR max coordinates" << endl; fflush( stdout );
#endif
                        
#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Requesting minimum, j=" << j << "<" << oldItemsMBR.size() << " and i=" << i << endl; fflush( stdout );
#endif

                        double t = oldItems[ j ]->_mins[ i ];

#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Minimum t=" << t << endl; fflush( stdout );
                        cout << "\t Done, going for if statement." << endl; fflush( stdout );
#endif

                        if ( t <= lowerBounds[ i ] ) {
                                lowerBounds[ i ] = t;
                                lowerElements[ i ] = j;
                        }
                                
#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Requesting maximum, j="<<j<<" and i=" << i << endl; fflush( stdout );
#endif
                                
#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Maximum t=" << t << endl; fflush( stdout );
                        cout << "\t Done, going for if statement." << endl; fflush( stdout );
#endif

                        if ( t > upperBounds[ i ] ) {
                                upperBounds[ i ] = t;
                                upperElements[ i ] = j;
                        }
                }

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Calculating difference" << endl; fflush( stdout );
#endif

                //store only the upper<>lower difference
                lowerBounds[ i ] = upperBounds[ i ] - lowerBounds[ i ];

        }

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Calculating maximum" << endl; fflush( stdout );
#endif

        //the below can be incorporated in the above loop
        //altough it shouldnt make that much difference
        //select the dimension with max difference
        int k=0; double t=lowerBounds[0];
        
#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Max = " << t << endl; fflush( stdout );
#endif

        for ( int i=1; i<dimension; i++ ) {

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Difference = " << lowerBounds[ i ] << endl; fflush( stdout );
#endif

                if ( lowerBounds[i] > t ) {
                        t=lowerBounds[i];
                        k=i;

#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Max = " << k << endl; fflush( stdout );
#endif

                }
        }

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Add everything to a single vector" << endl; fflush( stdout );
#endif

        //put all elements to be stored in a single vector
        oldItems.push_back( newItem );

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Add the first two items" << endl; fflush( stdout );
#endif
                
        //put the extreme 
        set_one->push_back( oldItems[ lowerElements[ k ] ] );
        set_two->push_back( oldItems[ upperElements[ k ] ] );
        
#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Construct the two set MBRs" << endl; fflush( stdout );
        cout << "\t Initially added extreme objects: " <<  oldItems[ lowerElements[ k ] ] << " and " <<  oldItems[ upperElements[ k ] ] << endl;
#endif

        //remember the MBRs of each set
        BB_type *set_one_mbr = new BB_type( oldItems[ lowerElements[ k ] ] );
        BB_type *set_two_mbr = new BB_type( oldItems[ upperElements[ k ] ] );

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Erasing the two already added items" << endl; fflush( stdout );
        cout << "\t Going to erase: " << (*(oldItems.begin() + lowerElements[ k ])) << endl;
        cout << "\t and: " << (*(oldItems.begin() + upperElements[ k ])) << endl;
#endif

        //erase the already added items
        oldItems.erase( oldItems.begin() + lowerElements[ k ] );
        
#ifndef _HP
        if ( lowerElements[ k ] == upperElements[ k ] ) {
                cerr << "Error: Linear split found two extreme elements to be the same!" << endl;
                cerr << set_one_mbr->toString() << endl;
                cerr << set_two_mbr->toString() << endl;
                exit( 1 );
        }
#endif
        
        if ( lowerElements[ k ] < upperElements[ k ] ) {
                oldItems.erase( oldItems.begin() + ( upperElements[ k ] - 1 ) );
        } else {
                oldItems.erase( oldItems.begin() + upperElements[ k ] );
        }
        
#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\t Adding the not yet added elements" << endl; fflush( stdout );
#endif

        //add the remaining entries
        while ( !oldItems.empty() ) {
        
                //check for minimum constraint
                if ( properties->minimum - set_one->size() == oldItems.size() ) {
                        //all remaining entries must be added to set one, otherwise the min
                        //requirement will not be met.
                        for ( unsigned int i=0 ; i<oldItems.size(); i++ ) {
                                set_one->push_back( oldItems[ i ] );
                                set_one_mbr->unite( oldItems[ i ] );
                                //*set_one_mbr = set_one_mbr->unite( *oldItems[ i ] );
                                
#ifdef _DEBUG_LINEAR_SPLIT
                                cout << "\t Adding to set one (forced): " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        }
                        break;
                } else if ( oldItems.size() == properties->minimum - set_two->size() ) {
                        //likewise for set two
                        for ( unsigned int i=0 ; i<oldItems.size(); i++ ) {
                                set_two->push_back( oldItems[ i ] );
                                set_two_mbr->unite( oldItems[ i ] );
                                //*set_two_mbr = set_two_mbr->unite( *oldItems[ i ] );

#ifdef _DEBUG_LINEAR_SPLIT
                                cout << "\t Adding to set two (forced): " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        }
                        break;                  
                }
        
#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Getting random number" << endl; fflush( stdout );
#endif

                //select randomly
                double rdm = ((double)rand()) / ((double)RAND_MAX + 1);
                unsigned int i = (int)(rdm * oldItems.size());

#ifndef _HP
                if ( i>=oldItems.size() ) {
                        cerr << "Random index number generated is too large!" << endl;
                        exit(1);
                }
#endif

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Calculating area enlargements" << endl; fflush( stdout );
#endif

                //calculate area enlargement
                double s = areaEnlargement( *set_one_mbr, *oldItems[ i ] );
                double t = areaEnlargement( *set_two_mbr, *oldItems[ i ] );

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Going for ifs" << endl; fflush( stdout );
#endif

                if ( s < t ) {
                        set_one->push_back( oldItems[ i ] );

#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Adding to set one: " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        //note the following code duplication, could be optimised
                        set_one_mbr->unite( oldItems[ i ] );
                        //*set_one_mbr = set_one_mbr->unite( *oldItems[ i ] );
                } else {
                        set_two->push_back( oldItems[ i ] );

#ifdef _DEBUG_LINEAR_SPLIT
                        cout << "\t Adding to set two: " << oldItems[ i ] << endl; fflush( stdout );
#endif

                        //note the following code duplication, could be optimised
                        set_two_mbr->unite( oldItems[ i ] );
                        //*set_two_mbr = set_two_mbr->unite( *oldItems[ i ] );
                }       

#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Going for erase" << endl; fflush( stdout );
                cout << "\t Erasing the just now added item" << endl; fflush( stdout );
                cout << "\t Going to erase: " << (*(oldItems.begin() + i )) << endl;
#endif

                //delete
#ifdef _DEBUG_LINEAR_SPLIT
                cout << "\t Erasing item" << endl; fflush( stdout );
#endif


                oldItems.erase( oldItems.begin() + i );
                
        }

#ifdef _DEBUG_LINEAR_SPLIT
        cout << "Propagating mbr changes" << endl; fflush( stdout );
#endif          
                
        mbr_one->become( set_one_mbr ); delete set_one_mbr;
        mbr_two->become( set_two_mbr ); delete set_two_mbr;
        
#ifdef _DEBUG_LINEAR_SPLIT
        cout << "\tNumber of elements in set 1: " << set_one->size() << endl; fflush( stdout );
        cout << "\tSet one MBR: " << endl << set_one_mbr->toString();
        cout << "\tNumber of elements in set 2: " << set_two->size() << endl; fflush( stdout );
        cout << "\tSet two MBR: " << endl << set_two_mbr->toString();
#endif

#ifdef _DEBUG
        cout << "Exitting linearSplit" << endl; fflush( stdout );
#endif


}


Basic_R_tree *Basic_R_tree::handleOverflow( Basic_R_tree *node, BB_container *element ) {
#ifdef _DEBUG
        cout << "Entering handleOverflow, the node-polytope version" << endl; fflush( stdout );
#endif
#ifdef _GREATER_CHECK
        checkEntireTree();
 #ifdef _DEBUG
        cout << "\tTree is valid." << endl; fflush( stdout );
 #endif
#endif

        //set splits
        vector< BB_container* > set_one;
        vector< BB_container* > set_two;
        BB_type *mbr_one;
        BB_type *mbr_two;
        mbr_one = new BB_type();
        mbr_two = new BB_type();
        
        //build item nodes
        vector< BB_container* > oldItems;
        for( unsigned int i=0; i<this->elements.size(); i++ ) {
                oldItems.push_back( this->elements[ i ] );
        }
        
        switch( SPLIT_STRATEGY ) {
                case LINEAR_SPLIT:
                        linearSplitElements( oldItems, element, &set_one, &set_two, mbr_one, mbr_two, element->getDimension() );
                        break;
                case QUADRATIC_SPLIT:
                        quadraticSplitElements( oldItems, element, &set_one, &set_two, mbr_one, mbr_two, element->getDimension() ); 
                        break;
                case EXPONENTIAL_SPLIT:
                        cerr << "x^Split! " << endl; exit(1);
                        break;
                default:
                        cerr << "No valid split strategy selected! (r-tree.h)" << endl;
                        exit(1);
        }

#ifdef _DEBUG
        cout << "Set one has " << set_one.size() << " items." << endl; fflush( stdout );
        cout << "Set two has " << set_two.size() << " items." << endl; fflush( stdout );
#endif

        // build a node from the first set. Let it have the correct MBR.
        Basic_R_tree *child_one = buildNode( set_one, mbr_one );

#ifdef _DEBUG
        cout << "Child one has " << child_one->elements.size() << " elements." << endl; fflush( stdout );
#endif

#ifdef _GREATER_CHECK
 #ifdef _DEBUG
                        cout << "\tcheckEntireTree after buildnode" << endl; fflush( stdout );
                        checkEntireTree();
                        cout << "\tOK" << endl; fflush( stdout );
 #endif
#endif

        //let the overflowed node contain the elements of the second set, with the correct MBR.
        node->setElements( set_two, mbr_two );

#ifdef _DEBUG
        cout << "Current node has " << node->elements.size() << " elements." << endl; fflush( stdout );
#endif

        //delete temporary mbrs
        delete mbr_one;
        delete mbr_two;

#ifdef _GREATER_CHECK
 #ifdef _DEBUG
        cout << "\tCheck child one subtree invariants: " << endl;
 #endif
        child_one->checkInvariants();
 #ifdef _DEBUG
        cout << "\tOK. Check current subtree invariants: " << endl;
 #endif
        node->checkInvariants();
 #ifdef _DEBUG
        cout << "\tOK." << endl;
 #endif
#endif
        
        //insert the new node
        if ( node->isRoot() ) {

#ifdef _DEBUG
                cout << "Exitting handleOverflow, the node-polytope version" << endl; fflush( stdout );
#endif

                //make new root should supply the new root with a valid MBR
                return node->makeNewRoot( child_one );
        } else {

#ifdef _DEBUG
                cout << "Exitting handleOverflow, the node-polytope version" << endl; fflush( stdout );
#endif

                //node insertion will check for new overflows
                //it will also propagate some MBR updates
                return node->parent->insert( child_one );
        }
}

Basic_R_tree *Basic_R_tree::chooseLeaf( Basic_R_tree *v, const BB_type bb ) const {
#ifdef _DEBUG
        cout << "Entering chooseLeaf" << endl; fflush( stdout );
#endif
        if ( v->isLeaf() ) {

#ifdef _DEBUG
                cout << "Exitting chooseLeaf" << endl; fflush( stdout );
#endif
                return v;

        }
                
        //v is not leaf, so there is at least one child
        double m = areaEnlargement( this->children[0]->mbr, bb );
        double c = m;
        int j = 0;
        
        for( unsigned int i=1; i<this->children.size(); i++ ) {
                c = areaEnlargement( this->children[i]->mbr, bb );
                if ( c < m ) {
                        m = c;
                        j = i;
                } else if ( c == m ) {
                        if ( Current_Metric::Volume( this->children[j]->mbr ) > Current_Metric::Volume( this->children[i]->mbr ) ) {
                                m = c;
                                j = i;
                        }
                }
                // else if ( c == m )?? TODO
        }

#ifdef _DEBUG
        cout << "calling chooseLeaf recursively" << endl; fflush( stdout );
#endif

        return chooseLeaf( this->children[j], bb );
}

Basic_R_tree *Basic_R_tree::search( BB_container *element ) {

#ifdef _DEBUG
        cout << "Entering search(polytope)" << endl; fflush( stdout );
#endif
        
        if ( this->isLeaf() ) {
                vector< BB_container* >::iterator it = this->elements.begin();
                for( ; it!=this->elements.end(); it++ )
                        if ( (*it)->getID() == element->getID() )
                                return this;
                return 0;
        } else {
                childIterator it = this->children.begin();
                for( ; it!=this->children.end(); it++ ) {
                        if ( element->intersects( (*it)->mbr ) ) {
                                Basic_R_tree *candidate = (*it)->search( element );
                                if ( candidate != 0 ) {
                                        return candidate;
                                }
                        }
                }
                
#ifdef _DEBUG
                cout << "Exitting search(polytope) -- nothing found" << endl; fflush( stdout );
#endif
                return 0;
        }
}

#ifdef _OUTPUT_TREE
unsigned int _counter_insertion = 0;
#endif

Basic_R_tree *Basic_R_tree::insert( BB_container *element ) {

#ifdef _DEBUG
        cout << "Entering insert(element)" << endl; fflush( stdout );
#endif

#ifdef _GREATER_CHECK
 #ifdef _DEBUG
        cout << "Going for check at the start of insert( element )" << endl;
 #endif
        checkEntireTree();
 #ifdef _DEBUG
        cout << "Check succes!" << endl;
 #endif
#endif

        Basic_R_tree *node = chooseLeaf( this, *element );
        if ( !( node->full() ) ) {

#ifndef _HP
                if ( !node->isLeaf() ) {
                        cerr << "Attempted to store element at non-leaf node in R-tree!" << endl;
                        exit(1);
                }
#endif

                node->elements.push_back( element );

                node->updateMBR();

        } else {
                //MBR updating is handled inside handleOverflow
                handleOverflow( node, element );
        }

#ifdef _GREATER_CHECK
 #ifdef _DEBUG
        cout << "Going for check at the end of insert( element )" << endl;
 #endif
        checkEntireTree();
 #ifdef _DEBUG
        cout << "Check succes!" << endl;
 #endif
#endif
        
#ifdef _DEBUG
        cout << "Exitting insert(element)" << endl; fflush( stdout );
#endif

#ifdef _OUTPUT_TREE
        ostringstream oss;
        
        oss << "debug_tree_out.";
        oss << _counter_insertion;

        node->getRoot()->writeTreeToFile( oss.str() );
        _counter_insertion++;
#endif

        return node->getRoot();

}

const Basic_R_tree *Basic_R_tree::getRoot() const {

#ifdef _DEBUG
        cout << "const getRoot() called in R-tree. Current node has " << this->children.size() << " children and stores " << this->elements.size() << " elements." << endl; fflush( stdout );
#endif

        if ( !this->isRoot() )
                return this->parent->getRoot();
        else
                return this;
}

Basic_R_tree *Basic_R_tree::getRoot() {

#ifdef _DEBUG
        cout << "getRoot() called in R-tree. Current node has " << this->children.size() << " children and stores " << this->elements.size() << " elements." << endl; fflush( stdout );
#endif

        if ( !this->isRoot() )
                return this->parent->getRoot();
        else
                return this;
}

Basic_R_tree *Basic_R_tree::remove( BB_container *element ) {

#ifdef _DEBUG
        cout << "Entering remove(element)" << endl; fflush( stdout );
#endif

        //first search the element
        Basic_R_tree *node = this->search( element );
        if ( node == 0 )
                cerr << "Warning: to be removed element from R-tree was not found. Ignoring..." << endl;
        else
                this->remove( node, element );
                
        node->updateMBR();

#ifdef _GREATER_CHECK
        this->checkEntireTree();
#endif
                        
#ifdef _DEBUG
        cout << "Exitting remove(element)" << endl; fflush( stdout );
#endif

        return getRoot();
}

#endif

---