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
00056
00057
00058
00059
00060 #ifndef __SGI_STL_INTERNAL_QUEUE_H
00061 #define __SGI_STL_INTERNAL_QUEUE_H
00062
00063 #include <bits/concept_check.h>
00064
00065 namespace std
00066 {
00067
00068
00069
00070 template <class _Tp,
00071 class _Sequence = deque<_Tp> >
00072 class queue;
00073
00074 template <class _Tp, class _Seq>
00075 inline bool operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
00076
00077 template <class _Tp, class _Seq>
00078 inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
00079
00080
00081 template <class _Tp, class _Sequence>
00082 class queue
00083 {
00084
00085 __glibcpp_class_requires(_Tp, _SGIAssignableConcept);
00086 __glibcpp_class_requires(_Sequence, _FrontInsertionSequenceConcept);
00087 __glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept);
00088 typedef typename _Sequence::value_type _Sequence_value_type;
00089 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept);
00090
00091 template <class _Tp1, class _Seq1>
00092 friend bool operator== (const queue<_Tp1, _Seq1>&,
00093 const queue<_Tp1, _Seq1>&);
00094 template <class _Tp1, class _Seq1>
00095 friend bool operator< (const queue<_Tp1, _Seq1>&,
00096 const queue<_Tp1, _Seq1>&);
00097 public:
00098 typedef typename _Sequence::value_type value_type;
00099 typedef typename _Sequence::size_type size_type;
00100 typedef _Sequence container_type;
00101
00102 typedef typename _Sequence::reference reference;
00103 typedef typename _Sequence::const_reference const_reference;
00104 protected:
00105 _Sequence c;
00106 public:
00107 explicit queue(const _Sequence& __c = _Sequence()) : c(__c) {}
00108
00109 bool empty() const { return c.empty(); }
00110 size_type size() const { return c.size(); }
00111 reference front() { return c.front(); }
00112 const_reference front() const { return c.front(); }
00113 reference back() { return c.back(); }
00114 const_reference back() const { return c.back(); }
00115 void push(const value_type& __x) { c.push_back(__x); }
00116 void pop() { c.pop_front(); }
00117 };
00118
00119 template <class _Tp, class _Sequence>
00120 bool
00121 operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00122 {
00123 return __x.c == __y.c;
00124 }
00125
00126 template <class _Tp, class _Sequence>
00127 bool
00128 operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00129 {
00130 return __x.c < __y.c;
00131 }
00132
00133 template <class _Tp, class _Sequence>
00134 bool
00135 operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00136 {
00137 return !(__x == __y);
00138 }
00139
00140 template <class _Tp, class _Sequence>
00141 bool
00142 operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00143 {
00144 return __y < __x;
00145 }
00146
00147 template <class _Tp, class _Sequence>
00148 bool
00149 operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00150 {
00151 return !(__y < __x);
00152 }
00153
00154 template <class _Tp, class _Sequence>
00155 bool
00156 operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
00157 {
00158 return !(__x < __y);
00159 }
00160
00161 template <class _Tp,
00162 class _Sequence = vector<_Tp>,
00163 class _Compare = less<typename _Sequence::value_type> >
00164 class priority_queue
00165 {
00166
00167 __glibcpp_class_requires(_Tp, _SGIAssignableConcept);
00168 __glibcpp_class_requires(_Sequence, _SequenceConcept);
00169 __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept);
00170 typedef typename _Sequence::value_type _Sequence_value_type;
00171 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept);
00172 __glibcpp_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept);
00173
00174 public:
00175 typedef typename _Sequence::value_type value_type;
00176 typedef typename _Sequence::size_type size_type;
00177 typedef _Sequence container_type;
00178
00179 typedef typename _Sequence::reference reference;
00180 typedef typename _Sequence::const_reference const_reference;
00181 protected:
00182 _Sequence c;
00183 _Compare comp;
00184 public:
00185 explicit priority_queue(const _Compare& __x = _Compare(),
00186 const _Sequence& __s = _Sequence())
00187 : c(__s), comp(__x)
00188 { make_heap(c.begin(), c.end(), comp); }
00189
00190 template <class _InputIterator>
00191 priority_queue(_InputIterator __first, _InputIterator __last,
00192 const _Compare& __x = _Compare(),
00193 const _Sequence& __s = _Sequence())
00194 : c(__s), comp(__x)
00195 {
00196 c.insert(c.end(), __first, __last);
00197 make_heap(c.begin(), c.end(), comp);
00198 }
00199
00200 bool empty() const { return c.empty(); }
00201 size_type size() const { return c.size(); }
00202 const_reference top() const { return c.front(); }
00203 void push(const value_type& __x) {
00204 __STL_TRY {
00205 c.push_back(__x);
00206 push_heap(c.begin(), c.end(), comp);
00207 }
00208 __STL_UNWIND(c.clear());
00209 }
00210 void pop() {
00211 __STL_TRY {
00212 pop_heap(c.begin(), c.end(), comp);
00213 c.pop_back();
00214 }
00215 __STL_UNWIND(c.clear());
00216 }
00217 };
00218
00219
00220
00221 }
00222
00223 #endif
00224
00225
00226
00227