include/c++/stl/stl/_queue.h

   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 #if defined(__SC__) && !defined(__DMC__)    //*ty 12/07/2001 - since "comp" is a built-in type and reserved under SCpp
  50 #  define comp _Comp
  51 #endif
  52
  53 _STLP_BEGIN_NAMESPACE
  54
  55 # if ! defined ( _STLP_LIMITED_DEFAULT_TEMPLATES )
  56 template <class _Tp, class _Sequence = deque<_Tp> >
  57 # elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS )
  58 #  define _STLP_QUEUE_ARGS _Tp
  59 template <class _Tp>
  60 # else
  61 template <class _Tp, class _Sequence>
  62 # endif
  63 class queue
  64 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
  65 #  if defined (_STLP_QUEUE_ARGS)
  66             : public __stlport_class<queue<_Tp> >
  67 #  else
  68             : public __stlport_class<queue<_Tp, _Sequence> >
  69 #  endif
  70 #endif
  71 {
  72 # if defined ( _STLP_QUEUE_ARGS )
  73   typedef deque<_Tp> _Sequence;
  74   typedef queue<_Tp> _Self;
  75 # else
  76   typedef queue<_Tp, _Sequence> _Self;
  77 # endif
  78 public:
  79   typedef typename _Sequence::value_type      value_type;
  80   typedef typename _Sequence::size_type       size_type;
  81   typedef          _Sequence                  container_type;
  82
  83   typedef typename _Sequence::reference       reference;
  84   typedef typename _Sequence::const_reference const_reference;
  85
  86 protected:
  87   //c is a Standard name (23.2.3.1), do no make it STLport naming convention compliant.
  88   _Sequence c;
  89 public:
  90   queue() : c() {}
  91   explicit queue(const _Sequence& __c) : c(__c) {}
  92
  93   queue(__move_source<_Self> src)
  94     : c(_STLP_PRIV _AsMoveSource(src.get().c)) {}
  95
  96   bool empty() const { return c.empty(); }
  97   size_type size() const { return c.size(); }
  98   reference front() { return c.front(); }
  99   const_reference front() const { return c.front(); }
 100   reference back() { return c.back(); }
 101   const_reference back() const { return c.back(); }
 102   void push(const value_type& __x) { c.push_back(__x); }
 103   void pop() { c.pop_front(); }
 104   const _Sequence& _Get_s() const { return c; }
 105 };
 106
 107 #ifndef _STLP_QUEUE_ARGS
 108 #  define _STLP_QUEUE_ARGS _Tp, _Sequence
 109 #  define _STLP_QUEUE_HEADER_ARGS class _Tp, class _Sequence
 110 #else
 111 #  define _STLP_QUEUE_HEADER_ARGS class _Tp
 112 #endif
 113
 114 template < _STLP_QUEUE_HEADER_ARGS >
 115 inline bool _STLP_CALL
 116 operator==(const queue<_STLP_QUEUE_ARGS >& __x, const queue<_STLP_QUEUE_ARGS >& __y) {
 117   return __x._Get_s() == __y._Get_s();
 118 }
 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 _STLP_RELOPS_OPERATORS( template < _STLP_QUEUE_HEADER_ARGS >, queue<_STLP_QUEUE_ARGS > )
 127
 128 # if !(defined ( _STLP_LIMITED_DEFAULT_TEMPLATES ) || defined ( _STLP_TEMPLATE_PARAM_SUBTYPE_BUG ))
 129 template <class _Tp, class _Sequence = vector<_Tp>,
 130           class _Compare = less<_STLP_HEADER_TYPENAME _Sequence::value_type> >
 131 # elif defined ( _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS )
 132 template <class _Tp>
 133 # else
 134 template <class _Tp, class _Sequence, class _Compare>
 135 # endif
 136 class priority_queue
 137 #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
 138 #  if defined (_STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS)
 139             : public __stlport_class<priority_queue<_Tp> >
 140 #  else
 141             : public __stlport_class<priority_queue<_Tp, _Sequence> >
 142 #  endif
 143 #endif
 144 {
 145 # ifdef _STLP_MINIMUM_DEFAULT_TEMPLATE_PARAMS
 146   typedef vector<_Tp> _Sequence;
 147   typedef less< typename vector<_Tp>::value_type> _Compare;
 148   typedef priority_queue<_Tp> _Self;
 149 # else
 150   typedef priority_queue<_Tp, _Sequence, _Compare> _Self;
 151 # endif
 152 public:
 153   typedef typename _Sequence::value_type      value_type;
 154   typedef typename _Sequence::size_type       size_type;
 155   typedef          _Sequence                  container_type;
 156
 157   typedef typename _Sequence::reference       reference;
 158   typedef typename _Sequence::const_reference const_reference;
 159 protected:
 160   //c is a Standard name (23.2.3.2), do no make it STLport naming convention compliant.
 161   _Sequence c;
 162   _Compare comp;
 163 public:
 164   priority_queue() : c() {}
 165   explicit priority_queue(const _Compare& __x) :  c(), comp(__x) {}
 166   priority_queue(const _Compare& __x, const _Sequence& __s)
 167     : c(__s), comp(__x)
 168     { make_heap(c.begin(), c.end(), comp); }
 169
 170   priority_queue(__move_source<_Self> src)
 171     : c(_STLP_PRIV _AsMoveSource(src.get().c)),
 172       comp(_STLP_PRIV _AsMoveSource(src.get().comp)) {}
 173
 174 #ifdef _STLP_MEMBER_TEMPLATES
 175   template <class _InputIterator>
 176   priority_queue(_InputIterator __first, _InputIterator __last)
 177     : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
 178
 179   template <class _InputIterator>
 180   priority_queue(_InputIterator __first,
 181                  _InputIterator __last, const _Compare& __x)
 182     : c(__first, __last), comp(__x)
 183     { make_heap(c.begin(), c.end(), comp); }
 184
 185   template <class _InputIterator>
 186   priority_queue(_InputIterator __first, _InputIterator __last,
 187                  const _Compare& __x, const _Sequence& __s)
 188   : c(__s), comp(__x)
 189   {
 190     c.insert(c.end(), __first, __last);
 191     make_heap(c.begin(), c.end(), comp);
 192   }
 193
 194 #else /* _STLP_MEMBER_TEMPLATES */
 195   priority_queue(const value_type* __first, const value_type* __last)
 196     : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
 197
 198   priority_queue(const value_type* __first, const value_type* __last,
 199                  const _Compare& __x)
 200     : c(__first, __last), comp(__x)
 201     { make_heap(c.begin(), c.end(), comp); }
 202
 203   priority_queue(const value_type* __first, const value_type* __last,
 204                  const _Compare& __x, const _Sequence& __c)
 205     : c(__c), comp(__x)
 206   {
 207     c.insert(c.end(), __first, __last);
 208     make_heap(c.begin(), c.end(), comp);
 209   }
 210 #endif /* _STLP_MEMBER_TEMPLATES */
 211
 212   bool empty() const { return c.empty(); }
 213   size_type size() const { return c.size(); }
 214   const_reference top() const { return c.front(); }
 215   void push(const value_type& __x) {
 216     _STLP_TRY {
 217       c.push_back(__x);
 218       push_heap(c.begin(), c.end(), comp);
 219     }
 220     _STLP_UNWIND(c.clear())
 221   }
 222   void pop() {
 223     _STLP_TRY {
 224       pop_heap(c.begin(), c.end(), comp);
 225       c.pop_back();
 226     }
 227     _STLP_UNWIND(c.clear())
 228   }
 229 };
 230
 231 #if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
 232 template <class _Tp, class _Sequence>
 233 struct __move_traits<queue<_Tp, _Sequence> > :
 234   _STLP_PRIV __move_traits_aux<_Sequence>
 235 {};
 236
 237 template <class _Tp, class _Sequence, class _Compare>
 238 struct __move_traits<priority_queue<_Tp, _Sequence, _Compare> > :
 239   _STLP_PRIV __move_traits_aux2<_Sequence, _Compare>
 240 {};
 241 #endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
 242
 243 _STLP_END_NAMESPACE
 244
 245 #undef _STLP_QUEUE_ARGS
 246 #undef _STLP_QUEUE_HEADER_ARGS
 247 #undef comp
 248
 249 #endif /* _STLP_INTERNAL_QUEUE_H */
 250
 251 // Local Variables:
 252 // mode:C++
 253 // End: