mirror of
https://github.com/DarkflameUniverse/DarkflameServer.git
synced 2024-09-20 01:21:32 +00:00
253 lines
10 KiB
C++
253 lines
10 KiB
C++
/// \file
|
|
/// \brief \b [Internal] Ordered Channel Heap . This is a heap where you add to it on multiple ordered channels, with each channel having a different weight.
|
|
///
|
|
/// This file is part of RakNet Copyright 2003 Kevin Jenkins.
|
|
///
|
|
/// Usage of RakNet is subject to the appropriate license agreement.
|
|
/// Creative Commons Licensees are subject to the
|
|
/// license found at
|
|
/// http://creativecommons.org/licenses/by-nc/2.5/
|
|
/// Single application licensees are subject to the license found at
|
|
/// http://www.jenkinssoftware.com/SingleApplicationLicense.html
|
|
/// Custom license users are subject to the terms therein.
|
|
/// GPL license users are subject to the GNU General Public
|
|
/// License as published by the Free
|
|
/// Software Foundation; either version 2 of the License, or (at your
|
|
/// option) any later version.
|
|
|
|
#ifndef __RAKNET_ORDERED_CHANNEL_HEAP_H
|
|
#define __RAKNET_ORDERED_CHANNEL_HEAP_H
|
|
|
|
#include "DS_Heap.h"
|
|
#include "DS_Map.h"
|
|
#include "DS_Queue.h"
|
|
#include "Export.h"
|
|
#include <assert.h>
|
|
#include "Rand.h"
|
|
|
|
/// The namespace DataStructures was only added to avoid compiler errors for commonly named data structures
|
|
/// As these data structures are stand-alone, you can use them outside of RakNet for your own projects if you wish.
|
|
namespace DataStructures
|
|
{
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)=defaultMapKeyComparison<channel_key_type> >
|
|
class RAK_DLL_EXPORT OrderedChannelHeap : public RakNet::RakMemoryOverride
|
|
{
|
|
public:
|
|
static void IMPLEMENT_DEFAULT_COMPARISON(void) {DataStructures::defaultMapKeyComparison<channel_key_type>(channel_key_type(),channel_key_type());}
|
|
|
|
OrderedChannelHeap();
|
|
~OrderedChannelHeap();
|
|
void Push(const channel_key_type &channelID, const heap_data_type &data);
|
|
void PushAtHead(const unsigned index, const channel_key_type &channelID, const heap_data_type &data);
|
|
heap_data_type Pop(const unsigned startingIndex=0);
|
|
heap_data_type Peek(const unsigned startingIndex) const;
|
|
void AddChannel(const channel_key_type &channelID, const double weight);
|
|
void RemoveChannel(channel_key_type channelID);
|
|
void Clear(void);
|
|
heap_data_type& operator[] ( const unsigned int position ) const;
|
|
unsigned ChannelSize(const channel_key_type &channelID);
|
|
unsigned Size(void) const;
|
|
|
|
struct QueueAndWeight
|
|
{
|
|
DataStructures::Queue<double> randResultQueue;
|
|
double weight;
|
|
bool signalDeletion;
|
|
};
|
|
|
|
struct HeapChannelAndData
|
|
{
|
|
HeapChannelAndData() {}
|
|
HeapChannelAndData(const channel_key_type &_channel, const heap_data_type &_data) : data(_data), channel(_channel) {}
|
|
heap_data_type data;
|
|
channel_key_type channel;
|
|
};
|
|
|
|
protected:
|
|
DataStructures::Map<channel_key_type, QueueAndWeight*, channel_key_comparison_func> map;
|
|
DataStructures::Heap<double, HeapChannelAndData, true> heap;
|
|
void GreatestRandResult(void);
|
|
};
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::OrderedChannelHeap()
|
|
{
|
|
}
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::~OrderedChannelHeap()
|
|
{
|
|
Clear();
|
|
}
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
void OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::Push(const channel_key_type &channelID, const heap_data_type &data)
|
|
{
|
|
PushAtHead(MAX_UNSIGNED_LONG, channelID, data);
|
|
}
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
void OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::GreatestRandResult(void)
|
|
{
|
|
double greatest;
|
|
unsigned i;
|
|
greatest=0.0;
|
|
for (i=0; i < map.Size(); i++)
|
|
{
|
|
if (map[i]->randResultQueue.Size() && map[i]->randResultQueue[0]>greatest)
|
|
greatest=map[i]->randResultQueue[0];
|
|
}
|
|
return greatest;
|
|
}
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
void OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::PushAtHead(const unsigned index, const channel_key_type &channelID, const heap_data_type &data)
|
|
{
|
|
// If an assert hits here then this is an unknown channel. Call AddChannel first.
|
|
QueueAndWeight *queueAndWeight=map.Get(channelID);
|
|
double maxRange, minRange, rnd;
|
|
if (queueAndWeight->randResultQueue.Size()==0)
|
|
{
|
|
// Set maxRange to the greatest random number waiting to be returned, rather than 1.0 necessarily
|
|
// This is so weights are scaled similarly among channels. For example, if the head weight for a used channel was .25
|
|
// and then we added another channel, the new channel would need to choose between .25 and 0
|
|
// If we chose between 1.0 and 0, it would be 1/.25 (4x) more likely to be at the head of the heap than it should be
|
|
maxRange=GreatestRandResult();
|
|
if (maxRange==0.0)
|
|
maxRange=1.0;
|
|
minRange=0.0;
|
|
}
|
|
else if (index >= queueAndWeight->randResultQueue.Size())
|
|
{
|
|
maxRange=queueAndWeight->randResultQueue[queueAndWeight->randResultQueue.Size()-1]*.99999999;
|
|
minRange=0.0;
|
|
}
|
|
else
|
|
{
|
|
if (index==0)
|
|
{
|
|
maxRange=GreatestRandResult();
|
|
if (maxRange==queueAndWeight->randResultQueue[0])
|
|
maxRange=1.0;
|
|
}
|
|
else if (index >= queueAndWeight->randResultQueue.Size())
|
|
maxRange=queueAndWeight->randResultQueue[queueAndWeight->randResultQueue.Size()-1]*.99999999;
|
|
else
|
|
maxRange=queueAndWeight->randResultQueue[index-1]*.99999999;
|
|
|
|
minRange=maxRange=queueAndWeight->randResultQueue[index]*1.00000001;
|
|
}
|
|
|
|
#ifdef _DEBUG
|
|
assert(maxRange!=0.0);
|
|
#endif
|
|
rnd=frandomMT() * (maxRange - minRange);
|
|
if (rnd==0.0)
|
|
rnd=maxRange/2.0;
|
|
|
|
if (index >= queueAndWeight->randResultQueue.Size())
|
|
queueAndWeight->randResultQueue.Push(rnd);
|
|
else
|
|
queueAndWeight->randResultQueue.PushAtHead(rnd, index);
|
|
|
|
heap.Push(rnd*queueAndWeight->weight, HeapChannelAndData(channelID, data));
|
|
}
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
heap_data_type OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::Pop(const unsigned startingIndex)
|
|
{
|
|
assert(startingIndex < heap.Size());
|
|
|
|
QueueAndWeight *queueAndWeight=map.Get(heap[startingIndex].channel);
|
|
if (startingIndex!=0)
|
|
{
|
|
// Ugly - have to count in the heap how many nodes have the same channel, so we know where to delete from in the queue
|
|
unsigned indiceCount=0;
|
|
unsigned i;
|
|
for (i=0; i < startingIndex; i++)
|
|
if (channel_key_comparison_func(heap[i].channel,heap[startingIndex].channel)==0)
|
|
indiceCount++;
|
|
queueAndWeight->randResultQueue.RemoveAtIndex(indiceCount);
|
|
}
|
|
else
|
|
{
|
|
// TODO - ordered channel heap uses progressively lower values as items are inserted. But this won't give relative ordering among channels. I have to renormalize after every pop.
|
|
queueAndWeight->randResultQueue.Pop();
|
|
}
|
|
|
|
// Try to remove the channel after every pop, because doing so is not valid while there are elements in the list.
|
|
if (queueAndWeight->signalDeletion)
|
|
RemoveChannel(heap[startingIndex].channel);
|
|
|
|
return heap.Pop(startingIndex).data;
|
|
}
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
heap_data_type OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::Peek(const unsigned startingIndex) const
|
|
{
|
|
HeapChannelAndData heapChannelAndData = heap.Peek(startingIndex);
|
|
return heapChannelAndData.data;
|
|
}
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
void OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::AddChannel(const channel_key_type &channelID, const double weight)
|
|
{
|
|
QueueAndWeight *qaw = new QueueAndWeight;
|
|
qaw->weight=weight;
|
|
qaw->signalDeletion=false;
|
|
map.SetNew(channelID, qaw);
|
|
}
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
void OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::RemoveChannel(channel_key_type channelID)
|
|
{
|
|
if (map.Has(channelID))
|
|
{
|
|
unsigned i;
|
|
i=map.GetIndexAtKey(channelID);
|
|
if (map[i]->randResultQueue.Size()==0)
|
|
{
|
|
delete map[i];
|
|
map.RemoveAtIndex(i);
|
|
}
|
|
else
|
|
{
|
|
// Signal this channel for deletion later, because the heap has nodes with this channel right now
|
|
map[i]->signalDeletion=true;
|
|
}
|
|
}
|
|
}
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
unsigned OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::Size(void) const
|
|
{
|
|
return heap.Size();
|
|
}
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
heap_data_type& OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::operator[]( const unsigned int position ) const
|
|
{
|
|
return heap[position].data;
|
|
}
|
|
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
unsigned OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::ChannelSize(const channel_key_type &channelID)
|
|
{
|
|
QueueAndWeight *queueAndWeight=map.Get(channelID);
|
|
return queueAndWeight->randResultQueue.Size();
|
|
}
|
|
|
|
template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
|
|
void OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::Clear(void)
|
|
{
|
|
unsigned i;
|
|
for (i=0; i < map.Size(); i++)
|
|
delete map[i];
|
|
map.Clear();
|
|
heap.Clear();
|
|
}
|
|
}
|
|
|
|
#endif
|