HilbertTGSinsert.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
 *
 *  HilbertTGS.h: Definition of a Hilbert-bulk-loaded Basic R-tree.
 *
 */

#ifndef _H_HILBERTinsert_TGS
#define _H_HILBERTinsert_TGS
 
#include "TGS.h"
#include <limits>
#include <vector>

template< typename base_tree >
class Hilbert_TGSinsert_tree : public TGS_tree< base_tree > {

  private:
        inline void insertionSort( BB_container* element );
        
        unsigned int lowestGeqThan( const double currentVal, const unsigned int left, const unsigned int right ) const;
        
        vector< double > hilbertCache;

  protected:
  
        virtual vector< Ordering< BB_container > * > useOrderings() const;

  public:
  
        Hilbert_TGSinsert_tree() : TGS_tree< base_tree >() {}
        
        Hilbert_TGSinsert_tree( R_tree_props* props ) : TGS_tree< base_tree >( props ) {}
        
        virtual base_tree* insert( BB_container *element );

};

template< typename base_tree >
unsigned int Hilbert_TGSinsert_tree< base_tree >::lowestGeqThan( const double currentVal, const unsigned int left, const unsigned int right ) const {
        if ( hilbertCache[ left ] >= currentVal )
                return left;
        if ( left == right )
                return left + 1;
        
        const unsigned int mid = ( left + right ) / 2;
        
        if ( hilbertCache[ mid ] >= currentVal )
                return lowestGeqThan( currentVal, left + 1, mid );
        else
                return lowestGeqThan( currentVal, mid + 1, right );
}

template< typename base_tree >
void Hilbert_TGSinsert_tree< base_tree >::insertionSort( BB_container* element ) {
        const unsigned int size = this->cache.size();
        vector< double > centre;
        element->getCenterCoordinate( &centre );
        const double currentVal = HilbertCoordinateMapper::toHilbert3D( &centre );
        if ( size == 0 ) {
                hilbertCache.push_back( currentVal );
                this->cache.push_back( BB_container( element ) );
                return;
        }
        const unsigned int insertAt = lowestGeqThan( currentVal, 0, size-1 );
        hilbertCache.insert( hilbertCache.begin() + insertAt, currentVal );
        this->cache.insert( this->cache.begin() + insertAt, BB_container( element ) );
}

template< typename base_tree >
base_tree* Hilbert_TGSinsert_tree< base_tree >::insert( BB_container *element ) {
        if ( this->loaded ) {
                return base_tree::insert( element );
        } else {
                insertionSort( element );
                delete element;
                return this;
        }
}

template< typename base_tree >
vector< Ordering< BB_container > * > Hilbert_TGSinsert_tree< base_tree >::useOrderings() const {
        vector< Ordering< BB_container > * > ret;
        
        ret.push_back( &BB_container::NO_ORDERING );
        
        return ret;
}

#endif

---