CompactArrayStack.h

Go to the documentation of this file.

 
#pragma once
#include "catapult/constants.h"
#include "catapult/exceptions.h"
#include "catapult/types.h"
 
namespace catapult { namespace state {
 
    template<typename T, size_t N>
    class CompactArrayStack {
    public:
        // region const_iterator
 
        class const_iterator {
        public:
            using difference_type = std::ptrdiff_t;
            using value_type = const T;
            using pointer = const T*;
            using reference = const T&;
            using iterator_category = std::forward_iterator_tag;
 
        public:
            explicit const_iterator(const std::array<T, N>* pArray, size_t index)
                    : m_pArray(pArray)
                    , m_index(index)
            {}
 
        public:
            bool operator==(const const_iterator& rhs) const {
                return m_pArray == rhs.m_pArray && m_index == rhs.m_index;
            }
 
            bool operator!=(const const_iterator& rhs) const {
                return !(*this == rhs);
            }
 
        public:
            const_iterator& operator++() {
                if (isEnd())
                    CATAPULT_THROW_OUT_OF_RANGE("cannot advance iterator beyond end");
 
                ++m_index;
                return *this;
            }
 
            const_iterator operator++(int) {
                auto copy = *this;
                ++*this;
                return copy;
            }
 
        public:
            reference operator*() const {
                return *(this->operator->());
            }
 
            pointer operator->() const {
                if (isEnd())
                    CATAPULT_THROW_OUT_OF_RANGE("cannot dereference at end");
 
                return m_pArray ? &(*m_pArray)[m_index] : &m_defaultValue;
            }
 
        private:
            bool isEnd() const {
                return N == m_index;
            }
 
        private:
            const std::array<T, N>* m_pArray;
            size_t m_index;
            T m_defaultValue;
        };
 
        // endregion
 
    public:
        CompactArrayStack() : m_size(0)
        {}
 
        CompactArrayStack(const CompactArrayStack& stack) {
            *this = stack;
        }
 
        CompactArrayStack(CompactArrayStack&& stack)
                : m_pArray(std::move(stack.m_pArray))
                , m_size(stack.m_size) {
            stack.m_size = 0;
        }
 
    public:
        CompactArrayStack& operator=(const CompactArrayStack& stack) {
            if (stack.m_pArray)
                m_pArray = std::make_unique<std::array<T, N>>(*stack.m_pArray);
 
            m_size = stack.m_size;
            return *this;
        }
 
        CompactArrayStack& operator=(CompactArrayStack&& stack) {
            m_pArray = std::move(stack.m_pArray);
            m_size = stack.m_size;
            stack.m_size = 0;
            return *this;
        }
 
    public:
        size_t size() const {
            return m_size;
        }
 
    public:
        const_iterator begin() const {
            return const_iterator(m_pArray.get(), 0);
        }
 
        const_iterator end() const {
            return const_iterator(m_pArray.get(), N);
        }
 
    public:
        const T& peek() const {
            if (0 == m_size)
                CATAPULT_THROW_OUT_OF_RANGE("cannot peek when empty");
 
            return m_pArray->front();
        }
 
        T& peek() {
            if (0 == m_size)
                CATAPULT_THROW_OUT_OF_RANGE("cannot peek when empty");
 
            return m_pArray->front();
        }
 
    public:
        void push(const T& value) {
            shiftRight();
            if (m_size < N)
                ++m_size;
 
            if (!m_pArray)
                m_pArray = std::make_unique<std::array<T, N>>();
 
            m_pArray->front() = value;
        }
 
        void pop() {
            shiftLeft();
            m_pArray->back() = T();
            --m_size;
 
            if (0 == m_size)
                m_pArray.reset();
        }
 
    private:
        void shiftLeft() {
            if (!m_pArray)
                CATAPULT_THROW_OUT_OF_RANGE("cannot pop when empty");
 
            auto& array = *m_pArray;
            for (auto i = 0u; i < array.size() - 1; ++i)
                array[i] = array[i + 1];
        }
 
        void shiftRight() {
            if (!m_pArray)
                return;
 
            auto& array = *m_pArray;
            for (auto i = array.size() - 1; i > 0; --i)
                array[i] = array[i - 1];
        }
 
    private:
        std::unique_ptr<std::array<T, N>> m_pArray;
        size_t m_size;
    };
}}