RakNet: DS_OrderedChannelHeap.h Source File

Go to the documentation of this file.
00001 
00002 
00003 
00004 
00005 
00006 
00007 
00008 
00009 
00010 #ifndef __RAKNET_ORDERED_CHANNEL_HEAP_H
00011 #define __RAKNET_ORDERED_CHANNEL_HEAP_H
00012 
00013 #include "DS_Heap.h"
00014 #include "DS_Map.h"
00015 #include "DS_Queue.h"
00016 #include "Export.h"
00017 #include "RakAssert.h"
00018 #include "Rand.h"
00019 
00022 namespace DataStructures
00023 {
00024         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> >
00025         class RAK_DLL_EXPORT OrderedChannelHeap
00026         {
00027         public:
00028                 static void IMPLEMENT_DEFAULT_COMPARISON(void) {DataStructures::defaultMapKeyComparison<channel_key_type>(channel_key_type(),channel_key_type());}
00029 
00030                 OrderedChannelHeap();
00031                 ~OrderedChannelHeap();
00032                 void Push(const channel_key_type &channelID, const heap_data_type &data);
00033                 void PushAtHead(const unsigned index, const channel_key_type &channelID, const heap_data_type &data);
00034                 heap_data_type Pop(const unsigned startingIndex=0);
00035                 heap_data_type Peek(const unsigned startingIndex) const;
00036                 void AddChannel(const channel_key_type &channelID, const double weight);
00037                 void RemoveChannel(channel_key_type channelID);
00038                 void Clear(void);
00039                 heap_data_type& operator[] ( const unsigned int position ) const;
00040                 unsigned ChannelSize(const channel_key_type &channelID);
00041                 unsigned Size(void) const;
00042 
00043                 struct QueueAndWeight
00044                 {
00045                         DataStructures::Queue<double> randResultQueue;
00046                         double weight;
00047                         bool signalDeletion;
00048                 };
00049 
00050                 struct HeapChannelAndData
00051                 {
00052                         HeapChannelAndData() {}
00053                         HeapChannelAndData(const channel_key_type &_channel, const heap_data_type &_data) : data(_data), channel(_channel) {}
00054                         heap_data_type data;
00055                         channel_key_type channel;
00056                 };
00057 
00058         protected:
00059                 DataStructures::Map<channel_key_type, QueueAndWeight*, channel_key_comparison_func> map;
00060                 DataStructures::Heap<double, HeapChannelAndData, true> heap;
00061                 void GreatestRandResult(void);
00062         };
00063 
00064         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00065                 OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::OrderedChannelHeap()
00066         {
00067         }
00068 
00069         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00070                 OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::~OrderedChannelHeap()
00071         {
00072                 Clear();
00073         }
00074 
00075         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00076         void OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::Push(const channel_key_type &channelID, const heap_data_type &data)
00077         {
00078                 PushAtHead(MAX_UNSIGNED_LONG, channelID, data);
00079         }
00080 
00081         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00082         void OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::GreatestRandResult(void)
00083         {
00084                 double greatest;
00085                 unsigned i;
00086                 greatest=0.0;
00087                 for (i=0; i < map.Size(); i++)
00088                 {
00089                         if (map[i]->randResultQueue.Size() && map[i]->randResultQueue[0]>greatest)
00090                                 greatest=map[i]->randResultQueue[0];
00091                 }
00092                 return greatest;
00093         }
00094 
00095         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00096         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)
00097         {
00098                 // If an assert hits here then this is an unknown channel.  Call AddChannel first.
00099                 QueueAndWeight *queueAndWeight=map.Get(channelID);
00100                 double maxRange, minRange, rnd;
00101                 if (queueAndWeight->randResultQueue.Size()==0)
00102                 {
00103                         // Set maxRange to the greatest random number waiting to be returned, rather than 1.0 necessarily
00104                         // This is so weights are scaled similarly among channels.  For example, if the head weight for a used channel was .25
00105                         // and then we added another channel, the new channel would need to choose between .25 and 0
00106                         // 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
00107                         maxRange=GreatestRandResult();
00108                         if (maxRange==0.0)
00109                                 maxRange=1.0;
00110                         minRange=0.0;
00111                 }
00112                 else if (index >= queueAndWeight->randResultQueue.Size())
00113                 {
00114                         maxRange=queueAndWeight->randResultQueue[queueAndWeight->randResultQueue.Size()-1]*.99999999;
00115                         minRange=0.0;
00116                 }
00117                 else
00118                 {
00119                         if (index==0)
00120                         {
00121                                 maxRange=GreatestRandResult();
00122                                 if (maxRange==queueAndWeight->randResultQueue[0])
00123                                         maxRange=1.0;
00124                         }
00125                         else if (index >= queueAndWeight->randResultQueue.Size())
00126                                 maxRange=queueAndWeight->randResultQueue[queueAndWeight->randResultQueue.Size()-1]*.99999999;
00127                         else
00128                                 maxRange=queueAndWeight->randResultQueue[index-1]*.99999999;
00129 
00130                         minRange=maxRange=queueAndWeight->randResultQueue[index]*1.00000001;
00131                 }
00132                 
00133 #ifdef _DEBUG
00134                 RakAssert(maxRange!=0.0);
00135 #endif
00136                 rnd=frandomMT() * (maxRange - minRange);
00137                 if (rnd==0.0)
00138                         rnd=maxRange/2.0;
00139 
00140                 if (index >= queueAndWeight->randResultQueue.Size())
00141                         queueAndWeight->randResultQueue.Push(rnd);
00142                 else
00143                         queueAndWeight->randResultQueue.PushAtHead(rnd, index);
00144 
00145                 heap.Push(rnd*queueAndWeight->weight, HeapChannelAndData(channelID, data));
00146         }
00147 
00148         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00149         heap_data_type OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::Pop(const unsigned startingIndex)
00150         {
00151                 RakAssert(startingIndex < heap.Size());
00152 
00153                 QueueAndWeight *queueAndWeight=map.Get(heap[startingIndex].channel);
00154                 if (startingIndex!=0)
00155                 {
00156                         // Ugly - have to count in the heap how many nodes have the same channel, so we know where to delete from in the queue
00157                         unsigned indiceCount=0;
00158                         unsigned i;
00159                         for (i=0; i < startingIndex; i++)
00160                                 if (channel_key_comparison_func(heap[i].channel,heap[startingIndex].channel)==0)
00161                                         indiceCount++;
00162                         queueAndWeight->randResultQueue.RemoveAtIndex(indiceCount);
00163                 }
00164                 else
00165                 {
00166                         // 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.
00167                         queueAndWeight->randResultQueue.Pop();
00168                 }
00169 
00170                 // Try to remove the channel after every pop, because doing so is not valid while there are elements in the list.
00171                 if (queueAndWeight->signalDeletion)
00172                         RemoveChannel(heap[startingIndex].channel);
00173 
00174                 return heap.Pop(startingIndex).data;
00175         }
00176 
00177         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00178         heap_data_type OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::Peek(const unsigned startingIndex) const
00179         {
00180                 HeapChannelAndData heapChannelAndData = heap.Peek(startingIndex);
00181                 return heapChannelAndData.data;
00182         }
00183 
00184         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00185         void OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::AddChannel(const channel_key_type &channelID, const double weight)
00186         {
00187                 QueueAndWeight *qaw = RakNet::OP_NEW<QueueAndWeight>( __FILE__, __LINE__ );
00188                 qaw->weight=weight;
00189                 qaw->signalDeletion=false;
00190                 map.SetNew(channelID, qaw);
00191         }
00192 
00193         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00194                 void OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::RemoveChannel(channel_key_type channelID)
00195         {
00196                 if (map.Has(channelID))
00197                 {
00198                         unsigned i;
00199                         i=map.GetIndexAtKey(channelID);
00200                         if (map[i]->randResultQueue.Size()==0)
00201                         {
00202                                 RakNet::OP_DELETE(map[i], __FILE__, __LINE__);
00203                                 map.RemoveAtIndex(i);
00204                         }
00205                         else
00206                         {
00207                                 // Signal this channel for deletion later, because the heap has nodes with this channel right now
00208                                 map[i]->signalDeletion=true;
00209                         }
00210                 }
00211         }
00212 
00213         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00214                 unsigned OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::Size(void) const
00215         {
00216                 return heap.Size();
00217         }
00218 
00219         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00220                 heap_data_type& OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::operator[]( const unsigned int position ) const
00221         {
00222                 return heap[position].data;
00223         }
00224 
00225 
00226         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00227                 unsigned OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::ChannelSize(const channel_key_type &channelID)
00228         {
00229                 QueueAndWeight *queueAndWeight=map.Get(channelID);
00230                 return queueAndWeight->randResultQueue.Size();
00231         }
00232 
00233         template <class channel_key_type, class heap_data_type, int (*channel_key_comparison_func)(const channel_key_type&, const channel_key_type&)>
00234                 void OrderedChannelHeap<channel_key_type, heap_data_type, channel_key_comparison_func>::Clear(void)
00235         {
00236                 unsigned i;
00237                 for (i=0; i < map.Size(); i++)
00238                         RakNet::OP_DELETE(map[i], __FILE__, __LINE__);
00239                 map.Clear(__FILE__, __LINE__);
00240                 heap.Clear(__FILE__, __LINE__);
00241         }
00242 }
00243 
00244 #endif