252 lines
10 KiB
C++
252 lines
10 KiB
C++
/*
|
|
* Copyright (c) 2014, Oculus VR, Inc.
|
|
* All rights reserved.
|
|
*
|
|
* This source code is licensed under the BSD-style license found in the
|
|
* LICENSE file in the root directory of this source tree. An additional grant
|
|
* of patent rights can be found in the PATENTS file in the same directory.
|
|
*
|
|
*/
|
|
|
|
/// \file DS_OrderedChannelHeap.h
|
|
/// \internal
|
|
/// \brief Ordered Channel Heap . This is a heap where you add to it on multiple ordered channels, with each channel having a different weight.
|
|
///
|
|
|
|
|
|
#ifndef __RAKNET_ORDERED_CHANNEL_HEAP_H
|
|
#define __RAKNET_ORDERED_CHANNEL_HEAP_H
|
|
|
|
#include "DS_Heap.hpp"
|
|
#include "DS_Map.hpp"
|
|
#include "DS_Queue.hpp"
|
|
#include "Export.hpp"
|
|
#include "RakAssert.hpp"
|
|
#include "Rand.hpp"
|
|
|
|
/// 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:
|
|
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
|
|
RakAssert(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)
|
|
{
|
|
RakAssert(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 = RakNet::OP_NEW<QueueAndWeight>( _FILE_AND_LINE_ );
|
|
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)
|
|
{
|
|
RakNet::OP_DELETE(map[i], _FILE_AND_LINE_);
|
|
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++)
|
|
RakNet::OP_DELETE(map[i], _FILE_AND_LINE_);
|
|
map.Clear(_FILE_AND_LINE_);
|
|
heap.Clear(_FILE_AND_LINE_);
|
|
}
|
|
}
|
|
|
|
#endif
|