r-tree.h

Go to the documentation of this file.

#ifndef _H_R_tree
#define _H_R_tree

#include "NearestNeighbours.h"
#include "Cubic_Bounding_Box.h"
#include "Cubic_Bounding_Box_Container.h"
#include "Spatial_Tree.h"
#include "Cart.h"

#include <vector>

#define LINEAR_SPLIT 0
#define QUADRATIC_SPLIT 1
#define EXPONENTIAL_SPLIT 2

//#define SPLIT_STRATEGY LINEAR_SPLIT
#define SPLIT_STRATEGY QUADRATIC_SPLIT

//gives tree output to files after each insert operation
//#define _OUTPUT_TREE

//this flags disables safety checks to gain performance. Use only for production code.
//#define _HP

#ifdef _NODE_COUNT

unsigned int _node_count;

void resetNodeCount() {
        _node_count = 0;
}

#endif

//checks invariants, prints no debug info to stdout unless the debug flag is set
//warning -- this flag extremely slows program execution
//#define _GREATER_CHECK

//#define _DEBUG
//#define _DEBUG_LINEAR_SPLIT

typedef Cubic_Bounding_Box BB_type;
typedef Cubic_Bounding_Box_Container BB_container;
typedef Cart Current_Metric;

class R_tree_props {
   public:
        unsigned int maximum; 
        unsigned int minimum; 
};

//template < typename bb_type > Pending...
template < typename r_tree_variation >
class R_tree : public Spatial_Tree< r_tree_variation, BB_type, BB_container > {

        friend class Basic_R_tree;

  private:
  
        template <class T>
        bool from_string(T& t, 
                 const std::string& s, 
                 std::ios_base& (*f)(std::ios_base&)) const
        {
                std::istringstream iss(s);
                return !(iss >> f >> t).fail();
        }

  protected:

        void setElements( vector< BB_container* > newElements, BB_type *newMbr );

        //internally used convenience methods

        void init();

        bool full() const;

#ifdef _GREATER_CHECK

        void checkDepth( const int depth, const int level ) const;

        void checkInvariants() const;

        void checkInvariants( int level ) const;

        void checkEntireTree() const;

        void checkEntireTreeRecursive( int level ) const;

        void checkEntireTreeRecursive() const;

        int getHeightEstimate() const;

        int getLocalHeightEstimate() const;
#endif

        //tree construction helper algorithms

        double areaEnlargement( const BB_type bb1, const BB_type bb2 ) const;

        double deadSpace( const BB_type bb1, const BB_type bb2 ) const;

        void writeTreeToFile( ofstream &ofs ) const;
        
        void readTreeFromStream( ifstream &ifs ) const;


        BB_type mbr;

        R_tree_props *properties;

        void nullifyProperties();

        void updateAllMBRs();

        void updateMBRLocal();

        void updateMBRNode();


        void *updateMBR();

        //spatial queries

        void containedIn( const BB_type *box, vector< int > *ret ) const;

        void intersects( const vector< double > &begin, const vector< double > &end, vector< int > *ret ) const;

        void intersects( const Point &point, vector< int > *ret ) const;

        void intersects( const vector<double> &a, const double b, vector< int > *ret ) const;

        void neighboursOf( const BB_container *item, vector< int > *ret ) const;

        void neighboursOf( const vector<double> &point, NearestNeighbours<BB_container> *ns, MinDistTreeOrdering<BB_type, r_tree_variation> *mdt) const;

        typedef typename vector< r_tree_variation * >::const_iterator childIterator;

  public:

        bool deleteLeaves;

        //constructors & deconstructor

        R_tree< r_tree_variation >();

        R_tree< r_tree_variation >( R_tree_props *props );

        virtual ~R_tree< r_tree_variation >();

        void gatherTreeInfo( int *x, int *y ) const;

         const BB_type *getMBR() const { return &mbr; }

        virtual void postBulkLoad() { }

        R_tree< r_tree_variation >* getRoot() { if ( this->parent == 0 ) return this; else return this->parent->getRoot(); }

        //(spatial) tree methods:

                //not implemented in this abstract class

        //spatial queries

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

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

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

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

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

        virtual vector< int > neighboursOf( const vector<double> &point, const unsigned int k ) const;

        //special

        void writeTreeToFile( string fn ) const;

        void readTreeFromFile( string fn ) const;

        void printTreeInfo( ostringstream &oss ) const;

#ifdef _NODE_COUNT

