libs/container/stack.h

   1 /*\r
   2 Copyright (C) 2001-2006, William Joseph.\r
   3 All Rights Reserved.\r
   4 \r
   5 This file is part of GtkRadiant.\r
   6 \r
   7 GtkRadiant is free software; you can redistribute it and/or modify\r
   8 it under the terms of the GNU General Public License as published by\r
   9 the Free Software Foundation; either version 2 of the License, or\r
  10 (at your option) any later version.\r
  11 \r
  12 GtkRadiant is distributed in the hope that it will be useful,\r
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  15 GNU General Public License for more details.\r
  16 \r
  17 You should have received a copy of the GNU General Public License\r
  18 along with GtkRadiant; if not, write to the Free Software\r
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA\r
  20 */\r
  21 \r
  22 #if !defined(INCLUDED_CONTAINER_STACK_H)\r
  23 #define INCLUDED_CONTAINER_STACK_H\r
  24 \r
  25 #include "memory/allocator.h"\r
  26 #include <algorithm>\r
  27 \r
  28 /// \brief A stack whose storage capacity is variable at run-time. Similar to std::vector.\r
  29 ///\r
  30 /// - Pushing or popping elements is a constant-time operation (on average).\r
  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.\r
  32 /// - DefaultConstructible, Copyable, Assignable.\r
  33 /// - Compatible with the containers and algorithms in the Standard Template Library (STL) - http://www.sgi.com/tech/stl/\r
  34 ///\r
  35 /// \param Type: The type to be stored in the stack. Must provide a copy-constructor.\r
  36 template<typename Type>\r
  37 class Stack : public DefaultAllocator<Type>\r
  38 {\r
  39   typedef DefaultAllocator<Type> Allocator;\r
  40 \r
  41   enum\r
  42   {\r
  43     DEFAULT_CAPACITY = 4,\r
  44   };\r
  45 \r
  46   typedef Type* pointer;\r
  47   typedef const Type* const_pointer;\r
  48 \r
  49 public:\r
  50   typedef const_pointer const_iterator;\r
  51 private:\r
  52 \r
  53   pointer m_data;\r
  54   pointer m_end;\r
  55   std::size_t m_capacity;\r
  56 \r
  57 \r
  58   void insert(const Type& value)\r
  59   {\r
  60     Allocator::construct(m_end++, value);\r
  61   }\r
  62   void insert_overflow(const Type& value)\r
  63   {\r
  64     const std::size_t new_capacity = (m_capacity) ? m_capacity + m_capacity : std::size_t(DEFAULT_CAPACITY);\r
  65     const pointer new_data = Allocator::allocate(new_capacity);\r
  66     const pointer new_end = std::copy(m_data, m_end, new_data);\r
  67 \r
  68     destroy();\r
  69     Allocator::deallocate(m_data, m_capacity);\r
  70 \r
  71     m_capacity = new_capacity;\r
  72     m_data = new_data;\r
  73     m_end = new_end;\r
  74     insert(value); \r
  75   }\r
  76   void destroy()\r
  77   {\r
  78     for(pointer p = m_data; p != m_end; ++p)\r
  79     {\r
  80       Allocator::destroy(p);\r
  81     }\r
  82   }\r
  83   void construct(const Stack& other)\r
  84   {\r
  85     pointer p = m_data;\r
  86     for(const_iterator i = other.begin(); i != other.end(); ++i)\r
  87     {\r
  88       Allocator::construct(p++, *i);\r
  89     }\r
  90   }\r
  91 \r
  92 public:\r
  93 \r
  94   Stack() :\r
  95     m_data(0),\r
  96     m_end(0),\r
  97     m_capacity(0)\r
  98   {\r
  99   }\r
 100   Stack(const Type& value) :\r
 101     m_data(0),\r
 102     m_end(0),\r
 103     m_capacity(0)\r
 104   {\r
 105     push(value);\r
 106   }\r
 107   Stack(const Stack& other) :\r
 108     DefaultAllocator<Type>(other)\r
 109   {\r
 110     m_capacity = other.m_capacity;\r
 111     m_data = Allocator::allocate(m_capacity);\r
 112     construct(other);\r
 113     m_end = m_data + other.size();\r
 114   }\r
 115   ~Stack()\r
 116   {\r
 117     destroy();\r
 118     Allocator::deallocate(m_data, m_capacity);\r
 119   }\r
 120 \r
 121   const_iterator begin() const\r
 122   {\r
 123     return m_data;\r
 124   }\r
 125   const_iterator end() const\r
 126   {\r
 127     return m_end;\r
 128   }\r
 129 \r
 130   bool empty() const\r
 131   {\r
 132     return end() == begin();\r
 133   }\r
 134   void clear()\r
 135   {\r
 136     destroy();\r
 137     m_end = m_data;\r
 138   }\r
 139 \r
 140   std::size_t size() const\r
 141   {\r
 142     return m_end - m_data;\r
 143   }\r
 144   Type operator[](const std::size_t i) const\r
 145   {\r
 146     return m_data[i];\r
 147   }\r
 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.\r
 149   void push(const Type& value)\r
 150   {\r
 151     if(size() == m_capacity)\r
 152     {\r
 153       insert_overflow(value);\r
 154     }\r
 155     else\r
 156     {\r
 157       insert(value);\r
 158     }\r
 159   }\r
 160   /// \brief Removes the top element of the stack.\r
 161   void pop()\r
 162   {\r
 163     Allocator::destroy(--m_end);\r
 164   }\r
 165   /// \brief Returns the top element of the mutable stack.\r
 166   Type& top()\r
 167   {\r
 168     return *(m_end-1);\r
 169   }\r
 170   /// \brief Returns the top element of the non-mutable stack.\r
 171   const Type& top() const\r
 172   {\r
 173     return *(m_end-1);\r
 174   }\r
 175   /// \brief Returns the element below the top element of the mutable stack.\r
 176   Type& parent()\r
 177   {\r
 178     return *(m_end-2);\r
 179   }\r
 180   /// \brief Returns the element below the top element of the non-mutable stack.\r
 181   const Type& parent() const\r
 182   {\r
 183     return *(m_end-2);\r
 184   }\r
 185   /// \brief Swaps the values of this stack and \p other.\r
 186   void swap(Stack& other)\r
 187   {\r
 188     std::swap(m_data, other.m_data);\r
 189     std::swap(m_end, other.m_end);\r
 190     std::swap(m_capacity, other.m_capacity);\r
 191   }\r
 192 #if 1 // use copy-swap technique\r
 193   Stack& operator=(const Stack& other)\r
 194   {\r
 195     Stack temp(other);\r
 196     temp.swap(*this);\r
 197     return *this;\r
 198   }\r
 199 #else // avoids memory allocation if capacity is already sufficient.\r
 200   Stack& operator=(const Stack& other)\r
 201   {\r
 202     if(&other != this)\r
 203     {\r
 204       destroy();\r
 205 \r
 206       if(other.size() > m_capacity)\r
 207       {\r
 208         Allocator::deallocate(m_data, m_capacity);\r
 209         m_capacity = other.m_capacity;\r
 210         m_data = Allocator::allocate(m_capacity);\r
 211       }\r
 212       m_end = m_data + other.size();\r
 213 \r
 214       construct(other);\r
 215     }\r
 216     return *this;\r
 217   }\r
 218 #endif\r
 219 };\r
 220 \r
 221 /// \brief Returns true if \p self is lexicographically less than \p other.\r
 222 template<typename Type>\r
 223 inline bool operator<(const Stack<Type>& self, const Stack<Type>& other)\r
 224 {\r
 225   return std::lexicographical_compare(self.begin(), self.end(), other.begin(), other.end());\r
 226 }\r
 227 \r
 228 namespace std\r
 229 {\r
 230   /// \brief Swaps the values of \p self and \p other.\r
 231   /// Overloads std::swap().\r
 232   template<typename Type>\r
 233   inline void swap(Stack<Type>& self, Stack<Type>& other)\r
 234   {\r
 235     self.swap(other);\r
 236   }\r
 237 }\r
 238 \r
 239 #endif