fixed eol-style
[xonotic/netradiant.git] / libs / container / stack.h
1 /*
2 Copyright (C) 2001-2006, William Joseph.
3 All Rights Reserved.
4
5 This file is part of GtkRadiant.
6
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.
11
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.
16
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
20 */
21
22 #if !defined(INCLUDED_CONTAINER_STACK_H)
23 #define INCLUDED_CONTAINER_STACK_H
24
25 #include "memory/allocator.h"
26 #include <algorithm>
27
28 /// \brief A stack whose storage capacity is variable at run-time. Similar to std::vector.
29 ///
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/
34 ///
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>
38 {
39   typedef DefaultAllocator<Type> Allocator;
40
41   enum
42   {
43     DEFAULT_CAPACITY = 4,
44   };
45
46   typedef Type* pointer;
47   typedef const Type* const_pointer;
48
49 public:
50   typedef const_pointer const_iterator;
51 private:
52
53   pointer m_data;
54   pointer m_end;
55   std::size_t m_capacity;
56
57
58   void insert(const Type& value)
59   {
60     Allocator::construct(m_end++, value);
61   }
62   void insert_overflow(const Type& value)
63   {
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);
67
68     destroy();
69     Allocator::deallocate(m_data, m_capacity);
70
71     m_capacity = new_capacity;
72     m_data = new_data;
73     m_end = new_end;
74     insert(value); 
75   }
76   void destroy()
77   {
78     for(pointer p = m_data; p != m_end; ++p)
79     {
80       Allocator::destroy(p);
81     }
82   }
83   void construct(const Stack& other)
84   {
85     pointer p = m_data;
86     for(const_iterator i = other.begin(); i != other.end(); ++i)
87     {
88       Allocator::construct(p++, *i);
89     }
90   }
91
92 public:
93
94   Stack() :
95     m_data(0),
96     m_end(0),
97     m_capacity(0)
98   {
99   }
100   Stack(const Type& value) :
101     m_data(0),
102     m_end(0),
103     m_capacity(0)
104   {
105     push(value);
106   }
107   Stack(const Stack& other) :
108     DefaultAllocator<Type>(other)
109   {
110     m_capacity = other.m_capacity;
111     m_data = Allocator::allocate(m_capacity);
112     construct(other);
113     m_end = m_data + other.size();
114   }
115   ~Stack()
116   {
117     destroy();
118     Allocator::deallocate(m_data, m_capacity);
119   }
120
121   const_iterator begin() const
122   {
123     return m_data;
124   }
125   const_iterator end() const
126   {
127     return m_end;
128   }
129
130   bool empty() const
131   {
132     return end() == begin();
133   }
134   void clear()
135   {
136     destroy();
137     m_end = m_data;
138   }
139
140   std::size_t size() const
141   {
142     return m_end - m_data;
143   }
144   Type operator[](const std::size_t i) const
145   {
146     return m_data[i];
147   }
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)
150   {
151     if(size() == m_capacity)
152     {
153       insert_overflow(value);
154     }
155     else
156     {
157       insert(value);
158     }
159   }
160   /// \brief Removes the top element of the stack.
161   void pop()
162   {
163     Allocator::destroy(--m_end);
164   }
165   /// \brief Returns the top element of the mutable stack.
166   Type& top()
167   {
168     return *(m_end-1);
169   }
170   /// \brief Returns the top element of the non-mutable stack.
171   const Type& top() const
172   {
173     return *(m_end-1);
174   }
175   /// \brief Returns the element below the top element of the mutable stack.
176   Type& parent()
177   {
178     return *(m_end-2);
179   }
180   /// \brief Returns the element below the top element of the non-mutable stack.
181   const Type& parent() const
182   {
183     return *(m_end-2);
184   }
185   /// \brief Swaps the values of this stack and \p other.
186   void swap(Stack& other)
187   {
188     std::swap(m_data, other.m_data);
189     std::swap(m_end, other.m_end);
190     std::swap(m_capacity, other.m_capacity);
191   }
192 #if 1 // use copy-swap technique
193   Stack& operator=(const Stack& other)
194   {
195     Stack temp(other);
196     temp.swap(*this);
197     return *this;
198   }
199 #else // avoids memory allocation if capacity is already sufficient.
200   Stack& operator=(const Stack& other)
201   {
202     if(&other != this)
203     {
204       destroy();
205
206       if(other.size() > m_capacity)
207       {
208         Allocator::deallocate(m_data, m_capacity);
209         m_capacity = other.m_capacity;
210         m_data = Allocator::allocate(m_capacity);
211       }
212       m_end = m_data + other.size();
213
214       construct(other);
215     }
216     return *this;
217   }
218 #endif
219 };
220
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)
224 {
225   return std::lexicographical_compare(self.begin(), self.end(), other.begin(), other.end());
226 }
227
228 namespace std
229 {
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)
234   {
235     self.swap(other);
236   }
237 }
238
239 #endif