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 37template <class _Tp, class _Sequence = deque<_Tp> > 38#else 39template <class _Tp, class _Sequence> 40#endif 41class 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&); 44public: 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; 51protected: 52 _Sequence c; 53public: 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 67template <class _Tp, class _Sequence> 68bool 69operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 70{ 71 return __x.c == __y.c; 72} 73 74template <class _Tp, class _Sequence> 75bool 76operator<(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 83template <class _Tp, class _Sequence> 84bool 85operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 86{ 87 return !(__x == __y); 88} 89 90template <class _Tp, class _Sequence> 91bool 92operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 93{ 94 return __y < __x; 95} 96 97template <class _Tp, class _Sequence> 98bool 99operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 100{ 101 return !(__y < __x); 102} 103 104template <class _Tp, class _Sequence> 105bool 106operator>=(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 114template <class _Tp, class _Sequence = vector<_Tp>, 115 class _Compare = less<typename _Sequence::value_type> > 116#else 117template <class _Tp, class _Sequence, class _Compare> 118#endif 119class priority_queue { 120public: 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; 127protected: 128 _Sequence c; 129 _Compare comp; 130public: 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