Saf/Collection/Deque.h

Go to the documentation of this file.

/*
    This file is part of Simple Application Framework (Saf) library.
    Copyright (C) 2010 - 2012 Ondrej Danek <ondrej.danek@gmail.com>

    This library 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 3 of the License, or
    (at your option) any later version.

    Saf 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 Simple Application Framework library. If not, 
    see <http://www.gnu.org/licenses/>.
*/

#ifndef SAF_COLLECTION_DEQUEUE_H
#define SAF_COLLECTION_DEQUEUE_H

#include "../Mem/Alloc.h"
#include "../Algo/Swap.h"
#include "../Algo/Selection/MinMax.h"
#include "../Math/Calculus/Powers.h"
#include "../Type/IteratorCategory.h"
#include "Array.h"

namespace Saf
{
    namespace Collection
    {
        template <class T>
        class Deque
        {
        protected:
            typedef Deque<T> MyType;

        public:
            class ConstIterator
            {
            public:
                typedef T ValType;
                typedef Type::IteratorCategory::RandomAccessCategory CategoryType;

            protected:
                Size m_ofs;
                T *m_ptr;
                MyType *m_deque;

                // Deque needs to access the protected properties
                friend class Deque<T>;

            public:
                ConstIterator()
                {}

                explicit ConstIterator(Size ofs, MyType &deque)
                    : m_ofs(ofs), m_ptr(deque.ElementAt(ofs)), m_deque(&deque)
                {}

                ConstIterator(const ConstIterator& it)
                    : m_ofs(it.m_ofs), m_ptr(it.m_ptr), m_deque(it.m_deque)
                {}
                    
                ConstIterator& operator=(const ConstIterator& it)
                {
                    m_ofs = it.m_ofs;
                    m_ptr = it.m_ptr;
                    m_deque = it.m_deque;
                    return *this;
                }

                const T& operator*() const
                {
                    return *m_ptr;
                }

                const T* operator->() const
                {
                    return m_ptr;
                }

                ConstIterator& operator++()
                {
                    if (!m_deque->BlockOffset(++m_ofs))
                    {
                        m_ptr = m_deque->ElementAt(m_ofs);
                    }
                    else
                    {
                        ++m_ptr;
                    }

                    return *this;
                }

                ConstIterator operator++(int)
                {
                    ConstIterator ci(*this);
                    ++(*this);
                    return ci;
                }

                ConstIterator& operator+=(Diff offset)
                {
                    m_ofs += offset;
                    m_ptr = m_deque->ElementAt(m_ofs);
                    return *this;
                }

                ConstIterator operator+(Diff offset) const
                {
                    ConstIterator ci(*this);
                    ci += offset;
                    return ci;
                }

                ConstIterator& operator--()
                {
                    if (!m_deque->BlockOffset(m_ofs--))
                    {
                        m_ptr = m_deque->ElementAt(m_ofs);
                    }
                    else
                    {
                        --m_ptr;
                    }

                    return *this;
                }

                ConstIterator operator--(int)
                {
                    ConstIterator ci(*this);
                    --(*this);
                    return ci;
                }

                ConstIterator& operator-=(Diff offset)
                {                                        
                    m_ofs -= offset;
                    m_ptr = m_deque->ElementAt(m_ofs);
                    return *this;
                }

                ConstIterator operator-(Diff offset) const
                {
                    ConstIterator ci(*this);
                    ci -= offset;
                    return ci;
                }

                bool operator==(const ConstIterator& it) const
                {
                    return (m_ofs == it.m_ofs);
                }

                bool operator!=(const ConstIterator& it) const
                {
                    return (m_ofs != it.m_ofs);
                }

                bool operator<(const ConstIterator& it) const
                {
                    return (m_ofs < it.m_ofs);
                }

                bool operator>(const ConstIterator& it) const
                {
                    return (m_ofs > it.m_ofs);
                }

                bool operator<=(const ConstIterator& it) const
                {
                    return (m_ofs <= it.m_ofs);
                }

