1 /* 2 * 3 * Copyright (c) 1994 4 * Hewlett-Packard Company 5 * 6 * Copyright (c) 1996,1997 7 * Silicon Graphics Computer Systems, Inc. 8 * 9 * Copyright (c) 1997 10 * Moscow Center for SPARC Technology 11 * 12 * Copyright (c) 1999 13 * Boris Fomitchev 14 * 15 * This material is provided "as is", with absolutely no warranty expressed 16 * or implied. Any use is at your own risk. 17 * 18 * Permission to use or copy this software for any purpose is hereby granted 19 * without fee, provided the above notices are retained on all copies. 20 * Permission to modify the code and to distribute modified code is granted, 21 * provided the above notices are retained, and a notice that the code was 22 * modified is included with the above copyright notice. 23 * 24 */ 25 26 /* NOTE: This is an internal header file, included by other STL headers. 27 * You should not attempt to use it directly. 28 */ 29 30 #ifndef _STLP_INTERNAL_QUEUE_H 31 #define _STLP_INTERNAL_QUEUE_H 32 33 #ifndef _STLP_INTERNAL_DEQUE_H 34 # include <stl/_deque.h> 35 #endif 36 37 #ifndef _STLP_INTERNAL_VECTOR_H 38 # include <stl/_vector.h> 39 #endif 40 41 #ifndef _STLP_INTERNAL_HEAP_H 42 # include <stl/_heap.h> 43 #endif 44 45 #ifndef _STLP_INTERNAL_FUNCTION_BASE_H 46 # include <stl/_function_base.h> 47 #endif 48 49 _STLP_BEGIN_NAMESPACE 50 51 # if ! defined ( _STLP_LIMITED_DEFAULT_TEMPLATES ) 52 template <class _Tp, class _Sequence = deque<_Tp> > 53 # elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS ) 54 # define _STLP_QUEUE_ARGS _Tp 55 template <class _Tp> 56 # else 57 template <class _Tp, class _Sequence> 58 # endif 59 class queue 60 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 61 # if defined (_STLP_QUEUE_ARGS) 62 : public __stlport_class<queue<_Tp> > 63 # else 64 : public __stlport_class<queue<_Tp, _Sequence> > 65 # endif 66 #endif 67 { 68 # if defined ( _STLP_QUEUE_ARGS ) 69 typedef deque<_Tp> _Sequence; 70 typedef queue<_Tp> _Self; 71 # else 72 typedef queue<_Tp, _Sequence> _Self; 73 # endif 74 public: 75 typedef typename _Sequence::value_type value_type; 76 typedef typename _Sequence::size_type size_type; 77 typedef _Sequence container_type; 78 79 typedef typename _Sequence::reference reference; 80 typedef typename _Sequence::const_reference const_reference; 81 82 protected: 83 //c is a Standard name (23.2.3.1), do no make it STLport naming convention compliant. 84 _Sequence c; 85 public: 86 queue() : c() {} 87 explicit queue(const _Sequence& __c) : c(__c) {} 88 89 #if !defined (_STLP_NO_MOVE_SEMANTIC) 90 queue(__move_source<_Self> src) 91 : c(_STLP_PRIV _AsMoveSource(src.get().c)) {} 92 #endif 93 94 bool empty() const { return c.empty(); } 95 size_type size() const { return c.size(); } 96 reference front() { return c.front(); } 97 const_reference front() const { return c.front(); } 98 reference back() { return c.back(); } 99 const_reference back() const { return c.back(); } 100 void push(const value_type& __x) { c.push_back(__x); } 101 void pop() { c.pop_front(); } 102 const _Sequence& _Get_s() const { return c; } 103 104 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 105 void _M_swap_workaround(_Self& __x) { 106 _Sequence __tmp = c; 107 c = __x.c; 108 __x.c = __tmp; 109 } 110 #endif 111 }; 112 113 #ifndef _STLP_QUEUE_ARGS 114 # define _STLP_QUEUE_ARGS _Tp, _Sequence 115 # define _STLP_QUEUE_HEADER_ARGS class _Tp, class _Sequence 116 #else 117 # define _STLP_QUEUE_HEADER_ARGS class _Tp 118 #endif 119 120 template < _STLP_QUEUE_HEADER_ARGS > 121 inline bool _STLP_CALL 122 operator==(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y) { 123 return __x._Get_s() == __y._Get_s(); 124 } 125 126 template < _STLP_QUEUE_HEADER_ARGS > 127 inline bool _STLP_CALL 128 operator<(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y) { 129 return __x._Get_s() < __y._Get_s(); 130 } 131 132 _STLP_RELOPS_OPERATORS( template < _STLP_QUEUE_HEADER_ARGS >, queue<_STLP_QUEUE_ARGS > ) 133 134 # if !(defined ( _STLP_LIMITED_DEFAULT_TEMPLATES ) || defined ( _STLP_TEMPLATE_PARAM_SUBTYPE_BUG )) 135 template <class _Tp, class _Sequence = vector<_Tp>, 136 class _Compare = less<_STLP_HEADER_TYPENAME _Sequence::value_type> > 137 # elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS ) 138 template <class _Tp> 139 # else 140 template <class _Tp, class _Sequence, class _Compare> 141 # endif 142 class priority_queue 143 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) 144 # if defined (_STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS) 145 : public __stlport_class<priority_queue<_Tp> > 146 # else 147 : public __stlport_class<priority_queue<_Tp, _Sequence> > 148 # endif 149 #endif 150 { 151 # ifdef _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS 152 typedef vector<_Tp> _Sequence; 153 typedef less< typename vector<_Tp>::value_type> _Compare; 154 typedef priority_queue<_Tp> _Self; 155 # else 156 typedef priority_queue<_Tp, _Sequence, _Compare> _Self; 157 # endif 158 public: 159 typedef typename _Sequence::value_type value_type; 160 typedef typename _Sequence::size_type size_type; 161 typedef _Sequence container_type; 162 163 typedef typename _Sequence::reference reference; 164 typedef typename _Sequence::const_reference const_reference; 165 protected: 166 //c is a Standard name (23.2.3.2), do no make it STLport naming convention compliant. 167 _Sequence c; 168 _Compare comp; 169 public: 170 priority_queue() : c() {} 171 explicit priority_queue(const _Compare& __x) : c(), comp(__x) {} 172 priority_queue(const _Compare& __x, const _Sequence& __s) 173 : c(__s), comp(__x) 174 { make_heap(c.begin(), c.end(), comp); } 175 176 #if !defined (_STLP_NO_MOVE_SEMANTIC) 177 priority_queue(__move_source<_Self> src) 178 : c(_STLP_PRIV _AsMoveSource(src.get().c)), 179 comp(_STLP_PRIV _AsMoveSource(src.get().comp)) {} 180 #endif 181 182 #ifdef _STLP_MEMBER_TEMPLATES 183 template <class _InputIterator> 184 priority_queue(_InputIterator __first, _InputIterator __last) 185 : c(__first, __last) { make_heap(c.begin(), c.end(), comp); } 186 187 template <class _InputIterator> 188 priority_queue(_InputIterator __first, 189 _InputIterator __last, const _Compare& __x) 190 : c(__first, __last), comp(__x) 191 { make_heap(c.begin(), c.end(), comp); } 192 193 template <class _InputIterator> 194 priority_queue(_InputIterator __first, _InputIterator __last, 195 const _Compare& __x, const _Sequence& __s) 196 : c(__s), comp(__x) 197 { 198 c.insert(c.end(), __first, __last); 199 make_heap(c.begin(), c.end(), comp); 200 } 201 202 #else /* _STLP_MEMBER_TEMPLATES */ 203 priority_queue(const value_type* __first, const value_type* __last) 204 : c(__first, __last) { make_heap(c.begin(), c.end(), comp); } 205 206 priority_queue(const value_type* __first, const value_type* __last, 207 const _Compare& __x) 208 : c(__first, __last), comp(__x) 209 { make_heap(c.begin(), c.end(), comp); } 210 211 priority_queue(const value_type* __first, const value_type* __last, 212 const _Compare& __x, const _Sequence& __c) 213 : c(__c), comp(__x) 214 { 215 c.insert(c.end(), __first, __last); 216 make_heap(c.begin(), c.end(), comp); 217 } 218 #endif /* _STLP_MEMBER_TEMPLATES */ 219 220 bool empty() const { return c.empty(); } 221 size_type size() const { return c.size(); } 222 const_reference top() const { return c.front(); } 223 void push(const value_type& __x) { 224 _STLP_TRY { 225 c.push_back(__x); 226 push_heap(c.begin(), c.end(), comp); 227 } 228 _STLP_UNWIND(c.clear()) 229 } 230 void pop() { 231 _STLP_TRY { 232 pop_heap(c.begin(), c.end(), comp); 233 c.pop_back(); 234 } 235 _STLP_UNWIND(c.clear()) 236 } 237 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER) 238 void _M_swap_workaround(_Self& __x) { 239 _Sequence __tmp = c; 240 c = __x.c; 241 __x.c = __tmp; 242 } 243 #endif 244 }; 245 246 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION) && !defined (_STLP_NO_MOVE_SEMANTIC) 247 template <class _Tp, class _Sequence> 248 struct __move_traits<queue<_Tp, _Sequence> > : 249 _STLP_PRIV __move_traits_aux<_Sequence> 250 {}; 251 252 template <class _Tp, class _Sequence, class _Compare> 253 struct __move_traits<priority_queue<_Tp, _Sequence, _Compare> > : 254 _STLP_PRIV __move_traits_aux2<_Sequence, _Compare> 255 {}; 256 #endif 257 258 _STLP_END_NAMESPACE 259 260 #undef _STLP_QUEUE_ARGS 261 #undef _STLP_QUEUE_HEADER_ARGS 262 #undef comp 263 264 #endif /* _STLP_INTERNAL_QUEUE_H */ 265 266 // Local Variables: 267 // mode:C++ 268 // End: 269
