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