libassa
3.5.0
|
00001 // -*- c++ -*- 00002 //------------------------------------------------------------------------------ 00003 // PriorityQueue.h 00004 //------------------------------------------------------------------------------ 00005 // Copyright (c) 1999 by Vladislav Grinchenko 00006 // 00007 // This library is free software; you can redistribute it and/or 00008 // modify it under the terms of the GNU Library General Public 00009 // License as published by the Free Software Foundation; either 00010 // version 2 of the License, or (at your option) any later version. 00011 //------------------------------------------------------------------------------ 00012 #ifndef PRIORITY_QUEUE_H 00013 #define PRIORITY_QUEUE_H 00014 00015 #include <unistd.h> 00016 #include <limits.h> 00017 00018 #include "assa/Assure.h" 00019 #include "assa/PriorityQueue_Impl.h" 00020 #include "assa/PriorityQueue_Heap.h" 00021 00022 namespace ASSA { 00023 00031 template<class T, class Compare> class PriorityQueue_Impl; 00032 00033 template<class T, class Compare > 00034 class PriorityQueue 00035 { 00036 public: 00037 PriorityQueue (size_t max_ = 20); 00038 PriorityQueue (size_t max_, const Compare&); 00039 00040 virtual ~PriorityQueue (); 00041 00042 virtual void insert (const T&); 00043 virtual T pop (); 00044 virtual const T& top () const; 00045 virtual bool remove (T&); 00046 virtual size_t size (); 00047 virtual T& operator[] (int); 00048 00049 virtual void setHeapImpl (size_t, const Compare&); 00050 00051 protected: 00052 const PriorityQueue_Impl<T, Compare>* getPriorityQueueImpl () const; 00053 Compare m_comp; 00054 00055 PriorityQueue (const PriorityQueue&); 00056 PriorityQueue& operator= (const PriorityQueue&); 00057 00058 private: 00059 PriorityQueue_Impl< T, Compare >* m_impl; 00060 }; 00061 00062 //---------------------------------------------------------------------------- 00063 // Member functions 00064 //---------------------------------------------------------------------------- 00065 00066 template <class T, class Compare> 00067 inline 00068 PriorityQueue<T, Compare>:: 00069 PriorityQueue (size_t maxsz_) 00070 : m_impl (0) 00071 { 00072 // This is a perfect place for using Factory to decide which 00073 // implementation to use 00074 // const char self[]="PriorityQueue::PriorityQueue(maxsz)"; trace(); 00075 00076 setHeapImpl (maxsz_, m_comp); 00077 } 00078 00079 template <class T, class Compare> 00080 inline 00081 PriorityQueue<T, Compare>:: 00082 PriorityQueue (size_t maxsz_, const Compare& x_) 00083 : m_comp (x_), m_impl (0) 00084 { 00085 // This is perfect place for using Factory to decide which 00086 // implementation to use 00087 setHeapImpl (maxsz_, m_comp); 00088 } 00089 00090 template <class T, class Compare> 00091 inline void 00092 PriorityQueue<T, Compare>:: 00093 setHeapImpl (size_t maxsz_, const Compare& x_) 00094 { 00095 // Maybe here you would want to copy contents of the old 00096 // implementation to the new one? 00097 // 00098 00099 if (m_impl != 0) 00100 delete m_impl; 00101 00102 m_impl = new PriorityQueue_Heap<T, Compare> (maxsz_, x_); 00103 } 00104 00105 template <class T, class Compare> 00106 inline 00107 PriorityQueue<T, Compare>:: 00108 ~PriorityQueue () 00109 { 00110 delete m_impl; 00111 } 00112 00113 template <class T, class Compare> void 00114 inline 00115 PriorityQueue<T, Compare>:: 00116 insert (const T& el_) 00117 { 00118 m_impl->insert (el_); 00119 } 00120 00121 template <class T, class Compare> T 00122 inline 00123 PriorityQueue<T, Compare>:: 00124 pop () 00125 { 00126 return m_impl->pop (); 00127 } 00128 00129 template <class T, class Compare> 00130 inline const T& 00131 PriorityQueue<T, Compare>:: 00132 top () const 00133 { 00134 return m_impl->top (); 00135 } 00136 00137 template <class T, class Compare> 00138 inline bool 00139 PriorityQueue<T, Compare>:: 00140 remove (T& t_) 00141 { 00142 return m_impl->remove (t_); 00143 } 00144 00145 template <class T, class Compare> 00146 inline size_t 00147 PriorityQueue<T, Compare>:: 00148 size () 00149 { 00150 return m_impl->size (); 00151 } 00152 00153 template <class T, class Compare> 00154 inline const PriorityQueue_Impl<T, Compare>* 00155 PriorityQueue<T, Compare>:: 00156 getPriorityQueueImpl () const 00157 { 00158 return (const PriorityQueue_Impl<T, Compare>*) m_impl; 00159 } 00160 00161 template <class T, class Compare> 00162 inline T& 00163 PriorityQueue<T, Compare>:: 00164 operator[] (int idx) 00165 { 00166 return (*m_impl)[idx]; 00167 } 00168 00169 } // end namespace ASSA 00170 00171 #endif /* PRIORITY_QUEUE_H */