libassa 3.5.1
Loading...
Searching...
No Matches
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
22namespace ASSA {
23
31template<class T, class Compare> class PriorityQueue_Impl;
32
33template<class T, class Compare >
35{
36public:
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
51protected:
54
57
58private:
60};
61
62//----------------------------------------------------------------------------
63// Member functions
64//----------------------------------------------------------------------------
65
66template <class T, class Compare>
67inline
69PriorityQueue (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
77}
78
79template <class T, class Compare>
80inline
82PriorityQueue (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
88}
89
90template <class T, class Compare>
91inline void
93setHeapImpl (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
103}
104
105template <class T, class Compare>
106inline
109{
110 delete m_impl;
111}
112
113template <class T, class Compare> void
114inline
116insert (const T& el_)
117{
118 m_impl->insert (el_);
119}
120
121template <class T, class Compare> T
122inline
124pop ()
125{
126 return m_impl->pop ();
127}
128
129template <class T, class Compare>
130inline const T&
132top () const
133{
134 return m_impl->top ();
135}
136
137template <class T, class Compare>
138inline bool
140remove (T& t_)
141{
142 return m_impl->remove (t_);
143}
144
145template <class T, class Compare>
146inline size_t
148size ()
149{
150 return m_impl->size ();
151}
152
153template <class T, class Compare>
160
161template <class T, class Compare>
162inline T&
164operator[] (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.
A wrapper class to provide AutoPtr with reference semantics.
Definition AutoPtr.h:32
PriorityQueue & operator=(const PriorityQueue &)
virtual T & operator[](int)
PriorityQueue(size_t max_=20)
virtual size_t size()
PriorityQueue(const PriorityQueue &)
virtual void insert(const T &)
virtual const T & top() const
virtual void setHeapImpl(size_t, const Compare &)
const PriorityQueue_Impl< T, Compare > * getPriorityQueueImpl() const
PriorityQueue(size_t max_, const Compare &)
virtual bool remove(T &)
PriorityQueue_Impl< T, Compare > * m_impl