1 : // Stack implementation -*- C++ -*-
2 :
3 : // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
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 2, 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 : // You should have received a copy of the GNU General Public License along
18 : // with this library; see the file COPYING. If not, write to the Free
19 : // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
20 : // USA.
21 :
22 : // As a special exception, you may use this file as part of a free software
23 : // library without restriction. Specifically, if other files instantiate
24 : // templates or use macros or inline functions from this file, or you compile
25 : // this file and link it with other files to produce an executable, this
26 : // file does not by itself cause the resulting executable to be covered by
27 : // the GNU General Public License. This exception does not however
28 : // invalidate any other reasons why the executable file might be covered by
29 : // the GNU General Public License.
30 :
31 : /*
32 : *
33 : * Copyright (c) 1994
34 : * Hewlett-Packard Company
35 : *
36 : * Permission to use, copy, modify, distribute and sell this software
37 : * and its documentation for any purpose is hereby granted without fee,
38 : * provided that the above copyright notice appear in all copies and
39 : * that both that copyright notice and this permission notice appear
40 : * in supporting documentation. Hewlett-Packard Company makes no
41 : * representations about the suitability of this software for any
42 : * purpose. It is provided "as is" without express or implied warranty.
43 : *
44 : *
45 : * Copyright (c) 1996,1997
46 : * Silicon Graphics Computer Systems, Inc.
47 : *
48 : * Permission to use, copy, modify, distribute and sell this software
49 : * and its documentation for any purpose is hereby granted without fee,
50 : * provided that the above copyright notice appear in all copies and
51 : * that both that copyright notice and this permission notice appear
52 : * in supporting documentation. Silicon Graphics makes no
53 : * representations about the suitability of this software for any
54 : * purpose. It is provided "as is" without express or implied warranty.
55 : */
56 :
57 : /** @file stl_stack.h
58 : * This is an internal header file, included by other library headers.
59 : * You should not attempt to use it directly.
60 : */
61 :
62 : #ifndef _STACK_H
63 : #define _STACK_H 1
64 :
65 : #include <bits/concept_check.h>
66 : #include <debug/debug.h>
67 :
68 : _GLIBCXX_BEGIN_NAMESPACE(std)
69 :
70 : /**
71 : * @brief A standard container giving FILO behavior.
72 : *
73 : * @ingroup Containers
74 : * @ingroup Sequences
75 : *
76 : * Meets many of the requirements of a
77 : * <a href="tables.html#65">container</a>,
78 : * but does not define anything to do with iterators. Very few of the
79 : * other standard container interfaces are defined.
80 : *
81 : * This is not a true container, but an @e adaptor. It holds
82 : * another container, and provides a wrapper interface to that
83 : * container. The wrapper is what enforces strict
84 : * first-in-last-out %stack behavior.
85 : *
86 : * The second template parameter defines the type of the underlying
87 : * sequence/container. It defaults to std::deque, but it can be
88 : * any type that supports @c back, @c push_back, and @c pop_front,
89 : * such as std::list, std::vector, or an appropriate user-defined
90 : * type.
91 : *
92 : * Members not found in "normal" containers are @c container_type,
93 : * which is a typedef for the second Sequence parameter, and @c
94 : * push, @c pop, and @c top, which are standard %stack/FILO
95 : * operations.
96 : */
97 : template<typename _Tp, typename _Sequence = deque<_Tp> >
98 : class stack
99 0 : {
100 : // concept requirements
101 : typedef typename _Sequence::value_type _Sequence_value_type;
102 : __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
103 : __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept)
104 : __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept)
105 :
106 : template<typename _Tp1, typename _Seq1>
107 : friend bool
108 : operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
109 :
110 : template<typename _Tp1, typename _Seq1>
111 : friend bool
112 : operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&);
113 :
114 : public:
115 : typedef typename _Sequence::value_type value_type;
116 : typedef typename _Sequence::reference reference;
117 : typedef typename _Sequence::const_reference const_reference;
118 : typedef typename _Sequence::size_type size_type;
119 : typedef _Sequence container_type;
120 :
121 : protected:
122 : // See queue::c for notes on this name.
123 : _Sequence c;
124 :
125 : public:
126 : // XXX removed old def ctor, added def arg to this one to match 14882
127 : /**
128 : * @brief Default constructor creates no elements.
129 : */
130 : explicit
131 : stack(const _Sequence& __c = _Sequence())
132 : : c(__c) { }
133 :
134 : /**
135 : * Returns true if the %stack is empty.
136 : */
137 : bool
138 : empty() const
139 : { return c.empty(); }
140 :
141 : /** Returns the number of elements in the %stack. */
142 : size_type
143 : size() const
144 : { return c.size(); }
145 :
146 : /**
147 : * Returns a read/write reference to the data at the first
148 : * element of the %stack.
149 : */
150 : reference
151 : top()
152 : {
153 : __glibcxx_requires_nonempty();
154 : return c.back();
155 : }
156 :
157 : /**
158 : * Returns a read-only (constant) reference to the data at the first
159 : * element of the %stack.
160 : */
161 : const_reference
162 : top() const
163 : {
164 : __glibcxx_requires_nonempty();
165 : return c.back();
166 : }
167 :
168 : /**
169 : * @brief Add data to the top of the %stack.
170 : * @param x Data to be added.
171 : *
172 : * This is a typical %stack operation. The function creates an
173 : * element at the top of the %stack and assigns the given data
174 : * to it. The time complexity of the operation depends on the
175 : * underlying sequence.
176 : */
177 : void
178 : push(const value_type& __x)
179 : { c.push_back(__x); }
180 :
181 : /**
182 : * @brief Removes first element.
183 : *
184 : * This is a typical %stack operation. It shrinks the %stack
185 : * by one. The time complexity of the operation depends on the
186 : * underlying sequence.
187 : *
188 : * Note that no data is returned, and if the first element's
189 : * data is needed, it should be retrieved before pop() is
190 : * called.
191 : */
192 : void
193 : pop()
194 : {
195 : __glibcxx_requires_nonempty();
196 : c.pop_back();
197 : }
198 : };
199 :
200 : /**
201 : * @brief Stack equality comparison.
202 : * @param x A %stack.
203 : * @param y A %stack of the same type as @a x.
204 : * @return True iff the size and elements of the stacks are equal.
205 : *
206 : * This is an equivalence relation. Complexity and semantics
207 : * depend on the underlying sequence type, but the expected rules
208 : * are: this relation is linear in the size of the sequences, and
209 : * stacks are considered equivalent if their sequences compare
210 : * equal.
211 : */
212 : template<typename _Tp, typename _Seq>
213 : inline bool
214 : operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
215 : { return __x.c == __y.c; }
216 :
217 : /**
218 : * @brief Stack ordering relation.
219 : * @param x A %stack.
220 : * @param y A %stack of the same type as @a x.
221 : * @return True iff @a x is lexicographically less than @a y.
222 : *
223 : * This is an total ordering relation. Complexity and semantics
224 : * depend on the underlying sequence type, but the expected rules
225 : * are: this relation is linear in the size of the sequences, the
226 : * elements must be comparable with @c <, and
227 : * std::lexicographical_compare() is usually used to make the
228 : * determination.
229 : */
230 : template<typename _Tp, typename _Seq>
231 : inline bool
232 : operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
233 : { return __x.c < __y.c; }
234 :
235 : /// Based on operator==
236 : template<typename _Tp, typename _Seq>
237 : inline bool
238 : operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
239 : { return !(__x == __y); }
240 :
241 : /// Based on operator<
242 : template<typename _Tp, typename _Seq>
243 : inline bool
244 : operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y)
245 : { return __y < __x; }
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 !(__y < __x); }
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 !(__x < __y); }
258 :
259 : _GLIBCXX_END_NAMESPACE
260 :
261 : #endif /* _STACK_H */
|
