ok, so yesterday in EU4 I've got a little too greedy, kicked the shit out of a neighbour country and its allies, and took a little too much from their countries ( including vasalizing one of them by force, and taking a bit land from another ) so they made a coalition against me, and to regenerate before yet another war I turned off the game and thought I need to relax in a different way.

I'm aiming in fixing the reaction fire mechanics, so I wanted to use a priority queue, but then I thought that the regular priority que doesn't my full needs in my project, so it is likely it wouldn't fit yours here, hence I've got a fun attitude of making a nice heap that would meet most of my needs ( I still will need to expand it a little for my project ) and sharing it.

I've used __forceinline when I wanted to be totally sure the compiler will inline the code. I also tried to bring things up if possible, so that is why I've made static all the metods that don't use a field, or a nonstatic method, because not passing the "this" pointer saves time. That way I got both : speed as if all that was typed directly in the code, and readability - and thanks to this I could do things like bitwise shifts, instead of multiplying/dividing by 2, because things like that are hidden behind meaningful names that describe my intentions.

The reason why I did this in 3 ways ( defined a method outside the class, defined it inside the class, defined inside and use __forceinline ) is because I wanted respectively: to be sure that the compiler will generate a function call, to suggest that a method can be inlined if the compiler sees this as an optimization, to make sure, that the piece of code will be inlined.

I know you are compiling on different platforms, so this should do the trick

`#ifdef _MSC_VER`

#define __forceinline __forceinline

#else

#define __forceinline inline

#endif

so here it is:

`template<`

typename DataType,

typename HeapIndexer = DirectIndexer,

typename HeapRelation = std::greater_equal<DataType>,

template <typename> class IndexParameterDefinition = PassByValue,

template <typename> class DataParameterDefinition = PassByValue

>

class Heap

{

private:

static const size_t TopIndex = 1;

public:

typedef typename IndexParameterDefinition<typename HeapIndexer::IndexingType>::PassedValue Index;

typedef typename DataParameterDefinition<DataType>::PassedValue Data;

Heap(const std::vector<DataType> data);

__forceinline const size_t& Size()const

{

return _heapSize;

}

const DataType& operator[](const Index indexToBrowseWith)const;

const DataType& Top()const

{

return _heapData[TopIndex];

}

void SetValue(const Index index, Data dataType);

__forceinline void Pop()

{

RemoveInternal(TopIndex);

HeapDown(TopIndex);

}

void Remove(const Index index)

{

const size_t indexToRemoveAt = _indexer.ToRawIndex(index);

RemoveInternal(indexToRemoveAt);

HeapifyInternal(indexToRemoveAt);

}

const bool IsEmpty()const

{

return _heapSize == 0;

}

void Clear();

private:

void HeapifyInternal(const size_t index);

void HeapDown(const size_t index);

size_t GetIndexOfHighestInTercet(const size_t index)const;

void HeapUp(const size_t index);

void Swap(const size_t leftIndex, const size_t rightIndex);

void SetMockOnZeroIndex();

void RemoveInternal(const size_t index)

{

Swap(index, _heapSize);

_heapSize--;

}

bool ShouldLeftsideBeHigherInHeap(const size_t leftsideIndex, const size_t rightsideIndex)const

{

return _shouldLeftGoUp(_heapData[leftsideIndex],_heapData[rightsideIndex]);

}

bool NeedsUpHeaping(const size_t index)const

{

const size_t parent = GetParent(index);

https:// if index = 1, then parent will be equal to 0. this is the only situation where an index doesn't have a legal parent.

return parent && _shouldLeftGoUp(_heapData[index],_heapData[parent]);

}

__forceinline static size_t GetLeftChild(const size_t index)

{

return index << 1; https:// multiply by 2

}

__forceinline static size_t GetRightChild(const size_t index)

{

return GetLeftChild(index) + 1; https:// GetLeftChild(...) is forced inline, so no overhead.

}

__forceinline static size_t GetParent(const size_t index)

{

return index >> 1; https:// divide by 2

}

__forceinline bool IsValidChild(const size_t index)const

{

return index <= _heapSize;

}

https:// an assumption that allows the optimization:

https:// the index of the parent given to this method is always acquired

https:// by using the GetParent method on a legal index inside the

__forceinline static bool IsParentOnHeap(const size_t indexOfAParent)

{

https:// index is in range 0 to 2^32-1, so 'index' returns the same bool value as 'index>0'

return indexOfAParent;

}

std::vector<DataType> _heapData;

HeapIndexer _indexer;

HeapRelation _shouldLeftGoUp;

size_t _heapSize;

};

