headers/cpp/stl_queue.h

   1 /*
   2  *
   3  * Copyright (c) 1994
   4  * Hewlett-Packard Company
   5  *
   6  * Permission to use, copy, modify, distribute and sell this software
   7  * and its documentation for any purpose is hereby granted without fee,
   8  * provided that the above copyright notice appear in all copies and
   9  * that both that copyright notice and this permission notice appear
  10  * in supporting documentation.  Hewlett-Packard Company makes no
  11  * representations about the suitability of this software for any
  12  * purpose.  It is provided "as is" without express or implied warranty.
  13  *
  14  *
  15  * Copyright (c) 1996,1997
  16  * Silicon Graphics Computer Systems, Inc.
  17  *
  18  * Permission to use, copy, modify, distribute and sell this software
  19  * and its documentation for any purpose is hereby granted without fee,
  20  * provided that the above copyright notice appear in all copies and
  21  * that both that copyright notice and this permission notice appear
  22  * in supporting documentation.  Silicon Graphics makes no
  23  * representations about the suitability of this software for any
  24  * purpose.  It is provided "as is" without express or implied warranty.
  25  */
  26
  27 /* NOTE: This is an internal header file, included by other STL headers.
  28  *   You should not attempt to use it directly.
  29  */
  30
  31 #ifndef __SGI_STL_INTERNAL_QUEUE_H
  32 #define __SGI_STL_INTERNAL_QUEUE_H
  33
  34 __STL_BEGIN_NAMESPACE
  35
  36 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
  37 template <class _Tp, class _Sequence = deque<_Tp> >
  38 #else
  39 template <class _Tp, class _Sequence>
  40 #endif
  41 class queue {
  42   friend bool operator== __STL_NULL_TMPL_ARGS (const queue&, const queue&);
  43   friend bool operator< __STL_NULL_TMPL_ARGS (const queue&, const queue&);
  44 public:
  45   typedef typename _Sequence::value_type      value_type;
  46   typedef typename _Sequence::size_type       size_type;
  47   typedef          _Sequence                  container_type;
  48
  49   typedef typename _Sequence::reference       reference;
  50   typedef typename _Sequence::const_reference const_reference;
  51 protected:
  52   _Sequence c;
  53 public:
  54   queue() : c() {}
  55   explicit queue(const _Sequence& __c) : c(__c) {}
  56
  57   bool empty() const { return c.empty(); }
  58   size_type size() const { return c.size(); }
  59   reference front() { return c.front(); }
  60   const_reference front() const { return c.front(); }
  61   reference back() { return c.back(); }
  62   const_reference back() const { return c.back(); }
  63   void push(const value_type& __x) { c.push_back(__x); }
  64   void pop() { c.pop_front(); }
  65 };
  66
  67 template <class _Tp, class _Sequence>
  68 bool
  69 operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  70 {
  71   return __x.c == __y.c;
  72 }
  73
  74 template <class _Tp, class _Sequence>
  75 bool
  76 operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  77 {
  78   return __x.c < __y.c;
  79 }
  80
  81 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  82
  83 template <class _Tp, class _Sequence>
  84 bool
  85 operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  86 {
  87   return !(__x == __y);
  88 }
  89
  90 template <class _Tp, class _Sequence>
  91 bool
  92 operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  93 {
  94   return __y < __x;
  95 }
  96
  97 template <class _Tp, class _Sequence>
  98 bool
  99 operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
 100 {
 101   return !(__y < __x);
 102 }
 103
 104 template <class _Tp, class _Sequence>
 105 bool
 106 operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
 107 {
 108   return !(__x < __y);
 109 }
 110
 111 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 112
 113 #ifndef __STL_LIMITED_DEFAULT_TEMPLATES
 114 template <class _Tp, class _Sequence = vector<_Tp>,
 115           class _Compare = less<typename _Sequence::value_type> >
 116 #else
 117 template <class _Tp, class _Sequence, class _Compare>
 118 #endif
 119 class  priority_queue {
 120 public:
 121   typedef typename _Sequence::value_type      value_type;
 122   typedef typename _Sequence::size_type       size_type;
 123   typedef          _Sequence                  container_type;
 124
 125   typedef typename _Sequence::reference       reference;
 126   typedef typename _Sequence::const_reference const_reference;
 127 protected:
 128   _Sequence c;
 129   _Compare comp;
 130 public:
 131   priority_queue() : c() {}
 132   explicit priority_queue(const _Compare& __x) :  c(), comp(__x) {}
 133   priority_queue(const _Compare& __x, const _Sequence& __s)
 134     : c(__s), comp(__x)
 135     { make_heap(c.begin(), c.end(), comp); }
 136
 137 #ifdef __STL_MEMBER_TEMPLATES
 138   template <class _InputIterator>
 139   priority_queue(_InputIterator __first, _InputIterator __last)
 140     : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
 141
 142   template <class _InputIterator>
 143   priority_queue(_InputIterator __first,
 144                  _InputIterator __last, const _Compare& __x)
 145     : c(__first, __last), comp(__x)
 146     { make_heap(c.begin(), c.end(), comp); }
 147
 148   template <class _InputIterator>
 149   priority_queue(_InputIterator __first, _InputIterator __last,
 150                  const _Compare& __x, const _Sequence& __s)
 151   : c(__s), comp(__x)
 152   {
 153     c.insert(c.end(), __first, __last);
 154     make_heap(c.begin(), c.end(), comp);
 155   }
 156
 157 #else /* __STL_MEMBER_TEMPLATES */
 158   priority_queue(const value_type* __first, const value_type* __last)
 159     : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
 160
 161   priority_queue(const value_type* __first, const value_type* __last,
 162                  const _Compare& __x)
 163     : c(__first, __last), comp(__x)
 164     { make_heap(c.begin(), c.end(), comp); }
 165
 166   priority_queue(const value_type* __first, const value_type* __last,
 167                  const _Compare& __x, const _Sequence& __c)
 168     : c(__c), comp(__x)
 169   {
 170     c.insert(c.end(), __first, __last);
 171     make_heap(c.begin(), c.end(), comp);
 172   }
 173 #endif /* __STL_MEMBER_TEMPLATES */
 174
 175   bool empty() const { return c.empty(); }
 176   size_type size() const { return c.size(); }
 177   const_reference top() const { return c.front(); }
 178   void push(const value_type& __x) {
 179     __STL_TRY {
 180       c.push_back(__x);
 181       push_heap(c.begin(), c.end(), comp);
 182     }
 183     __STL_UNWIND(c.clear());
 184   }
 185   void pop() {
 186     __STL_TRY {
 187       pop_heap(c.begin(), c.end(), comp);
 188       c.pop_back();
 189     }
 190     __STL_UNWIND(c.clear());
 191   }
 192 };
 193
 194 // no equality is provided
 195
 196 __STL_END_NAMESPACE
 197
 198 #endif /* __SGI_STL_INTERNAL_QUEUE_H */
 199
 200 // Local Variables:
 201 // mode:C++
 202 // End: