Merge branch 'master' of ssh://crater.dragonflybsd.org/repository/git/dragonfly
[dragonfly.git] / contrib / gcc-3.4 / libstdc++-v3 / include / bits / stl_stack.h
CommitLineData
003757ed
MD
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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
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
67namespace 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 {
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 stack(const _Sequence& __c = _Sequence())
144 : c(__c) {}
145
146 /**
147 * Returns true if the %stack is empty.
148 */
149 bool
150 empty() const
151 { 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 top()
164 {
165 __glibcxx_requires_nonempty();
166 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 push(const value_type& __x)
191 { 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 pop()
206 {
207 __glibcxx_requires_nonempty();
208 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 */