Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CS_CSUTIL_PRIORTITYQUEUE_H__
00020 #define __CS_CSUTIL_PRIORTITYQUEUE_H__
00021
00026 #include "array.h"
00027
00028 namespace CS
00029 {
00030 namespace Utility
00031 {
00032
00038 template<typename T, class Container = csArray<T>,
00039 class Comparator = csComparator<T, T> >
00040 class PriorityQueue
00041 {
00042 Container items;
00043
00044 inline static size_t Parent (size_t n) { return (n-1)/2; }
00045 inline static size_t Left (size_t n) { return 2*n+1; }
00046 inline static size_t Right (size_t n) { return 2*n+2; }
00047
00048 void SwapItems (size_t a, size_t b)
00049 {
00050 T tmp (items[a]);
00051 items[a] = items[b];
00052 items[b] = tmp;
00053 }
00054 inline bool Larger (size_t a, size_t b)
00055 { return Comparator::Compare (items[a], items[b]) > 0; }
00056
00058 void HeapifyUp (size_t n)
00059 {
00060 size_t current = n;
00061 while (current > 0)
00062 {
00063 size_t parent = Parent (current);
00064 size_t larger = current;
00065 if (((current ^ 1) < items.GetSize())
00066 && Larger (current ^ 1, larger))
00067 {
00068 larger = current ^ 1;
00069 }
00070 if (Larger (larger, parent))
00071 SwapItems (larger, parent);
00072 else
00073 return;
00074 current = parent;
00075 }
00076 }
00078 void HeapifyDown (size_t n)
00079 {
00080 size_t current = n;
00081 do
00082 {
00083 size_t l = Left (current);
00084 size_t r = Right (current);
00085 size_t larger = current;
00086 if ((l < items.GetSize())
00087 && Larger (l, larger))
00088 {
00089 larger = l;
00090 }
00091 if ((r < items.GetSize())
00092 && Larger (r, larger))
00093 {
00094 larger = r;
00095 }
00096 if (larger == current) return;
00097 SwapItems (larger, current);
00098 current = larger;
00099 }
00100 while (current < items.GetSize ());
00101 }
00102 public:
00104 void Insert (const T& what)
00105 {
00106 size_t n = items.Push (what);
00107 HeapifyUp (n);
00108 }
00109
00111
00112 T Pop ()
00113 {
00114 T val = items[0];
00115 items.DeleteIndexFast (0);
00116 HeapifyDown (0);
00117 return val;
00118 }
00120
00122
00123 const T& Top () const
00124 {
00125 return items[0];
00126 }
00128
00135 template<typename T2>
00136 bool Delete (const T2& what)
00137 {
00138 for (size_t n = 0; n < items.GetSize(); n++)
00139 {
00140 if (csComparator<T, T2>::Compare (items[n], what) == 0)
00141 {
00142 items.DeleteIndexFast (n);
00143 HeapifyDown (n);
00144 return true;
00145 }
00146 }
00147 return false;
00148 }
00149
00151 bool IsEmpty() const { return items.IsEmpty(); }
00152 };
00153
00154 }
00155 }
00156
00157 #endif // __CS_CSUTIL_PRIORTITYQUEUE_H__