template<

typename DataType,

typename HeapIndexer,

typename HeapRelation,

template <typename> class IndexParameterDefinition,

template <typename> class DataParameterDefinition

>

const DataType& Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::operator[](const Index indexToBrowseWith)const

{

return _heapData[ _indexer.ToRawIndex(indexToBrowseWith) ];

}

template<

typename DataType,

typename HeapIndexer,

typename HeapRelation,

template <typename> class IndexParameterDefinition,

template <typename> class DataParameterDefinition

>

void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::Swap(const size_t leftIndex, const size_t rightIndex)

{

std::swap(_heapData[leftIndex], _heapData[rightIndex]);

_indexer.Swap(leftIndex, rightIndex);

}

template<

typename DataType,

typename HeapIndexer,

typename HeapRelation,

template <typename> class IndexParameterDefinition,

template <typename> class DataParameterDefinition

>

void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::HeapUp(const size_t index)

{

size_t reciever = GetParent(index);

size_t donor = index;

while(IsParentOnHeap(reciever) && ShouldLeftsideBeHigherInHeap(donor, reciever)) https:// a small optimization

{

Swap(reciever, donor);

donor = reciever;

reciever = GetParent(reciever);

}

}

template<

typename DataType,

typename HeapIndexer,

typename HeapRelation,

template <typename> class IndexParameterDefinition,

template <typename> class DataParameterDefinition

>

size_t Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::GetIndexOfHighestInTercet(const size_t index)const

{

size_t higherItemIndex = index;

const size_t leftChild = GetLeftChild(index);

const size_t rightChild = GetRightChild(index);

if(IsValidChild(leftChild) && ShouldLeftsideBeHigherInHeap(leftChild, higherItemIndex))

{

higherItemIndex = leftChild;

}

if(IsValidChild(rightChild) && ShouldLeftsideBeHigherInHeap(rightChild, higherItemIndex))

{

higherItemIndex = rightChild;

}

return higherItemIndex;

}

template<

typename DataType,

typename HeapIndexer,

typename HeapRelation,

template <typename> class IndexParameterDefinition,

template <typename> class DataParameterDefinition

>

void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::HeapifyInternal(const size_t index)

{

if(NeedsUpHeaping(index))

{

HeapUp(index);

}else

{

HeapDown(index);

}

}

template<

typename DataType,

typename HeapIndexer,

typename HeapRelation,

template <typename> class IndexParameterDefinition,

template <typename> class DataParameterDefinition

>

void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::HeapDown(const size_t index)

{

size_t donor = index;

size_t reciever = GetIndexOfHighestInTercet(donor);

while(donor != reciever)

{

Swap(donor,reciever);

donor = reciever;

reciever = GetIndexOfHighestInTercet(reciever);

}

}

template<

typename DataType,

typename HeapIndexer,

typename HeapRelation,

template <typename> class IndexParameterDefinition,

template <typename> class DataParameterDefinition

>

void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::SetValue(const Index index, Data dataType)

{

const size_t internalIndex = _indexer.ToRawIndex(index);

_heapData[internalIndex] = dataType;

HeapifyInternal(internalIndex);

}

template<

typename DataType,

typename HeapIndexer,

typename HeapRelation,

template <typename> class IndexParameterDefinition,

template <typename> class DataParameterDefinition

>

Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::Heap(const std::vector<DataType> data)

: _heapSize(data.size())

{

https:// add 0 index mock value

SetMockOnZeroIndex();

for(auto currentDataItem = data.begin(); currentDataItem != data.end(); ++currentDataItem)

{

_heapData.push_back(*currentDataItem);

}

const size_t halfOfHeap = _heapSize / 2;

for(size_t currentIndex = halfOfHeap; currentIndex >= TopIndex; --currentIndex)

{

HeapDown(currentIndex);

}

}

template<

typename DataType,

typename HeapIndexer,

typename HeapRelation,

template <typename> class IndexParameterDefinition,

template <typename> class DataParameterDefinition

>

void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::Clear()

{

_heapData.clear();

_heapSize = 0;

_indexer.Clear();

SetMockOnZeroIndex();

}

template<

typename DataType,

typename HeapIndexer,

typename HeapRelation,

template <typename> class IndexParameterDefinition,

template <typename> class DataParameterDefinition

>

void Heap<DataType, HeapIndexer, HeapRelation,IndexParameterDefinition,DataParameterDefinition>::SetMockOnZeroIndex()

{

_indexer.Add (Index(), 0);

_heapData.push_back(DataType());

}

I've wrote two simple heap indexers:

the default one, which allows direct indexing, and takes just one byte of memory

