197403Sobrien// Stack implementation -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 597403Sobrien// 697403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 797403Sobrien// software; you can redistribute it and/or modify it under the 897403Sobrien// terms of the GNU General Public License as published by the 997403Sobrien// Free Software Foundation; either version 2, or (at your option) 1097403Sobrien// any later version. 1197403Sobrien 1297403Sobrien// This library is distributed in the hope that it will be useful, 1397403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1497403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1597403Sobrien// GNU General Public License for more details. 1697403Sobrien 1797403Sobrien// You should have received a copy of the GNU General Public License along 1897403Sobrien// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2097403Sobrien// USA. 2197403Sobrien 2297403Sobrien// As a special exception, you may use this file as part of a free software 2397403Sobrien// library without restriction. Specifically, if other files instantiate 2497403Sobrien// templates or use macros or inline functions from this file, or you compile 2597403Sobrien// this file and link it with other files to produce an executable, this 2697403Sobrien// file does not by itself cause the resulting executable to be covered by 2797403Sobrien// the GNU General Public License. This exception does not however 2897403Sobrien// invalidate any other reasons why the executable file might be covered by 2997403Sobrien// the GNU General Public License. 3097403Sobrien 3197403Sobrien/* 3297403Sobrien * 3397403Sobrien * Copyright (c) 1994 3497403Sobrien * Hewlett-Packard Company 3597403Sobrien * 3697403Sobrien * Permission to use, copy, modify, distribute and sell this software 3797403Sobrien * and its documentation for any purpose is hereby granted without fee, 3897403Sobrien * provided that the above copyright notice appear in all copies and 3997403Sobrien * that both that copyright notice and this permission notice appear 4097403Sobrien * in supporting documentation. Hewlett-Packard Company makes no 4197403Sobrien * representations about the suitability of this software for any 4297403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4397403Sobrien * 4497403Sobrien * 4597403Sobrien * Copyright (c) 1996,1997 4697403Sobrien * Silicon Graphics Computer Systems, Inc. 4797403Sobrien * 4897403Sobrien * Permission to use, copy, modify, distribute and sell this software 4997403Sobrien * and its documentation for any purpose is hereby granted without fee, 5097403Sobrien * provided that the above copyright notice appear in all copies and 5197403Sobrien * that both that copyright notice and this permission notice appear 5297403Sobrien * in supporting documentation. Silicon Graphics makes no 5397403Sobrien * representations about the suitability of this software for any 5497403Sobrien * purpose. It is provided "as is" without express or implied warranty. 5597403Sobrien */ 5697403Sobrien 5797403Sobrien/** @file stl_stack.h 5897403Sobrien * This is an internal header file, included by other library headers. 5997403Sobrien * You should not attempt to use it directly. 6097403Sobrien */ 6197403Sobrien 62132720Skan#ifndef _STACK_H 63132720Skan#define _STACK_H 1 6497403Sobrien 6597403Sobrien#include <bits/concept_check.h> 66132720Skan#include <debug/debug.h> 6797403Sobrien 68169691Skan_GLIBCXX_BEGIN_NAMESPACE(std) 69132720Skan 70117397Skan /** 71117397Skan * @brief A standard container giving FILO behavior. 72117397Skan * 73117397Skan * @ingroup Containers 74117397Skan * @ingroup Sequences 75117397Skan * 76117397Skan * Meets many of the requirements of a 77117397Skan * <a href="tables.html#65">container</a>, 78117397Skan * but does not define anything to do with iterators. Very few of the 79117397Skan * other standard container interfaces are defined. 80117397Skan * 81132720Skan * This is not a true container, but an @e adaptor. It holds 82132720Skan * another container, and provides a wrapper interface to that 83132720Skan * container. The wrapper is what enforces strict 84132720Skan * first-in-last-out %stack behavior. 85117397Skan * 86117397Skan * The second template parameter defines the type of the underlying 87132720Skan * sequence/container. It defaults to std::deque, but it can be 88132720Skan * any type that supports @c back, @c push_back, and @c pop_front, 89132720Skan * such as std::list, std::vector, or an appropriate user-defined 90132720Skan * type. 91117397Skan * 92117397Skan * Members not found in "normal" containers are @c container_type, 93132720Skan * which is a typedef for the second Sequence parameter, and @c 94132720Skan * push, @c pop, and @c top, which are standard %stack/FILO 95132720Skan * operations. 96117397Skan */ 97169691Skan template<typename _Tp, typename _Sequence = deque<_Tp> > 98117397Skan class stack 99132720Skan { 100132720Skan // concept requirements 101132720Skan typedef typename _Sequence::value_type _Sequence_value_type; 102132720Skan __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 103132720Skan __glibcxx_class_requires(_Sequence, _BackInsertionSequenceConcept) 104132720Skan __glibcxx_class_requires2(_Tp, _Sequence_value_type, _SameTypeConcept) 105132720Skan 106132720Skan template<typename _Tp1, typename _Seq1> 107132720Skan friend bool 108132720Skan operator==(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 109132720Skan 110132720Skan template<typename _Tp1, typename _Seq1> 111132720Skan friend bool 112132720Skan operator<(const stack<_Tp1, _Seq1>&, const stack<_Tp1, _Seq1>&); 113132720Skan 114132720Skan public: 115132720Skan typedef typename _Sequence::value_type value_type; 116132720Skan typedef typename _Sequence::reference reference; 117132720Skan typedef typename _Sequence::const_reference const_reference; 118132720Skan typedef typename _Sequence::size_type size_type; 119132720Skan typedef _Sequence container_type; 120132720Skan 121132720Skan protected: 122132720Skan // See queue::c for notes on this name. 123132720Skan _Sequence c; 124132720Skan 125132720Skan public: 126132720Skan // XXX removed old def ctor, added def arg to this one to match 14882 127132720Skan /** 128132720Skan * @brief Default constructor creates no elements. 129132720Skan */ 130132720Skan explicit 131132720Skan stack(const _Sequence& __c = _Sequence()) 132169691Skan : c(__c) { } 133132720Skan 134132720Skan /** 135132720Skan * Returns true if the %stack is empty. 136132720Skan */ 137132720Skan bool 138132720Skan empty() const 139132720Skan { return c.empty(); } 140132720Skan 141132720Skan /** Returns the number of elements in the %stack. */ 142132720Skan size_type 143132720Skan size() const 144132720Skan { return c.size(); } 145132720Skan 146132720Skan /** 147132720Skan * Returns a read/write reference to the data at the first 148132720Skan * element of the %stack. 149132720Skan */ 150132720Skan reference 151132720Skan top() 152132720Skan { 153132720Skan __glibcxx_requires_nonempty(); 154132720Skan return c.back(); 155132720Skan } 156132720Skan 157132720Skan /** 158132720Skan * Returns a read-only (constant) reference to the data at the first 159132720Skan * element of the %stack. 160132720Skan */ 161132720Skan const_reference 162132720Skan top() const 163132720Skan { 164132720Skan __glibcxx_requires_nonempty(); 165132720Skan return c.back(); 166132720Skan } 167132720Skan 168132720Skan /** 169132720Skan * @brief Add data to the top of the %stack. 170132720Skan * @param x Data to be added. 171132720Skan * 172132720Skan * This is a typical %stack operation. The function creates an 173132720Skan * element at the top of the %stack and assigns the given data 174132720Skan * to it. The time complexity of the operation depends on the 175132720Skan * underlying sequence. 176132720Skan */ 177132720Skan void 178132720Skan push(const value_type& __x) 179132720Skan { c.push_back(__x); } 180132720Skan 181132720Skan /** 182132720Skan * @brief Removes first element. 183132720Skan * 184132720Skan * This is a typical %stack operation. It shrinks the %stack 185132720Skan * by one. The time complexity of the operation depends on the 186132720Skan * underlying sequence. 187132720Skan * 188132720Skan * Note that no data is returned, and if the first element's 189132720Skan * data is needed, it should be retrieved before pop() is 190132720Skan * called. 191132720Skan */ 192132720Skan void 193132720Skan pop() 194132720Skan { 195132720Skan __glibcxx_requires_nonempty(); 196132720Skan c.pop_back(); 197132720Skan } 198132720Skan }; 199132720Skan 200117397Skan /** 201117397Skan * @brief Stack equality comparison. 202117397Skan * @param x A %stack. 203117397Skan * @param y A %stack of the same type as @a x. 204117397Skan * @return True iff the size and elements of the stacks are equal. 205117397Skan * 206132720Skan * This is an equivalence relation. Complexity and semantics 207132720Skan * depend on the underlying sequence type, but the expected rules 208132720Skan * are: this relation is linear in the size of the sequences, and 209132720Skan * stacks are considered equivalent if their sequences compare 210132720Skan * equal. 211117397Skan */ 212132720Skan template<typename _Tp, typename _Seq> 213117397Skan inline bool 214132720Skan operator==(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 215117397Skan { return __x.c == __y.c; } 216132720Skan 217117397Skan /** 218117397Skan * @brief Stack ordering relation. 219117397Skan * @param x A %stack. 220117397Skan * @param y A %stack of the same type as @a x. 221132720Skan * @return True iff @a x is lexicographically less than @a y. 222117397Skan * 223132720Skan * This is an total ordering relation. Complexity and semantics 224132720Skan * depend on the underlying sequence type, but the expected rules 225132720Skan * are: this relation is linear in the size of the sequences, the 226132720Skan * elements must be comparable with @c <, and 227132720Skan * std::lexicographical_compare() is usually used to make the 228117397Skan * determination. 229117397Skan */ 230132720Skan template<typename _Tp, typename _Seq> 231117397Skan inline bool 232132720Skan operator<(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 233117397Skan { return __x.c < __y.c; } 234132720Skan 235117397Skan /// Based on operator== 236132720Skan template<typename _Tp, typename _Seq> 237117397Skan inline bool 238132720Skan operator!=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 239117397Skan { return !(__x == __y); } 240132720Skan 241117397Skan /// Based on operator< 242132720Skan template<typename _Tp, typename _Seq> 243117397Skan inline bool 244132720Skan operator>(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 245117397Skan { return __y < __x; } 246132720Skan 247117397Skan /// Based on operator< 248132720Skan template<typename _Tp, typename _Seq> 249117397Skan inline bool 250132720Skan operator<=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 251117397Skan { return !(__y < __x); } 252132720Skan 253117397Skan /// Based on operator< 254132720Skan template<typename _Tp, typename _Seq> 255117397Skan inline bool 256132720Skan operator>=(const stack<_Tp, _Seq>& __x, const stack<_Tp, _Seq>& __y) 257117397Skan { return !(__x < __y); } 25897403Sobrien 259169691Skan_GLIBCXX_END_NAMESPACE 260169691Skan 261132720Skan#endif /* _STACK_H */ 262