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 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 } // namespace Utility 00155 } // namespace CS 00156 00157 #endif // __CS_CSUTIL_PRIORTITYQUEUE_H__
Generated for Crystal Space 2.0 by doxygen 1.6.1