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