#include <DS_OrderedChannelHeap.h>

Classes
struct	HeapChannelAndData
struct	QueueAndWeight
Public Member Functions
void	AddChannel (const channel_key_type &channelID, const double weight)
unsigned	ChannelSize (const channel_key_type &channelID)
void	Clear (void)
heap_data_type &	operator[] (const unsigned int position) const
	OrderedChannelHeap ()
heap_data_type	Peek (const unsigned startingIndex) const
heap_data_type	Pop (const unsigned startingIndex=0)
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)
void	RemoveChannel (channel_key_type channelID)
unsigned	Size (void) const
	~OrderedChannelHeap ()
Static Public Member Functions
static void	IMPLEMENT_DEFAULT_COMPARISON (void)
Protected Member Functions
void	GreatestRandResult (void)
Protected Attributes
DataStructures::Heap< double, HeapChannelAndData, true >	heap
DataStructures::Map < channel_key_type, QueueAndWeight *, channel_key_comparison_func >	map

Detailed Description

template<class channel_key_type, class heap_data_type, int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func = defaultMapKeyComparison<channel_key_type>>
class DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >

Definition at line 25 of file DS_OrderedChannelHeap.h.

Constructor & Destructor Documentation

template<class channel_key_type , class heap_data_type , int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::OrderedChannelHeap ( )

Definition at line 65 of file DS_OrderedChannelHeap.h.

    {
    }

template<class channel_key_type , class heap_data_type , int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::~OrderedChannelHeap ( )

Definition at line 70 of file DS_OrderedChannelHeap.h.

    {
        Clear();
    }

Member Function Documentation

template<class channel_key_type , class heap_data_type , int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

void DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::AddChannel	(	const channel_key_type &	channelID,
		const double	weight
	)

Definition at line 185 of file DS_OrderedChannelHeap.h.

References _FILE_AND_LINE_, DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::QueueAndWeight::signalDeletion, and DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::QueueAndWeight::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(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

unsigned DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::ChannelSize ( const channel_key_type & channelID )

Definition at line 227 of file DS_OrderedChannelHeap.h.

References DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::QueueAndWeight::randResultQueue, and DataStructures::Queue< queue_type >::Size().

    {
        QueueAndWeight *queueAndWeight=map.Get(channelID);
        return queueAndWeight->randResultQueue.Size();
    }

template<class channel_key_type , class heap_data_type , int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

void DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::Clear ( void )

Definition at line 234 of file DS_OrderedChannelHeap.h.

References _FILE_AND_LINE_, and RakNet::OP_DELETE().

    {
        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_);
    }

template<class channel_key_type , class heap_data_type , int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

void DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::GreatestRandResult ( void ) [protected]

Definition at line 82 of file DS_OrderedChannelHeap.h.

    {
        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(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func = defaultMapKeyComparison<channel_key_type>>

static void DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::IMPLEMENT_DEFAULT_COMPARISON ( void ) [inline, static]

Definition at line 28 of file DS_OrderedChannelHeap.h.

{DataStructures::defaultMapKeyComparison<channel_key_type>(channel_key_type(),channel_key_type());}

template<class channel_key_type , class heap_data_type , int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

heap_data_type & DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::operator[] ( const unsigned int position ) const

Definition at line 220 of file DS_OrderedChannelHeap.h.

    {
        return heap[position].data;
    }

template<class channel_key_type , class heap_data_type , int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

heap_data_type DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::Peek ( const unsigned startingIndex ) const

Definition at line 178 of file DS_OrderedChannelHeap.h.

References DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::HeapChannelAndData::data.

    {
        HeapChannelAndData heapChannelAndData = heap.Peek(startingIndex);
        return heapChannelAndData.data;
    }

template<class channel_key_type , class heap_data_type , int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

heap_data_type DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::Pop ( const unsigned startingIndex = 0 )

Definition at line 149 of file DS_OrderedChannelHeap.h.

References RakAssert, DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::QueueAndWeight::randResultQueue, and DataStructures::Queue< queue_type >::RemoveAtIndex().

    {
        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(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

void DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::Push	(	const channel_key_type &	channelID,
		const heap_data_type &	data
	)

Definition at line 76 of file DS_OrderedChannelHeap.h.

References MAX_UNSIGNED_LONG.

    {
        PushAtHead(MAX_UNSIGNED_LONG, channelID, data);
    }

template<class channel_key_type , class heap_data_type , int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

void DataStructures::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
	)

Definition at line 96 of file DS_OrderedChannelHeap.h.

References frandomMT(), DataStructures::Queue< queue_type >::Push(), DataStructures::Queue< queue_type >::PushAtHead(), RakAssert, DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::QueueAndWeight::randResultQueue, DataStructures::Queue< queue_type >::Size(), and DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::QueueAndWeight::weight.

    {
        // 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(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

void DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::RemoveChannel ( channel_key_type channelID )

Definition at line 194 of file DS_OrderedChannelHeap.h.

References _FILE_AND_LINE_, and RakNet::OP_DELETE().

    {
        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(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func>

unsigned DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::Size ( void ) const

Definition at line 214 of file DS_OrderedChannelHeap.h.

    {
        return heap.Size();
    }

Member Data Documentation

template<class channel_key_type , class heap_data_type , int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func = defaultMapKeyComparison<channel_key_type>>

DataStructures::Heap<double, HeapChannelAndData, true> DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::heap [protected]

Definition at line 60 of file DS_OrderedChannelHeap.h.

template<class channel_key_type , class heap_data_type , int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func = defaultMapKeyComparison<channel_key_type>>

DataStructures::Map<channel_key_type, QueueAndWeight*, channel_key_comparison_func> DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >::map [protected]

Definition at line 59 of file DS_OrderedChannelHeap.h.

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

DS_OrderedChannelHeap.h

Classes

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<class channel_key_type, class heap_data_type, int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func = defaultMapKeyComparison<channel_key_type>> class DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class channel_key_type, class heap_data_type, int(*)(const channel_key_type &, const channel_key_type &) channel_key_comparison_func = defaultMapKeyComparison<channel_key_type>>
class DataStructures::OrderedChannelHeap< channel_key_type, heap_data_type, channel_key_comparison_func >