1// Stack implementation -*- C++ -*- 2 3// Copyright (C) 2001, 2002 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_stack.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_STACK_H 62#define __GLIBCPP_INTERNAL_STACK_H 63 64#include <bits/concept_check.h> 65 66namespace std 67{ 68 // Forward declarations of operators == and <, needed for friend declaration. 69 70 template <typename _Tp, typename _Sequence = deque<_Tp> > 71 class stack; 72 73 template <typename _Tp, typename _Seq> 74 inline bool operator==(const stack<_Tp,_Seq>& __x, 75 const stack<_Tp,_Seq>& __y); 76 77 template <typename _Tp, typename _Seq> 78 inline bool operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y); 79 80 81 /** 82 * @brief A standard container giving FILO behavior. 83 * 84 * @ingroup Containers 85 * @ingroup Sequences 86 * 87 * Meets many of the requirements of a 88 * <a href="tables.html#65">container</a>, 89 * but does not define anything to do with iterators. Very few of the 90 * other standard container interfaces are defined. 91 * 92 * This is not a true container, but an @e adaptor. It holds another 93 * container, and provides a wrapper interface to that container. The 94 * wrapper is what enforces strict first-in-last-out %stack behavior. 95 * 96 * The second template parameter defines the type of the underlying 97 * sequence/container. It defaults to std::deque, but it can be any type 98 * that supports @c back, @c push_back, and @c pop_front, such as 99 * std::list, std::vector, or an appropriate user-defined type. 100 * 101 * Members not found in "normal" containers are @c container_type, 102 * which is a typedef for the second Sequence parameter, and @c push, 103 * @c pop, and @c top, which are standard %stack/FILO operations. 104 */ 105 template <typename _Tp, typename _Sequence> 106 class stack 107 { 108 // concept requirements 109 typedef typename _Sequence::value_type _Sequence_value_type; 110 __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 111 __glibcpp_class_requires(_Sequence, _BackInsertionSequenceConcept) 112 __glibcpp_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 113 114 template <typename _Tp1, typename _Seq1> 115 friend bool operator== (const stack<_Tp1, _Seq1>&, 116 const stack<_Tp1, _Seq1>&); 117 template <typename _Tp1, typename _Seq1> 118 friend bool operator< (const stack<_Tp1, _Seq1>&, 119 const stack<_Tp1, _Seq1>&); 120 121 public: 122 typedef typename _Sequence::value_type value_type; 123 typedef typename _Sequence::reference reference; 124 typedef typename _Sequence::const_reference const_reference; 125 typedef typename _Sequence::size_type size_type; 126 typedef _Sequence container_type; 127 128 protected: 129 // See queue::c for notes on this name. 130 _Sequence c; 131 132 public: 133 // XXX removed old def ctor, added def arg to this one to match 14882 134 /** 135 * @brief Default constructor creates no elements. 136 */ 137 explicit 138 stack(const _Sequence& __c = _Sequence()) 139 : c(__c) {} 140 141 /** 142 * Returns true if the %stack is empty. 143 */ 144 bool 145 empty() const { return c.empty(); } 146 147 /** Returns the number of elements in the %stack. */ 148 size_type 149 size() const { return c.size(); } 150 151 /** 152 * Returns a read/write reference to the data at the first element of the 153 * %stack. 154 */ 155 reference 156 top() { return c.back(); } 157 158 /** 159 * Returns a read-only (constant) reference to the data at the first 160 * element of the %stack. 161 */ 162 const_reference 163 top() const { return c.back(); } 164 165 /** 166 * @brief Add data to the top of the %stack. 167 * @param x Data to be added. 168 * 169 * This is a typical %stack operation. The function creates an element at 170 * the top of the %stack and assigns the given data to it. 171 * The time complexity of the operation depends on the underlying 172 * sequence. 173 */ 174 void 175 push(const value_type& __x) { c.push_back(__x); } 176 177 /** 178 * @brief Removes first element. 179 * 180 * This is a typical %stack operation. It shrinks the %stack by one. 181 * The time complexity of the operation depends on the underlying 182 * sequence. 183 * 184 * Note that no data is returned, and if the first element's data is 185 * needed, it should be retrieved before pop() is called. 186 */ 187 void 188 pop() { c.pop_back(); } 189 }; 190 191 192 /** 193 * @brief Stack equality comparison. 194 * @param x A %stack. 195 * @param y A %stack of the same type as @a x. 196 * @return True iff the size and elements of the stacks are equal. 197 * 198 * This is an equivalence relation. Complexity and semantics depend on the 199 * underlying sequence type, but the expected rules are: this relation is 200 * linear in the size of the sequences, and stacks are considered equivalent 201 * if their sequences compare equal. 202 */ 203 template <typename _Tp, typename _Seq> 204 inline bool 205 operator==(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) 206 { return __x.c == __y.c; } 207 208 /** 209 * @brief Stack ordering relation. 210 * @param x A %stack. 211 * @param y A %stack of the same type as @a x. 212 * @return True iff @a x is lexographically less than @a y. 213 * 214 * This is an total ordering relation. Complexity and semantics depend on 215 * the underlying sequence type, but the expected rules are: this relation 216 * is linear in the size of the sequences, the elements must be comparable 217 * with @c <, and std::lexographical_compare() is usually used to make the 218 * determination. 219 */ 220 template <typename _Tp, typename _Seq> 221 inline bool 222 operator<(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) 223 { return __x.c < __y.c; } 224 225 /// Based on operator== 226 template <typename _Tp, typename _Seq> 227 inline bool 228 operator!=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) 229 { return !(__x == __y); } 230 231 /// Based on operator< 232 template <typename _Tp, typename _Seq> 233 inline bool 234 operator>(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) 235 { return __y < __x; } 236 237 /// Based on operator< 238 template <typename _Tp, typename _Seq> 239 inline bool 240 operator<=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) 241 { return !(__y < __x); } 242 243 /// Based on operator< 244 template <typename _Tp, typename _Seq> 245 inline bool 246 operator>=(const stack<_Tp,_Seq>& __x, const stack<_Tp,_Seq>& __y) 247 { return !(__x < __y); } 248} // namespace std 249 250#endif /* __GLIBCPP_INTERNAL_STACK_H */ 251