2 Copyright (C) 2001-2006, William Joseph.
5 This file is part of GtkRadiant.
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GtkRadiant 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.
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 #if !defined( INCLUDED_CONTAINER_STACK_H )
23 #define INCLUDED_CONTAINER_STACK_H
25 #include "memory/allocator.h"
28 /// \brief A stack whose storage capacity is variable at run-time. Similar to std::vector.
30 /// - Pushing or popping elements is a constant-time operation (on average).
31 /// - The storage capacity of the stack will grow when a new element is added beyond the current capacity. Iterators are invalidated when the storage capacity grows.
32 /// - DefaultConstructible, Copyable, Assignable.
33 /// - Compatible with the containers and algorithms in the Standard Template Library (STL) - http://www.sgi.com/tech/stl/
35 /// \param Type: The type to be stored in the stack. Must provide a copy-constructor.
36 template<typename Type>
37 class Stack : public DefaultAllocator<Type>
39 typedef DefaultAllocator<Type> Allocator;
46 typedef Type* pointer;
47 typedef const Type* const_pointer;
50 typedef const_pointer const_iterator;
55 std::size_t m_capacity;
58 void insert( const Type& value ){
59 Allocator::construct( m_end++, value );
61 void insert_overflow( const Type& value ){
62 const std::size_t new_capacity = ( m_capacity ) ? m_capacity + m_capacity : std::size_t( DEFAULT_CAPACITY );
63 const pointer new_data = Allocator::allocate( new_capacity );
64 const pointer new_end = std::copy( m_data, m_end, new_data );
67 Allocator::deallocate( m_data, m_capacity );
69 m_capacity = new_capacity;
75 for ( pointer p = m_data; p != m_end; ++p )
77 Allocator::destroy( p );
80 void construct( const Stack& other ){
82 for ( const_iterator i = other.begin(); i != other.end(); ++i )
84 Allocator::construct( p++, *i );
95 Stack( const Type& value ) :
101 Stack( const Stack& other ) :
102 DefaultAllocator<Type>( other ){
103 m_capacity = other.m_capacity;
104 m_data = Allocator::allocate( m_capacity );
106 m_end = m_data + other.size();
110 Allocator::deallocate( m_data, m_capacity );
113 const_iterator begin() const {
116 const_iterator end() const {
121 return end() == begin();
128 std::size_t size() const {
129 return m_end - m_data;
131 Type operator[]( const std::size_t i ) const {
134 /// \brief Pushes \p value onto the stack at the top element. If reserved storage is insufficient for the new element, this will invalidate all iterators.
135 void push( const Type& value ){
136 if ( size() == m_capacity ) {
137 insert_overflow( value );
144 /// \brief Removes the top element of the stack.
146 Allocator::destroy( --m_end );
148 /// \brief Returns the top element of the mutable stack.
150 return *( m_end - 1 );
152 /// \brief Returns the top element of the non-mutable stack.
153 const Type& top() const {
154 return *( m_end - 1 );
156 /// \brief Returns the element below the top element of the mutable stack.
158 return *( m_end - 2 );
160 /// \brief Returns the element below the top element of the non-mutable stack.
161 const Type& parent() const {
162 return *( m_end - 2 );
164 /// \brief Swaps the values of this stack and \p other.
165 void swap( Stack& other ){
166 std::swap( m_data, other.m_data );
167 std::swap( m_end, other.m_end );
168 std::swap( m_capacity, other.m_capacity );
170 #if 1 // use copy-swap technique
171 Stack& operator=( const Stack& other ){
176 #else // avoids memory allocation if capacity is already sufficient.
177 Stack& operator=( const Stack& other ){
178 if ( &other != this ) {
181 if ( other.size() > m_capacity ) {
182 Allocator::deallocate( m_data, m_capacity );
183 m_capacity = other.m_capacity;
184 m_data = Allocator::allocate( m_capacity );
186 m_end = m_data + other.size();
195 /// \brief Returns true if \p self is lexicographically less than \p other.
196 template<typename Type>
197 inline bool operator<( const Stack<Type>& self, const Stack<Type>& other ){
198 return std::lexicographical_compare( self.begin(), self.end(), other.begin(), other.end() );
203 /// \brief Swaps the values of \p self and \p other.
204 /// Overloads std::swap().
205 template<typename Type>
206 inline void swap( Stack<Type>& self, Stack<Type>& other ){