FPB.h

Go to the documentation of this file.

/*
 *  Copyright (C) 2007  A.N. Yzelman
 *  Released under LGPL, see license.txt
 *
 *  Last modified at 31th of May, 2007, by A.N. Yzelman
 *
 *  FPB.h: Definition of a Fast Packed Bulk-loaded R-tree.
 */

#ifndef _H_FPB
#define _H_FPB
 
#include "Hilbert_R-Tree.h"
#include <limits>

//#define _DEBUG

template< typename base_tree >
class FPB_tree : public base_tree {

   private:
   
        virtual bool checkReady() const { return loaded; }
        
        bool loaded;
        
        vector< BB_container > cache;

        vector< base_tree* > bulkLoad( vector< BB_container* > *input );
        
   protected:
   
        virtual Ordering< BB_container >* useOrdering() const;
        
        
   public:
   
   FPB_tree() : base_tree() { loaded = false; this->deleteLeaves = false; }
   
   FPB_tree( R_tree_props *props ) : base_tree( props ) { loaded = false; this->deleteLeaves = false; }
        
    virtual ~FPB_tree() { }
   
        virtual void ensureReady();
   
        void bulkLoad();
        
         virtual base_tree *insert( BB_container *element );

        virtual base_tree *remove( BB_container *element );

        virtual base_tree *search( BB_container *element );

        virtual vector< int > containedIn( BB_type box ) const;

        virtual vector< int > intersects( const vector< double > begin, const vector< double > end ) const;

        virtual vector< int > intersects( Point point ) const;

        virtual vector< int > intersects( vector<double> a, double b ) const;

        virtual vector< int > neighboursOf( BB_container *item ) const;

};


/***************************************************
 *                       PRIVATE                   *
 ***************************************************/

template< typename base_tree >
void FPB_tree< base_tree >::ensureReady() {
        if ( !loaded ) {
                bulkLoad();
        }
}

template< typename base_tree >
Ordering< BB_container >* FPB_tree< base_tree >::useOrdering() const {
        //basic FPB algorithm assumes the existance of an Hilbert ordering
        return &BB_container::HILC_ORDERING;
}

template< typename base_tree >
void FPB_tree< base_tree >::bulkLoad() {
        if ( loaded ) {
                cerr << "FPB_tree::bulkLoad() called while already bulkloaded!" << endl;
                exit( 1 );
        }

        if ( cache.size() == 0 ) {
                cerr << "Error; tried to bulk load an empty set. Aborting..." << endl;
                return;
        }
        
        vector< BB_container* > p_cache;
        vector< BB_container >::iterator it = cache.begin();
        for( ; it!=cache.end(); it++ )
                p_cache.push_back( &( *it ) );

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

                useOrdering()->sort( &p_cache );

#ifdef _DEBUG
        cout << "Exitting sort... " << endl; fflush( stdout );
#endif
        
        vector< base_tree* > new_children = bulkLoad( &p_cache );
        
        /*BB_type children_mbr;
        
        vector< base_tree* >::iterator it = new_children.begin();
        for( ; it!=new_children.end(); it++ )
                children_mbr = (*it)->mbr.unite( children_mbr );
        
        //check for degenerate root
        if ( new_children.size() == 1 ) {
                base_tree* walk = new_children[0];
                elements = walk->elements;
                children = walk->children;
                properties = walk->properties; //actually kind of useless
                //mbr = children_mbr;
                updateMBRLocal();
        } else {*/
                //simply set new children
                this->setChildren( new_children, 0 );
                /* weird c++ protected rules prevent the below
                this->children = new_children;
                typename vector< base_tree* >::iterator childIt = new_children.begin();
                for( ; childIt!=new_children.end(); childIt++ )
                        (*childIt)->parent = this;*/
                //mbr = children_mbr;
                this->updateMBRLocal();
        //}
        
        //whilst MBRs were updated constantly, things like LHV were not (in the hilbert r-tree case).
        //we do this now;
        this->postBulkLoad();
        
        loaded = true;
}

