orderings.h

Go to the documentation of this file.

/*
 *  Copyright (C) 2007  A.N. Yzelman
 *  Released under LGPL, see license.txt
 *
 *  Last modified at 24th of May, 2007, by A.N. Yzelman
 *  After that, modified at 13th of June, 2007, by R. van Kesteren
 *
 *  orderings.h: Definition of orderings on specific bounding boxes (and trees)
 *
 */

#ifndef _H_ORDERINGS
#define _H_ORDERINGS

//#define _DEBUG

#include "randomUtils.h"
#include "HilbertCoordinateMapper.h"

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

template < typename bb_type >
class Ordering {

   private:

        void swap( bb_type** arr, unsigned int x, unsigned int y ) const {
                bb_type* temp = arr[x];
                arr[x] = arr[y];
                arr[y] = temp;
        }

        //classical quicksort implementation, no (smart) pivotting
        unsigned int pivotise( bb_type** arr, unsigned int left, unsigned int right, unsigned int pivot ) const {
                const double pivotMin = this->getVal( arr[ pivot ] );

                swap( arr, pivot, right ); //swap pivot to the side

                unsigned int l_hold = left;

                for ( unsigned int i=left; i<right; i++ ) {
                        if ( this->getVal( arr[ i ] ) <= pivotMin ) {
                                swap( arr, l_hold, i );
                                l_hold++;
                        }
                }

                swap( arr, right, l_hold );

                return l_hold;
        }

        void quicksort( bb_type** arr, unsigned int left, unsigned int right ) const {
#ifdef _DEBUG
                cout << "QuickSort( " << arr << " , " << left << " , " << right << " )" << endl;
                fflush( stdout );
#endif
                if ( right <= left )
                        return;
                const unsigned int pivot = randomUtils::randomInt( left, right+1 );
                const unsigned int middle = pivotise( arr, left, right, pivot );
                if ( middle != 0 )
                        quicksort( arr, left, middle-1 );

                quicksort( arr, middle+1, right);
#ifdef _DEBUG
                cout << "Exitting QuickSort( " << arr << " , " << left << " , " << right << " )" << endl;
                fflush( stdout );
#endif
        }

        static void cannotCall() { cerr << "Cannot call functions on abstract Orderings!" << endl; exit( 1 ); }

   protected:

        //virtual double getVal( const bb_type * const in ) const { cannotCall(); return 0; }
        
        virtual double getVal( const bb_type * const in ) const = 0;

   public:

        typedef typename std::vector< bb_type* >::iterator curtypeIterator;

        virtual void split( vector< bb_type* > *input, int loc, vector< bb_type* > *set_one, vector< bb_type* > *set_two ) {
                sort( input );
                set_one->assign( input->begin(), input->begin() + loc );
                set_two->assign( input->begin() + loc, input->end() );
        }

        virtual bb_type* max( vector< bb_type* > *input ) const {
#ifndef _HP
                if ( input->size() == 0 ) {
                        cerr << "Tried to get the maximum of an empty set" << endl;
                        exit( 1 );
                }
#endif

                bb_type* ret = (*input)[0];
                double curmax = this->getVal( ret );

                //curtypeIterator it;
                //it = input->begin();
                //it++;
                //for ( ; it!=input->end(); it++ ) {
                //      const double cur = this->getVal( *it );
                for( unsigned int i=1; i<input->size(); i++ ) {
                        const double cur = this->getVal( (*input)[ i ] );
                        if ( curmax < cur ) {
                                curmax = cur;
                                //ret = *it;
                                ret = (*input)[ i ];
                        }
                }

                return ret;
        }

        virtual bb_type* min( vector< bb_type* > *input ) const {
#ifndef _HP
                if ( input->size() == 0 ) {
                        cerr << "Tried to get the maximum of an empty set" << endl;
                        exit( 1 );
                }
#endif

                bb_type* ret = (*input)[0];
                double curmin = this->getVal( ret );

                //curtypeIterator it = input->begin(); it++;
                //for ( ; it!=input->end(); it++ ) {
                //      const double cur = this->getVal( *it );
                for ( unsigned int i=1; i<input->size(); i++ ) {
                        const double cur = this->getVal( (*input)[ i ] );
                        if ( curmin > cur ) {
                                curmin = cur;
                                ret = (*input)[ i ];
                //              ret = *it;
                        }
                }

                return ret;
        }


