TGS.h

Go to the documentation of this file.

/*
 *  Copyright (C) 2007  A.N. Yzelman
 *  Released under LGPL, see license.txt
 *
 *  Last modified at 12th of June, 2007, by A.N. Yzelman
 *
 *  TGS.h: Definition of a bulk-loaded R-tree.
 *
 */

#ifndef _H_TGS
#define _H_TGS

#include "basic-r-tree.h"
#include <limits>

#define _TIMINGS

#define  _EVALUATE_ALL

/*If defined, shows progress on screen
#define _PROGRESS*/

#ifdef _TIMINGS
        #include <sys/times.h>
        struct tms TIMING;
        clock_t TIMER;
        clock_t intertimer;
        clock_t intertimersum = 0;
#endif

//#define _DEBUG

template< typename base_tree >
class TGS_tree : public base_tree {

   private:
   
        virtual bool checkReady() const { return loaded; }
        
        //vector< base_tree* > bulkLoad( vector< BB_container* > *input );
        
   protected:
   
        bool loaded;
        
        vector< BB_container > cache;
   
        virtual vector< Ordering< BB_container > * > useOrderings() const;

        virtual double cost_function( const BB_type *x, const BB_type *y ) const;
        
        base_tree* BulkLoadChunk( vector< BB_container* >* D, unsigned int h );

        vector< vector< BB_container* >* >* BestBinarySplit( vector< BB_container* >* D, unsigned int m );

        vector< vector< BB_container* >* >* Partition( vector< BB_container* >* D, unsigned int m );

        
   public:
   
   TGS_tree() : base_tree() { loaded = false; this->deleteLeaves = false; }

   TGS_tree( R_tree_props *props ) : base_tree( props ) { loaded = false; this->deleteLeaves = false; }
        
