Hilbert_R-Tree.h

Go to the documentation of this file.

/*
 *  Copyright (C) 2007  A.N. Yzelman
 *  Released under LGPL, see license.txt
 *
 *  Last modified at 11th of May, 2007, by A.N. Yzelman
 *
 *  Hilbert_R-Tree.h: Definition of a Hilbert R-tree.
 *
 */

#ifndef _H_HILBERT_R_TREE
#define _H_HILBERT_R_TREE
 
#include "r-tree.h"
#include "orderings.h"
#include <limits>

#define Sfrom 2

//#define _DEBUG

class Hilbert_R_tree : public R_tree< Hilbert_R_tree > {

  private:
   
        double LHV;
        
  protected:

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

  
        class HilbertTreeOrdering: public Ordering< Hilbert_R_tree > {
                protected:
                        virtual double getVal( const Hilbert_R_tree * const inp ) const {
                                return inp->LHV;
                        }
        };
    
        Hilbert_R_tree *chooseLeaf( const double h );
        
        void handleOverflow();
        
        void handleRootOverflow();
        
        void handleUnderflow();
        
        void insert( BB_container* element, double h );
        
        void removeElement( BB_container* element );

        void updateLHVLocal();
        
        void updateLHV();
        
        void setChildren( vector< Hilbert_R_tree* > newChildren, BB_type *newMbr );
        
  public:
   
   Hilbert_R_tree() : R_tree< Hilbert_R_tree >() { LHV = 0; }

   Hilbert_R_tree( R_tree_props *props ) : R_tree< Hilbert_R_tree >( props ) { LHV = 0; }
        
   virtual ~Hilbert_R_tree() {}
 
   virtual void postBulkLoad() { getRoot()->updateLHV(); }

   int compareLHV( const Hilbert_R_tree* b ) const;
   
   void visualiseTree( const int level, Hilbert_R_tree *ref );
   
   Hilbert_R_tree* getRoot();
                
        virtual Hilbert_R_tree*insert( BB_container *element );
        
        virtual Hilbert_R_tree* remove( BB_container* element );

        virtual Hilbert_R_tree* search( BB_container* element );

};

int compare_hilbert_trees( const void* a, const void* b );

int compare_containers( const void* a, const void* b );


/*************************************************************
 *                    PROTECTED FUNCTIONS                    *
 *************************************************************/ 


void Hilbert_R_tree::setChildren( vector< Hilbert_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 ) );
                LHV = newChildren[0]->LHV;
                newChildren[0]->children.clear();
                newChildren[0]->elements.clear();
                delete newChildren[0];
                return;
        }

        this->children.clear();
        
        childIterator it = newChildren.begin();

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

                (*it)->parent = this;

                this->children.push_back( (*it) );

        }
                
        this->elements.clear();
        if ( newMbr != 0 )
                mbr = BB_type( newMbr );
}

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

        Hilbert_R_tree *ret = new Hilbert_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;
        }
        
        ret->mbr = BB_type( newMbr );

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

        return ret;
}

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

        Hilbert_R_tree *ret = new Hilbert_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;
}

void Hilbert_R_tree::updateLHVLocal() {

        if ( isLeaf() ) {
                vector< BB_container* >::iterator it = elements.begin();

#ifdef _DEBUG   
                if ( elements.size() == 0 ) {
                        cout << "Element size is zero? (Hilbert_R_tree::updateLHV)" << endl;
                        fflush( stdout );
                }       
#endif          

                //init
                vector< double > center;
                (*it)->getCenterCoordinate( &center );
                LHV = HilbertCoordinateMapper::toHilbert3D( &center );
                
                //find max (cannot use HilbertOrdering3D, because explicit ordering
                //value is needed here).
                for( ; it!=elements.end(); it++ ) {
                        vector< double > center;
                        (*it)->getCenterCoordinate( &center );
                        const double curLHV = HilbertCoordinateMapper::toHilbert3D( &center );
                        if ( curLHV > LHV )
                                LHV = curLHV;
                }
        } else {
                vector< Hilbert_R_tree* >::iterator it = children.begin();
                
                //init
                if ( (*it)->LHV == 0 )
                        (*it)->updateLHVLocal();
                else
                        LHV = (*it)->LHV;
                
                //loop to find max
                for( ; it!=children.end(); it++ )
                        if ( (*it)->LHV > LHV )
                                LHV = (*it)->LHV;
        }
}