        virtual void sort( vector< bb_type* > *input ) {

#ifdef _DEBUG
                cout << "Sorting..." << endl; fflush( stdout );
#endif
                bb_type** curarr = &( ( *input )[0] );
                const unsigned int n = input->size();
                quicksort( curarr, 0, n - 1 );
#ifdef _DEBUG
                cout << "Done Sorting!" << endl; fflush( stdout );
#endif

        }

        virtual ~Ordering() {}

};

template< typename cur_type >
class CURRENTORDERING: public Ordering< cur_type > {

  protected:
        virtual double getVal( const cur_type * const in ) const {
                return 0.0;
        }


  public:
        virtual cur_type* min( vector< cur_type* > *input ) const {
                return input->front();
        }
        
        virtual cur_type* max( vector< cur_type* > *input ) const {
                return input->back();
        }
        
        virtual void sort( vector< cur_type* > *input ) {
                return;
        }
        
};

template< typename cur_type >
class DistOrdering: public Ordering< cur_type > {

  protected:

        virtual double getVal( const cur_type * const in ) const {
                
                const unsigned int dim = in->getDimension();

                double ret = in->_mins[0] * in->_mins[0];
                for ( unsigned int i=1; i<dim; i++ )
                        ret += in->_mins[1] * in->_mins[1];
                return ret;
        }

  public:

};

template< int dim, typename cur_type >
class CubicLowCoorOrdering : public Ordering< cur_type > {

  protected:

        virtual double getVal( const cur_type* const item ) const {

                return item->_mins[ dim ];
        }

  public:

};

template< typename cur_type >
class HilbertOrdering2D: public Ordering< cur_type > {

        protected:

                virtual double getVal( const cur_type * const in ) const {
                        return HilbertCoordinateMapper::toHilbert2D( in->getCenterCoordinate() );
                }

};

template< typename cur_type >
class HilbertOrdering3D: public Ordering< cur_type > {

        protected:

                double* hilbertCache;
                unsigned int min;

                virtual double getVal( const cur_type * const inp ) const {
                        //const vector< double > centre = inp->getCenterCoordinate();
                        //cout << HilbertCoordinateMapper::toHilbert3D( &centre ) << " =?= " << hilbertCache[ inp->getID() - min ];

                        return hilbertCache[ inp->getID() - min ];
                }

        public:
                virtual void sort( vector< cur_type* > *input ) {
                        //find max and min
                        unsigned int max = (*input)[ 0 ]->getID();
                        min = (*input)[ 0 ]->getID();
                        for( unsigned int i=1; i<input->size(); i++ ) {
                                if ( (*input)[ i ]->getID() > max )
                                        max = (*input)[ i ]->getID();
                                if ( (*input)[ i ]->getID() < min )
                                        min = (*input)[ i ]->getID();
                        }

                        //build cache
                        hilbertCache = new double[ max - min + 1 ];
                        for( unsigned int i=0; i<input->size(); i++ ) {
                                const unsigned int id = (*input)[ i ]->getID();
                                vector< double > centre;
                                (*input)[ i ]->getCenterCoordinate( &centre );
                                hilbertCache[ id - min ] = HilbertCoordinateMapper::toHilbert3D( &centre );
                        }

                        Ordering< cur_type >::sort( input );

                        delete [] hilbertCache;
                }
};


template< typename cur_type, typename cur_tree >
class MinDistTreeOrdering : public Ordering< cur_tree > {

        protected:

        vector<double> p;


        virtual double getVal( const cur_tree * const intree ) const {
                const cur_type * in = intree->getMBR();

                const unsigned int dim = in->getDimension();
                double ret = 0;
                for ( unsigned int i = 0; i < dim; i++ )  {
                        if (p[i] < in->getMinCoordinateOnDimension(i)) {
                                ret += (in->getMinCoordinateOnDimension(i) - p[i]) * (in->getMinCoordinateOnDimension(i) - p[i]);
                        } else if (p[i] > in->getMaxCoordinateOnDimension(i)) {
                                ret += (p[i] - in->getMaxCoordinateOnDimension(i)) * (p[i] - in->getMaxCoordinateOnDimension(i));
                        } else {
                                ret += 0;
                        }
                }
                return ret;
        }

        public:
        MinDistTreeOrdering(vector<double> point) : p(point) { }
};


#endif

---