                bool operator>=(const ConstIterator& it) const
                {
                    return (m_ofs >= it.m_ofs);
                }

                const T& operator[](Diff ofs) const
                {
                    return *m_deque->ElementAt(m_ofs + ofs);
                }

                Diff operator-(const ConstIterator& it) const
                {
                    return (m_ofs < it.m_ofs) ? -Diff(it.m_ofs - m_ofs) 
                        : Diff(m_ofs - it.m_ofs);
                }
            };

            class Iterator
                : public ConstIterator
            {
            public:
                Iterator()
                    : ConstIterator()
                {}

                explicit Iterator(Size ofs, MyType &deque)
                    : ConstIterator(ofs, deque)
                {}

                Iterator(const Iterator& iter)
                    : ConstIterator(iter)
                {}
                    
                Iterator& operator=(const Iterator& iter)
                {
                    ConstIterator::operator=(iter);
                    return *this;
                }

                T& operator*() const
                {
                    return *this->m_ptr;
                }

                T* operator->() const
                {
                    return this->m_ptr;
                }

                Iterator& operator++()
                {
                    ++(*((ConstIterator *)this));
                    return *this;
                }

                Iterator operator++(int)
                {
                    Iterator it(*this);
                    ++(*this);
                    return it;
                }

                Iterator& operator+=(Diff offset)
                {
                    *((ConstIterator *)this) += offset;
                    return *this;
                }

                Iterator operator+(Diff offset) const
                {
                    Iterator it(*this);
                    it += offset;
                    return it;
                }

                Iterator& operator--()
                {
                    --(*((ConstIterator *)this));
                    return *this;
                }

                Iterator operator--(int)
                {
                    Iterator it(*this);
                    --(*this);
                    return it;
                }

                Iterator& operator-=(Diff offset)
                {
                    *((ConstIterator *)this) -= offset;
                    return *this;
                }

                Iterator operator-(Diff offset) const
                {
                    Iterator it(*this);
                    it -= offset;
                    return it;
                }

                T& operator[](Diff ofs) const
                {
                    return *this->m_deque->ElementAt(this->m_ofs + ofs);
                }

                Diff operator-(const Iterator& it) const
                {
                    return (this->m_ofs < it.m_ofs) ? -Diff(it.m_ofs - this->m_ofs) 
                        : Diff(this->m_ofs - it.m_ofs);
                }
            };

        protected:
            static const Size MinBlockSize = 4096;
            static const Size MinMapSize = 8;

        private:
            Array<1,T *> m_map;
            Size m_mapMask;
            Size m_blockBits;
            Size m_blockMask;
            Iterator m_begin;
            Iterator m_end;

        protected:
            T *ElementAt(Size ofs)
            {
                return m_map[BlockIndex(ofs)] + BlockOffset(ofs);
            }

            const T *ElementAt(Size ofs) const
            {
                return m_map[BlockIndex(ofs)] + BlockOffset(ofs);
            }

            Size BlockSize() const
            {
                return (Size(1) << m_blockBits);
            }

            Size BlockIndex(Size ofs) const
            {
                return (ofs >> m_blockBits) & m_mapMask;
            }

            Size BlockOffset(Size ofs) const
            {
                return ofs & m_blockMask;
            }

            void ComputeBlockSize() 
            {
                Size blockElemCount = Math::IntegerDivCeil(MinBlockSize, sizeof(T));
                Size blockSize = Math::Calculus::RoundUpToPowerOf2(blockElemCount);
                m_blockBits = Math::Calculus::BinaryLogarithm(blockSize);
                m_blockMask = blockSize - 1;
            }

            void AllocateBlock(T *&block)
            {
                if (block == nullptr)
                {
                    Mem::OperatorNew(block, BlockSize(), SAF_SOURCE_LOCATION);
                }
            }

            void InitIterators()
            {
                m_begin.m_ofs = 0;
                m_begin.m_ptr = nullptr;
                m_begin.m_deque = this;

                m_end.m_ofs = 0;
                m_end.m_ptr = nullptr;
                m_end.m_deque = this;
            }