`struct DirectIndexer`

{

typedef size_t IndexingType;

__forceinline size_t ToRawIndex(const size_t& indirectIndex)const

{

return indirectIndex;

}

https:// no need to handle mapping in a direct indexer :)

https:// calls to those method should be removed from the binary when compiled with -o2

void Add(const size_t, const size_t){}

void Swap(const size_t, const size_t){}

void Clear(){}

};

a templated default mapped indexer ( for example to be able to map the things in the heap with strings, points or whatever you may wish ) - this one weights 40bytes

`template<typename IndexType>`

struct Indexer

{

typedef typename IndexType IndexingType;

__forceinline size_t ToRawIndex(const IndexType& indirectIndex)

{

return _indexToInternalMap[indirectIndex];

}

void Add(const IndexType& indirectIndex, const size_t directIndex)

{

_indexToInternalMap[indirectIndex] = directIndex;

_internalToIndexMap.push_back( indirectIndex );

}

void Swap(const size_t leftDirectIndex, const size_t rightDirectIndex)

{

const IndexType& leftIndirectIndex = _internalToIndexMap[leftDirectIndex];

const IndexType& rightIndirectIndex = _internalToIndexMap[rightDirectIndex];

std::swap(_internalToIndexMap[leftDirectIndex], _internalToIndexMap[rightDirectIndex]);

std::swap(_indexToInternalMap[leftIndirectIndex], _indexToInternalMap[rightIndirectIndex]);

}

void Clear()

{

_internalToIndexMap.clear();

_indexToInternalMap.clear();

}

private:

std::map<IndexType,size_t> _indexToInternalMap;

std::vector<IndexType> _internalToIndexMap;

};

I also have given an option to chose how to pass the parameters to the public methods, whether it would be by value or by reference, thanks to these two guys:

`template<typename T>`

struct PassByValue

{

typedef T PassedValue;

};

`template<typename T>`

struct PassByReference

{

typedef T& PassedValue;

};

finally, I've made simplified templates, because mostly the change will be between the type of data hold and the type of index, so I've made these four guys, all with default way of passing value to the public methods, and relation set accordingly to their names.

`template<typename DataType>`

class MaxHeap : public Heap<DataType>{};

`template<typename DataType>`

class MinHeap : public Heap<DataType,DirectIndexer,std::less_equal<DataType>>

{

public:

MinHeap(const std::vector<DataType> data) : Heap(data){}

};

`template<typename DataType, typename IndexType>`

class IndexedMaxHeap : public Heap<DataType, Indexer<IndexType>>{};

`template<typename DataType, typename IndexType>`

class IndexedMinHeap : public Heap<DataType, Indexer<IndexType>, std::less_equal<DataType>>{};

I've made a lot of automated, randomized tests ( I was hitting hard the part with removing items from an arbitrary index, and tested the mechanism above 500 milions of times on small and medium heap sizes ( <50, 10000 elements respectively ) and with bigger or smaller duplicate value ratio ( due to setting the value cap for 50 to 32 thousand ( the max rand value ) ), and in total there was above 1000000000 tests of all the heaps mechanisms in total).

the method I was checking the heap property preserved at all times is

`template<typename T>`

bool IsChildInRightRelationsWithParent(const T& child, const T& parent)

{

#ifdef _MIN_HEAP_

return child >= parent;

#else

return child <= parent;

#endif

}

template<typename T>

bool RecurrentCheck(const T& heap, const size_t index)

{

const size_t size = heap.Size();

const size_t leftChild = index * 2;

const size_t rightChild = leftChild + 1;

const bool hasLeftChild = leftChild <= size;

const bool hasRightChild = rightChild <= size;

const bool leftChildOK = (hasLeftChild && IsChildInRightRelationsWithParent(heap[leftChild] , heap[index])) || !hasLeftChild;

const bool rightChildOK = ((hasRightChild) && IsChildInRightRelationsWithParent(heap[rightChild] , heap[index])) || !hasRightChild;

const bool rightIsOk = (!hasRightChild) || RecurrentCheck(heap, rightChild);

const bool leftIsOk = (!hasLeftChild) || RecurrentCheck(heap, leftChild);

const bool isEverythingAllRight = leftChildOK && rightChildOK && leftIsOk && rightIsOk;

}

template<typename T>

bool CheckHeap(const T& heap)

{

return RecurrentCheck(heap, 1);

}

I've used a trick here, that allows to avoid branching of the recurrent function.

if something looks suspicious, or like na error, post about it, and I will verify and comment the reasonin behind.

regards,

djemon_lda