template< typename base_tree >
vector< base_tree* > FPB_tree< base_tree >::bulkLoad( vector< BB_container* > *input ) {
                
        //initialise lowest tree level
        vector< base_tree* > singleTreeLevel;

        //add all elements and build the lowest level
        vector< BB_container* >::iterator it = input->begin();
        unsigned int added = 0;
        BB_type curBB;
        vector< BB_container* > nodeElems;
        for( ; it!=input->end(); it++ ) {
                if ( added == this->properties->maximum ) {
                        singleTreeLevel.push_back( this->buildNode( nodeElems, new BB_type( curBB ) ) );
                        nodeElems.clear();
                        added = 0;
                }
                curBB = curBB && ( *(*it) );
                nodeElems.push_back( *it );
                added++;
        }
        
        //could be that nodeElems is not empty;
        if ( added > 0 )
                        singleTreeLevel.push_back( this->buildNode( nodeElems, new BB_type( curBB ) ) );
        
        added = 0;
        nodeElems.clear();
        curBB.clear();
        
        //lowest level done, now we recurse until singleTreeLevel < max
        while ( singleTreeLevel.size() > this->properties->maximum ) {
                vector< base_tree* > newLevel;
                typename vector< base_tree* >::iterator it;
                vector< base_tree* > nodeElems;
                it = singleTreeLevel.begin();
                for( ; it!=singleTreeLevel.end(); it++ ) {
                        if ( added == this->properties->maximum ) {
                                newLevel.push_back( buildNode( nodeElems, new BB_type( curBB ) ) );
                                nodeElems.clear();
                                added = 0;
                        }
                        curBB.unite( (*it)->getMBR() );
                        //curBB = (*it)->getMBR()->unite( curBB );
                        nodeElems.push_back( *it );
                        added++;
                }
                if ( added > 0 )
                        newLevel.push_back( buildNode( nodeElems, new BB_type( curBB ) ) );
                added = 0;
                nodeElems.clear();
                curBB.clear();
                //prepare next recursion
                singleTreeLevel.assign( newLevel.begin(), newLevel.end() );
                newLevel.clear();
        }
        
        //return the highest level of children
        return singleTreeLevel;
        
}

template< typename base_tree >
base_tree* FPB_tree< base_tree >::insert( BB_container *element ) {
        if ( loaded ) {
                return base_tree::insert( element );
        } else {
                cache.push_back( BB_container( element ) );
                delete element;
                return this;
        }
}

template< typename base_tree >
base_tree* FPB_tree< base_tree >::remove( BB_container *element ) {
        if ( loaded ) {
                return base_tree::remove( element );
        } else {
                vector< BB_container >:: iterator it = cache.begin();
                for( ; it!=cache.end(); it++ )
                        if ( &(*it) == element || (*it).getID() == element->getID() )
                                cache.erase( it );
                return this;
        }
}

template< typename base_tree >
base_tree* FPB_tree< base_tree >::search( BB_container *element ) {
        if ( loaded ) {
                return base_tree::search( element );
        } else {
                vector< BB_container >:: iterator it = cache.begin();
                for( ; it!=cache.end(); it++ )
                        if ( &(*it) == element || (*it).getID() == element->getID() )
                                return this;
                return 0;
        }
}

template< typename base_tree >
vector< int > FPB_tree< base_tree >::containedIn( BB_type box ) const {
        if ( !checkReady() ) {
                cerr << "Trying to query while datastructure was not ready for access!" << endl;
                exit( 1 );
        }
        return base_tree::containedIn( box );
}

template< typename base_tree >
vector< int > FPB_tree< base_tree >::intersects( const vector< double > begin, const vector< double > end ) const {
        if ( !checkReady() ) {
                cerr << "Trying to query while datastructure was not ready for access!" << endl;
                exit( 1 );
        }
        return base_tree::intersects( begin, end );
}

template< typename base_tree >
vector< int > FPB_tree< base_tree >::intersects( Point point ) const {
        if ( !checkReady() ) {
                cerr << "Trying to query while datastructure was not ready for access!" << endl;
                exit( 1 );
        }
        return base_tree::intersects( point );
}

template< typename base_tree >
vector< int > FPB_tree< base_tree >::intersects( vector<double> a, double b ) const {
        if ( !checkReady() ) {
                cerr << "Trying to query while datastructure was not ready for access!" << endl;
                exit( 1 );
        }
        return base_tree::intersects( a, b );
}

template< typename base_tree >
vector< int > FPB_tree< base_tree >::neighboursOf( BB_container *item ) const {
        if ( !checkReady() ) {
                cerr << "Trying to query while datastructure was not ready for access!" << endl;
                exit( 1 );
        }
        return base_tree::neighboursOf( item );
}

#endif

---