            void GrowMap()
            {
                if (m_map.IsEmpty())
                {
                    m_map.Resize(MinMapSize, nullptr);
                    m_mapMask = m_map.Elements() - 1;

                    // Allocate room for the sentinel element and setup iterators
                    AllocateBlock(m_map[0]);

                    m_begin.m_ofs = 0;
                    m_begin.m_ptr = m_map[0];
                    m_end.m_ofs = 0;
                    m_end.m_ptr = m_map[0];
                }
                else
                {
                    // Double the size of the map
                    Array<1,T *> newMap(2 * m_map.Elements());

                    // Copy old block pointers (unroll map)
                    Size firstBlock = BlockIndex(m_begin.m_ofs);
                    typename Array<1,T *>::Iterator iter = newMap.Begin();

                    for (Size i = 0; i < m_map.Elements(); ++i, ++iter)
                    {
                        *iter = m_map[firstBlock];
                        firstBlock = (firstBlock + 1) & m_mapMask;
                    }

                    // Initialize new block pointers
                    Algo::Range::Fill(iter, newMap.End(), (T *)nullptr);

                    // Replace old map with the new one
                    Algo::Swap(m_map, newMap);
                    m_mapMask = m_map.Elements() - 1;
                    
                    // Update iterators -> shift to beginning of the new map
                    Size elems = Elements();
                    m_begin.m_ofs = BlockOffset(m_begin.m_ofs);
                    m_end.m_ofs = m_begin.m_ofs + elems;
                }                
            }

            Size NormElemCount() const
            {
                return BlockOffset(m_begin.m_ofs) + Elements() + 1;
            }

        public:
            explicit Deque(Size elems = 0, const T& val = T())
                : m_mapMask(0)
            {
                ComputeBlockSize();
                InitIterators();

                while (elems-- > 0)
                {
                    PushBack(val);
                }
            }

            Deque(const MyType& d)
                : m_mapMask(0)
            {
                ComputeBlockSize();
                InitIterators();
                *this = d;
            }

            ~Deque()
            {
                Free();
            }

            MyType& operator=(const MyType& d)
            {
                if (this != &d)
                {
                    Free();

                    m_blockBits = d.m_blockBits;
                    m_blockMask = d.m_blockMask;

                    // Copy elements                    
                    for (ConstIterator ci = d.Begin(); ci != d.End(); ++ci)
                    {
                        PushBack(*ci);
                    }
                }

                return *this;
            }

            void Free()
            {
                while (!IsEmpty())
                {
                    PopBack();
                }

                for (Size i = 0; i < m_map.Elements(); i++)
                {
                    if (m_map[i] != nullptr)
                    {
                        Mem::OperatorDelete(m_map[i], BlockSize());
                    }
                }

                InitIterators();
                m_map.Free();
                m_mapMask = 0;
            }

            MyType& Swap(MyType& d)
            {
                if (this != &d)
                {
                    m_map.Swap(d.m_map);
                    Algo::Swap(m_mapMask, d.m_mapMask);
                    Algo::Swap(m_blockBits, d.m_blockBits);
                    Algo::Swap(m_blockMask, d.m_blockMask);
                    Algo::Swap(m_begin, d.m_begin);
                    Algo::Swap(m_end, d.m_end);
                }

                return *this;
            }

            Size Elements() const
            {
                return (m_end - m_begin);
            }

            bool IsEmpty() const
            {
                return (m_begin == m_end);
            }

            MyType& PushBack(const T& val)
            {
                // Check if we need to enlarge the block map
                if ((NormElemCount() >> m_blockBits) >= m_map.Elements())
                {
                    GrowMap();
                }

                // Insert position
                T *insPtr = m_end.m_ptr;

                // Increment end iterator
                AllocateBlock(m_map[BlockIndex(m_end.m_ofs + 1)]);
                ++m_end;

                // Insert new element
                new (insPtr) T(val);

                // Make sure that the start offset doesn't go to infinity after a series
                // of PushBack() + PopFront() operations. We cannot do this in PopFront()
                // because that would invalidate iterators.
                if ((m_begin.m_ofs >> m_blockBits) > m_mapMask)
                {
                    Size elems = m_end.m_ofs - m_begin.m_ofs;
                    m_begin.m_ofs &= (m_map.Elements() << m_blockBits) - 1;
                    m_end.m_ofs = m_begin.m_ofs + elems;
                }

                return *this;
            }

