stack.h

#pragma once
 
#include <utils/messageException.h>
#include <memory/memoryStructure.h>
 
#include <vector>
 
namespace TuringSim::Memory::Stack {
    template <typename T> class StackObserver;
    template <typename T> class StackModifier;
 
    class StackTooSmallException : public Utils::MessageException {
    public:
        StackTooSmallException() = delete;
 
        StackTooSmallException(std::string message, size_t allocated, size_t freeSpace, size_t requestedElementsNumber) :
                MessageException(message), allocated(allocated), freeSpace(freeSpace), requestedElementsNumber(requestedElementsNumber)
        {}
 
        size_t getAllocated() const noexcept {
            return allocated;
        }
 
        size_t getFreeSpace() const noexcept {
            return freeSpace;
        }
 
    protected:
        virtual std::string makeFullMessage() const override {
            std::ostringstream ss;
            ss << this->msg << std::endl;
            ss << "  Allocated size: " << allocated << std::endl;
            ss << "  Free space: " << freeSpace << std::endl;
            ss << "  Requested elements number: " << requestedElementsNumber << std::endl;
            return ss.str();
        }
 
        size_t allocated;  
        size_t freeSpace;  
        size_t requestedElementsNumber;  
    };
 
    template<typename T>
    class Stack : public MemoryStructure<T, Stack<T>, StackObserver<T>, StackModifier<T>>
    {
        friend class StackObserver<T>;
 
        friend class StackModifier<T>;
 
    public:
        static constexpr size_t MinAllocatedStackSize = 10;
 
        constexpr Stack();
 
        constexpr Stack(const Stack<T>& other);
 
        constexpr Stack(Stack<T>&& other);
 
        constexpr Stack<T>& operator=(const Stack<T>& other);
 
        constexpr Stack<T>& operator=(Stack<T>&& other);
 
        ~Stack() = default;
 
        constexpr void push(const T& symbol);
 
        constexpr void push(T&& symbol);
 
        constexpr void pushs(const std::vector<T>& symbol);
 
        constexpr void pushs(std::vector<T>&& symbol);
 
        [[nodiscard]] const T& top() const;
 
        [[nodiscard]] std::optional<T> top_opt() const;
 
        [[nodiscard]] std::vector<T> tops(size_t nb) const;
 
        [[nodiscard]] std::optional<std::vector<T>> tops_opt(size_t nb) const;
 
        void pop();
 
        void pops(size_t nb);
 
        [[nodiscard]] constexpr bool empty() const noexcept;
 
        void assertNonEmpty() const;
 
    private:
        constexpr void allocate();
        constexpr void allocate(size_t additionalSize);
        constexpr void shrink();
        constexpr void disableFree();
        constexpr void enableFree();
        void setSizeFactor(size_t newSizeFactor);
        constexpr void free();
 
        size_t size = 0;
        size_t freeSpace = MinAllocatedStackSize;
        std::vector<T> stack = std::vector<T>(MinAllocatedStackSize);
        bool enabledFree = true;
        size_t sizeFactor = 2;
    };
 
    template<typename T>
    constexpr Stack<T>::Stack()
    {}
 
    template<typename T>
    constexpr Stack<T>::Stack(const Stack<T>& other) :
            size(other.size),
            freeSpace(other.freeSpace),
            stack(other.stack),
            enabledFree(other.enabledFree),
            sizeFactor(other.sizeFactor)
    {}
 
    template<typename T>
    constexpr Stack<T>::Stack(Stack<T>&& other) :
            size(std::move(other.size)),
            freeSpace(std::move(other.freeSpace)),
            stack(std::move(other.stack)),
            enabledFree(std::move(other.enabledFree)),
            sizeFactor(std::move(other.sizeFactor))
    {}
 
    template<typename T>
    constexpr Stack<T> &Stack<T>::operator=(const Stack<T>& other) {
        if(this != &other) {
            size = other.size;
            freeSpace = other.freeSpace;
            stack = other.stack;
            enabledFree = other.enabledFree;
            sizeFactor = other.sizeFactor;
        }
        return *this;
    }
 
    template<typename T>
    constexpr Stack<T> &Stack<T>::operator=(Stack<T>&& other) {
        if(this != &other) {
            size = std::move(other.size);
            freeSpace = std::move(other.freeSpace);
            stack = std::move(other.stack);
            enabledFree = std::move(other.enabledFree);
            sizeFactor = std::move(other.sizeFactor);
        }
        return *this;
    }
 
    template<typename T>
    constexpr void Stack<T>::push(const T& symbol) {
        if(!freeSpace) {
            allocate();
        }
 
        stack[size] = symbol;
        size++;
        freeSpace--;
    }
 
    template<typename T>
    constexpr void Stack<T>::push(T&& symbol) {
        if(!freeSpace) {
            allocate();
        }
 
        stack[size] = std::move(symbol);
        size++;
        freeSpace--;
    }
 
    template<typename T>
    constexpr void Stack<T>::pushs(const std::vector<T>& symbols) {
        while(freeSpace < symbols.size()) {
            allocate();
        }
 
        for(const T& symbol: symbols) {
            stack[size] = symbol;
            size++;
        }
 
        freeSpace -= symbols.size();
    }
 
