libassa  3.5.1
PriorityQueue.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //------------------------------------------------------------------------------
3 // PriorityQueue.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 #ifndef PRIORITY_QUEUE_H
13 #define PRIORITY_QUEUE_H
14 
15 #include <unistd.h>
16 #include <limits.h>
17 
18 #include "assa/Assure.h"
21 
22 namespace ASSA {
23 
31 template<class T, class Compare> class PriorityQueue_Impl;
32 
33 template<class T, class Compare >
35 {
36 public:
37  PriorityQueue (size_t max_ = 20);
38  PriorityQueue (size_t max_, const Compare&);
39 
40  virtual ~PriorityQueue ();
41 
42  virtual void insert (const T&);
43  virtual T pop ();
44  virtual const T& top () const;
45  virtual bool remove (T&);
46  virtual size_t size ();
47  virtual T& operator[] (int);
48 
49  virtual void setHeapImpl (size_t, const Compare&);
50 
51 protected:
53  Compare m_comp;
54 
57 
58 private:
60 };
61 
62 //----------------------------------------------------------------------------
63 // Member functions
64 //----------------------------------------------------------------------------
65 
66 template <class T, class Compare>
67 inline
69 PriorityQueue (size_t maxsz_)
70  : m_impl (0)
71 {
72  // This is a perfect place for using Factory to decide which
73  // implementation to use
74  // const char self[]="PriorityQueue::PriorityQueue(maxsz)"; trace();
75 
76  setHeapImpl (maxsz_, m_comp);
77 }
78 
79 template <class T, class Compare>
80 inline
82 PriorityQueue (size_t maxsz_, const Compare& x_)
83  : m_comp (x_), m_impl (0)
84 {
85  // This is perfect place for using Factory to decide which
86  // implementation to use
87  setHeapImpl (maxsz_, m_comp);
88 }
89 
90 template <class T, class Compare>
91 inline void
93 setHeapImpl (size_t maxsz_, const Compare& x_)
94 {
95  // Maybe here you would want to copy contents of the old
96  // implementation to the new one?
97  //
98 
99  if (m_impl != 0)
100  delete m_impl;
101 
102  m_impl = new PriorityQueue_Heap<T, Compare> (maxsz_, x_);
103 }
104 
105 template <class T, class Compare>
106 inline
109 {
110  delete m_impl;
111 }
112 
113 template <class T, class Compare> void
114 inline
116 insert (const T& el_)
117 {
118  m_impl->insert (el_);
119 }
120 
121 template <class T, class Compare> T
122 inline
124 pop ()
125 {
126  return m_impl->pop ();
127 }
128 
129 template <class T, class Compare>
130 inline const T&
132 top () const
133 {
134  return m_impl->top ();
135 }
136 
137 template <class T, class Compare>
138 inline bool
140 remove (T& t_)
141 {
142  return m_impl->remove (t_);
143 }
144 
145 template <class T, class Compare>
146 inline size_t
148 size ()
149 {
150  return m_impl->size ();
151 }
152 
153 template <class T, class Compare>
154 inline const PriorityQueue_Impl<T, Compare>*
156 getPriorityQueueImpl () const
157 {
158  return (const PriorityQueue_Impl<T, Compare>*) m_impl;
159 }
160 
161 template <class T, class Compare>
162 inline T&
164 operator[] (int idx)
165 {
166  return (*m_impl)[idx];
167 }
168 
169 } // end namespace ASSA
170 
171 #endif /* PRIORITY_QUEUE_H */
A collection of assert function wrappers.
Heap-based implementation of PriorityQueue algorithm based on Robert Sedgewick's "Algorithms in C++",...
Interface class that defines Implementor of the Bridge pattern.
Class PriorityQueue_Impl.
virtual T & operator[](int)
PriorityQueue & operator=(const PriorityQueue &)
PriorityQueue(size_t max_=20)
Definition: PriorityQueue.h:69
virtual ~PriorityQueue()
virtual size_t size()
PriorityQueue(const PriorityQueue &)
virtual void insert(const T &)
virtual const T & top() const
virtual void setHeapImpl(size_t, const Compare &)
Definition: PriorityQueue.h:93
const PriorityQueue_Impl< T, Compare > * getPriorityQueueImpl() const
PriorityQueue(size_t max_, const Compare &)
Definition: PriorityQueue.h:82
virtual bool remove(T &)
PriorityQueue_Impl< T, Compare > * m_impl
Definition: PriorityQueue.h:59
Definition: Acceptor.h:40