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 _QUEUE_H
00062 #define _QUEUE_H 1
00063
00064 #include <bits/concept_check.h>
00065 #include <debug/debug.h>
00066
00067 namespace std
00068 {
00069
00070 template<typename _Tp, typename _Sequence = deque<_Tp> >
00071 class queue;
00072
00073 template<typename _Tp, typename _Seq>
00074 inline bool
00075 operator==(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
00076
00077 template<typename _Tp, typename _Seq>
00078 inline bool
00079 operator<(const queue<_Tp,_Seq>&, const queue<_Tp,_Seq>&);
00080
00105 template<typename _Tp, typename _Sequence>
00106 class queue
00107 {
00108
00109 typedef typename _Sequence::value_type _Sequence_value_type;
00110 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00111 __glibcxx_class_requires(_Sequence, _FrontInsertionSequenceConcept)
00112 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
00113 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00114
00115 template<typename _Tp1, typename _Seq1>
00116 friend bool
00117 operator==(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
00118
00119 template<typename _Tp1, typename _Seq1>
00120 friend bool
00121 operator<(const queue<_Tp1, _Seq1>&, const queue<_Tp1, _Seq1>&);
00122
00123 public:
00124 typedef typename _Sequence::value_type value_type;
00125 typedef typename _Sequence::reference reference;
00126 typedef typename _Sequence::const_reference const_reference;
00127 typedef typename _Sequence::size_type size_type;
00128 typedef _Sequence container_type;
00129
00130 protected:
00139 _Sequence c;
00140
00141 public:
00145 explicit
00146 queue(const _Sequence& __c = _Sequence()) : c(__c) {}
00147
00151 bool
00152 empty() const
00153 { return c.empty(); }
00154
00156 size_type
00157 size() const
00158 { return c.size(); }
00159
00164 reference
00165 front()
00166 {
00167 __glibcxx_requires_nonempty();
00168 return c.front();
00169 }
00170
00175 const_reference
00176 front() const
00177 {
00178 __glibcxx_requires_nonempty();
00179 return c.front();
00180 }
00181
00186 reference
00187 back()
00188 {
00189 __glibcxx_requires_nonempty();
00190 return c.back();
00191 }
00192
00197 const_reference
00198 back() const
00199 {
00200 __glibcxx_requires_nonempty();
00201 return c.back();
00202 }
00203
00213 void
00214 push(const value_type& __x)
00215 { c.push_back(__x); }
00216
00228 void
00229 pop()
00230 {
00231 __glibcxx_requires_nonempty();
00232 c.pop_front();
00233 }
00234 };
00235
00236
00248 template<typename _Tp, typename _Sequence>
00249 inline bool
00250 operator==(const queue<_Tp,_Sequence>& __x,
00251 const queue<_Tp,_Sequence>& __y)
00252 { return __x.c == __y.c; }
00253
00267 template<typename _Tp, typename _Sequence>
00268 inline bool
00269 operator<(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
00270 { return __x.c < __y.c; }
00271
00273 template<typename _Tp, typename _Sequence>
00274 inline bool
00275 operator!=(const queue<_Tp,_Sequence>& __x,
00276 const queue<_Tp,_Sequence>& __y)
00277 { return !(__x == __y); }
00278
00280 template<typename _Tp, typename _Sequence>
00281 inline bool
00282 operator>(const queue<_Tp,_Sequence>& __x, const queue<_Tp,_Sequence>& __y)
00283 { return __y < __x; }
00284
00286 template<typename _Tp, typename _Sequence>
00287 inline bool
00288 operator<=(const queue<_Tp,_Sequence>& __x,
00289 const queue<_Tp,_Sequence>& __y)
00290 { return !(__y < __x); }
00291
00293 template<typename _Tp, typename _Sequence>
00294 inline bool
00295 operator>=(const queue<_Tp,_Sequence>& __x,
00296 const queue<_Tp,_Sequence>& __y)
00297 { return !(__x < __y); }
00298
00337 template<typename _Tp, typename _Sequence = vector<_Tp>,
00338 typename _Compare = less<typename _Sequence::value_type> >
00339 class priority_queue
00340 {
00341
00342 typedef typename _Sequence::value_type _Sequence_value_type;
00343 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
00344 __glibcxx_class_requires(_Sequence, _SequenceConcept)
00345 __glibcxx_class_requires(_Sequence, _RandomAccessContainerConcept)
00346 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
00347 __glibcxx_class_requires4(_Compare, bool, _Tp,_Tp,_BinaryFunctionConcept)
00348
00349 public:
00350 typedef typename _Sequence::value_type value_type;
00351 typedef typename _Sequence::reference reference;
00352 typedef typename _Sequence::const_reference const_reference;
00353 typedef typename _Sequence::size_type size_type;
00354 typedef _Sequence container_type;
00355
00356 protected:
00357
00358 _Sequence c;
00359 _Compare comp;
00360
00361 public:
00365 explicit
00366 priority_queue(const _Compare& __x = _Compare(),
00367 const _Sequence& __s = _Sequence())
00368 : c(__s), comp(__x)
00369 { std::make_heap(c.begin(), c.end(), comp); }
00370
00386 template<typename _InputIterator>
00387 priority_queue(_InputIterator __first, _InputIterator __last,
00388 const _Compare& __x = _Compare(),
00389 const _Sequence& __s = _Sequence())
00390 : c(__s), comp(__x)
00391 {
00392 __glibcxx_requires_valid_range(__first, __last);
00393 c.insert(c.end(), __first, __last);
00394 std::make_heap(c.begin(), c.end(), comp);
00395 }
00396
00400 bool
00401 empty() const { return c.empty(); }
00402
00404 size_type
00405 size() const { return c.size(); }
00406
00411 const_reference
00412 top() const
00413 {
00414 __glibcxx_requires_nonempty();
00415 return c.front();
00416 }
00417
00426 void
00427 push(const value_type& __x)
00428 {
00429 try
00430 {
00431 c.push_back(__x);
00432 std::push_heap(c.begin(), c.end(), comp);
00433 }
00434 catch(...)
00435 {
00436 c.clear();
00437 __throw_exception_again;
00438 }
00439 }
00440
00452 void
00453 pop()
00454 {
00455 __glibcxx_requires_nonempty();
00456 try
00457 {
00458 std::pop_heap(c.begin(), c.end(), comp);
00459 c.pop_back();
00460 }
00461 catch(...)
00462 {
00463 c.clear();
00464 __throw_exception_again;
00465 }
00466 }
00467 };
00468
00469
00470 }
00471
00472 #endif