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)
60 Allocator::construct(m_end++, value);
62 void insert_overflow(const Type& value)
64 const std::size_t new_capacity = (m_capacity) ? m_capacity + m_capacity : std::size_t(DEFAULT_CAPACITY);
65 const pointer new_data = Allocator::allocate(new_capacity);
66 const pointer new_end = std::copy(m_data, m_end, new_data);
69 Allocator::deallocate(m_data, m_capacity);
71 m_capacity = new_capacity;
78 for(pointer p = m_data; p != m_end; ++p)
80 Allocator::destroy(p);
83 void construct(const Stack& other)
86 for(const_iterator i = other.begin(); i != other.end(); ++i)
88 Allocator::construct(p++, *i);
100 Stack(const Type& value) :
107 Stack(const Stack& other) :
108 DefaultAllocator<Type>(other)
110 m_capacity = other.m_capacity;
111 m_data = Allocator::allocate(m_capacity);
113 m_end = m_data + other.size();
118 Allocator::deallocate(m_data, m_capacity);
121 const_iterator begin() const
125 const_iterator end() const
132 return end() == begin();
140 std::size_t size() const
142 return m_end - m_data;
144 Type operator[](const std::size_t i) const
148 /// \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.
149 void push(const Type& value)
151 if(size() == m_capacity)
153 insert_overflow(value);
160 /// \brief Removes the top element of the stack.
163 Allocator::destroy(--m_end);
165 /// \brief Returns the top element of the mutable stack.
170 /// \brief Returns the top element of the non-mutable stack.
171 const Type& top() const
175 /// \brief Returns the element below the top element of the mutable stack.
180 /// \brief Returns the element below the top element of the non-mutable stack.
181 const Type& parent() const
185 /// \brief Swaps the values of this stack and \p other.
186 void swap(Stack& other)
188 std::swap(m_data, other.m_data);
189 std::swap(m_end, other.m_end);
190 std::swap(m_capacity, other.m_capacity);
192 #if 1 // use copy-swap technique
193 Stack& operator=(const Stack& other)
199 #else // avoids memory allocation if capacity is already sufficient.
200 Stack& operator=(const Stack& other)
206 if(other.size() > m_capacity)
208 Allocator::deallocate(m_data, m_capacity);
209 m_capacity = other.m_capacity;
210 m_data = Allocator::allocate(m_capacity);
212 m_end = m_data + other.size();
221 /// \brief Returns true if \p self is lexicographically less than \p other.
222 template<typename Type>
223 inline bool operator<(const Stack<Type>& self, const Stack<Type>& other)
225 return std::lexicographical_compare(self.begin(), self.end(), other.begin(), other.end());
230 /// \brief Swaps the values of \p self and \p other.
231 /// Overloads std::swap().
232 template<typename Type>
233 inline void swap(Stack<Type>& self, Stack<Type>& other)