stack.h

Go to the documentation of this file.

/*
 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>

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];
        }
        void push (const Type& value)
        {
            if (size() == m_capacity) {
                insert_overflow(value);
            } else {
                insert(value);
            }
        }
        void pop ()
        {
            Allocator::destroy(--m_end);
        }
        Type& top ()
        {
            return *(m_end - 1);
        }
        const Type& top () const
        {
            return *(m_end - 1);
        }
        Type& parent ()
        {
            return *(m_end - 2);
        }
        const Type& parent () const
        {
            return *(m_end - 2);
        }
        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
};

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
{
    template<typename Type>
    inline void swap (Stack<Type>& self, Stack<Type>& other)
    {
        self.swap(other);
    }
}

#endif