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: 203