            MyType& PushFront(const T& val)
            {
                // Check if we need to enlarge the block map
                if ((NormElemCount() >> m_blockBits) >= m_map.Elements())
                {
                    GrowMap();
                }

                // Shift offsets if necessary
                if (!m_begin.m_ofs)
                {
                    Size totalCap = (m_map.Elements() << m_blockBits);
                    m_begin.m_ofs = totalCap;
                    m_end.m_ofs += totalCap;
                }

                // Decrement begin iterator and insert element
                AllocateBlock(m_map[BlockIndex(m_begin.m_ofs - 1)]);
                --m_begin;
                new (m_begin.m_ptr) T(val);

                return *this;
            }

            MyType& PopBack()
            {
                if (!IsEmpty())
                {
                    --m_end;
                    m_end.m_ptr->~T();
                }

                return *this;
            }

            MyType& PopFront()
            {
                if (!IsEmpty())
                {
                    T *ptr = m_begin.m_ptr;
                    ++m_begin;
                    ptr->~T();
                }

                return *this;
            }

            void Shrink()
            {
                if (IsEmpty())
                {
                    Free();
                }
                else
                {                    
                    // First block with valid elements
                    Size firstBlock = BlockIndex(m_begin.m_ofs);
                    // Number of blocks containing valid elements
                    Size validBlocks = Math::IntegerDivCeil(NormElemCount(), BlockSize());

                    // Create new block map
                    Array<1,T *> newMap(Algo::Selection::Max(MinMapSize, Math::Calculus::RoundUpToPowerOf2(validBlocks)));
                    typename Array<1,T *>::Iterator iter = newMap.Begin();

                    // Unroll the map, copy pointers to valid blocks and free empty blocks
                    for (Size i = 0; i < m_map.Elements(); ++i)
                    {
                        if (i < validBlocks)
                        {
                            *iter = m_map[firstBlock];
                            ++iter;
                        }
                        else if (m_map[firstBlock] != nullptr)
                        {
                            Mem::OperatorDelete(m_map[firstBlock], BlockSize());
                        }

                        firstBlock = (firstBlock + 1) & m_mapMask;
                    }

                    // Initialize new block pointers
                    Algo::Range::Fill(iter, newMap.End(), (T *)nullptr);

                    // Replace old map with the new one
                    Algo::Swap(m_map, newMap);
                    m_mapMask = m_map.Elements() - 1;

                    // Update iterators -> shift to beginning of the new map
                    Size elems = Elements();
                    m_begin.m_ofs = BlockOffset(m_begin.m_ofs);
                    m_end.m_ofs = m_begin.m_ofs + elems;
                }
            }

            T& operator[](Size i)
            {
                return m_begin[i];
            }

            const T& operator[](Size i) const
            {
                return m_begin[i];
            }

            Iterator Begin()
            {
                return m_begin;
            }

            ConstIterator Begin() const
            {
                return m_begin;
            }

            Iterator End()
            {
                return m_end;
            }

            ConstIterator End() const
            {
                return m_end;
            }

            Iterator Front()
            {
                return Begin();
            }

            ConstIterator Front() const
            {
                return Begin();
            }

            Iterator Back()
            {
                Iterator iEnd(m_end);
                return --iEnd;
            }

            ConstIterator Back() const
            {
                ConstIterator iEnd(m_end);
                return --iEnd;
            }
        };
    }

    namespace Algo
    {
        // Swap specialization for the double-ended queue container.
        template <class T>
        struct SwapFunc< Collection::Deque<T> >
        {
            void operator()(Collection::Deque<T>& x, Collection::Deque<T>& y)
            {
                x.Swap(y);
            }
        };
    }
}

#endif