libstdc++-v3/include/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 #include <bits/concept_check.h>
  35
  36 namespace std
  37 {
  38
  39 // Forward declarations of operators < and ==, needed for friend declaration.
  40
  41 template <class _Tp,
  42           class _Sequence = deque<_Tp> >
  43 class queue;
  44
  45 template <class _Tp, class _Seq>
  46 inline bool operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
  47
  48 template <class _Tp, class _Seq>
  49 inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&);
  50
  51
  52 template <class _Tp, class _Sequence>
  53 class queue
  54 {
  55   // concept requirements
  56   __glibcpp_class_requires(_Tp, _SGIAssignableConcept);
  57   __glibcpp_class_requires(_Sequence, _FrontInsertionSequenceConcept);
  58   __glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept);
  59   typedef typename _Sequence::value_type _Sequence_value_type;
  60   __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept);
  61
  62   template <class _Tp1, class _Seq1>
  63   friend bool operator== (const queue<_Tp1, _Seq1>&,
  64                           const queue<_Tp1, _Seq1>&);
  65   template <class _Tp1, class _Seq1>
  66   friend bool operator< (const queue<_Tp1, _Seq1>&,
  67                          const queue<_Tp1, _Seq1>&);
  68 public:
  69   typedef typename _Sequence::value_type      value_type;
  70   typedef typename _Sequence::size_type       size_type;
  71   typedef          _Sequence                  container_type;
  72
  73   typedef typename _Sequence::reference       reference;
  74   typedef typename _Sequence::const_reference const_reference;
  75 protected:
  76   _Sequence c;
  77 public:
  78   explicit queue(const _Sequence& __c = _Sequence()) : c(__c) {}
  79
  80   bool empty() const { return c.empty(); }
  81   size_type size() const { return c.size(); }
  82   reference front() { return c.front(); }
  83   const_reference front() const { return c.front(); }
  84   reference back() { return c.back(); }
  85   const_reference back() const { return c.back(); }
  86   void push(const value_type& __x) { c.push_back(__x); }
  87   void pop() { c.pop_front(); }
  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 __x.c == __y.c;
  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 __x.c < __y.c;
 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 template <class _Tp, class _Sequence>
 112 bool
 113 operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
 114 {
 115   return __y < __x;
 116 }
 117
 118 template <class _Tp, class _Sequence>
 119 bool
 120 operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
 121 {
 122   return !(__y < __x);
 123 }
 124
 125 template <class _Tp, class _Sequence>
 126 bool
 127 operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y)
 128 {
 129   return !(__x < __y);
 130 }
 131
 132 template <class _Tp,
 133           class _Sequence = vector<_Tp>,
 134           class _Compare  = less<typename _Sequence::value_type> >
 135 class priority_queue
 136 {
 137   // concept requirements
 138   __glibcpp_class_requires(_Tp, _SGIAssignableConcept);
 139   __glibcpp_class_requires(_Sequence, _SequenceConcept);
 140   __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept);
 141   typedef typename _Sequence::value_type _Sequence_value_type;
 142   __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept);
 143   __glibcpp_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept);
 144
 145 public:
 146   typedef typename _Sequence::value_type      value_type;
 147   typedef typename _Sequence::size_type       size_type;
 148   typedef          _Sequence                  container_type;
 149
 150   typedef typename _Sequence::reference       reference;
 151   typedef typename _Sequence::const_reference const_reference;
 152 protected:
 153   _Sequence c;
 154   _Compare comp;
 155 public:
 156   explicit priority_queue(const _Compare& __x = _Compare(),
 157                           const _Sequence& __s = _Sequence())
 158     : c(__s), comp(__x)
 159     { make_heap(c.begin(), c.end(), comp); }
 160
 161   template <class _InputIterator>
 162   priority_queue(_InputIterator __first, _InputIterator __last,
 163                  const _Compare& __x = _Compare(),
 164                  const _Sequence& __s = _Sequence())
 165   : c(__s), comp(__x)
 166   {
 167     c.insert(c.end(), __first, __last);
 168     make_heap(c.begin(), c.end(), comp);
 169   }
 170
 171   bool empty() const { return c.empty(); }
 172   size_type size() const { return c.size(); }
 173   const_reference top() const { return c.front(); }
 174   void push(const value_type& __x) {
 175     __STL_TRY {
 176       c.push_back(__x);
 177       push_heap(c.begin(), c.end(), comp);
 178     }
 179     __STL_UNWIND(c.clear());
 180   }
 181   void pop() {
 182     __STL_TRY {
 183       pop_heap(c.begin(), c.end(), comp);
 184       c.pop_back();
 185     }
 186     __STL_UNWIND(c.clear());
 187   }
 188 };
 189
 190 // no equality is provided
 191
 192 } // namespace std
 193
 194 #endif /* __SGI_STL_INTERNAL_QUEUE_H */
 195
 196 // Local Variables:
 197 // mode:C++
 198 // End: