williamr@2
|
1 |
/*
|
williamr@2
|
2 |
*
|
williamr@2
|
3 |
* Copyright (c) 1994
|
williamr@2
|
4 |
* Hewlett-Packard Company
|
williamr@2
|
5 |
*
|
williamr@2
|
6 |
* Copyright (c) 1996,1997
|
williamr@2
|
7 |
* Silicon Graphics Computer Systems, Inc.
|
williamr@2
|
8 |
*
|
williamr@2
|
9 |
* Copyright (c) 1997
|
williamr@2
|
10 |
* Moscow Center for SPARC Technology
|
williamr@2
|
11 |
*
|
williamr@2
|
12 |
* Copyright (c) 1999
|
williamr@2
|
13 |
* Boris Fomitchev
|
williamr@2
|
14 |
*
|
williamr@2
|
15 |
* This material is provided "as is", with absolutely no warranty expressed
|
williamr@2
|
16 |
* or implied. Any use is at your own risk.
|
williamr@2
|
17 |
*
|
williamr@2
|
18 |
* Permission to use or copy this software for any purpose is hereby granted
|
williamr@2
|
19 |
* without fee, provided the above notices are retained on all copies.
|
williamr@2
|
20 |
* Permission to modify the code and to distribute modified code is granted,
|
williamr@2
|
21 |
* provided the above notices are retained, and a notice that the code was
|
williamr@2
|
22 |
* modified is included with the above copyright notice.
|
williamr@2
|
23 |
*
|
williamr@2
|
24 |
*/
|
williamr@2
|
25 |
|
williamr@2
|
26 |
/* NOTE: This is an internal header file, included by other STL headers.
|
williamr@2
|
27 |
* You should not attempt to use it directly.
|
williamr@2
|
28 |
*/
|
williamr@2
|
29 |
|
williamr@2
|
30 |
#ifndef _STLP_INTERNAL_QUEUE_H
|
williamr@2
|
31 |
#define _STLP_INTERNAL_QUEUE_H
|
williamr@2
|
32 |
|
williamr@2
|
33 |
#ifndef _STLP_INTERNAL_DEQUE_H
|
williamr@2
|
34 |
# include <stl/_deque.h>
|
williamr@2
|
35 |
#endif
|
williamr@2
|
36 |
|
williamr@2
|
37 |
#ifndef _STLP_INTERNAL_VECTOR_H
|
williamr@2
|
38 |
# include <stl/_vector.h>
|
williamr@2
|
39 |
#endif
|
williamr@2
|
40 |
|
williamr@2
|
41 |
#ifndef _STLP_INTERNAL_HEAP_H
|
williamr@2
|
42 |
# include <stl/_heap.h>
|
williamr@2
|
43 |
#endif
|
williamr@2
|
44 |
|
williamr@2
|
45 |
#ifndef _STLP_INTERNAL_FUNCTION_H
|
williamr@2
|
46 |
# include <stl/_function.h>
|
williamr@2
|
47 |
#endif
|
williamr@2
|
48 |
|
williamr@2
|
49 |
#if defined(__SC__) && !defined(__DMC__) //*ty 12/07/2001 - since "comp" is a built-in type and reserved under SCpp
|
williamr@2
|
50 |
#define comp _Comp
|
williamr@2
|
51 |
#endif
|
williamr@2
|
52 |
|
williamr@2
|
53 |
_STLP_BEGIN_NAMESPACE
|
williamr@2
|
54 |
|
williamr@2
|
55 |
# if ! defined ( _STLP_LIMITED_DEFAULT_TEMPLATES )
|
williamr@2
|
56 |
template <class _Tp, class _Sequence = deque<_Tp> >
|
williamr@2
|
57 |
# elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS )
|
williamr@2
|
58 |
# define _STLP_QUEUE_ARGS _Tp
|
williamr@2
|
59 |
template <class _Tp>
|
williamr@2
|
60 |
# else
|
williamr@2
|
61 |
template <class _Tp, class _Sequence>
|
williamr@2
|
62 |
# endif
|
williamr@2
|
63 |
|
williamr@2
|
64 |
class queue {
|
williamr@2
|
65 |
# if defined ( _STLP_QUEUE_ARGS )
|
williamr@2
|
66 |
typedef deque<_Tp> _Sequence;
|
williamr@2
|
67 |
# endif
|
williamr@2
|
68 |
public:
|
williamr@2
|
69 |
typedef typename _Sequence::value_type value_type;
|
williamr@2
|
70 |
typedef typename _Sequence::size_type size_type;
|
williamr@2
|
71 |
typedef _Sequence container_type;
|
williamr@2
|
72 |
|
williamr@2
|
73 |
typedef typename _Sequence::reference reference;
|
williamr@2
|
74 |
typedef typename _Sequence::const_reference const_reference;
|
williamr@2
|
75 |
|
williamr@2
|
76 |
protected:
|
williamr@2
|
77 |
_Sequence c;
|
williamr@2
|
78 |
public:
|
williamr@2
|
79 |
queue() : c() {}
|
williamr@2
|
80 |
explicit queue(const _Sequence& __c) : c(__c) {}
|
williamr@2
|
81 |
|
williamr@2
|
82 |
bool empty() const { return c.empty(); }
|
williamr@2
|
83 |
size_type size() const { return c.size(); }
|
williamr@2
|
84 |
reference front() { return c.front(); }
|
williamr@2
|
85 |
const_reference front() const { return c.front(); }
|
williamr@2
|
86 |
reference back() { return c.back(); }
|
williamr@2
|
87 |
const_reference back() const { return c.back(); }
|
williamr@2
|
88 |
void push(const value_type& __x) { c.push_back(__x); }
|
williamr@2
|
89 |
void pop() { c.pop_front(); }
|
williamr@2
|
90 |
const _Sequence& _Get_c() const { return c; }
|
williamr@2
|
91 |
};
|
williamr@2
|
92 |
|
williamr@2
|
93 |
# ifndef _STLP_QUEUE_ARGS
|
williamr@2
|
94 |
# define _STLP_QUEUE_ARGS _Tp, _Sequence
|
williamr@2
|
95 |
# define _STLP_QUEUE_HEADER_ARGS class _Tp, class _Sequence
|
williamr@2
|
96 |
# else
|
williamr@2
|
97 |
# define _STLP_QUEUE_HEADER_ARGS class _Tp
|
williamr@2
|
98 |
# endif
|
williamr@2
|
99 |
|
williamr@2
|
100 |
template < _STLP_QUEUE_HEADER_ARGS >
|
williamr@2
|
101 |
inline bool _STLP_CALL
|
williamr@2
|
102 |
operator==(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y)
|
williamr@2
|
103 |
{
|
williamr@2
|
104 |
return __x._Get_c() == __y._Get_c();
|
williamr@2
|
105 |
}
|
williamr@2
|
106 |
|
williamr@2
|
107 |
template < _STLP_QUEUE_HEADER_ARGS >
|
williamr@2
|
108 |
inline bool _STLP_CALL
|
williamr@2
|
109 |
operator<(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y)
|
williamr@2
|
110 |
{
|
williamr@2
|
111 |
return __x._Get_c() < __y._Get_c();
|
williamr@2
|
112 |
}
|
williamr@2
|
113 |
|
williamr@2
|
114 |
_STLP_RELOPS_OPERATORS( template < _STLP_QUEUE_HEADER_ARGS >, queue<_STLP_QUEUE_ARGS > )
|
williamr@2
|
115 |
|
williamr@2
|
116 |
# if !(defined ( _STLP_LIMITED_DEFAULT_TEMPLATES ) || defined ( _STLP_TEMPLATE_PARAM_SUBTYPE_BUG ))
|
williamr@2
|
117 |
template <class _Tp, class _Sequence = vector<_Tp>,
|
williamr@2
|
118 |
class _Compare = less<_STLP_HEADER_TYPENAME _Sequence::value_type> >
|
williamr@2
|
119 |
# elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS )
|
williamr@2
|
120 |
template <class _Tp>
|
williamr@2
|
121 |
# else
|
williamr@2
|
122 |
template <class _Tp, class _Sequence, class _Compare>
|
williamr@2
|
123 |
# endif
|
williamr@2
|
124 |
class priority_queue {
|
williamr@2
|
125 |
# ifdef _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS
|
williamr@2
|
126 |
typedef vector<_Tp> _Sequence;
|
williamr@2
|
127 |
typedef less< typename vector<_Tp>::value_type> _Compare;
|
williamr@2
|
128 |
# endif
|
williamr@2
|
129 |
public:
|
williamr@2
|
130 |
typedef typename _Sequence::value_type value_type;
|
williamr@2
|
131 |
typedef typename _Sequence::size_type size_type;
|
williamr@2
|
132 |
typedef _Sequence container_type;
|
williamr@2
|
133 |
|
williamr@2
|
134 |
typedef typename _Sequence::reference reference;
|
williamr@2
|
135 |
typedef typename _Sequence::const_reference const_reference;
|
williamr@2
|
136 |
protected:
|
williamr@2
|
137 |
_Sequence c;
|
williamr@2
|
138 |
_Compare comp;
|
williamr@2
|
139 |
public:
|
williamr@2
|
140 |
priority_queue() : c() {}
|
williamr@2
|
141 |
explicit priority_queue(const _Compare& __x) : c(), comp(__x) {}
|
williamr@2
|
142 |
explicit priority_queue(const _Compare& __x, const _Sequence& __s)
|
williamr@2
|
143 |
: c(__s), comp(__x)
|
williamr@2
|
144 |
{ make_heap(c.begin(), c.end(), comp); }
|
williamr@2
|
145 |
|
williamr@2
|
146 |
#ifdef _STLP_MEMBER_TEMPLATES
|
williamr@2
|
147 |
template <class _InputIterator>
|
williamr@2
|
148 |
priority_queue(_InputIterator __first, _InputIterator __last)
|
williamr@2
|
149 |
: c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
|
williamr@2
|
150 |
|
williamr@2
|
151 |
template <class _InputIterator>
|
williamr@2
|
152 |
priority_queue(_InputIterator __first,
|
williamr@2
|
153 |
_InputIterator __last, const _Compare& __x)
|
williamr@2
|
154 |
: c(__first, __last), comp(__x)
|
williamr@2
|
155 |
{ make_heap(c.begin(), c.end(), comp); }
|
williamr@2
|
156 |
|
williamr@2
|
157 |
template <class _InputIterator>
|
williamr@2
|
158 |
priority_queue(_InputIterator __first, _InputIterator __last,
|
williamr@2
|
159 |
const _Compare& __x, const _Sequence& __s)
|
williamr@2
|
160 |
: c(__s), comp(__x)
|
williamr@2
|
161 |
{
|
williamr@2
|
162 |
c.insert(c.end(), __first, __last);
|
williamr@2
|
163 |
make_heap(c.begin(), c.end(), comp);
|
williamr@2
|
164 |
}
|
williamr@2
|
165 |
|
williamr@2
|
166 |
#else /* _STLP_MEMBER_TEMPLATES */
|
williamr@2
|
167 |
priority_queue(const value_type* __first, const value_type* __last)
|
williamr@2
|
168 |
: c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
|
williamr@2
|
169 |
|
williamr@2
|
170 |
priority_queue(const value_type* __first, const value_type* __last,
|
williamr@2
|
171 |
const _Compare& __x)
|
williamr@2
|
172 |
: c(__first, __last), comp(__x)
|
williamr@2
|
173 |
{ make_heap(c.begin(), c.end(), comp); }
|
williamr@2
|
174 |
|
williamr@2
|
175 |
priority_queue(const value_type* __first, const value_type* __last,
|
williamr@2
|
176 |
const _Compare& __x, const _Sequence& __c)
|
williamr@2
|
177 |
: c(__c), comp(__x)
|
williamr@2
|
178 |
{
|
williamr@2
|
179 |
c.insert(c.end(), __first, __last);
|
williamr@2
|
180 |
make_heap(c.begin(), c.end(), comp);
|
williamr@2
|
181 |
}
|
williamr@2
|
182 |
#endif /* _STLP_MEMBER_TEMPLATES */
|
williamr@2
|
183 |
|
williamr@2
|
184 |
bool empty() const { return c.empty(); }
|
williamr@2
|
185 |
size_type size() const { return c.size(); }
|
williamr@2
|
186 |
const_reference top() const { return c.front(); }
|
williamr@2
|
187 |
void push(const value_type& __x) {
|
williamr@2
|
188 |
_STLP_TRY {
|
williamr@2
|
189 |
c.push_back(__x);
|
williamr@2
|
190 |
push_heap(c.begin(), c.end(), comp);
|
williamr@2
|
191 |
}
|
williamr@2
|
192 |
_STLP_UNWIND(c.clear());
|
williamr@2
|
193 |
}
|
williamr@2
|
194 |
void pop() {
|
williamr@2
|
195 |
_STLP_TRY {
|
williamr@2
|
196 |
pop_heap(c.begin(), c.end(), comp);
|
williamr@2
|
197 |
c.pop_back();
|
williamr@2
|
198 |
}
|
williamr@2
|
199 |
_STLP_UNWIND(c.clear());
|
williamr@2
|
200 |
}
|
williamr@2
|
201 |
};
|
williamr@2
|
202 |
|
williamr@2
|
203 |
_STLP_END_NAMESPACE
|
williamr@2
|
204 |
|
williamr@2
|
205 |
# undef _STLP_QUEUE_ARGS
|
williamr@2
|
206 |
# undef _STLP_QUEUE_HEADER_ARGS
|
williamr@2
|
207 |
|
williamr@2
|
208 |
#endif /* _STLP_INTERNAL_QUEUE_H */
|
williamr@2
|
209 |
|
williamr@2
|
210 |
// Local Variables:
|
williamr@2
|
211 |
// mode:C++
|
williamr@2
|
212 |
// End:
|