   virtual ~TGS_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 >
double TGS_tree< base_tree >::cost_function( const BB_type *a, const BB_type *b ) const {
        return Current_Metric::Volume( *a ) + Current_Metric::Volume ( *b );
}

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

template< typename base_tree >
vector< Ordering< BB_container > * > TGS_tree< base_tree >::useOrderings() const {

#ifdef _EVALUATE_ALL
        return BB_container::getOrderings();
#else
        vector< Ordering< BB_container > * > ret;
        ret.push_back( BB_container::getDefaultOrdering() );
        return ret;
#endif
}

template< typename base_tree >
base_tree* TGS_tree< base_tree >::BulkLoadChunk( vector< BB_container* >* D, unsigned int h ) {
        
        if ( h==0 ) {
                //calculate mbr
                BB_type mbr;
                typename vector< BB_container* >::iterator it = D->begin();
                for( ; it!=D->end(); it++ )
                        mbr.unite( (*it) );
                        //mbr = (*it)->unite( mbr );
                
                //build leaf node
                base_tree* ret = this->buildNode( *D, &mbr );

                //remember leaf flag
                ret->deleteLeaves = false;
                
                //delete used vector
                //delete D;
                
                //return
                return ret;
        } else {
                vector< base_tree* > children;
                
                //calculate m = max^h
                unsigned int m = this->properties->maximum;
                for( unsigned int i=1; i<h; i++ )
                        m *= this->properties->maximum;
                
                //partition input into partitions containing <= m elements
                vector< vector< BB_container* >* >* partitions = Partition( D, m );

                //remember this mbr
                BB_type master_mbr;

                //recurse, and store internal node; loop over all partitions
                typename vector< vector< BB_container* >* >::iterator partIt = partitions->begin();
                for( ; partIt!=partitions->end(); partIt++ ) {
                
                        //calculate the mbr of each partition
                        BB_type mbr;
                        typename vector< BB_container* >::iterator it = (*partIt)->begin();
                        for( ; it!=(*partIt)->end(); it++ ) {
                                mbr.unite( (*it) );
                                //mbr = (*it)->unite( mbr );
                        }
                        master_mbr.unite( &mbr );
                        
                        //store the R-tree partition in a node, by recursing on the partition itself
                        children.push_back( BulkLoadChunk( *partIt, h - 1 ) );
                }

                while( partitions->size() > 0 ) {
                        delete partitions->back();
                        partitions->pop_back();
                }

                //we are done with the partitions vector
                delete partitions;

                //check
                if( children.size() > this->properties->maximum ) {
                        cerr << "Too many partitions returned! (" << children.size() << ")" << endl;
                        cerr << "k = |D|/m = " << ( (double) D->size() ) / ( (double) m ) << " \\neq " << children.size() << endl;
                        exit( 1 );
                }
        
                //nodes
                base_tree* ret = buildNode( children, &master_mbr );

                //leaves flag
                ret->deleteLeaves = false;

                //and return
                return ret;
        }
}

template< typename base_tree >
vector< vector< BB_container* >* >* TGS_tree< base_tree >::Partition( vector< BB_container* >* D, unsigned int m ) {

#ifdef _DEBUG
        cout << "Trying to split a vector containing " << D->size() << " elements into partitions containing " << m << " elements." << endl;
#endif

        //allocate return vector
        vector< vector< BB_container* >* >* ret = new vector< vector< BB_container* >* >();
        
        //return a single partition if input size is smaller than partition size
        if ( D->size() <= m ) {
                //copy for safety
                vector< BB_container* >* toAdd = new vector< BB_container* >( D->begin(), D->end() );
                ret->push_back( toAdd );
                //ret->push_back( D );
        } else {
                
                //getting binary split
                vector< vector< BB_container* >* >* binarySplit = BestBinarySplit( D, m );
                
                //concatenate results
                vector< BB_container* >* b_left = binarySplit->at( 0 );
                vector< BB_container* >* b_rght = binarySplit->at( 1 );
                vector< vector< BB_container* >* >* left = Partition( b_left, m );
                vector< vector< BB_container* >* >* rght = Partition( b_rght, m );
                ret->assign( left->begin(), left->end() );
                ret->insert( ret->end(), rght->begin(), rght->end() );
                delete left;
                delete rght;
                delete b_left;
                delete b_rght;
                //delete binarySplit->at( 0 );
                //delete binarySplit->at( 1 );
                
                //we are done with the binarySplit vector
                delete binarySplit;
        }

#ifdef _DEBUG
        cout << "Number of returned partitions: " << ret->size() << endl;
#endif

        return ret;
}

template< typename base_tree >
vector< vector< BB_container* >* >* TGS_tree< base_tree >::BestBinarySplit( vector< BB_container* >* D, unsigned int m ) {

#ifdef _DEBUG
        cout << "Trying to get a binary split of a vector containing " << D->size() << " elements." << endl;
#endif

        vector< BB_container* >* left = new vector< BB_container* >();
        vector< BB_container* >* right = new vector< BB_container* >();
        BB_type left_mbr;
        BB_type right_mbr;

        //M = ceil( |D|/m )
        unsigned int M = D->size() / m;
        if ( ( (double) D->size() / (double) m ) - ( (double) M ) > 0 )
                M++;
        
        double c = numeric_limits<double>::infinity();
        
        vector< Ordering< BB_container > * > orderings = useOrderings();
        vector< Ordering< BB_container > * >::iterator it = orderings.begin();

#ifdef _TIMINGS
#endif
                
        for( ; it!=orderings.end(); it++ ) {
                
                if ( orderings.size() > 1 ) {
#ifdef _TIMINGS
                        intertimer = times( &TIMING );
#endif
                        (*it)->sort( D );
#ifdef _TIMINGS
                        intertimer = times( &TIMING ) - intertimer;
                        intertimersum += intertimer;
#endif
                }
                        
                for ( unsigned int i = 0; i < M-1; i++ ) {

/*#ifdef _PROGRESS
                        cout << "\r" << i << "/" << ( M - 2 );
#endif*/

                        //find split
                        vector< BB_container* >* set_one = new vector< BB_container* >();
                        vector< BB_container* >* set_two = new vector< BB_container* >();

                        //the following can be done since input is sorted at this point.
                        const unsigned int loc = ( i + 1 ) * m;

                        set_one->assign( D->begin(), D->begin() + loc );
                        set_two->assign( D->begin() + loc, D->end() );
                                
                        //build mbrs
                        BB_type left_split;
                        BB_type right_split;

                        vector< BB_container* >::iterator itbb = set_one->begin();
                        for( ; itbb!=set_one->end(); itbb++ )
                                left_split.unite( (*itbb) );
                                //left_split = (*itbb)->unite( left_split );
                        itbb = set_two->begin();
                        for( ; itbb!=set_two->end(); itbb++ )
                                right_split.unite( (*itbb) );
                                //right_split = (*itbb)->unite( right_split );

                        //calculate cost
                        double t = cost_function( &left_split, &right_split );
                        //determine if minimum
                        if ( t < c ) {
                                //set as minimum
                                c = t;
                                left->assign( set_one->begin(), set_one->end() );
                                right->assign( set_two->begin(), set_two->end() );

#ifdef _DEBUG
                                cout << "Set two contains " << right->size() << "elements" << endl << "Setting set one MBR" << endl;
                                cout << "Input set contained " << input->size() << " elements" << endl; 
                                fflush( stdout );
#endif

                                left_mbr = left_split;
                                right_mbr = right_split;
                        }
                        delete set_one;
                        delete set_two;
                }
        }

#ifdef _DEBUG   
        cout << "First vector has " << left->size() << " elements." << endl;
        cout << "Second vector has " << right->size() << " elements." << endl;
#endif

        vector< vector< BB_container* >* >* ret = new vector< vector< BB_container* >* >();
        ret->resize( 2 );
        (*ret)[ 0 ] = left;
        (*ret)[ 1 ] = right;
        return ret;
}

template< typename base_tree >
void TGS_tree< base_tree >::bulkLoad() {

#ifdef _TIMINGS
        TIMER = times( &TIMING ); 
#endif

        if ( loaded ) {
                cerr << "TGS_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( cache.size() );
        for( unsigned int i = 0; i < cache.size(); i++ ){
                p_cache[i] = &cache[i];
        }
        
        if ( useOrderings().size() == 1 ) {

#ifdef _DEBUG
                cout << "Entering sort... " << endl; fflush( stdout );
#endif
                useOrderings().at( 0 )->sort( &p_cache );

#ifdef _TIMINGS
                cout << "*Initial sort took: ";
                TIMER = times( &TIMING ) - TIMER;
                cout << TIMER << " ticks" << endl; fflush( stdout );
#endif
#ifdef _DEBUG
                cout << "Exitting sort... " << endl; fflush( stdout );
#endif

        }
        
        
        double frac = p_cache.size() / this->properties->maximum;
        unsigned int h;
        if ( frac < 0 )
                h = 0;
        else {
                frac = log10( frac ) / log10( static_cast< double >( this->properties->maximum ) );
                h = (unsigned int) frac;
                if ( frac - h > 0 )
                        h++;
        }

#ifdef _TIMINGS
        TIMER = times( &TIMING );
#endif  
        base_tree* new_root = BulkLoadChunk( &p_cache, h );
#ifdef _TIMINGS
        TIMER = times( &TIMING) - TIMER;
        cout << "*Intermediate searches took a total of " << intertimersum << " ticks" << endl; fflush( stdout );
        cout << "*bulkLoading took : " << TIMER << " ticks" << endl; fflush( stdout );
#endif
        vector< base_tree* > new_children;
        new_children.push_back( new_root ); //quick hack, also, degenerate root handling should be handled in setChildren
        
        /*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->children = new_children;
                this->setChildren( new_children, 0 );
                //mbr = children_mbr;
                this->updateMBRLocal();
        //}

        loaded = true;
        
        this->postBulkLoad();
}

template< typename base_tree >
base_tree* TGS_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* TGS_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* TGS_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 > TGS_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 > TGS_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 > TGS_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 > TGS_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 > TGS_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

---