    template<typename T>
    constexpr void Stack<T>::pushs(std::vector<T>&& symbols) {
        while(freeSpace < symbols.size()) {
            allocate();
        }
 
        for(T& symbol: symbols) {
            stack[size] = std::move(symbol);
            size++;
        }
 
        freeSpace -= symbols.size();
    }
 
    template<typename T>
    constexpr void Stack<T>::allocate()
    {
        stack.resize(sizeFactor*stack.size());
        freeSpace = stack.size() - size;
    }
 
    template<typename T>
    constexpr void Stack<T>::allocate(size_t additionalSize) {
        stack.resize(stack.size() + additionalSize);
        freeSpace = stack.size() - size;
    }
 
    template <typename T>
    const T& Stack<T>::top() const {
        if(!size) {
            throw StackTooSmallException("Empty stack in Stack<T>::top()", stack.size(), freeSpace, 1);
        }
        return stack[size-1];
    }
 
    template <typename T>
    std::optional<T> Stack<T>::top_opt() const {
        if(!size) {
            return {};
        }
        return {stack[size - 1]};
    }
 
    template <typename T>
    std::vector<T> Stack<T>::tops(size_t nb) const {
        if(size < nb) {
            throw StackTooSmallException("Empty stack in Stack<T>::tops()", stack.size(), freeSpace, nb);
        }
        return {stack.begin() + static_cast<long>(size) - static_cast<long>(nb), stack.begin() + static_cast<long>(size)};
    }
 
    template <typename T>
    std::optional<std::vector<T>> Stack<T>::tops_opt(size_t nb) const {
        if(size < nb) {
            return {};
        }
        return {std::vector<T>{stack.begin() + static_cast<long>(size) - static_cast<long>(nb), stack.begin() + static_cast<long>(size)}};
    }
 
    template <typename T>
    void Stack<T>::pop() {
        if(!size) {
            throw StackTooSmallException("Empty stack in Stack<T>::pop()", stack.size(), freeSpace, 1);
        }
        size--;
        freeSpace++;
 
        if(enabledFree) {
            free();
        }
    }
 
    template <typename T>
    void Stack<T>::pops(size_t nb) {
        if(size < nb) {
            throw StackTooSmallException("Stack too small in Stack<T>::pops()", stack.size(), freeSpace, nb);
        }
        size -= nb;
        freeSpace += nb;
 
        if(enabledFree) {
            free();
        }
    }
 
    template <typename T>
    constexpr bool Stack<T>::empty() const noexcept {
        return size==0;
    }
 
    template <typename T>
    void Stack<T>::assertNonEmpty() const {
        if (!size) {
            throw StackTooSmallException("Empty stack in Stack<T>::assertNonEmpty()", stack.size(), freeSpace, 1);
        }
    }
 
    template <typename T>
    constexpr void Stack<T>::free() {
        if((sizeFactor*sizeFactor-1)*size < freeSpace) {
            stack.resize(std::max(MinAllocatedStackSize, stack.size()/sizeFactor));
            freeSpace = stack.size() - size;
        }
    }
 
    template <typename T>
    constexpr void Stack<T>::shrink() {
        stack.resize(std::max(size, MinAllocatedStackSize));
        freeSpace = 0;
    }
 
    template <typename T>
    constexpr void Stack<T>::disableFree() {
        enabledFree = false;
    }
 
    template <typename T>
    constexpr void Stack<T>::enableFree() {
        enabledFree = true;
        free();
    }
 
    template <typename T>
    void Stack<T>::setSizeFactor(size_t newSizeFactor) {
        if(newSizeFactor < 2) {
            throw InvalidFactorException("Size factor is too small in Stack<T>::setSizeFactor(size_t). Must be > 1.", newSizeFactor);
        }
        sizeFactor = newSizeFactor;
    }
 
    template <typename T>
    class StackObserver : public MemoryObserver<Stack<T>, StackObserver<T>>
    {
    public:
        constexpr StackObserver(const Stack<T>& stack) : MemoryObserver<Stack<T>, StackObserver<T>>(&stack) {}
        [[nodiscard]] constexpr size_t getSize() const { return this->memory->size; }
        [[nodiscard]] constexpr size_t getFreeSpace() const { return this->memory->freeSpace; }
        [[nodiscard]] constexpr size_t getAllocatedSize() const { return this->memory->stack.size(); }
        [[nodiscard]] constexpr const std::vector<T>& getStack() const { return this->memory->stack; }
        [[nodiscard]] constexpr bool getEnabledFree() const { return this->memory->enabledFree; }
        [[nodiscard]] constexpr size_t getSizeFactor() const { return this->memory->sizeFactor; }
    };
 
    template <typename T>
    class StackModifier : public MemoryModifier<Stack<T>, StackModifier<T>>
    {
    public:
        constexpr StackModifier(Stack<T>& stack) : MemoryModifier<Stack<T>, StackModifier<T>>(&stack) {}
        constexpr void allocate() const { this->memory->allocate(); }
        constexpr void allocate(size_t additionalSize) const { this->memory->allocate(additionalSize); }
        constexpr void shrink() const { this->memory->shrink(); }
 
        constexpr void disableFree() const { this->memory->disableFree(); }
 
        constexpr void enableFree() const { this->memory->enableFree(); }
 
        constexpr void setSizeFactor(size_t newSizeFactor) { this->memory->setSizeFactor(newSizeFactor); }
    };
}