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