csutil/priorityqueue.h
Go to the documentation of this file.00001 /* 00002 Copyright (C) 2007 by Frank Richter 00003 00004 This library is free software; you can redistribute it and/or 00005 modify it under the terms of the GNU Library General Public 00006 License as published by the Free Software Foundation; either 00007 version 2 of the License, or (at your option) any later version. 00008 00009 This library is distributed in the hope that it will be useful, 00010 but WITHOUT ANY WARRANTY; without even the implied warranty of 00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00012 Library General Public License for more details. 00013 00014 You should have received a copy of the GNU Library General Public 00015 License along with this library; if not, write to the Free 00016 Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 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 PriorityQueue 00040 { 00041 Container items; 00042 00043 inline static size_t Parent (size_t n) { return (n-1)/2; } 00044 inline static size_t Left (size_t n) { return 2*n+1; } 00045 inline static size_t Right (size_t n) { return 2*n+2; } 00046 00047 void SwapItems (size_t a, size_t b) 00048 { 00049 T tmp (items[a]); 00050 items[a] = items[b]; 00051 items[b] = tmp; 00052 } 00053 inline bool Larger (size_t a, size_t b) 00054 { return csComparator<T, T>::Compare (items[a], items[b]) > 0; } 00055 00057 void HeapifyUp (size_t n) 00058 { 00059 size_t current = n; 00060 while (current > 0) 00061 { 00062 size_t parent = Parent (current); 00063 size_t larger = current; 00064 if (((current ^ 1) < items.GetSize()) 00065 && Larger (current ^ 1, larger)) 00066 { 00067 larger = current ^ 1; 00068 } 00069 if (Larger (larger, parent)) 00070 SwapItems (larger, parent); 00071 else 00072 return; 00073 current = parent; 00074 } 00075 } 00077 void HeapifyDown (size_t n) 00078 { 00079 size_t current = n; 00080 do 00081 { 00082 size_t l = Left (current); 00083 size_t r = Right (current); 00084 size_t larger = current; 00085 if ((l < items.GetSize()) 00086 && Larger (l, larger)) 00087 { 00088 larger = l; 00089 } 00090 if ((r < items.GetSize()) 00091 && Larger (r, larger)) 00092 { 00093 larger = r; 00094 } 00095 if (larger == current) return; 00096 SwapItems (larger, current); 00097 current = larger; 00098 } 00099 while (current < items.GetSize ()); 00100 } 00101 public: 00103 void Insert (const T& what) 00104 { 00105 size_t n = items.Push (what); 00106 HeapifyUp (n); 00107 } 00108 00110 00111 T Pop () 00112 { 00113 T val = items[0]; 00114 items.DeleteIndexFast (0); 00115 HeapifyDown (0); 00116 return val; 00117 } 00119 00121 00122 const T& Top () const 00123 { 00124 return items[0]; 00125 } 00127 00134 template<typename T2> 00135 bool Delete (const T2& what) 00136 { 00137 for (size_t n = 0; n < items.GetSize(); n++) 00138 { 00139 if (csComparator<T, T2>::Compare (items[n], what) == 0) 00140 { 00141 items.DeleteIndexFast (n); 00142 HeapifyDown (n); 00143 return true; 00144 } 00145 } 00146 return false; 00147 } 00148 00150 bool IsEmpty() const { return items.IsEmpty(); } 00151 }; 00152 00153 } // namespace Utility 00154 } // namespace CS 00155 00156 #endif // __CS_CSUTIL_PRIORTITYQUEUE_H__
Generated for Crystal Space 1.2 by doxygen 1.4.7