PagedStack.h

// PagedStack.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2004

#pragma once
#ifndef Ceda_cxUtils_PagedStack_H
#define Ceda_cxUtils_PagedStack_H

#include "cxUtils.h"
#include "CedaAssert.h"
#include <algorithm>

namespace ceda
{

// A paged stack is useful for storing small elements of type T by value under the following circumstances
//     *   It is sufficient to only be able to find a given element in O(n) time
//     *   The stack may grow very large, so a page allocation approach is required
//     *   Pushing and popping elements is very fast
//     *   Iteratng through the entire stack is fast

template <typename T, ssize_t pageSize>
class PagedStack
{
private:
    struct Page
    {
        Page() : m_count(0), prev_(nullptr), next_(nullptr) {}
        
        T m_buffer[pageSize];
        ssize_t m_count;

        // Double linked list of pages
        Page* prev_;
        Page* next_;
    };

    // The first and last pages in the linked list
    Page* first_;
    Page* last_;
    ssize_t size_;

public:
    PagedStack() : first_(nullptr), last_(nullptr), size_(0) {}

    PagedStack(const PagedStack<T,pageSize>& other) : first_(nullptr), last_(nullptr), size_(0)
    {
        push(other.begin(), other.end());    
    }

    ~PagedStack() { clear(); }

    PagedStack<T,pageSize>& operator=(const PagedStack<T,pageSize>& other)
    {
        if (this != &other)
        {
            clear();
            push(other.begin(), other.end());    
        }
        return *this;
    }

    void swap(PagedStack<T,pageSize>& rhs)
    {
        using std::swap;
        swap(first_, rhs.first_);
        swap(last_, rhs.last_);
        swap(size_, rhs.size_);
    }

    void clear()
    {
        Page* p = first_;
        while(p)
        {
            Page* n = p->next_;
            delete p;
            p = n;
        }
        first_ = last_ = nullptr;
        size_ = 0;
    }

    // Avoids deleting the first page if any.
    // WARNING: This is incompatible with const_iterator::atEnd()
    void clear2()
    {
        if (first_)
        {
            Page* p = first_->next_;
            while(p)
            {
                Page* n = p->next_;
                delete p;
                p = n;
            }
            cxAssert(first_->prev_ == nullptr);
            first_->m_count = 0;
            first_->next_ = nullptr;
            
            last_ = first_;
            size_ = 0;
        }
        else
        {
            cxAssert(last_ == nullptr);
            cxAssert(size_ == 0);
        }
    }

    struct const_iterator
    {
        const_iterator() : m_page(nullptr), m_index(-1) {}
        const_iterator(Page* page, ssize_t index) : m_page(page), m_index(index) {}
        
        bool atEnd() const { return m_page == nullptr; }

        const T& operator*() const
        { 
            cxAssert(m_page != nullptr);
            cxAssert(0 <= m_index && m_index < m_page->m_count && m_page->m_count <= pageSize);
            return m_page->m_buffer[m_index];
        }

        const T* operator->() const
        {
            cxAssert(m_page != nullptr);
            cxAssert(0 <= m_index && m_index < m_page->m_count && m_page->m_count <= pageSize);
            return &m_page->m_buffer[m_index];
        }

        const_iterator& operator++()           // Prefix
        {
            cxAssert(m_page != nullptr);
            cxAssert(0 <= m_index && m_index < m_page->m_count && m_page->m_count <= pageSize);

            if (++m_index == m_page->m_count)
            {
                m_index = 0;
                
                // Go to next non-empty page, if any
                do
                {
                    m_page = m_page->next_;
                } while(m_page && m_page->m_count == 0);
            }

            return *this;
        }
        
        const const_iterator operator++(int)   // Postfix
        {
            const_iterator it = *this;
            ++(*this);
            return it;
        }

        bool operator==(const const_iterator& other) const
        {
            return m_page == other.m_page && m_index == other.m_index;
        }

        bool operator!=(const const_iterator& other) const
        {
            return m_page != other.m_page || m_index != other.m_index;
        }

        Page* m_page;
        ssize_t m_index;        // index of element within the page
    };

    ssize_t size() const
    {
        return size_;
    }

    bool empty() const
    {
        return size_ == 0;
    }

