/*
-Copyright (C) 2001-2006, William Joseph.
-All Rights Reserved.
+ Copyright (C) 2001-2006, William Joseph.
+ All Rights Reserved.
-This file is part of GtkRadiant.
+ 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 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.
+ 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
-*/
+ 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)
+#if !defined( INCLUDED_CONTAINER_STACK_H )
#define INCLUDED_CONTAINER_STACK_H
#include "memory/allocator.h"
template<typename Type>
class Stack : public DefaultAllocator<Type>
{
- typedef DefaultAllocator<Type> Allocator;
+typedef DefaultAllocator<Type> Allocator;
- enum
- {
- DEFAULT_CAPACITY = 4,
- };
+enum
+{
+ DEFAULT_CAPACITY = 4,
+};
- typedef Type* pointer;
- typedef const Type* const_pointer;
+typedef Type* pointer;
+typedef const Type* const_pointer;
public:
- typedef const_pointer const_iterator;
+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);
- }
- }
+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);
- }
+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;
- }
+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;
- }
+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());
+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);
- }
+/// \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