        virtual int visitedNodes() const { return _node_count; }
#endif


        //debug funcs -- not documented.
        void printTreeToStdOut( const int x, const void* par ) const;

};


//debug funcs:
template< typename r_tree_variation >
void R_tree< r_tree_variation >::printTreeToStdOut( const int x, const void* par ) const {
        for( int i=0; i<x; i++ )
                cout << " ";
        cout << "|";
        if ( this->parent != par )
                cout << "*";
        else if ( this->children.size() < properties->minimum && !this->isLeaf() )
                cout << "u";
        else if ( this->children.size() > properties->maximum && !this->isLeaf() )
                cout << "O";
        else if ( this->elements.size() < properties->minimum && this->isLeaf() )
                cout << "u";
        else if ( this->elements.size() > properties->maximum && this->isLeaf() )
                cout << "O";
        else
                cout << "-";
        cout << endl;
        if ( this->isLeaf() )
                return;
        for( unsigned int i=0; i<this->children.size(); i++ ) {
                this->children[i]->printTreeToStdOut( x+1, this );
        }
}

/****************************************
 *          PRIVATE FUNCTIONS           *
 ****************************************/

template< typename r_tree_variation >
void R_tree< r_tree_variation >::writeTreeToFile( ofstream &ofs ) const {

        mbr.writeToFile( ofs );

        if ( this->isLeaf() ) {
                for ( unsigned int i=0; i<this->elements.size(); i++ ) {
                        this->elements[i]->writeToFile( ofs );
                        ofs << "-2 0 0 0 0 0 0" << endl;
                }
        } else {
                for ( unsigned int i=0; i<this->children.size(); i++ ) {
                        this->children[i]->writeTreeToFile( ofs );
                        ofs << "-2 0 0 0 0 0 0" << endl;
                }
        }
}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::readTreeFromStream( ifstream &ifs ) const {

        //get line
        string line; ifs>>line;
        
        //split off the first number
        string first = line.substr( 0, line.length() - line.find( " " ) - 1 );
        
        //get tag
        int tag;
        from_string< int >( tag, first, std::dec );
        cout << tag;
        
        exit( 1 ); //debug TODO !
        
        //case split
        if ( tag==-2 ) {
                //going up
        } else if ( tag==-1 ) {
                //new internal node
        } else {
                //new external node
                unsigned int id;
        }

}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::gatherTreeInfo( int *numNodes, int *numLeafs ) const {

        (*numNodes)++;
        if ( this->isLeaf() ) {
                (*numLeafs) += this->elements.size();
        } else {
                childIterator it = this->children.begin();
                for( ; it!=this->children.end(); ++it ) {
                        (*it)->gatherTreeInfo( numNodes, numLeafs );
                }
        }

}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::init() {
        this->children.clear();
        this->elements.clear();
        this->parent = 0;
        this->deleteLeaves = true;
}

#ifdef _GREATER_CHECK

template< typename r_tree_variation >
void R_tree< r_tree_variation >::checkEntireTree() const {

        getRoot()->checkEntireTreeRecursive( -1 );

}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::checkEntireTreeRecursive() const { checkEntireTreeRecursive( 0 ); }

template< typename r_tree_variation >
void R_tree< r_tree_variation >::checkEntireTreeRecursive( int level ) const {

        checkInvariants( level );

        for ( unsigned int i = 0; i<this->children.size(); i++ )
                        this->children[i]->checkEntireTreeRecursive( level + 1 );

}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::checkInvariants() const { checkInvariants( -1 ); }

