1 // Queue implementation -*- C++ -*- 2 3 // Copyright (C) 2001 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 2, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // You should have received a copy of the GNU General Public License along 17 // with this library; see the file COPYING. If not, write to the Free 18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19 // USA. 20 21 // As a special exception, you may use this file as part of a free software 22 // library without restriction. Specifically, if other files instantiate 23 // templates or use macros or inline functions from this file, or you compile 24 // this file and link it with other files to produce an executable, this 25 // file does not by itself cause the resulting executable to be covered by 26 // the GNU General Public License. This exception does not however 27 // invalidate any other reasons why the executable file might be covered by 28 // the GNU General Public License. 29 30 /* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996,1997 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56 /** @file stl_queue.h 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61 #ifndef __GLIBCPP_INTERNAL_QUEUE_H 62 #define __GLIBCPP_INTERNAL_QUEUE_H 63 64 #include <bits/concept_check.h> 65 66 namespace std 67 { 68 69 // Forward declarations of operators < and ==, needed for friend declaration. 70 71 template <class _Tp, 72 class _Sequence = deque<_Tp> > 73 class queue; 74 75 template <class _Tp, class _Seq> 76 inline bool operator==(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&); 77 78 template <class _Tp, class _Seq> 79 inline bool operator<(const queue<_Tp, _Seq>&, const queue<_Tp, _Seq>&); 80 81 82 template <class _Tp, class _Sequence> 83 class queue 84 { 85 // concept requirements 86 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 87 __glibcpp_class_requires(_Sequence, _FrontInsertionSequenceConcept) 88 __glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept) 89 typedef typename _Sequence::value_type _Sequence_value_type; 90 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept); 91 92 template <class _Tp1, class _Seq1> 93 friend bool operator== (const queue<_Tp1, _Seq1>&, 94 const queue<_Tp1, _Seq1>&); 95 template <class _Tp1, class _Seq1> 96 friend bool operator< (const queue<_Tp1, _Seq1>&, 97 const queue<_Tp1, _Seq1>&); 98 public: 99 typedef typename _Sequence::value_type value_type; 100 typedef typename _Sequence::size_type size_type; 101 typedef _Sequence container_type; 102 103 typedef typename _Sequence::reference reference; 104 typedef typename _Sequence::const_reference const_reference; 105 protected: 106 _Sequence c; 107 public: 108 explicit queue(const _Sequence& __c = _Sequence()) : c(__c) {} 109 110 bool empty() const { return c.empty(); } 111 size_type size() const { return c.size(); } 112 reference front() { return c.front(); } 113 const_reference front() const { return c.front(); } 114 reference back() { return c.back(); } 115 const_reference back() const { return c.back(); } 116 void push(const value_type& __x) { c.push_back(__x); } 117 void pop() { c.pop_front(); } 118 }; 119 120 template <class _Tp, class _Sequence> 121 bool 122 operator==(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 123 { 124 return __x.c == __y.c; 125 } 126 127 template <class _Tp, class _Sequence> 128 bool 129 operator<(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 130 { 131 return __x.c < __y.c; 132 } 133 134 template <class _Tp, class _Sequence> 135 bool 136 operator!=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 137 { 138 return !(__x == __y); 139 } 140 141 template <class _Tp, class _Sequence> 142 bool 143 operator>(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 144 { 145 return __y < __x; 146 } 147 148 template <class _Tp, class _Sequence> 149 bool 150 operator<=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 151 { 152 return !(__y < __x); 153 } 154 155 template <class _Tp, class _Sequence> 156 bool 157 operator>=(const queue<_Tp, _Sequence>& __x, const queue<_Tp, _Sequence>& __y) 158 { 159 return !(__x < __y); 160 } 161 162 template <class _Tp, 163 class _Sequence = vector<_Tp>, 164 class _Compare = less<typename _Sequence::value_type> > 165 class priority_queue 166 { 167 // concept requirements 168 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 169 __glibcpp_class_requires(_Sequence, _SequenceConcept) 170 __glibcpp_class_requires(_Sequence, _RandomAccessContainerConcept) 171 typedef typename _Sequence::value_type _Sequence_value_type; 172 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept); 173 __glibcpp_class_requires4(_Compare, bool, _Tp, _Tp, _BinaryFunctionConcept); 174 175 public: 176 typedef typename _Sequence::value_type value_type; 177 typedef typename _Sequence::size_type size_type; 178 typedef _Sequence container_type; 179 180 typedef typename _Sequence::reference reference; 181 typedef typename _Sequence::const_reference const_reference; 182 protected: 183 _Sequence c; 184 _Compare comp; 185 public: 186 explicit priority_queue(const _Compare& __x = _Compare(), 187 const _Sequence& __s = _Sequence()) 188 : c(__s), comp(__x) 189 { make_heap(c.begin(), c.end(), comp); } 190 191 template <class _InputIterator> 192 priority_queue(_InputIterator __first, _InputIterator __last, 193 const _Compare& __x = _Compare(), 194 const _Sequence& __s = _Sequence()) 195 : c(__s), comp(__x) 196 { 197 c.insert(c.end(), __first, __last); 198 make_heap(c.begin(), c.end(), comp); 199 } 200 201 bool empty() const { return c.empty(); } 202 size_type size() const { return c.size(); } 203 const_reference top() const { return c.front(); } 204 205 void 206 push(const value_type& __x) 207 { 208 try 209 { 210 c.push_back(__x); 211 push_heap(c.begin(), c.end(), comp); 212 } 213 catch(...) 214 { 215 c.clear(); 216 __throw_exception_again; 217 } 218 } 219 220 void 221 pop() 222 { 223 try 224 { 225 pop_heap(c.begin(), c.end(), comp); 226 c.pop_back(); 227 } 228 catch(...) 229 { 230 c.clear(); 231 __throw_exception_again; 232 } 233 } 234 }; 235 236 // no equality is provided 237 238 } // namespace std 239 240 #endif /* __GLIBCPP_INTERNAL_QUEUE_H */ 241 242 // Local Variables: 243 // mode:C++ 244 // End: 245