    const_iterator begin() const
    {
        return const_iterator(first_,0);
    }

    const_iterator end() const
    {
        return const_iterator(nullptr,0);
    }

    void push(const T& t)
    {
        // Allocate the first page if necessary
        if (first_ == nullptr)
        {
            first_ = last_ = new Page();
        }

        cxAssert(first_ != nullptr);
        cxAssert(first_->prev_ == nullptr);
        cxAssert(last_ != nullptr);
        cxAssert(last_->next_ == nullptr);

        // Allocate a new last page if necessary
        if (last_->m_count == pageSize)
        {
            // Need to allocate a new page
            Page* p = new Page();
            last_->next_ = p;
            p->prev_ = last_;
            last_ = p;
        }

        // Insert the element into the last page
        last_->m_buffer[last_->m_count++] = t;

        ++size_;
    }

    const T& pop()
    {
        cxAssert(last_ != nullptr);
        cxAssert(size_ > 0);

        if (last_->m_count == 0)
        {
            Page* p = last_->prev_;
            delete last_;
            last_ = p;
            cxAssert(last_ != nullptr);
            cxAssert(last_->m_count > 0);
            last_->next_ = nullptr;
        }

        --size_;
        return last_->m_buffer[--last_->m_count];
    }

    // Inserts the range [i1,i2) into this PagedStack
    template <typename It> void push(It i1, It i2)
    {
        while(i1 != i2)
        {
            push(*i1);
            ++i1;
        }
    }
    
    bool find(const T& t) const
    {
        const Page* p = first_;
        while(p)
        {
            const T* i = p->m_buffer;
            const T* iend = i + p->m_count;
            while (i != iend)
            {
                if (*i == t) return true;
                ++i;
            }
            p = p->next_;
        }
        return false;
    }

    bool remove(const T& t)
    {
        Page* p = first_;
        while(p)
        {
            T* i = p->m_buffer;
            T* iend = i + p->m_count;
            while (i != iend)
            {
                if (*i == t) 
                {
                    // Remove element, assuming the elements in the array are relocatable

                    //    --------------xxx-------------
                    //                  ^  ^            ^
                    //                  i  i+1          iend
                    void* dst = i;
                    const void* src = i+1;
                    ssize_t count = (iend-(i+1)) * sizeof(T);
                    cxAssert(count >= 0);
                    memmove(dst,src,count);

                    --p->m_count;
                    return true;
                }
                ++i;
            }
            p = p->next_;
        }
        return false;
    }

    void FastOrderPreservingAccumulate(PagedStack<T,pageSize>& other)
    {
        if (other.size_)
        {
            cxAssert(other.first_);
            cxAssert(other.first_->prev_ == nullptr);
            cxAssert(other.last_);
            cxAssert(other.last_->next_ == nullptr);
            
            if (last_)
            {
                cxAssert(last_->next_ == nullptr);
                cxAssert(first_);
                cxAssert(first_->prev_ == nullptr);
                
                last_->next_ = other.first_;
                other.first_->prev_ = last_;
            }
            else
            {
                first_ = other.first_;
                cxAssert(size_ == 0);
            }
            last_ = other.last_;
            size_ += other.size_;

            other.first_ = other.last_ = nullptr;
            other.size_ = 0;
        }
    }

    
    // A fast way to add all the elements from another stack to this stack.  Makes no promise about 
    // maintaining the order
    // On exit 'other' will be empty
    void accumulate(PagedStack<T,pageSize>& other)
    {
        Page* p = other.first_;
        while(p)
        {
            Page* n = p->next_;

            if (n)
            {
                // p is a full page that we can add to the head of this paged set
                size_ += p->m_count;
                p->prev_ = nullptr;
                p->next_ = first_;
                if (first_) first_->prev_ = p;
                first_ = p;
                if (last_ == nullptr) last_ = first_;
            }
            else
            {
                // insert all the other elements at the end of this paged set
                const T* i = p->m_buffer;
                const T* iend = i + p->m_count;
                while (i != iend)
                {
                    push(*i);
                    ++i;
                }
                delete p;
            }

            p = n;
        }

        other.first_ = other.last_ = nullptr;
        other.size_ = 0;
    }
};

} // namespace ceda

#endif // include guard