void Hilbert_R_tree::updateLHV() {
        updateLHVLocal();

        //if not root, recurse upwards
        if ( !isRoot() )
                parent->updateLHV();
}

Hilbert_R_tree *Hilbert_R_tree::chooseLeaf( const double h ) {
        if ( isLeaf() )
                return this;

        vector< Hilbert_R_tree* >::iterator it = children.begin();
        
        double curLHV = (*it)->LHV;
        Hilbert_R_tree *ret = *it;
        it++;
        
        //find one which is larger than h
        for( ; it!=children.end() && curLHV<h; it++ ) {
                const double cur = (*it)->LHV;
                if ( cur > curLHV ) {
                        curLHV = cur;
                        ret = *it;
                }
        }
        
        //find the minimum one which is larger than h
        for( ; it!=children.end(); it++ ) {
                const double cur = (*it)->LHV;
                if ( cur < curLHV && cur > h ) {
                        curLHV = cur;
                        ret = *it;
                }
        }
        
        return ret->chooseLeaf( h );
}

void Hilbert_R_tree::handleOverflow() {
        if ( isRoot() ) {
#ifdef _DEBUG
                cout << "Root overflow detected, heightening tree..." << endl;
#endif          
        
                //root overflow
                Hilbert_R_tree *childOne = new Hilbert_R_tree( properties );
                childOne->parent = this;
                
                //child one is a clone of current node
                childOne->children.assign( children.begin(), children.end() );
                childOne->elements.assign( elements.begin(), elements.end() );
                childOne->LHV = LHV;
                childOne->updateMBRLocal();
                
                //the children of child one should have child one as parent
                vector< Hilbert_R_tree * >::iterator it = childOne->children.begin();
                for( ; it!=childOne->children.end(); it++ )
                        (*it)->parent = childOne;
                
                //current node is the father of the new node
                children.clear();
                elements.clear();
                children.push_back( childOne );
#ifdef _DEBUG
                cout << "Recursing on child" << endl;
#endif
                //now, the situation of root overflow is reduced to non-root overflow
                //so call handleOverflow on the overflowing child
                childOne->handleOverflow();
        } else {
                //non-root overflow
                //get all siblings, including ourselves
                vector< Hilbert_R_tree * > siblings;
                vector< Hilbert_R_tree * >::iterator it = parent->children.begin();
                
#ifdef _DEBUG
                bool check = false;
#endif          
                for ( ; it!=parent->children.end(); it++ ) {
                        siblings.push_back( *it );
#ifdef _DEBUG
                        if ( *it == this )
                                check = true;
#endif          
                }
#ifdef _DEBUG           
                if ( !check )
                        cout << "Im not a child of my parent!!" << endl;
#endif          
                
                //we should have a total of s siblings or less
                while ( siblings.size() > Sfrom ) {
                        it = siblings.begin();
                        if ( (*it) == this )
                                it++;
                        double max = fabs( (*it)->LHV - LHV );
                        vector< Hilbert_R_tree * >::iterator maxElem = it;
                        it++;
                        for( it=siblings.begin(); it!=siblings.end(); it++ ) {
                                const double curmax = fabs( (*it)->LHV - LHV );
                                if ( curmax > max && (*it) != this ) {
                                        maxElem = it;
                                        max = curmax;
                                }
                        }
                        siblings.erase( maxElem );
                }
#ifdef _DEBUG           
                cout << "Number of siblings: " << siblings.size() << endl;
#endif          
                
                //now we have exactly s siblings, or less
                //we have an s to s+1 splitting policy
                //so we should defer splitting as long
                //as possible.
                unsigned int roomInSiblings = 0;
                unsigned int numberOfElemts = 0;
                it = siblings.begin();
                for( ; it!=siblings.end(); it++ ) {
                        roomInSiblings += properties->maximum;
                        if ( isLeaf() )
                                numberOfElemts += (*it)->elements.size();
                        else
                                numberOfElemts += (*it)->children.size();
                }
#ifdef _DEBUG
                cout << "Room in siblings: " << roomInSiblings << endl;
                cout << "Number of elemts: " << numberOfElemts << endl;
#endif          
                if ( numberOfElemts > roomInSiblings ) {
                        //at this point, we need to create a new sibling
                        Hilbert_R_tree *newSibling = new Hilbert_R_tree( properties );
                        newSibling->parent = parent;
                        parent->children.push_back( newSibling );
                        siblings.push_back( newSibling );
                        roomInSiblings += properties->maximum;
#ifdef _DEBUG
                        cout << "Created and added new child to siblings;" << endl;
                        cout << "Number of children of parent: " << parent->children.size() << endl;
                        cout << "Room in siblings: " << roomInSiblings << endl;
                        cout << "Number of elemts: " << numberOfElemts << endl;
#endif          
                }
                
                if ( numberOfElemts <= roomInSiblings ) {
                        //determine number of elements per sibling
                        const unsigned int numberOfElemsPerSibling = (const unsigned int) ( (double) numberOfElemts / (double) siblings.size() );
#ifdef _DEBUG                   
                        cout << numberOfElemts << "/" << siblings.size() << "=" << numberOfElemsPerSibling << endl;
#endif                  
                        //redistribute elements
                        if ( isLeaf() ) {
                                //get leaf elements
                                vector< BB_container * > toReDist;
                                it = siblings.begin();
                                for ( ; it!=siblings.end(); it++ )
                                        toReDist.insert( toReDist.end(), (*it)->elements.begin(), (*it)->elements.end() );
                                
#ifdef _DEBUG
                                cout << "Redist size: " << toReDist.size() << endl;
#endif

                                //sort them according to LHVs
                                HilbertOrdering3D< BB_container > ordering;
                                ordering.sort( &toReDist );
                                
                                //redistribute
                                it = siblings.begin();
                                for( unsigned int i=0; i<( siblings.size() - 1 ); i++ ) {
                                        const unsigned int start = i * numberOfElemsPerSibling;
                                        const unsigned int end = start + numberOfElemsPerSibling;
                                        (*it)->elements.assign( toReDist.begin() + start, toReDist.begin() + end );
#ifdef _DEBUG
                                        cout << (*it)->elements.size() << " elements assigned." << endl;
#endif
                                        it++;
                                }
                                //add the remaining items (could be 1 more than numberOfElemsPerSibling)
                                const unsigned int start = numberOfElemsPerSibling * ( siblings.size() - 1 );
                                (*it)->elements.assign( toReDist.begin() + start, toReDist.end() );
#ifdef _DEBUG
                                cout << (*it)->elements.size() << " elements assigned." << endl;
#endif
                        } else {
                                //get sibling children
                                vector< Hilbert_R_tree * > toReDist;
                                it = siblings.begin();
                                for( ; it!=siblings.end(); it++ )
                                        toReDist.insert( toReDist.end(), (*it)->children.begin(), (*it)->children.end() );
                                
#ifdef _DEBUG
                                cout << "Redist size: " << toReDist.size() << endl;
#endif
                                
                                //sort them according to LHVs
                                HilbertTreeOrdering ordering;
                                ordering.sort( &toReDist );
                                
                                //redistribute
                                it = siblings.begin();
                                for( unsigned int i=0; i<( siblings.size() - 1 ); i++ ){ 
                                        const unsigned int start = i * numberOfElemsPerSibling;
                                        const unsigned int end = start + numberOfElemsPerSibling;
                                        
                                        //assign children
                                        (*it)->children.assign( toReDist.begin() + start, toReDist.begin() + end );
                                        
                                        //parent of children should point to *it
                                        vector< Hilbert_R_tree * >::iterator childit = (*it)->children.begin();
                                        for ( ; childit!=(*it)->children.end(); childit++ )
                                                (*childit)->parent = (*it);
#ifdef _DEBUG
                                        cout << (*it)->children.size() << " elements assigned." << endl;
#endif
                                        it++;
                                }
                                //add the remaining items (could be 1 more than numberOfElemsPerSibling)
                                const unsigned int start = numberOfElemsPerSibling * ( siblings.size() - 1 );
                                (*it)->children.assign( toReDist.begin() + start, toReDist.end() );
                                //parent of children should point to *it
                                vector< Hilbert_R_tree * >::iterator childit = (*it)->children.begin();
                                for ( ; childit!=(*it)->children.end(); childit++ )
                                        (*childit)->parent = (*it);
#ifdef _DEBUG
                                cout << (*it)->children.size() << " elements assigned." << endl;
#endif
                        }
                        
                        //update LHVs and such
                        //first local in siblings
                        it = siblings.begin();
                        for( ; it!=siblings.end(); it++ ) {
                                (*it)->updateMBRLocal();
                                (*it)->updateLHVLocal();
                        }
                        //then propagate upwards from parent
                        parent->updateMBR();
                        parent->updateLHV();
                } else {
                        //this should be impossible
                        cerr << "Fatal error; Hilbert_R_tree::handleOverflow() in invalid state." << endl;
                        exit( 1 );
                }
                
                if ( parent->children.size() > properties->maximum ) {
#ifdef _DEBUG
                        cout << "Parent has overflowed, recursing..." << endl;
#endif          
                        parent->handleOverflow();
                } else {
#ifdef _DEBUG
                        cout << "Overflow handling finished" << endl;
#endif          
                }
#ifdef _DEBUG
                getRoot()->visualiseTree( 0, 0 );
#endif
        }
}

