libassa 3.5.0
|
00001 // -*- c++ -*- 00002 //------------------------------------------------------------------------------ 00003 // PriorityQueue_STLPQ.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 // Created: 09/29/1999 00013 //------------------------------------------------------------------------------ 00014 #ifndef PRIORITY_QUEUE_STLPQ_H 00015 #define PRIORITY_QUEUE_STLPQ_H 00016 00017 #include <stack> 00018 #include <deque> 00019 #include <list> 00020 #include <queue> 00021 using namespace std; 00022 00023 #include "assa/Timer.h" 00024 00025 namespace ASSA { 00026 00032 template< class T, class Compare > 00033 class PriorityQueue_STLPQ : 00034 public PriorityQueue_Impl< T, Compare > 00035 { 00036 public: 00037 ~PriorityQueue_STLPQ (); 00038 00039 void insert (const T&); 00040 T pop (); 00041 const T& top () const; 00042 bool remove (const int); 00043 size_t size (); 00044 00045 void dump (); 00046 00047 private: 00048 priority_queue<T*, deque<T*>, Compare> m_queue; 00049 }; 00050 00051 template< class T, class Compare> 00052 inline 00053 PriorityQueue_STLPQ<T, Compare>:: 00054 ~PriorityQueue_STLPQ () 00055 { 00056 trace("PriorityQueue_STLPQ::~PriorityQueue_STLPQ"); 00057 00058 while ( m_queue.size () ) { 00059 delete m_queue.top (); 00060 m_queue.pop (); 00061 } 00062 } 00063 00064 template< class T, class Compare> 00065 inline void 00066 PriorityQueue_STLPQ<T, Compare>:: 00067 insert (const T& t_) 00068 { 00069 trace("PriorityQueue_STLPQ::insert"); 00070 m_queue.push (t_); 00071 } 00072 00073 template< class T, class Compare> 00074 inline T 00075 PriorityQueue_STLPQ<T, Compare>:: 00076 pop () 00077 { 00078 trace("PriorityQueue_STLPQ::pop"); 00079 00080 T t = m_queue.top (); 00081 m_queue.pop (); 00082 return t; 00083 } 00084 00085 template< class T, class Compare> 00086 inline const T& 00087 PriorityQueue_STLPQ<T, Compare>:: 00088 top () const 00089 { 00090 trace("PriorityQueue_STLPQ::top"); 00091 return (const T&) m_queue.top (); 00092 } 00093 00094 /******************************************************************************* 00095 STL priority queue doesn't allow to remove arbitrary 00096 element from the queue. Only top element can be removed. 00097 To search for the element, I extract top one, and if it 00098 doesn't match my search, put it into list<>. When either 00099 found or reached end of queue, I restore all elements 00100 in the list<> back to the priority queue. 00101 This needs rethinking! 00102 *******************************************************************************/ 00103 template< class T, class Compare> 00104 bool 00105 PriorityQueue_STLPQ<T, Compare>:: 00106 remove (const int id_) 00107 { 00108 trace("PriorityQueue_STLPQ::remove"); 00109 00110 list<Timer*> t_list; 00111 register Timer* t_ptr = 0; 00112 register int cnt = 0; 00113 00114 while (m_queue.size () > 0) { 00115 t_ptr = m_queue.top (); 00116 if (t_ptr->getHandler ()-> id() == id_) { 00117 delete t_ptr; 00118 cnt++; 00119 } 00120 else { 00121 t_list.push_back (t_ptr); 00122 } 00123 m_queue.pop (); 00124 } 00125 // Restore queue 00126 00127 list<Timer*>::iterator i; 00128 00129 for (i = t_list.begin (); i != t_list.end (); i++) { 00130 m_queue.push (*i); 00131 } 00132 00133 return cnt; 00134 } 00135 00136 template< class T, class Compare> 00137 inline size_t 00138 PriorityQueue_STLPQ<T, Compare>:: 00139 size () 00140 { 00141 return m_queue.size (); 00142 } 00143 00144 template< class T, class Compare> 00145 inline void 00146 PriorityQueue_STLPQ<T, Compare>:: 00147 dump () 00148 { 00149 trace("PriorityQueue_STLPQ::dump"); 00150 00151 list<Timer*> t_list; 00152 register Timer* t_ptr = 0; 00153 DL((TRACE,"======TimerQueue start=======\n")); 00154 while (m_queue.size () > 0) { 00155 t_ptr = m_queue.top (); 00156 t_ptr->dump (); 00157 t_list.push_back (t_ptr); 00158 } 00159 DL((TRACE,"======TimerQueue end=========\n")); 00160 list<Timer*>::iterator i; 00161 00162 for (i = t_list.begin (); i != t_list.end (); i++) { 00163 m_queue.push (*i); 00164 } 00165 } 00166 00167 } // end namespace ASSA 00168 00169 #endif /* PRIORITY_QUEUE_STLPQ_H */