libassa
3.5.1
assa
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
"
19
#include "
assa/PriorityQueue_Impl.h
"
20
#include "
assa/PriorityQueue_Heap.h
"
21
22
namespace
ASSA
{
23
31
template
<
class
T,
class
Compare>
class
PriorityQueue_Impl
;
32
33
template
<
class
T,
class
Compare >
34
class
PriorityQueue
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
:
52
const
PriorityQueue_Impl<T, Compare>
*
getPriorityQueueImpl
()
const
;
53
Compare
m_comp
;
54
55
PriorityQueue
(
const
PriorityQueue
&);
56
PriorityQueue
&
operator=
(
const
PriorityQueue
&);
57
58
private
:
59
PriorityQueue_Impl< T, Compare >
*
m_impl
;
60
};
61
62
//----------------------------------------------------------------------------
63
// Member functions
64
//----------------------------------------------------------------------------
65
66
template
<
class
T,
class
Compare>
67
inline
68
PriorityQueue<T, Compare>::
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
81
PriorityQueue<T, Compare>::
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
92
PriorityQueue<T, Compare>::
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
107
PriorityQueue<T, Compare>::
108
~PriorityQueue
()
109
{
110
delete
m_impl;
111
}
112
113
template
<
class
T,
class
Compare>
void
114
inline
115
PriorityQueue<T, Compare>::
116
insert
(
const
T& el_)
117
{
118
m_impl->
insert
(el_);
119
}
120
121
template
<
class
T,
class
Compare> T
122
inline
123
PriorityQueue<T, Compare>::
124
pop
()
125
{
126
return
m_impl->
pop
();
127
}
128
129
template
<
class
T,
class
Compare>
130
inline
const
T&
131
PriorityQueue<T, Compare>::
132
top
()
const
133
{
134
return
m_impl->
top
();
135
}
136
137
template
<
class
T,
class
Compare>
138
inline
bool
139
PriorityQueue<T, Compare>::
140
remove
(T& t_)
141
{
142
return
m_impl->
remove
(t_);
143
}
144
145
template
<
class
T,
class
Compare>
146
inline
size_t
147
PriorityQueue<T, Compare>::
148
size
()
149
{
150
return
m_impl->
size
();
151
}
152
153
template
<
class
T,
class
Compare>
154
inline
const
PriorityQueue_Impl<T, Compare>
*
155
PriorityQueue<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&
163
PriorityQueue<T, Compare>::
164
operator[]
(
int
idx)
165
{
166
return
(*m_impl)[idx];
167
}
168
169
}
// end namespace ASSA
170
171
#endif
/* PRIORITY_QUEUE_H */
ASSA::PriorityQueue::remove
virtual bool remove(T &)
Definition:
PriorityQueue.h:140
ASSA::PriorityQueue::operator=
PriorityQueue & operator=(const PriorityQueue &)
ASSA::PriorityQueue::m_comp
Compare m_comp
Definition:
PriorityQueue.h:53
ASSA::PriorityQueue::setHeapImpl
virtual void setHeapImpl(size_t, const Compare &)
Definition:
PriorityQueue.h:93
ASSA::PriorityQueue::pop
virtual T pop()
Definition:
PriorityQueue.h:124
ASSA::PriorityQueue::top
virtual const T & top() const
Definition:
PriorityQueue.h:132
PriorityQueue_Impl.h
ASSA::PriorityQueue_Impl
Class PriorityQueue_Impl.
Definition:
PriorityQueue.h:31
ASSA::PriorityQueue::getPriorityQueueImpl
const PriorityQueue_Impl< T, Compare > * getPriorityQueueImpl() const
Definition:
PriorityQueue.h:156
ASSA::PriorityQueue::size
virtual size_t size()
Definition:
PriorityQueue.h:148
ASSA::PriorityQueue_Heap
Definition:
PriorityQueue_Heap.h:29
ASSA::PriorityQueue::operator[]
virtual T & operator[](int)
Definition:
PriorityQueue.h:164
ASSA::PriorityQueue
Definition:
PriorityQueue.h:34
ASSA::PriorityQueue::PriorityQueue
PriorityQueue(size_t max_=20)
Definition:
PriorityQueue.h:69
ASSA::PriorityQueue::insert
virtual void insert(const T &)
Definition:
PriorityQueue.h:116
Assure.h
ASSA::PriorityQueue::m_impl
PriorityQueue_Impl< T, Compare > * m_impl
Definition:
PriorityQueue.h:59
ASSA::PriorityQueue::~PriorityQueue
virtual ~PriorityQueue()
Definition:
PriorityQueue.h:108
ASSA
Definition:
Acceptor.h:40
PriorityQueue_Heap.h
Generated by
1.8.17