template< typename r_tree_variation >
void R_tree< r_tree_variation >::checkInvariants( int level ) const {

        //mbr check (are mbr really mbrs?)
        if ( isLeaf() && this->elements.size() > 0 ) {
                for ( unsigned int i=0; i<this->elements.size(); i++ ) {
                        if ( !mbr.contains( *this->elements[i] ) ) {
                                cerr << "At level " << level << ":" << endl;
                                cerr << "MBR does not contain all elements!" << endl;
                                cerr << "MBR: " << mbr;
                                cerr << "MBR not in it: " << endl << (*this->elements[i]);
                                exit(1);
                        }
                }
        } else {
                for ( unsigned int i=0; i<this->children.size(); i++ ) {
                        if ( !mbr.contains( this->children[i]->mbr ) ) {
                                cerr << "At level " << level << ":" << endl;
                                cerr << "MBR does not contain all children MBR!" << endl;
                                cerr << "MBR: " << endl << mbr;
                                cerr << "MBR not in it: " << endl << this->children[i]->mbr;
                                cerr << "Tree output given to debug_tree_out.crh" << endl;
                                getRoot()->writeTreeToFile( "debug_tree_out.crh" );
                                exit(1);
                        }
                }
        }

        //max elements invariant
        if ( isLeaf() ) {
                if ( this->elements.size() > properties->maximum ) {
                        cerr << "At level " << level << ":" << endl;
                        cerr << "Maximum elements at leaf node invariant corrupt!" << endl;
                        cerr << this->elements.size() << " elements stored at checked node." << endl;
                        exit(1);
                }
        } else {
                if ( this->children.size() > properties->maximum ) {
                        cerr << "At level " << level << ":" << endl;
                        cerr << "Maximum children at internal node invariant corrupt!" << endl;
                        cerr << this->children.size() << " children stored at checked node." << endl;
                        exit(1);
                }
        }

        //min elements invariant
        if ( !this->isRoot() ) {
                if ( isLeaf() ) {
                        if ( this->elements.size() < properties->minimum ) {
                                cerr << "At level " << level << ":" << endl;
                                cerr << "Minimum elements at leaf node invariant corrupt!" << endl;
                                cerr << this->children.size() << " children stored at checked node." << endl;
                                cerr << this->elements.size() << " elements stored at checked node." << endl;
                                exit(1);
                        }
                } else {
                        if ( this->children.size() < properties->minimum ) {
                                cerr << "At level " << level << ":" << endl;
                                cerr << "Minimum children at internal node invariant corrupt!" << endl;
                                cerr << this->children.size() << " children stored at checked node." << endl;
                                cerr << this->elements.size() << " elements stored at checked node." << endl;
                                exit(1);
                        }
                }
        }

        //leaf depth invariant
        //only for this subtree
        checkDepth( getHeightEstimate(), level );

        //parent-child invariant
        if ( !isLeaf() ) {
                for ( unsigned int i=0; i<this->children.size(); i++ ) {
                        if ( this->children[i]->parent != this ) {
                                cerr << "At level " << level << ":" << endl;
                                cerr << "Childs parent is not me!" << endl;
                                cerr << this->children[i]->parent << " != " << this << endl;
                                exit(1);
                        }
                }
        }
        if ( !this->isRoot() ) {
                bool okidoki = false;
                for ( unsigned int i=0; i<this->parent->children.size(); i++ ) {
                        if ( this->parent->children[i] == this )
                                okidoki = true;
                }
                if ( !okidoki ) {
                        cerr << "At level " << level << ":" << endl;
                        cerr << "Im not a child of my parent!" << endl;
                        cerr << this << " is not a child of " << this->parent << endl;
                        exit(1);
                }
        }

        //no-clones
        if ( !isLeaf() ) {
                for ( unsigned int i=0; i<this->children.size(); i++ ) {
                        for ( unsigned int j=0; j<this->children.size(); j++ ) {
                                if ( (i!=j ) && ( this->children[i]==this->children[j] ) ) {
                                        cerr << "At level " << level << ":" << endl;
                                        cerr << "I have cloned children!" << endl;
                                        cerr << "At " << i << " " << this->children[i] << " == " << this->children[j] << " at " << j << endl;
                                        exit(1);
                                }
                        }
                }
        } else {
                for ( unsigned int i=0; i<this->elements.size(); i++ ) {
                        for ( unsigned int j=0; j<this->elements.size(); j++ ) {
                                if ( (i!=j ) && ( this->elements[i]->getID()==this->elements[j]->getID() ) ) {
                                        cerr << "At level " << level << ":" << endl;
                                        cerr << "I have cloned elements!" << endl;
                                        cerr << "At " << i << " " << this->elements[i] << " == " << this->elements[j] << " at " << j << endl;
                                        exit(1);
                                }
                        }
                }
        }
}

template< typename r_tree_variation >
int R_tree< r_tree_variation >::getHeightEstimate() const {
        const R_tree< r_tree_variation > *walk = this;
        while ( ! (walk->isLeaf() ) ) {
                walk = walk->children.at(0);
        }
        return walk->getDepth();
}

