1// Stack implementation -*- C++ -*-
2
3// Copyright (C) 2001-2016 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 3, 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// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23// <http://www.gnu.org/licenses/>.
24
25/*
26 *
27 * Copyright (c) 1994
28 * Hewlett-Packard Company
29 *
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
37 *
38 *
39 * Copyright (c) 1996,1997
40 * Silicon Graphics Computer Systems, Inc.
41 *
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
49 */
50
51/** @file bits/stl_stack.h
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{stack}
54 */
55
56#ifndef _STL_STACK_H
57#define _STL_STACK_H 1
58
59#include <bits/concept_check.h>
60#include <debug/debug.h>
61#if __cplusplus >= 201103L
62# include <bits/uses_allocator.h>
63#endif
64
65namespace std _GLIBCXX_VISIBILITY(default)
66{
67_GLIBCXX_BEGIN_NAMESPACE_VERSION
68
69 /**
70 * @brief A standard container giving FILO behavior.
71 *
72 * @ingroup sequences
73 *
74 * @tparam _Tp Type of element.
75 * @tparam _Sequence Type of underlying sequence, defaults to deque<_Tp>.
76 *
77 * Meets many of the requirements of a
78 * <a href="tables.html#65">container</a>,
79 * but does not define anything to do with iterators. Very few of the
80 * other standard container interfaces are defined.
81 *
82 * This is not a true container, but an @e adaptor. It holds
83 * another container, and provides a wrapper interface to that
84 * container. The wrapper is what enforces strict
85 * first-in-last-out %stack behavior.
86 *
87 * The second template parameter defines the type of the underlying
88 * sequence/container. It defaults to std::deque, but it can be
89 * any type that supports @c back, @c push_back, and @c pop_front,
90 * such as std::list, std::vector, or an appropriate user-defined
91 * type.
92 *
93 * Members not found in @a normal containers are @c container_type,
94 * which is a typedef for the second Sequence parameter, and @c
95 * push, @c pop, and @c top, which are standard %stack/FILO
96 * operations.
97 */
98 template<typename _Tp, typename _Sequence = deque<_Tp> >
99 class stack
100 {
101 // concept requirements
102 typedef typename _Sequence::value_type _Sequence_value_type;
103#if __cplusplus < 201103L
104 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
105 __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
106#endif
107 __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
108
109 template<typename _Tp1, typename _Seq1>
110 friend bool
111 operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
112
113 template<typename _Tp1, typename _Seq1>
114 friend bool
115 operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
116
117#if __cplusplus >= 201103L
118 template<typename _Alloc>
119 using _Uses = typename
120 enable_if<uses_allocator<_Sequence, _Alloc>::value>::type;
121#endif
122
123 public:
124 typedef typename _Sequence::value_type value_type;
125 typedef typename _Sequence::reference reference;
126 typedef typename _Sequence::const_reference const_reference;
127 typedef typename _Sequence::size_type size_type;
128 typedef _Sequence container_type;
129
130 protected:
131 // See queue::c for notes on this name.
132 _Sequence c;
133
134 public:
135 // XXX removed old def ctor, added def arg to this one to match 14882
136 /**
137 * @brief Default constructor creates no elements.
138 */
139#if __cplusplus < 201103L
140 explicit
141 stack(const _Sequence& __c = _Sequence())
142 : c(__c) { }
143#else
144 explicit
145 stack(const _Sequence& __c)
146 : c(__c) { }
147
148 explicit
149 stack(_Sequence&& __c = _Sequence())
150 : c(std::move(__c)) { }
151
152 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
153 explicit
154 stack(const _Alloc& __a)
155 : c(__a) { }
156
157 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
158 stack(const _Sequence& __c, const _Alloc& __a)
159 : c(__c, __a) { }
160
161 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
162 stack(_Sequence&& __c, const _Alloc& __a)
163 : c(std::move(__c), __a) { }
164
165 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
166 stack(const stack& __q, const _Alloc& __a)
167 : c(__q.c, __a) { }
168
169 template<typename _Alloc, typename _Requires = _Uses<_Alloc>>
170 stack(stack&& __q, const _Alloc& __a)
171 : c(std::move(__q.c), __a) { }
172#endif
173
174 /**
175 * Returns true if the %stack is empty.
176 */
177 bool
178 empty() const
179 { return c.empty(); }
180
181 /** Returns the number of elements in the %stack. */
182 size_type
183 size() const
184 { return c.size(); }
185
186 /**
187 * Returns a read/write reference to the data at the first
188 * element of the %stack.
189 */
190 reference
191 top()
192 {
193 __glibcxx_requires_nonempty();
194 return c.back();
195 }
196
197 /**
198 * Returns a read-only (constant) reference to the data at the first
199 * element of the %stack.
200 */
201 const_reference
202 top() const
203 {
204 __glibcxx_requires_nonempty();
205 return c.back();
206 }
207
208 /**
209 * @brief Add data to the top of the %stack.
210 * @param __x Data to be added.
211 *
212 * This is a typical %stack operation. The function creates an
213 * element at the top of the %stack and assigns the given data
214 * to it. The time complexity of the operation depends on the
215 * underlying sequence.
216 */
217 void
218 push(const value_type& __x)
219 { c.push_back(__x); }
220
221#if __cplusplus >= 201103L
222 void
223 push(value_type&& __x)
224 { c.push_back(std::move(__x)); }
225
226 template<typename... _Args>
227 void
228 emplace(_Args&&... __args)
229 { c.emplace_back(std::forward<_Args>(__args)...); }
230#endif
231
232 /**
233 * @brief Removes first element.
234 *
235 * This is a typical %stack operation. It shrinks the %stack
236 * by one. The time complexity of the operation depends on the
237 * underlying sequence.
238 *
239 * Note that no data is returned, and if the first element's
240 * data is needed, it should be retrieved before pop() is
241 * called.
242 */
243 void
244 pop()
245 {
246 __glibcxx_requires_nonempty();
247 c.pop_back();
248 }
249
250#if __cplusplus >= 201103L
251 void
252 swap(stack& __s)
253 noexcept(__is_nothrow_swappable<_Tp>::value)
254 {
255 using std::swap;
256 swap(c, __s.c);
257 }
258#endif
259 };
260
261 /**
262 * @brief Stack equality comparison.
263 * @param __x A %stack.
264 * @param __y A %stack of the same type as @a __x.
265 * @return True iff the size and elements of the stacks are equal.
266 *
267 * This is an equivalence relation. Complexity and semantics
268 * depend on the underlying sequence type, but the expected rules
269 * are: this relation is linear in the size of the sequences, and
270 * stacks are considered equivalent if their sequences compare
271 * equal.
272 */
273 template<typename _Tp, typename _Seq>
274 inline bool
275 operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
276 { return __x.c == __y.c; }
277
278 /**
279 * @brief Stack ordering relation.
280 * @param __x A %stack.
281 * @param __y A %stack of the same type as @a x.
282 * @return True iff @a x is lexicographically less than @a __y.
283 *
284 * This is an total ordering relation. Complexity and semantics
285 * depend on the underlying sequence type, but the expected rules
286 * are: this relation is linear in the size of the sequences, the
287 * elements must be comparable with @c <, and
288 * std::lexicographical_compare() is usually used to make the
289 * determination.
290 */
291 template<typename _Tp, typename _Seq>
292 inline bool
293 operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
294 { return __x.c < __y.c; }
295
296 /// Based on operator==
297 template<typename _Tp, typename _Seq>
298 inline bool
299 operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
300 { return !(__x == __y); }
301
302 /// Based on operator<
303 template<typename _Tp, typename _Seq>
304 inline bool
305 operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
306 { return __y < __x; }
307
308 /// Based on operator<
309 template<typename _Tp, typename _Seq>
310 inline bool
311 operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
312 { return !(__y < __x); }
313
314 /// Based on operator<
315 template<typename _Tp, typename _Seq>
316 inline bool
317 operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
318 { return !(__x < __y); }
319
320#if __cplusplus >= 201103L
321 template<typename _Tp, typename _Seq>
322 inline void
323 swap(stack<_Tp, _Seq>& __x, stack<_Tp, _Seq>& __y)
324 noexcept(noexcept(__x.swap(__y)))
325 { __x.swap(__y); }
326
327 template<typename _Tp, typename _Seq, typename _Alloc>
328 struct uses_allocator<stack<_Tp, _Seq>, _Alloc>
329 : public uses_allocator<_Seq, _Alloc>::type { };
330#endif
331
332_GLIBCXX_END_NAMESPACE_VERSION
333} // namespace
334
335#endif /* _STL_STACK_H */
336