/* //Compares two BB_containers using their LHVs, for use with qsort
int compare_containers( const void* a, const void* b ) {
   BB_container* arg1 = (BB_container*) a;
   BB_container* arg2 = (BB_container*) b;
   vector< double > centera = arg1->getCenterCoordinate();
   vector< double > centerb = arg2->getCenterCoordinate();
   const double ha = HilbertCoordinateMapper::toHilbert3D( &centera );
   const double hb = HilbertCoordinateMapper::toHilbert3D( &centerb );
   if( ha < hb ) return -1;
   else if( ha == hb ) return 0;
   else return 1;
}

// Compares two Hilbert R-trees using their LHVs
int compare_hilbert_trees( const void* a, const void* b ) {
   Hilbert_R_tree* arg1 = (Hilbert_R_tree*) a;
   Hilbert_R_tree* arg2 = (Hilbert_R_tree*) b;
   return arg1->compareLHV( arg2 );
}*/

int Hilbert_R_tree::compareLHV( const Hilbert_R_tree* b ) const {
   if( LHV < b->LHV ) return -1;
   else if( LHV == b->LHV ) return 0;
   else return 1;
}
 
void Hilbert_R_tree::insert( BB_container* element, const double h ) {
        //push it back, regardless of overflows
        elements.push_back( element );
        
        //do 'late' overflow checking
        if( elements.size() > properties->maximum ) {
#ifdef _DEBUG
                cout << elements.size() << " > " << properties->maximum << "; calling handleOverflow()" << endl;
#endif          
                handleOverflow();
                if( elements.size() > properties->maximum ) {
                        cerr << "handleOverflow did not reslove overflow!" << endl;
                        exit( 1 );
                }
        } else {
                //updates; note that handleOverflows handles updates also
                updateMBR();
                updateLHV();
        }
}