template< typename r_tree_variation >
int R_tree< r_tree_variation >::getLocalHeightEstimate() const {
        int c=0;
        const R_tree< r_tree_variation > *walk = this;
        while ( ! (walk->isLeaf() ) ) {
                walk = walk->children.at(0);
                c++;
        }
        return c;
}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::checkDepth( const int depth, const int level ) const {

        if ( isLeaf() ) {
                if ( getDepth() != depth ) {
                        cerr << "At level " << level << ":" << endl;
                        cerr << "Nodes are not at the same depth!" << endl;
                        cerr << depth << " != " << getDepth() << endl;
                        exit(1);
                }
        } else {
                for( unsigned int i=0; i<this->children.size(); i++ )
                        this->children[i]->checkDepth( depth, level );
        }

}
#endif

template< typename r_tree_variation >
double R_tree< r_tree_variation >::deadSpace( const BB_type bb1, const BB_type bb2 ) const {
        return Current_Metric::Volume( bb1.unionWith( bb2 ) ) - Current_Metric::Volume( bb1 ) - Current_Metric::Volume( bb2 );
}

template< typename r_tree_variation >
double R_tree< r_tree_variation >::areaEnlargement( BB_type bb1, BB_type bb2 ) const {

#ifdef _DEBUG
        cout << "areaEnlargement called" << endl; fflush( stdout );
        cout << "bb1: " << bb1 << endl; fflush( stdout );
        cout << "bb2: " << bb2 << endl; fflush( stdout );
        double temp = Current_Metric::Volume( bb1.unionWith( bb2 ) ) - Current_Metric::Volume( bb1 );
        cout << "areaEnlargement: " << temp << endl; fflush( stdout );
        return temp;
#else
        return Current_Metric::Volume( bb1.unionWith( bb2 ) ) - Current_Metric::Volume( bb1 );
#endif
}

template< typename r_tree_variation >
bool R_tree< r_tree_variation >::full() const {

#ifdef _DEBUG
        cout << "R_tree< r_tree_variation >::full() called" << endl; fflush( stdout );
#endif

        if ( this->isLeaf() )
                return properties->maximum <= this->elements.size();
        else
                return properties->maximum <= this->children.size();
}


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

template< typename r_tree_variation >
void R_tree< r_tree_variation >::nullifyProperties() {
        properties = 0;
        childIterator it = this->children.begin();
        for( ; it!=this->children.end(); it++ )
                (*it)->nullifyProperties();
}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::updateAllMBRs() {
        if ( this->isLeaf() )
                updateMBRLocal();
        else {
                for ( unsigned int i=0; i<this->children.size(); i++ )
                        this->children[i]->updateAllMBRs();
                updateMBRLocal();
        }
}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::updateMBRLocal() {
        if ( this->isLeaf() ) {
                mbr.clear();

                vector< BB_container* >::iterator it = this->elements.begin();
                for ( ; it!=this->elements.end(); it++ ) {
                        mbr.unite( *it );
                        //mbr = mbr.unite( *( *it ) );

#ifndef _HP
                        if ( !mbr.contains( *( *it ) ) ) {
                                cerr << "Weird!" << endl;
                                exit(1);
                        }
#endif

                }
        } else {
                mbr.clear();
                childIterator it = this->children.begin();
                for ( ; it!=this->children.end(); it++ ) {
                        mbr.unite( &( (*it)->mbr ) );
                        //mbr = mbr.unite( (*it)->mbr );

#ifndef _HP
                        if ( !mbr.contains( (*it)->mbr ) ) {
                                cerr << "Weird!" << endl;
                                exit(1);
                        }
#endif

                }
        }

#ifdef _GREATER_CHECK
        if ( !this->isLeaf() ) {
                vector< R_tree< r_tree_variation >* >::iterator it = this->children.begin();
                for ( ; it!=this->children.end(); it++ ) {
                        if ( !mbr.contains( (*it)->mbr ) ) {
                                cerr << "Error in updateMBRLocal! (non-leaf)" << endl;
                                exit(1);
                        }
                }
        }
#endif

}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::updateMBRNode() {
        updateAllMBRs();
        updateMBR();
}

