DataStructures::Heap< weight_type, data_type, isMaxHeap > Class Template Reference

#include <DS_Heap.h>

Inheritance diagram for DataStructures::Heap< weight_type, data_type, isMaxHeap >:

List of all members.

Classes
struct	HeapNode
Public Member Functions
void	Clear (bool doNotDeallocateSmallBlocks, const char *file, unsigned int line)
	Heap ()
data_type &	operator[] (const unsigned int position) const
data_type	Peek (const unsigned startingIndex=0) const
weight_type	PeekWeight (const unsigned startingIndex=0) const
data_type	Pop (const unsigned startingIndex)
void	Push (const weight_type &weight, const data_type &data, const char *file, unsigned int line)
void	PushSeries (const weight_type &weight, const data_type &data, const char *file, unsigned int line)
	If you are going to push a list of items, where the weights of the items on the list are in order and follow the heap order, PushSeries is faster than Push()
unsigned	Size (void) const
void	StartSeries (void)
	Call before calling PushSeries, for a new series of items.
	~Heap ()
Protected Member Functions
unsigned	LeftChild (const unsigned i) const
unsigned	Parent (const unsigned i) const
unsigned	RightChild (const unsigned i) const
void	Swap (const unsigned i, const unsigned j)
Protected Attributes
DataStructures::List< HeapNode >	heap
bool	optimizeNextSeriesPush

---

Detailed Description

template<class weight_type, class data_type, bool isMaxHeap>
class DataStructures::Heap< weight_type, data_type, isMaxHeap >

Definition at line 27 of file DS_Heap.h.

---

Constructor & Destructor Documentation

template<class weight_type , class data_type , bool isMaxHeap>

DataStructures::Heap< weight_type, data_type, isMaxHeap >::Heap

(

)

Definition at line 62 of file DS_Heap.h.

    {
        optimizeNextSeriesPush=false;
    }

template<class weight_type , class data_type , bool isMaxHeap>

DataStructures::Heap< weight_type, data_type, isMaxHeap >::~Heap

(

)

Definition at line 68 of file DS_Heap.h.

    {
        //Clear(true, _FILE_AND_LINE_);
    }

---

Member Function Documentation

template<class weight_type , class data_type , bool isMaxHeap>

void DataStructures::Heap< weight_type, data_type, isMaxHeap >::Clear	(	bool	doNotDeallocateSmallBlocks,
		const char *	file,
		unsigned int	line
	)

Definition at line 243 of file DS_Heap.h.

Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GenerateDisjktraMatrix().

    {
        heap.Clear(doNotDeallocateSmallBlocks, file, line);
    }

template<class weight_type , class data_type , bool isMaxHeap>

unsigned DataStructures::Heap< weight_type, data_type, isMaxHeap >::LeftChild

(

const unsigned

i

)

const [inline, protected]

Definition at line 260 of file DS_Heap.h.

    {
        return i*2+1;
    }

template<class weight_type , class data_type , bool isMaxHeap>

data_type & DataStructures::Heap< weight_type, data_type, isMaxHeap >::operator[]

(

const unsigned int

position

)

const [inline]

Definition at line 249 of file DS_Heap.h.

    {
        return heap[position].data;
    }

template<class weight_type , class data_type , bool isMaxHeap>

unsigned DataStructures::Heap< weight_type, data_type, isMaxHeap >::Parent

(

const unsigned

i

)

const [inline, protected]

Definition at line 272 of file DS_Heap.h.

References RakAssert.

    {
#ifdef _DEBUG
        RakAssert(i!=0);
#endif
        return (i-1)/2;
    }

template<class weight_type , class data_type , bool isMaxHeap>

data_type DataStructures::Heap< weight_type, data_type, isMaxHeap >::Peek

(

const unsigned

startingIndex = 0

)

const [inline]

Definition at line 231 of file DS_Heap.h.

    {
        return heap[startingIndex].data;
    }

template<class weight_type , class data_type , bool isMaxHeap>

weight_type DataStructures::Heap< weight_type, data_type, isMaxHeap >::PeekWeight

(

const unsigned

startingIndex = 0

)

const [inline]

Definition at line 237 of file DS_Heap.h.

Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GenerateDisjktraMatrix().

    {
        return heap[startingIndex].weight;
    }

template<class weight_type , class data_type , bool isMaxHeap>

data_type DataStructures::Heap< weight_type, data_type, isMaxHeap >::Pop

(

const unsigned

startingIndex

)

Definition at line 154 of file DS_Heap.h.

Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GenerateDisjktraMatrix().

    {
        // While we have children, swap out with the larger of the two children.

        // This line will assert on an empty heap
        data_type returnValue=heap[startingIndex].data;

        // Move the last element to the head, and re-heapify
        heap[startingIndex]=heap[heap.Size()-1];

        unsigned currentIndex,leftChild,rightChild;
        weight_type currentWeight;
        currentIndex=startingIndex;
        currentWeight=heap[startingIndex].weight;
        heap.RemoveFromEnd();

#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
        while (1)
        {
            leftChild=LeftChild(currentIndex);
            rightChild=RightChild(currentIndex);
            if (leftChild >= heap.Size())
            {
                // Done
                return returnValue;
            }
            if (rightChild >= heap.Size())
            {
                // Only left node.
                if ((isMaxHeap==true && currentWeight < heap[leftChild].weight) ||
                    (isMaxHeap==false && currentWeight > heap[leftChild].weight))
                        Swap(leftChild, currentIndex);

                return returnValue;
            }
            else
            {
                // Swap with the bigger/smaller of the two children and continue
                if (isMaxHeap)
                {
                    if (heap[leftChild].weight <= currentWeight && heap[rightChild].weight <= currentWeight)
                        return returnValue;

                    if (heap[leftChild].weight > heap[rightChild].weight)
                    {
                        Swap(leftChild, currentIndex);
                        currentIndex=leftChild;
                    }
                    else
                    {
                        Swap(rightChild, currentIndex);
                        currentIndex=rightChild;
                    }
                }
                else
                {
                    if (heap[leftChild].weight >= currentWeight && heap[rightChild].weight >= currentWeight)
                        return returnValue;

                    if (heap[leftChild].weight < heap[rightChild].weight)
                    {
                        Swap(leftChild, currentIndex);
                        currentIndex=leftChild;
                    }
                    else
                    {
                        Swap(rightChild, currentIndex);
                        currentIndex=rightChild;
                    }
                }
            }
        }
    }

