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         Allocator::construct( m_end++, value );
  60 }
  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 );
  65
  66         destroy();
  67         Allocator::deallocate( m_data, m_capacity );
  68
  69         m_capacity = new_capacity;
  70         m_data = new_data;
  71         m_end = new_end;
  72         insert( value );
  73 }
  74 void destroy(){
  75         for ( pointer p = m_data; p != m_end; ++p )
  76         {
  77                 Allocator::destroy( p );
  78         }
  79 }
  80 void construct( const Stack& other ){
  81         pointer p = m_data;
  82         for ( const_iterator i = other.begin(); i != other.end(); ++i )
  83         {
  84                 Allocator::construct( p++, *i );
  85         }
  86 }
  87
  88 public:
  89
  90 Stack() :
  91         m_data( 0 ),
  92         m_end( 0 ),
  93         m_capacity( 0 ){
  94 }
  95 Stack( const Type& value ) :
  96         m_data( 0 ),
  97         m_end( 0 ),
  98         m_capacity( 0 ){
  99         push( value );
 100 }
 101 Stack( const Stack& other ) :
 102         DefaultAllocator<Type>( other ){
 103         m_capacity = other.m_capacity;
 104         m_data = Allocator::allocate( m_capacity );
 105         construct( other );
 106         m_end = m_data + other.size();
 107 }
 108 ~Stack(){
 109         destroy();
 110         Allocator::deallocate( m_data, m_capacity );
 111 }
 112
 113 const_iterator begin() const {
 114         return m_data;
 115 }
 116 const_iterator end() const {
 117         return m_end;
 118 }
 119
 120 bool empty() const {
 121         return end() == begin();
 122 }
 123 void clear(){
 124         destroy();
 125         m_end = m_data;
 126 }
 127
 128 std::size_t size() const {
 129         return m_end - m_data;
 130 }
 131 Type operator[]( const std::size_t i ) const {
 132         return m_data[i];
 133 }
 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 );
 138         }
 139         else
 140         {
 141                 insert( value );
 142         }
 143 }
 144 /// \brief Removes the top element of the stack.
 145 void pop(){
 146         Allocator::destroy( --m_end );
 147 }
 148 /// \brief Returns the top element of the mutable stack.
 149 Type& top(){
 150         return *( m_end - 1 );
 151 }
 152 /// \brief Returns the top element of the non-mutable stack.
 153 const Type& top() const {
 154         return *( m_end - 1 );
 155 }
 156 /// \brief Returns the element below the top element of the mutable stack.
 157 Type& parent(){
 158         return *( m_end - 2 );
 159 }
 160 /// \brief Returns the element below the top element of the non-mutable stack.
 161 const Type& parent() const {
 162         return *( m_end - 2 );
 163 }
 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 );
 169 }
 170 #if 1 // use copy-swap technique
 171 Stack& operator=( const Stack& other ){
 172         Stack temp( other );
 173         temp.swap( *this );
 174         return *this;
 175 }
 176 #else // avoids memory allocation if capacity is already sufficient.
 177 Stack& operator=( const Stack& other ){
 178         if ( &other != this ) {
 179                 destroy();
 180
 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 );
 185                 }
 186                 m_end = m_data + other.size();
 187
 188                 construct( other );
 189         }
 190         return *this;
 191 }
 192 #endif
 193 };
 194
 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() );
 199 }
 200
 201 namespace std
 202 {
 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 ){
 207         self.swap( other );
 208 }
 209 }
 210
 211 #endif