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