template<class weight_type, class data_type, bool isMaxHeap>

void DataStructures::Heap< weight_type, data_type, isMaxHeap >::Push	(	const weight_type &	weight,
		const data_type &	data,
		const char *	file,
		unsigned int	line
	)

Definition at line 119 of file DS_Heap.h.

Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GenerateDisjktraMatrix().

    {
        unsigned currentIndex = heap.Size();
        unsigned parentIndex;
        heap.Insert(HeapNode(weight, data), file, line);
        while (currentIndex!=0)
        {
            parentIndex = Parent(currentIndex);
#ifdef _MSC_VER
#pragma warning( disable : 4127 ) // warning C4127: conditional expression is constant
#endif
            if (isMaxHeap)
            {
                if (heap[parentIndex].weight < weight)
                {
                    Swap(currentIndex, parentIndex);
                    currentIndex=parentIndex;
                }
                else
                    break;
            }
            else
            {
                if (heap[parentIndex].weight > weight)
                {
                    Swap(currentIndex, parentIndex);
                    currentIndex=parentIndex;
                }
                else
                    break;
            }
        }
    }

template<class weight_type, class data_type, bool isMaxHeap>

void DataStructures::Heap< weight_type, data_type, isMaxHeap >::PushSeries	(	const weight_type &	weight,
		const data_type &	data,
		const char *	file,
		unsigned int	line
	)

Definition at line 74 of file DS_Heap.h.

    {
        if (optimizeNextSeriesPush==false)
        {
            // If the weight of what we are inserting is greater than / less than in order of the heap of every sibling and sibling of parent, then can optimize next push
            unsigned currentIndex = heap.Size();
            unsigned parentIndex;
            if (currentIndex>0)
            {
                for (parentIndex = Parent(currentIndex); parentIndex < currentIndex; parentIndex++)
                {
                    if (isMaxHeap)
                    {
                        // Every child is less than its parent
                        if (weight>heap[parentIndex].weight)
                        {
                            // Can't optimize
                            Push(weight,data,file,line);
                            return;
                        }
                    }
                    else
                    {
                        // Every child is greater than than its parent
                        if (weight<heap[parentIndex].weight)
                        {
                            // Can't optimize
                            Push(weight,data,file,line);
                            return;
                        }
                    }
                }
            }

            // Parent's subsequent siblings and this row's siblings all are less than / greater than inserted element. Can insert all further elements straight to the end
            heap.Insert(HeapNode(weight, data), file, line);
            optimizeNextSeriesPush=true;
        }
        else
        {
            heap.Insert(HeapNode(weight, data), file, line);
        }
    }

template<class weight_type , class data_type , bool isMaxHeap>

unsigned DataStructures::Heap< weight_type, data_type, isMaxHeap >::RightChild

(

const unsigned

i

)

const [inline, protected]

Definition at line 266 of file DS_Heap.h.

    {
        return i*2+2;
    }

template<class weight_type , class data_type , bool isMaxHeap>

unsigned DataStructures::Heap< weight_type, data_type, isMaxHeap >::Size

(

void

)

const

Definition at line 254 of file DS_Heap.h.

Referenced by DataStructures::WeightedGraph< node_type, weight_type, allow_unlinkedNodes >::GenerateDisjktraMatrix().

    {
        return heap.Size();
    }

template<class weight_type, class data_type, bool isMaxHeap>

void DataStructures::Heap< weight_type, data_type, isMaxHeap >::StartSeries

(

void

)

[inline]

Definition at line 42 of file DS_Heap.h.

{optimizeNextSeriesPush=false;}

template<class weight_type , class data_type , bool isMaxHeap>

void DataStructures::Heap< weight_type, data_type, isMaxHeap >::Swap	(	const unsigned	i,
		const unsigned	j
	)		[protected]

Definition at line 281 of file DS_Heap.h.

    {
        HeapNode temp;
        temp=heap[i];
        heap[i]=heap[j];
        heap[j]=temp;
    }

---

Member Data Documentation

template<class weight_type, class data_type, bool isMaxHeap>

DataStructures::List<HeapNode> DataStructures::Heap< weight_type, data_type, isMaxHeap >::heap [protected]

Definition at line 57 of file DS_Heap.h.

template<class weight_type, class data_type, bool isMaxHeap>

bool DataStructures::Heap< weight_type, data_type, isMaxHeap >::optimizeNextSeriesPush [protected]

Definition at line 58 of file DS_Heap.h.

---

The documentation for this class was generated from the following file:

• DS_Heap.h