-/*\r
-Copyright (C) 2001-2006, William Joseph.\r
-All Rights Reserved.\r
-\r
-This file is part of GtkRadiant.\r
-\r
-GtkRadiant is free software; you can redistribute it and/or modify\r
-it under the terms of the GNU General Public License as published by\r
-the Free Software Foundation; either version 2 of the License, or\r
-(at your option) any later version.\r
-\r
-GtkRadiant is distributed in the hope that it will be useful,\r
-but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
-GNU General Public License for more details.\r
-\r
-You should have received a copy of the GNU General Public License\r
-along with GtkRadiant; if not, write to the Free Software\r
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA\r
-*/\r
-\r
-#if !defined(INCLUDED_CONTAINER_STACK_H)\r
-#define INCLUDED_CONTAINER_STACK_H\r
-\r
-#include "memory/allocator.h"\r
-#include <algorithm>\r
-\r
-/// \brief A stack whose storage capacity is variable at run-time. Similar to std::vector.\r
-///\r
-/// - Pushing or popping elements is a constant-time operation (on average).\r
-/// - 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
-/// - DefaultConstructible, Copyable, Assignable.\r
-/// - Compatible with the containers and algorithms in the Standard Template Library (STL) - http://www.sgi.com/tech/stl/\r
-///\r
-/// \param Type: The type to be stored in the stack. Must provide a copy-constructor.\r
-template<typename Type>\r
-class Stack : public DefaultAllocator<Type>\r
-{\r
- typedef DefaultAllocator<Type> Allocator;\r
-\r
- enum\r
- {\r
- DEFAULT_CAPACITY = 4,\r
- };\r
-\r
- typedef Type* pointer;\r
- typedef const Type* const_pointer;\r
-\r
-public:\r
- typedef const_pointer const_iterator;\r
-private:\r
-\r
- pointer m_data;\r
- pointer m_end;\r
- std::size_t m_capacity;\r
-\r
-\r
- void insert(const Type& value)\r
- {\r
- Allocator::construct(m_end++, value);\r
- }\r
- void insert_overflow(const Type& value)\r
- {\r
- const std::size_t new_capacity = (m_capacity) ? m_capacity + m_capacity : std::size_t(DEFAULT_CAPACITY);\r
- const pointer new_data = Allocator::allocate(new_capacity);\r
- const pointer new_end = std::copy(m_data, m_end, new_data);\r
-\r
- destroy();\r
- Allocator::deallocate(m_data, m_capacity);\r
-\r
- m_capacity = new_capacity;\r
- m_data = new_data;\r
- m_end = new_end;\r
- insert(value); \r
- }\r
- void destroy()\r
- {\r
- for(pointer p = m_data; p != m_end; ++p)\r
- {\r
- Allocator::destroy(p);\r
- }\r
- }\r
- void construct(const Stack& other)\r
- {\r
- pointer p = m_data;\r
- for(const_iterator i = other.begin(); i != other.end(); ++i)\r
- {\r
- Allocator::construct(p++, *i);\r
- }\r
- }\r
-\r
-public:\r
-\r
- Stack() :\r
- m_data(0),\r
- m_end(0),\r
- m_capacity(0)\r
- {\r
- }\r
- Stack(const Type& value) :\r
- m_data(0),\r
- m_end(0),\r
- m_capacity(0)\r
- {\r
- push(value);\r
- }\r
- Stack(const Stack& other) :\r
- DefaultAllocator<Type>(other)\r
- {\r
- m_capacity = other.m_capacity;\r
- m_data = Allocator::allocate(m_capacity);\r
- construct(other);\r
- m_end = m_data + other.size();\r
- }\r
- ~Stack()\r
- {\r
- destroy();\r
- Allocator::deallocate(m_data, m_capacity);\r
- }\r
-\r
- const_iterator begin() const\r
- {\r
- return m_data;\r
- }\r
- const_iterator end() const\r
- {\r
- return m_end;\r
- }\r
-\r
- bool empty() const\r
- {\r
- return end() == begin();\r
- }\r
- void clear()\r
- {\r
- destroy();\r
- m_end = m_data;\r
- }\r
-\r
- std::size_t size() const\r
- {\r
- return m_end - m_data;\r
- }\r
- Type operator[](const std::size_t i) const\r
- {\r
- return m_data[i];\r
- }\r
- /// \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
- void push(const Type& value)\r
- {\r
- if(size() == m_capacity)\r
- {\r
- insert_overflow(value);\r
- }\r
- else\r
- {\r
- insert(value);\r
- }\r
- }\r
- /// \brief Removes the top element of the stack.\r
- void pop()\r
- {\r
- Allocator::destroy(--m_end);\r
- }\r
- /// \brief Returns the top element of the mutable stack.\r
- Type& top()\r
- {\r
- return *(m_end-1);\r
- }\r
- /// \brief Returns the top element of the non-mutable stack.\r
- const Type& top() const\r
- {\r
- return *(m_end-1);\r
- }\r
- /// \brief Returns the element below the top element of the mutable stack.\r
- Type& parent()\r
- {\r
- return *(m_end-2);\r
- }\r
- /// \brief Returns the element below the top element of the non-mutable stack.\r
- const Type& parent() const\r
- {\r
- return *(m_end-2);\r
- }\r
- /// \brief Swaps the values of this stack and \p other.\r
- void swap(Stack& other)\r
- {\r
- std::swap(m_data, other.m_data);\r
- std::swap(m_end, other.m_end);\r
- std::swap(m_capacity, other.m_capacity);\r
- }\r
-#if 1 // use copy-swap technique\r
- Stack& operator=(const Stack& other)\r
- {\r
- Stack temp(other);\r
- temp.swap(*this);\r
- return *this;\r
- }\r
-#else // avoids memory allocation if capacity is already sufficient.\r
- Stack& operator=(const Stack& other)\r
- {\r
- if(&other != this)\r
- {\r
- destroy();\r
-\r
- if(other.size() > m_capacity)\r
- {\r
- Allocator::deallocate(m_data, m_capacity);\r
- m_capacity = other.m_capacity;\r
- m_data = Allocator::allocate(m_capacity);\r
- }\r
- m_end = m_data + other.size();\r
-\r
- construct(other);\r
- }\r
- return *this;\r
- }\r
-#endif\r
-};\r
-\r
-/// \brief Returns true if \p self is lexicographically less than \p other.\r
-template<typename Type>\r
-inline bool operator<(const Stack<Type>& self, const Stack<Type>& other)\r
-{\r
- return std::lexicographical_compare(self.begin(), self.end(), other.begin(), other.end());\r
-}\r
-\r
-namespace std\r
-{\r
- /// \brief Swaps the values of \p self and \p other.\r
- /// Overloads std::swap().\r
- template<typename Type>\r
- inline void swap(Stack<Type>& self, Stack<Type>& other)\r
- {\r
- self.swap(other);\r
- }\r
-}\r
-\r
-#endif\r
+/*
+ Copyright (C) 2001-2006, William Joseph.
+ All Rights Reserved.
+
+ This file is part of GtkRadiant.
+
+ GtkRadiant is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ GtkRadiant is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GtkRadiant; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#if !defined( INCLUDED_CONTAINER_STACK_H )
+#define INCLUDED_CONTAINER_STACK_H
+
+#include "memory/allocator.h"
+#include <algorithm>
+
+/// \brief A stack whose storage capacity is variable at run-time. Similar to std::vector.
+///
+/// - Pushing or popping elements is a constant-time operation (on average).
+/// - 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.
+/// - DefaultConstructible, Copyable, Assignable.
+/// - Compatible with the containers and algorithms in the Standard Template Library (STL) - http://www.sgi.com/tech/stl/
+///
+/// \param Type: The type to be stored in the stack. Must provide a copy-constructor.
+template<typename Type>
+class Stack : public DefaultAllocator<Type>
+{
+typedef DefaultAllocator<Type> Allocator;
+
+enum
+{
+ DEFAULT_CAPACITY = 4,
+};
+
+typedef Type* pointer;
+typedef const Type* const_pointer;
+
+public:
+typedef const_pointer const_iterator;
+private:
+
+pointer m_data;
+pointer m_end;
+std::size_t m_capacity;
+
+
+void insert( const Type& value ){
+ Allocator::construct( m_end++, value );
+}
+void insert_overflow( const Type& value ){
+ const std::size_t new_capacity = ( m_capacity ) ? m_capacity + m_capacity : std::size_t( DEFAULT_CAPACITY );
+ const pointer new_data = Allocator::allocate( new_capacity );
+ const pointer new_end = std::copy( m_data, m_end, new_data );
+
+ destroy();
+ Allocator::deallocate( m_data, m_capacity );
+
+ m_capacity = new_capacity;
+ m_data = new_data;
+ m_end = new_end;
+ insert( value );
+}
+void destroy(){
+ for ( pointer p = m_data; p != m_end; ++p )
+ {
+ Allocator::destroy( p );
+ }
+}
+void construct( const Stack& other ){
+ pointer p = m_data;
+ for ( const_iterator i = other.begin(); i != other.end(); ++i )
+ {
+ Allocator::construct( p++, *i );
+ }
+}
+
+public:
+
+Stack() :
+ m_data( 0 ),
+ m_end( 0 ),
+ m_capacity( 0 ){
+}
+Stack( const Type& value ) :
+ m_data( 0 ),
+ m_end( 0 ),
+ m_capacity( 0 ){
+ push( value );
+}
+Stack( const Stack& other ) :
+ DefaultAllocator<Type>( other ){
+ m_capacity = other.m_capacity;
+ m_data = Allocator::allocate( m_capacity );
+ construct( other );
+ m_end = m_data + other.size();
+}
+~Stack(){
+ destroy();
+ Allocator::deallocate( m_data, m_capacity );
+}
+
+const_iterator begin() const {
+ return m_data;
+}
+const_iterator end() const {
+ return m_end;
+}
+
+bool empty() const {
+ return end() == begin();
+}
+void clear(){
+ destroy();
+ m_end = m_data;
+}
+
+std::size_t size() const {
+ return m_end - m_data;
+}
+Type operator[]( const std::size_t i ) const {
+ return m_data[i];
+}
+/// \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.
+void push( const Type& value ){
+ if ( size() == m_capacity ) {
+ insert_overflow( value );
+ }
+ else
+ {
+ insert( value );
+ }
+}
+/// \brief Removes the top element of the stack.
+void pop(){
+ Allocator::destroy( --m_end );
+}
+/// \brief Returns the top element of the mutable stack.
+Type& top(){
+ return *( m_end - 1 );
+}
+/// \brief Returns the top element of the non-mutable stack.
+const Type& top() const {
+ return *( m_end - 1 );
+}
+/// \brief Returns the element below the top element of the mutable stack.
+Type& parent(){
+ return *( m_end - 2 );
+}
+/// \brief Returns the element below the top element of the non-mutable stack.
+const Type& parent() const {
+ return *( m_end - 2 );
+}
+/// \brief Swaps the values of this stack and \p other.
+void swap( Stack& other ){
+ std::swap( m_data, other.m_data );
+ std::swap( m_end, other.m_end );
+ std::swap( m_capacity, other.m_capacity );
+}
+#if 1 // use copy-swap technique
+Stack& operator=( const Stack& other ){
+ Stack temp( other );
+ temp.swap( *this );
+ return *this;
+}
+#else // avoids memory allocation if capacity is already sufficient.
+Stack& operator=( const Stack& other ){
+ if ( &other != this ) {
+ destroy();
+
+ if ( other.size() > m_capacity ) {
+ Allocator::deallocate( m_data, m_capacity );
+ m_capacity = other.m_capacity;
+ m_data = Allocator::allocate( m_capacity );
+ }
+ m_end = m_data + other.size();
+
+ construct( other );
+ }
+ return *this;
+}
+#endif
+};
+
+/// \brief Returns true if \p self is lexicographically less than \p other.
+template<typename Type>
+inline bool operator<( const Stack<Type>& self, const Stack<Type>& other ){
+ return std::lexicographical_compare( self.begin(), self.end(), other.begin(), other.end() );
+}
+
+namespace std
+{
+/// \brief Swaps the values of \p self and \p other.
+/// Overloads std::swap().
+template<typename Type>
+inline void swap( Stack<Type>& self, Stack<Type>& other ){
+ self.swap( other );
+}
+}
+
+#endif
projects / xonotic / netradiant.git / blobdiff