1 // -*- c++ -*-
2 //------------------------------------------------------------------------------
3 // PriorityQueue_STLPQ.h
4 //------------------------------------------------------------------------------
5 // Copyright (c) 1999 by Vladislav Grinchenko
6 //
7 // This library is free software; you can redistribute it and/or
8 // modify it under the terms of the GNU Library General Public
9 // License as published by the Free Software Foundation; either
10 // version 2 of the License, or (at your option) any later version.
11 //------------------------------------------------------------------------------
12 // Created: 09/29/1999
13 //------------------------------------------------------------------------------
14 #ifndef PRIORITY_QUEUE_STLPQ_H
15 #define PRIORITY_QUEUE_STLPQ_H
16
17 #include <stack>
18 #include <deque>
19 #include <list>
20 #include <queue>
21 using namespace std;
22
23 #include "assa/Timer.h"
24
25 namespace ASSA {
26
27 /** @file PriorityQueue_STLPQ.h
28
29 Priority Queue implementation based on STL priority_queue.
30 */
31
32 template< class T, class Compare >
33 class PriorityQueue_STLPQ :
34 public PriorityQueue_Impl< T, Compare >
35 {
36 public:
37 ~PriorityQueue_STLPQ ();
38
39 void insert (const T&);
40 T pop ();
41 const T& top () const;
42 bool remove (const int);
43 size_t size ();
44
45 void dump ();
46
47 private:
48 priority_queue<T*, deque<T*>, Compare> m_queue;
49 };
50
51 template< class T, class Compare>
52 inline
53 PriorityQueue_STLPQ<T, Compare>::
~PriorityQueue_STLPQ()54 ~PriorityQueue_STLPQ ()
55 {
56 trace("PriorityQueue_STLPQ::~PriorityQueue_STLPQ");
57
58 while ( m_queue.size () ) {
59 delete m_queue.top ();
60 m_queue.pop ();
61 }
62 }
63
64 template< class T, class Compare>
65 inline void
66 PriorityQueue_STLPQ<T, Compare>::
insert(const T & t_)67 insert (const T& t_)
68 {
69 trace("PriorityQueue_STLPQ::insert");
70 m_queue.push (t_);
71 }
72
73 template< class T, class Compare>
74 inline T
75 PriorityQueue_STLPQ<T, Compare>::
pop()76 pop ()
77 {
78 trace("PriorityQueue_STLPQ::pop");
79
80 T t = m_queue.top ();
81 m_queue.pop ();
82 return t;
83 }
84
85 template< class T, class Compare>
86 inline const T&
87 PriorityQueue_STLPQ<T, Compare>::
top()88 top () const
89 {
90 trace("PriorityQueue_STLPQ::top");
91 return (const T&) m_queue.top ();
92 }
93
94 /*******************************************************************************
95 STL priority queue doesn't allow to remove arbitrary
96 element from the queue. Only top element can be removed.
97 To search for the element, I extract top one, and if it
98 doesn't match my search, put it into list<>. When either
99 found or reached end of queue, I restore all elements
100 in the list<> back to the priority queue.
101 This needs rethinking!
102 *******************************************************************************/
103 template< class T, class Compare>
104 bool
105 PriorityQueue_STLPQ<T, Compare>::
remove(const int id_)106 remove (const int id_)
107 {
108 trace("PriorityQueue_STLPQ::remove");
109
110 list<Timer*> t_list;
111 register Timer* t_ptr = 0;
112 register int cnt = 0;
113
114 while (m_queue.size () > 0) {
115 t_ptr = m_queue.top ();
116 if (t_ptr->getHandler ()-> id() == id_) {
117 delete t_ptr;
118 cnt++;
119 }
120 else {
121 t_list.push_back (t_ptr);
122 }
123 m_queue.pop ();
124 }
125 // Restore queue
126
127 list<Timer*>::iterator i;
128
129 for (i = t_list.begin (); i != t_list.end (); i++) {
130 m_queue.push (*i);
131 }
132
133 return cnt;
134 }
135
136 template< class T, class Compare>
137 inline size_t
138 PriorityQueue_STLPQ<T, Compare>::
size()139 size ()
140 {
141 return m_queue.size ();
142 }
143
144 template< class T, class Compare>
145 inline void
146 PriorityQueue_STLPQ<T, Compare>::
dump()147 dump ()
148 {
149 trace("PriorityQueue_STLPQ::dump");
150
151 list<Timer*> t_list;
152 register Timer* t_ptr = 0;
153 DL((TRACE,"======TimerQueue start=======\n"));
154 while (m_queue.size () > 0) {
155 t_ptr = m_queue.top ();
156 t_ptr->dump ();
157 t_list.push_back (t_ptr);
158 }
159 DL((TRACE,"======TimerQueue end=========\n"));
160 list<Timer*>::iterator i;
161
162 for (i = t_list.begin (); i != t_list.end (); i++) {
163 m_queue.push (*i);
164 }
165 }
166
167 } // end namespace ASSA
168
169 #endif /* PRIORITY_QUEUE_STLPQ_H */
170