libstdc++-v3/bits/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 // Forward declarations of operators < and ==, needed for friend declaration.
  37
  38 template <class _Tp,
  39           class _Sequence = deque<_Tp> >
  40 class queue;
  41
  42 template <class _Tp, class _Seq>
  43 inline bool operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
  44
  45 template <class _Tp, class _Seq>
  46 inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
  47
  48
  49 template <class _Tp, class _Sequence>
  50 class queue {
  51
  52 #ifdef __STL_MEMBER_TEMPLATES
  53   template <class _Tp1, class _Seq1>
  54   friend bool operator== (const queue<_Tp1, _Seq1>&,
  55                           const queue<_Tp1, _Seq1>&);
  56   template <class _Tp1, class _Seq1>
  57   friend bool operator< (const queue<_Tp1, _Seq1>&,
  58                          const queue<_Tp1, _Seq1>&);
  59 #else /* __STL_MEMBER_TEMPLATES */
  60   friend bool __STD_QUALIFIER
  61   operator== __STL_NULL_TMPL_ARGS (const queue&, const queue&);
  62   friend bool __STD_QUALIFIER
  63   operator<  __STL_NULL_TMPL_ARGS (const queue&, const queue&);
  64 #endif /* __STL_MEMBER_TEMPLATES */
  65
  66 public:
  67   typedef typename _Sequence::value_type      value_type;
  68   typedef typename _Sequence::size_type       size_type;
  69   typedef          _Sequence                  container_type;
  70
  71   typedef typename _Sequence::reference       reference;
  72   typedef typename _Sequence::const_reference const_reference;
  73 protected:
  74   _Sequence c;
  75 public:
  76   queue() : c() {}
  77   explicit queue(const _Sequence& __c) : c(__c) {}
  78
  79   bool empty() const { return c.empty(); }
  80   size_type size() const { return c.size(); }
  81   reference front() { return c.front(); }
  82   const_reference front() const { return c.front(); }
  83   reference back() { return c.back(); }
  84   const_reference back() const { return c.back(); }
  85   void push(const value_type& __x) { c.push_back(__x); }
  86   void pop() { c.pop_front(); }
  87 };
  88
  89 template <class _Tp, class _Sequence>
  90 bool
  91 operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  92 {
  93   return __x.c == __y.c;
  94 }
  95
  96 template <class _Tp, class _Sequence>
  97 bool
  98 operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
  99 {
 100   return __x.c < __y.c;
 101 }
 102
 103 #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
 104
 105 template <class _Tp, class _Sequence>
 106 bool
 107 operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
 108 {
 109   return !(__x == __y);
 110 }
 111
 112 template <class _Tp, class _Sequence>
 113 bool
 114 operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
 115 {
 116   return __y < __x;
 117 }
 118
 119 template <class _Tp, class _Sequence>
 120 bool
 121 operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
 122 {
 123   return !(__y < __x);
 124 }
 125
 126 template <class _Tp, class _Sequence>
 127 bool
 128 operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
 129 {
 130   return !(__x < __y);
 131 }
 132
 133 #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
 134
 135 template <class _Tp,
 136           class _Sequence = vector<_Tp>,
 137           class _Compare = less<typename _Sequence::value_type> >
 138 class priority_queue {
 139 public:
 140   typedef typename _Sequence::value_type      value_type;
 141   typedef typename _Sequence::size_type       size_type;
 142   typedef          _Sequence                  container_type;
 143
 144   typedef typename _Sequence::reference       reference;
 145   typedef typename _Sequence::const_reference const_reference;
 146 protected:
 147   _Sequence c;
 148   _Compare comp;
 149 public:
 150   priority_queue() : c() {}
 151   explicit priority_queue(const _Compare& __x) :  c(), comp(__x) {}
 152   priority_queue(const _Compare& __x, const _Sequence& __s)
 153     : c(__s), comp(__x)
 154     { make_heap(c.begin(), c.end(), comp); }
 155
 156 #ifdef __STL_MEMBER_TEMPLATES
 157   template <class _InputIterator>
 158   priority_queue(_InputIterator __first, _InputIterator __last)
 159     : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
 160
 161   template <class _InputIterator>
 162   priority_queue(_InputIterator __first,
 163                  _InputIterator __last, const _Compare& __x)
 164     : c(__first, __last), comp(__x)
 165     { make_heap(c.begin(), c.end(), comp); }
 166
 167   template <class _InputIterator>
 168   priority_queue(_InputIterator __first, _InputIterator __last,
 169                  const _Compare& __x, const _Sequence& __s)
 170   : c(__s), comp(__x)
 171   {
 172     c.insert(c.end(), __first, __last);
 173     make_heap(c.begin(), c.end(), comp);
 174   }
 175
 176 #else /* __STL_MEMBER_TEMPLATES */
 177   priority_queue(const value_type* __first, const value_type* __last)
 178     : c(__first, __last) { make_heap(c.begin(), c.end(), comp); }
 179
 180   priority_queue(const value_type* __first, const value_type* __last,
 181                  const _Compare& __x)
 182     : c(__first, __last), comp(__x)
 183     { make_heap(c.begin(), c.end(), comp); }
 184
 185   priority_queue(const value_type* __first, const value_type* __last,
 186                  const _Compare& __x, const _Sequence& __c)
 187     : c(__c), comp(__x)
 188   {
 189     c.insert(c.end(), __first, __last);
 190     make_heap(c.begin(), c.end(), comp);
 191   }
 192 #endif /* __STL_MEMBER_TEMPLATES */
 193
 194   bool empty() const { return c.empty(); }
 195   size_type size() const { return c.size(); }
 196   const_reference top() const { return c.front(); }
 197   void push(const value_type& __x) {
 198     __STL_TRY {
 199       c.push_back(__x);
 200       push_heap(c.begin(), c.end(), comp);
 201     }
 202     __STL_UNWIND(c.clear());
 203   }
 204   void pop() {
 205     __STL_TRY {
 206       pop_heap(c.begin(), c.end(), comp);
 207       c.pop_back();
 208     }
 209     __STL_UNWIND(c.clear());
 210   }
 211 };
 212
 213 // no equality is provided
 214
 215 __STL_END_NAMESPACE
 216
 217 #endif /* __SGI_STL_INTERNAL_QUEUE_H */
 218
 219 // Local Variables:
 220 // mode:C++
 221 // End: