source: GTP/trunk/Lib/Vis/Preprocessing/src/MyHeap.h @ 1099

#ifndef MYHEAP_H
#define MYHEAP_H

#include <vector>

/** This class implementas a heap  for
        use as a priority queue.

        The class aditionally implements efficient remove
        of arbitrary elements.
*/

namespace GtpVisibilityPreprocessor {

const static int NOT_IN_HEAP = -100;

class Heapable
{
public:
    Heapable() { NotInHeap(); HeapKey(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(int t) { mPosition = t; }

    inline void  HeapKey(float k) { mPriority = k; }
    inline float HeapKey() const  { return mPriority; }

protected:

    float mPriority;
    int mPosition;
};


class MyHeap
{
public:
    MyHeap() { }
    MyHeap(unsigned int n) : mBuffer(n) { }

    void Push(Heapable *t) { Push(t, t->HeapKey()); }
    void Push(Heapable *, float);
    bool Update(Heapable *t) { return Update(t, t->HeapKey()); }
    bool Update(Heapable *, float);

    unsigned int Size() const { return (unsigned int)mBuffer.size(); }
        bool Empty() const {return mBuffer.empty(); }
    Heapable       *Item(unsigned int i)       { return mBuffer[i]; }
    const Heapable *Item(unsigned int i) const { return mBuffer[i]; }
    Heapable *Pop();
        Heapable *Top() { return (mBuffer.empty() ? (Heapable *)NULL : mBuffer.front()); }
    Heapable *Erase(Heapable *);

protected:

    void Place(Heapable *x, unsigned int i);
    void Swap(unsigned int i, unsigned int j);

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

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

        std::vector<Heapable* > mBuffer;
};

}

// MYHEAP_H
#endif