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 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.1 by doxygen 1.5.3