00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00061
#ifndef __GLIBCPP_INTERNAL_QUEUE_H
00062
#define __GLIBCPP_INTERNAL_QUEUE_H
00063
00064
#include <bits/concept_check.h>
00065
00066
namespace std
00067 {
00068
00069
00070
00071
template <
class _Tp,
00072
class _Sequence = deque<_Tp> >
00073
class queue;
00074
00075
template <
class _Tp,
class _Seq>
00076
inline bool operator==(
const queue<_Tp, _Seq>&,
const queue<_Tp, _Seq>&);
00077
00078
template <
class _Tp,
class _Seq>
00079
inline bool operator<(const queue<_Tp, _Seq>&,
const queue<_Tp, _Seq>&);
00080
00081
00082
template <
class _Tp,
class _Sequence>
00083
class queue
00084 {
00085
00086 __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00087 __glibcpp_class_requires(_Sequence, _FrontInsertionSequenceConcept)
00088 __glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept)
00089 typedef typename _Sequence::value_type _Sequence_value_type;
00090 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept);
00091
00092 template <class _Tp1, class _Seq1>
00093 friend
bool operator== (const queue<_Tp1, _Seq1>&,
00094 const queue<_Tp1, _Seq1>&);
00095 template <class _Tp1, class _Seq1>
00096 friend
bool operator< (const queue<_Tp1, _Seq1>&,
00097 const queue<_Tp1, _Seq1>&);
00098 public:
00099 typedef typename _Sequence::value_type value_type;
00100 typedef typename _Sequence::size_type size_type;
00101 typedef _Sequence container_type;
00102
00103 typedef typename _Sequence::reference reference;
00104 typedef typename _Sequence::const_reference const_reference;
00105 protected:
00106 _Sequence c;
00107 public:
00108 explicit queue(const _Sequence& __c = _Sequence()) : c(__c) {}
00109
00110
bool empty()
const {
return c.empty(); }
00111 size_type size()
const {
return c.size(); }
00112 reference front() {
return c.front(); }
00113 const_reference front()
const {
return c.front(); }
00114 reference back() {
return c.back(); }
00115 const_reference back()
const {
return c.back(); }
00116
void push(
const value_type& __x) { c.push_back(__x); }
00117
void pop() { c.pop_front(); }
00118 };
00119
00120
template <
class _Tp,
class _Sequence>
00121
bool
00122
operator==(
const queue<_Tp, _Sequence>& __x,
const queue<_Tp, _Sequence>& __y)
00123 {
00124
return __x.c == __y.c;
00125 }
00126
00127
template <
class _Tp,
class _Sequence>
00128
bool
00129 operator<(const queue<_Tp, _Sequence>& __x,
const queue<_Tp, _Sequence>& __y)
00130 {
00131
return __x.c < __y.c;
00132 }
00133
00134
template <
class _Tp,
class _Sequence>
00135
bool
00136
operator!=(
const queue<_Tp, _Sequence>& __x,
const queue<_Tp, _Sequence>& __y)
00137 {
00138
return !(__x == __y);
00139 }
00140
00141
template <
class _Tp,
class _Sequence>
00142
bool
00143
operator>(
const queue<_Tp, _Sequence>& __x,
const queue<_Tp, _Sequence>& __y)
00144 {
00145
return __y < __x;
00146 }
00147
00148
template <
class _Tp,
class _Sequence>
00149
bool
00150 operator<=(const queue<_Tp, _Sequence>& __x,
const queue<_Tp, _Sequence>& __y)
00151 {
00152
return !(__y < __x);
00153 }
00154
00155
template <
class _Tp,
class _Sequence>
00156
bool
00157
operator>=(
const queue<_Tp, _Sequence>& __x,
const queue<_Tp, _Sequence>& __y)
00158 {
00159
return !(__x < __y);
00160 }
00161
00162
template <
class _Tp,
00163
class _Sequence = vector<_Tp>,
00164
class _Compare = less<typename _Sequence::value_type> >
00165
class priority_queue
00166 {
00167
00168 __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
00169 __glibcpp_class_requires(_Sequence, _SequenceConcept)
00170 __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept)
00171 typedef typename _Sequence::value_type _Sequence_value_type;
00172 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept);
00173 __glibcpp_class_requires4(_Compare,
bool, _Tp, _Tp, _BinaryFunctionConcept);
00174
00175 public:
00176 typedef typename _Sequence::value_type value_type;
00177 typedef typename _Sequence::size_type size_type;
00178 typedef _Sequence container_type;
00179
00180 typedef typename _Sequence::reference reference;
00181 typedef typename _Sequence::const_reference const_reference;
00182 protected:
00183 _Sequence c;
00184 _Compare comp;
00185 public:
00186 explicit priority_queue(const _Compare& __x = _Compare(),
00187 const _Sequence& __s = _Sequence())
00188 : c(__s), comp(__x)
00189 { make_heap(c.begin(), c.end(), comp); }
00190
00191
template <
class _InputIterator>
00192 priority_queue(_InputIterator __first, _InputIterator __last,
00193
const _Compare& __x = _Compare(),
00194
const _Sequence& __s = _Sequence())
00195 : c(__s), comp(__x)
00196 {
00197 c.insert(c.end(), __first, __last);
00198 make_heap(c.begin(), c.end(), comp);
00199 }
00200
00201
bool empty()
const {
return c.empty(); }
00202 size_type size()
const {
return c.size(); }
00203 const_reference top()
const {
return c.front(); }
00204
00205
void
00206 push(
const value_type& __x)
00207 {
00208
try
00209 {
00210 c.push_back(__x);
00211 push_heap(c.begin(), c.end(), comp);
00212 }
00213
catch(...)
00214 {
00215 c.clear();
00216 __throw_exception_again;
00217 }
00218 }
00219
00220
void
00221 pop()
00222 {
00223
try
00224 {
00225 pop_heap(c.begin(), c.end(), comp);
00226 c.pop_back();
00227 }
00228
catch(...)
00229 {
00230 c.clear();
00231 __throw_exception_again;
00232 }
00233 }
00234 };
00235
00236
00237
00238 }
00239
00240
#endif
00241
00242
00243
00244