template< typename r_tree_variation >
void *R_tree< r_tree_variation >::updateMBR() {
#ifdef _DEBUG
        cout << "Updating MBR" << endl; fflush( stdout );
#endif

        updateMBRLocal();

        if ( !this->isRoot() ) {

#ifdef _DEBUG
                cout << "\tDone Updating MBR, going for parent" << endl; fflush( stdout );
#endif

                return this->parent->updateMBR();
        } else {

#ifdef _DEBUG
                cout << "Done Updating MBRs!" << endl; fflush( stdout );
#endif

                return this;

        }
}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::containedIn( const BB_type *box, vector< int > *ret ) const {
        typedef typename vector< BB_container * >::const_iterator elemIterator;
        if ( this->isLeaf() ) {
                //add the elements satisfying the query
                elemIterator it = this->elements.begin();

                for ( ; it!=this->elements.end(); it++ ) {
#ifdef _NODE_COUNT
                        _node_count++;
#endif
                        if ( box->intersects( *it ) ) {
                                ret->push_back( (*it)->getID() );
                        }
                }
        } else {
                //recurse into the children of this node based on MBR
                childIterator it = this->children.begin();

                for( ; it!=this->children.end(); it++ ) {
#ifdef _NODE_COUNT
                        _node_count++;
#endif
                        if ( box->intersects( (*it)->mbr ) ) {
                                (*it)->containedIn( box, ret );
                        }
                }
        }
}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::intersects( const vector< double > &begin, const vector< double > &end, vector< int > *ret ) const {

        if ( this->isLeaf() ) {
                //add the elements satisfying the query
                vector< BB_container* >::const_iterator it = this->elements.begin();

                for ( ; it!=this->elements.end(); it++ ) {
#ifdef _NODE_COUNT
                                _node_count++;
#endif
                        if ( (*it)->lineIntersect( begin, end ) )
                                ret->push_back( (*it)->getID() );
                }

        } else {
                //recurse into the children of this node based on MBR
                childIterator it = this->children.begin();
                for( ; it!=this->children.end(); it++ ) {
#ifdef _NODE_COUNT
                                _node_count++;
#endif
                        if ( (*it)->mbr.lineIntersect( begin, end ) ) {
                                (*it)->intersects( begin, end, ret );
                        }
                }
        }

#ifdef _GREATER_CHECK
        checkEntireTree();
#endif

}

//should do sth about all this code duplication... function pointers?

template< typename r_tree_variation >
void R_tree< r_tree_variation >::intersects( const Point &point, vector< int > *ret ) const {

#ifdef _GREATER_CHECK
        checkEntireTree();
#endif

        if ( this->isLeaf() ) {

#ifdef _DEBUG
                cout << "Pointintersect in leaf, " << this->elements.size() << " elements stored." << endl; fflush( stdout );
#endif

                vector< BB_container* >::const_iterator it = this->elements.begin();

                for ( ; it!=this->elements.end(); it++ ) {
#ifdef _DEBUG
                        cout << "Visitting element " << (*it) << (*it) << endl; fflush( stdout );
                        cout << "With ID " << (*it)->getID() << endl; fflush( stdout );
                        cout << "Intersection detection..." << endl; fflush( stdout );
#endif
#ifdef _NODE_COUNT
                                _node_count++;
#endif
                        if ( (*it)->contains( point ) ) {
                                ret->push_back( (*it)->getID() );
                        }
                }

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

        } else {
                childIterator it = this->children.begin();
                for ( ; it!=this->children.end(); it++ ) {
#ifdef _NODE_COUNT
                                _node_count++;
#endif
                        if ( (*it)->mbr.contains( point ) ) {
                                (*it)->intersects( point, ret );
                        }
                }
        }

#ifdef _GREATER_CHECK
        checkEntireTree();
#endif

}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::intersects( const vector<double> &a, const double b, vector< int > *ret ) const {}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::neighboursOf( const BB_container *item, vector< int > *ret ) const {}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::neighboursOf( const vector<double> &point, NearestNeighbours<BB_container> *ns, MinDistTreeOrdering<BB_type, r_tree_variation> *mdt) const {

        
        for (unsigned int i = 0; i < this->elements.size(); i++) {
                ns->insert(NearestNeighbours<BB_container>::minimumDistance(point, this->elements.at(i)), this->elements.at(i));

                #ifdef _NODE_COUNT
                        _node_count++;
                #endif
        }

        // ga door met de children in volgorde van de mindist van hun boudning box
        vector<r_tree_variation *> ch(this->children);
        if (ch.size() > 0)
                mdt->sort(&ch);

        

        for (childIterator child = ch.begin(); child != ch.end(); child++) {
                // ga niet in kinderen als ret vol zit en mindist > max van de dists in ret
                if (ns->max <= ns->size && NearestNeighbours<BB_type>::minimumDistance(point, (*child)->getMBR()) >= ns->maxdist) {
                        break;
                }
                (*child)->neighboursOf(point, ns, mdt);

                #ifdef _NODE_COUNT
                        _node_count++;
                #endif
        }

        return;
};



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

