source: GTP/trunk/Lib/Vis/Preprocessing/src/FlexibleHeap.h @ 2559

#ifndef FLEXIBLEHEAP_H
#define FLEXIBLEHEAP_H

#include <vector>


namespace GtpVisibilityPreprocessor {

const static int NOT_IN_HEAP = -100;

/** This class implements an element for a heap.
        Classes using the heap should be inherited from this class.
*/
class Heapable
{
public:
        
        Heapable(): mPriority(0) { NotInHeap(); SetPriority(0.0f); }

        inline bool IsInHeap() { return mPosition != NOT_IN_HEAP; }
        inline void NotInHeap() { mPosition = NOT_IN_HEAP; }
        inline int GetHeapPos() { return mPosition; }
        inline void SetHeapPos(const int t) { mPosition = t; }

        inline void  SetPriority(const float k) { mPriority = k; }
        //inline float GetPriority() const  { return mPriority; }
        virtual float GetPriority() const = 0;

protected:

        float mPriority;
        int mPosition;
};


/** This class implements a flexible heap for use as a priority queue.
        Unlike the stl priority_queue, the class allows access to all 
        elements. It implements efficient insertion routines and remove routines
        of arbitrary elements.
*/
template<typename T>
class FlexibleHeap
{
public:
        FlexibleHeap() { }
        FlexibleHeap(const unsigned int n): mBuffer(n) { }

        void Push(T t);
        void Push(T t, const float priority);
        bool Update(T t);
        bool Update(T t, const float priority);

        inline unsigned int Size() const;
        inline bool Empty() const;
        inline T Item(const unsigned int i);
        inline const T Item(const unsigned int i) const;
        T Pop();
        inline T Top() const;
        /** Erases the element from the heap.
        */
        T Erase(T);

        void Reserve(const size_t n);

protected:

        inline void Place(T x, const unsigned int i);
        inline void Swap(const unsigned int i, const unsigned int j);

        inline unsigned int Parent(const unsigned int i) const { return (i - 1) / 2; }
        inline unsigned int Left(const unsigned int i) const { return 2 * i + 1; }
        inline unsigned int Right(const unsigned int i) const { return 2 * i + 2; }

        void UpHeap(const unsigned int i);
        void DownHeap(const unsigned int i);


        ///////
        
        std::vector<T> mBuffer;
};




/******************************************************************/
/*                 FexibleHeap implementation                     */
/******************************************************************/


template <typename T>
void FlexibleHeap<T>::Push(T t) 
{ 
        Push(t, t->GetPriority()); 
}


template <typename T>
bool FlexibleHeap<T>::Update(T t) 
{ 
        return Update(t, t->GetPriority()); 
}


template <typename T>
inline unsigned int FlexibleHeap<T>::Size() const 
{ 
        return (unsigned int)mBuffer.size(); 
}

template <typename T>
void FlexibleHeap<T>::Reserve(const size_t n) 
{ 
        mBuffer.reserve(n); 
}

template <typename T>
inline bool FlexibleHeap<T>::Empty() const 
{
        return mBuffer.empty(); 
}


template <typename T>
inline T FlexibleHeap<T>::Item(const unsigned int i) 
{ 
        return mBuffer[i]; 
}


template <typename T>
inline const T FlexibleHeap<T>::Item(const unsigned int i) const 
{ 
        return mBuffer[i]; 
}


template <typename T>
inline T FlexibleHeap<T>::Top() const 
{ 
        return (mBuffer.empty() ? (T)NULL : mBuffer.front()); 
}


template <typename T>
inline void FlexibleHeap<T>::Place(T x, const unsigned int i)
{
        mBuffer[i] = x;
        x->SetHeapPos(i);
}


template <typename T>
void FlexibleHeap<T>::Swap(const unsigned int i, const unsigned int j)
{
        T tmp = mBuffer[i];

        Place(mBuffer[j], i);
        Place(tmp, j);
}


template <typename T>
void FlexibleHeap<T>::UpHeap(const unsigned int i)
{
        T moving = mBuffer[i];
        unsigned int index = i;
        unsigned int p = Parent(i);

        while ((index > 0) && (moving->GetPriority() > mBuffer[p]->GetPriority()))
        {
                Place(mBuffer[p], index);
                index = p;
                p = Parent(p);
        }

        if (index != i)
        {
                Place(moving, index);
        }
}


template <typename T>
void FlexibleHeap<T>::DownHeap(const unsigned int i)
{
        T moving = mBuffer[i];

        unsigned int index = i;
        unsigned int l = Left(i);
        unsigned int r = Right(i);
        unsigned int largest;

        while (l < (int)mBuffer.size())
        {
                if ((r < (unsigned int)mBuffer.size()) && (mBuffer[l]->GetPriority() < mBuffer[r]->GetPriority()))
                        largest = r;
                else 
                        largest = l;

                if (moving->GetPriority() < mBuffer[largest]->GetPriority())
                {
                        Place(mBuffer[largest], index);
                        index = largest;
                        l = Left(index);
                        r = Right(index);
                }
                else
                {
                        break;
                }
        }

        if (index != i)
        {
                Place(moving, index);
        }
}


template <typename T>
void FlexibleHeap<T>::Push(T t, const float v)
{
        t->SetPriority(v);

        unsigned int i = (unsigned int)mBuffer.size();

        t->SetHeapPos(i);
        mBuffer.push_back(t);

        UpHeap(i);
}

template <typename T>
bool FlexibleHeap<T>::Update(T t, const float v)
{
        if (t->IsInHeap())
                return false;

        t->SetPriority(v);

        const unsigned int i = t->GetHeapPos();

        if ((i > 0) && (v > mBuffer[Parent(i)]->GetPriority()))
                UpHeap(i);
        else
                DownHeap(i);

        return true;
}

template <typename T>
T FlexibleHeap<T>::Pop()
{
        if (mBuffer.empty()) 
                return NULL;

        Swap(0, (int)mBuffer.size() - 1);

        T dead = mBuffer.back();
        mBuffer.pop_back();

        if (!mBuffer.empty())
                DownHeap(0);

        dead->NotInHeap();

        return dead;
}


template <typename T>
T FlexibleHeap<T>::Erase(T t)
{
        if (!t->IsInHeap()) 
                return (T)NULL;

        const int i = t->GetHeapPos();

        Swap(i, (int)mBuffer.size() - 1);
        
        mBuffer.pop_back();
        t->NotInHeap();

        if (i < (int)mBuffer.size())
        {
        if (mBuffer[i]->GetPriority() < t->GetPriority())
                DownHeap(i);
        else
                UpHeap(i);
        }

        return t;
}

}

// FLEXIBLEHEAP_H
#endif