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 ) 52template <class _Tp, class _Sequence = deque<_Tp> > 53# elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS ) 54# define _STLP_QUEUE_ARGS _Tp 55template <class _Tp> 56# else 57template <class _Tp, class _Sequence> 58# endif 59class 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 74public: 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 82protected: 83 //c is a Standard name (23.2.3.1), do no make it STLport naming convention compliant. 84 _Sequence c; 85public: 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 120template < _STLP_QUEUE_HEADER_ARGS > 121inline bool _STLP_CALL 122operator==(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y) { 123 return __x._Get_s() == __y._Get_s(); 124} 125 126template < _STLP_QUEUE_HEADER_ARGS > 127inline bool _STLP_CALL 128operator<(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 )) 135template <class _Tp, class _Sequence = vector<_Tp>, 136 class _Compare = less<_STLP_HEADER_TYPENAME _Sequence::value_type> > 137# elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS ) 138template <class _Tp> 139# else 140template <class _Tp, class _Sequence, class _Compare> 141# endif 142class 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 158public: 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; 165protected: 166 //c is a Standard name (23.2.3.2), do no make it STLport naming convention compliant. 167 _Sequence c; 168 _Compare comp; 169public: 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) 247template <class _Tp, class _Sequence> 248struct __move_traits<queue<_Tp, _Sequence> > : 249 _STLP_PRIV __move_traits_aux<_Sequence> 250{}; 251 252template <class _Tp, class _Sequence, class _Compare> 253struct __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