template< typename r_tree_variation >
R_tree< r_tree_variation >::R_tree() {
        properties = new R_tree_props();
        properties->minimum=2;
        properties->maximum=4;
        init();
}

template< typename r_tree_variation >
R_tree< r_tree_variation >::R_tree( R_tree_props *props ) {
        properties = props;
        init();
}

template< typename r_tree_variation >
R_tree< r_tree_variation >::~R_tree() {
        if ( this->isRoot() && properties!=0 ) {
                //delete properties;
                nullifyProperties();
        }

        if ( !this->isLeaf() ) {
                childIterator it = this->children.begin();
                for( ; it!=this->children.end(); it++ )
                        delete *it;
        } else if ( deleteLeaves ) {
                vector< BB_container* >::iterator it = this->elements.begin();
                for( ; it!=this->elements.end(); it++ )
                        delete *it;
        }

#ifdef _ROOT_NODE_DESTRUCTION_WARNING
        if ( this->isRoot() )
                cerr << endl << "WARNING: ROOT NODE DESTROYED!" << endl;
#endif

}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::writeTreeToFile( string fn ) const {
        ofstream ofs;
        ofs.open( fn.c_str(), ios::out | ios::trunc );
        writeTreeToFile( ofs );
        ofs.close();
}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::readTreeFromFile( string fn ) const {
        ifstream ifs;
        ifs.open( fn.c_str(), ios::in );
        readTreeFromStream( ifs );
        ifs.close();
}

template< typename r_tree_variation >
vector< int > R_tree< r_tree_variation >::containedIn( const BB_type &box ) const {
#ifdef _NODE_COUNT
        resetNodeCount();
#endif
        vector< int > ret;

        containedIn( &box, &ret );

#ifdef _GREATER_CHECK
        checkEntireTree();
#endif

        return ret;
}

template< typename r_tree_variation >
vector< int > R_tree< r_tree_variation >::intersects( const vector< double > &begin, const vector< double > &end ) const {
#ifdef _NODE_COUNT
        resetNodeCount();
#endif
        vector< int > ret;

        intersects( begin, end, &ret );

        //return
        return ret;
}

template< typename r_tree_variation >
vector< int > R_tree< r_tree_variation >::intersects( const Point &point ) const {
#ifdef _NODE_COUNT
        resetNodeCount();
#endif
        vector< int > ret;

        intersects( point, &ret );

        return ret;
}

template< typename r_tree_variation >
vector< int > R_tree< r_tree_variation >::intersects( const vector<double> &a, const double b ) const {
#ifdef _NODE_COUNT
        resetNodeCount();
#endif
        cerr << "Error: plane intersection not yet implemented!" << endl;
        exit(1);
        return vector< int >();
}

template< typename r_tree_variation >
vector< int > R_tree< r_tree_variation >::neighboursOf( const BB_container *item ) const {
#ifdef _NODE_COUNT
        resetNodeCount();
#endif
        cerr << "Error: neighbour search not yet implemented!" << endl;
        exit(1);
        return vector< int >();
}


template< typename r_tree_variation >
vector< int > R_tree< r_tree_variation >::neighboursOf( const vector<double> &point, const unsigned int k ) const {
#ifdef _NODE_COUNT
        resetNodeCount();
#endif

        NearestNeighbours<BB_container> *ns = new NearestNeighbours<BB_container>(k);
        MinDistTreeOrdering<BB_type, r_tree_variation> *mdt = new MinDistTreeOrdering<BB_type, r_tree_variation>(point);

        neighboursOf( point, ns, mdt );

        vector<int> ret = *(ns->ids);
        delete ns;
        delete mdt;

        return ret;
}



template< typename r_tree_variation >
void R_tree< r_tree_variation >::printTreeInfo( ostringstream &oss ) const {
        int numNodes = 0;
        int numLeafs = 0;
        int height = this->getHeight();

        this->gatherTreeInfo( &numNodes, &numLeafs );

        oss << "Tree height: \t\t" << height << endl;
        oss << "Internal nodes: \t" << numNodes << endl;
        oss << "Leaf nodes: \t\t" << numLeafs << endl;

}

template< typename r_tree_variation >
void R_tree< r_tree_variation >::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

}

#endif

---