CrystalSpace

Public API Reference

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.7.6.1