void Hilbert_R_tree::handleUnderflow() {}

void Hilbert_R_tree::removeElement( BB_container* element ) {}

void Hilbert_R_tree::visualiseTree( const int level, Hilbert_R_tree *ref ) {
        for( int i=0; i<level; i++ )
                cout << "  ";
        if ( parent != ref )
                cout << "|*" << endl;
        else if ( children.size() > properties->maximum || elements.size() > properties->maximum )
                cout << "|O" << endl;
        else
                cout << "|-" << endl;
        if ( !isLeaf() ) {
                vector< Hilbert_R_tree * >::iterator it = children.begin();
                for( ; it!=children.end(); it++ )
                        (*it)->visualiseTree( level + 1, this );
        }
}


/*************************************************************
 *                    PUBLIC FUNCTIONS                       *
 *************************************************************/ 

Hilbert_R_tree* Hilbert_R_tree::insert( BB_container *element ) {
        //get hilbert value of data element
        vector< double > p;
        element->getCenterCoordinate( &p );
        double curLHV = HilbertCoordinateMapper::toHilbert3D( &p );
        
        //choose the correct leaf
        Hilbert_R_tree* toInsertAt = chooseLeaf( curLHV );
        
        //do the actual insertion at that leaf
        toInsertAt->insert( element, curLHV );
        
        //root has not changed
        return this;
}

Hilbert_R_tree* Hilbert_R_tree::remove( BB_container* element ) {
        cerr << "Element removal not yet implemented!" << endl; exit( 1 ); //TODO
}

Hilbert_R_tree* Hilbert_R_tree::search( BB_container* element ) {
        cerr << "Element search not yet implemented!" << endl; exit( 1 ); //TODO
}

Hilbert_R_tree* Hilbert_R_tree::getRoot() {
        if ( isRoot() )
                return this;
        else
                return parent->getRoot();
}

#endif

---