k-d tree implementation

Question

i have following code for trying to implement and analysis,

#include <iostream.h>
    #include "vector.h"

    /**
     * Quick illustration of a two-dimensional tree.
     * No abstraction here.
     */
    template <class Comparable>
    class KdTree
    {
      public:
        KdTree( ) : root( NULL ) { }

        void insert( const vector<Comparable> & x )
        {
            insert( x, root, 0 );
        }

        /**
         * Print items satisfying
         * low[ 0 ] <= x[ 0 ] <= high[ 0 ] and
         * low[ 1 ] <= x[ 1 ] <= high[ 1 ]
         */
        void printRange( const vector<Comparable> & low, 
                         const vector<Comparable> & high ) const
        {
            printRange( low, high, root, 0 );
        }

      private:
        struct KdNode
        {
            vector<Comparable> data;
            KdNode            *left;
            KdNode            *right;

            KdNode( const vector<Comparable> & item )
              : data( item ), left( NULL ), right( NULL ) { }
        };

        KdNode *root;

        void insert( const vector<Comparable> & x, KdNode * & t, int level )
        {
            if( t == NULL )
                t = new KdNode( x );
            else if( x[ level ] < t->data[ level ] )
                insert( x, t->left, 1 - level );
            else
                insert( x, t->right, 1 - level );
        }


        void printRange( const vector<Comparable> & low,
                         const vector<Comparable> & high,
                         KdNode *t, int level ) const
        {
            if( t != NULL )
            {
                if( low[ 0 ] <= t->data[ 0 ] && high[ 0 ] >= t->data[ 0 ] && 
                    low[ 1 ] <= t->data[ 1 ] && high[ 1 ] >= t->data[ 1 ] )
                    cout << "(" << t->data[ 0 ] << "," 
                                << t->data[ 1 ] << ")" << endl;

                if( low[ level ] <= t->data[ level ] )
                    printRange( low, high, t->left, 1 - level );
                if( high[ level ] >= t->data[ level ] )
                    printRange( low, high, t->right, 1 - level );
            }
        }
    };

        // Test program
        int main( )
        {
            KdTree<int> t;

            cout << "Starting program" << endl;
            for( int i = 300; i < 370; i++ )
            {
                vector<int> it( 2 );
                it[ 0 ] =  i;
                it[ 1 ] =  2500 - i;
                t.insert( it );
            }

            vector<int> low( 2 ), high( 2 );
            low[ 0 ] = 70;
            low[ 1 ] = 2186;
            high[ 0 ] = 1200;
            high[ 1 ] = 2200;

            t.printRange( low, high );

            return 0;
        }

problem is that ,here vector class is described very difficulty from source,so i want to use existing c++ STL vector,but dont know how to do it,please help me,for example how to use vector in insert procedure?and so on,please

Answer 1

Your code it's already compatible with STL: I just changed the headers, and mainly for readability, introduced a typedef:

#include <iostream>
#include <vector>
using namespace std;

/**
* Quick illustration of a two-dimensional tree.
* No abstraction here.
*/
template <class Comparable>
class KdTree
{
public:
    typedef vector<Comparable> tVec;

    KdTree( ) : root( NULL ) { }

    void insert( const tVec & x )
    {
        insert( x, root, 0 );
    }

    /**
    * Print items satisfying
    * low[ 0 ] <= x[ 0 ] <= high[ 0 ] and
    * low[ 1 ] <= x[ 1 ] <= high[ 1 ]
    */
    void printRange( const tVec & low,
                    const tVec & high ) const
    {
        printRange( low, high, root, 0 );
    }

private:
    struct KdNode
    {
        tVec data;
        KdNode            *left;
        KdNode            *right;

        KdNode( const tVec & item )
            : data( item ), left( NULL ), right( NULL ) { }
    };

    KdNode *root;

    void insert( const tVec & x, KdNode * & t, int level )
    {
        if( t == NULL )
            t = new KdNode( x );
        else if( x[ level ] < t->data[ level ] )
            insert( x, t->left, 1 - level );
        else
            insert( x, t->right, 1 - level );
    }


    void printRange( const tVec & low,
                    const tVec & high,
                    KdNode *t, int level ) const
    {
        if( t != NULL )
        {
            if( low[ 0 ] <= t->data[ 0 ] && high[ 0 ] >= t->data[ 0 ] &&
                    low[ 1 ] <= t->data[ 1 ] && high[ 1 ] >= t->data[ 1 ] )
                cout << "(" << t->data[ 0 ] << ","
                     << t->data[ 1 ] << ")" << endl;

            if( low[ level ] <= t->data[ level ] )
                printRange( low, high, t->left, 1 - level );
            if( high[ level ] >= t->data[ level ] )
                printRange( low, high, t->right, 1 - level );
        }
    }
};

// Test program
int main_kdtree(int, char **)
{
    typedef KdTree<int> tTree;
    tTree t;

    cout << "Starting program" << endl;
    for( int i = 300; i < 370; i++ )
    {
        tTree::tVec it( 2 );
        it[ 0 ] =  i;
        it[ 1 ] =  2500 - i;
        t.insert( it );
    }

    tTree::tVec low( 2 ), high( 2 );
    low[ 0 ] = 70;
    low[ 1 ] = 2186;
    high[ 0 ] = 1200;
    high[ 1 ] = 2200;

    t.printRange( low, high );

    return 0;
}

Output:

Starting program
(300,2200)
(301,2199)
....
(313,2187)
(314,2186)