data_structure/persistent_stack.hpp

View this file on GitHub
Last update: 2024-05-13 20:26:20+09:00
Include: #include "data_structure/persistent_stack.hpp"

Depends on

Required by

Verified with

Code

#pragma once


#include <memory>
#include <type_traits>
#include <memory_resource>


#include "data_structure/internal/node_handler.hpp"

#include "internal/dev_env.hpp"
#include "internal/types.hpp"


namespace uni {


template<class ValueType, class Allocator = std::allocator<ValueType>>
struct persistent_stack {
    using value_type = ValueType;
    using size_type = internal::size_t;


    struct node_type;
    using node_handler = node_handlers::cloneable<Allocator>::template handler<node_type>;

    using allocator_type = typename node_handler::allocator_type;
    using node_pointer = typename node_handler::node_pointer;

    struct node_type {
        value_type value;
        node_pointer next;

        node_type(node_pointer _next, value_type _value) noexcept(NO_EXCEPT)
          : value(_value), next(_next)
        {}

        template<class... Args>
        node_type(node_pointer _next, Args&&... args) noexcept(NO_EXCEPT)
          : value(std::forward<Args>(args)...), next(_next)
        {}
    };

  private:
    size_type _size = 0;
    node_pointer _head;

    [[no_unique_address]] node_handler _node_handler;

  public:
    explicit persistent_stack(const allocator_type& allocator = allocator_type()) noexcept(NO_EXCEPT) : _node_handler(allocator) {};


    persistent_stack(const persistent_stack& source, const allocator_type& allocator) noexcept(NO_EXCEPT)
      : _size(source._size), _head(source._head), _node_handler(allocator)
    {};

    persistent_stack(persistent_stack&& source, const allocator_type& allocator) noexcept(NO_EXCEPT)
      : _size(source._size), _head(source._head), _node_handler(allocator)
    {};


    inline auto clone() const noexcept(NO_EXCEPT) { return *this; }


    inline bool empty() const noexcept(NO_EXCEPT) { return !this->_head; }
    inline size_type size() const noexcept(NO_EXCEPT) { return this->_size; }

    inline value_type top() const noexcept(NO_EXCEPT) {
        assert(!this->empty());
        return this->_head->value;
    }

    template<std::convertible_to<value_type> T = value_type>
        requires std::is_move_constructible_v<T>
    inline value_type top_or(T&& v) const noexcept(NO_EXCEPT) {
        if(this->empty()) return static_cast<value_type>(std::forward<T>(v));
        else return this->top();
    }


    inline auto& clear() noexcept(NO_EXCEPT) {
        this->_head.reset();
        this->_size = 0;
        return *this;
    }


    template<std::convertible_to<value_type> T = value_type>
    inline auto& push(T&& x) noexcept(NO_EXCEPT) {
        this->_head = this->_node_handler.create(this->_head, std::forward<T>(x));
        ++this->_size;
        return *this;
    }

    template<class... Args>
    inline auto& emplace(Args&&... args) noexcept(NO_EXCEPT) {
        this->_head = this->_node_handler.create(this->_head, std::forward<Args>(args)...);
        ++this->_size;
        return this->_head->value;
    }


    inline auto& pop() noexcept(NO_EXCEPT) {
        assert(!this->empty());
        this->_head = this->_head->next;
        --this->_size;
        return *this;
    }
};


namespace pmr {


template<class T>
using persistent_stack = uni::persistent_stack<T, std::pmr::polymorphic_allocator<T>>;


} // namesapce pmr


} // namespace uni

#line 2 "data_structure/persistent_stack.hpp"


#include <memory>
#include <type_traits>
#include <memory_resource>


#line 2 "data_structure/internal/node_handler.hpp"


#line 5 "data_structure/internal/node_handler.hpp"

#line 2 "internal/dev_env.hpp"


#ifdef LOCAL_JUDGE
    inline constexpr bool DEV_ENV = true;
    inline constexpr bool NO_EXCEPT = false;
#else
    inline constexpr bool DEV_ENV = false;
    inline constexpr bool NO_EXCEPT = true;
#endif // LOCAL_JUDGE


#if __cplusplus >= 202100L
    #define CPP20 true
    #define CPP23 true
#elif __cplusplus >= 202002L
    #define CPP20 true
    #define CPP23 false
#else
    #define CPP20 false
    #define CPP23 false
#endif
#line 7 "data_structure/internal/node_handler.hpp"


namespace uni {

namespace node_handlers {

namespace internal {


template<class Allocator, class NodeType>
struct base_handler {
    using allocator_type = Allocator;

  protected:
    using allocator_traits = std::allocator_traits<allocator_type>;

    using node_allocator_type = allocator_traits::template rebind_alloc<NodeType>;
    using node_allocator_traits = std::allocator_traits<node_allocator_type>;

    [[no_unique_address]] node_allocator_type _allocator;

  public:
    base_handler(const allocator_type& allocator = allocator_type()) noexcept(NO_EXCEPT)
        : _allocator(allocator)
    {}

    base_handler(const base_handler& source) noexcept(NO_EXCEPT)
        : _allocator(node_allocator_traits::select_on_container_copy_construction(source._allocator))
    {}

    base_handler(base_handler&& source) noexcept = default;

    auto& operator=(const base_handler& source) noexcept(NO_EXCEPT) {
        if(&source != this) {
            if constexpr(allocator_traits::propagate_on_container_copy_assignment::value) {
                this->_allocator = source._allocator;
            }
        }
        return *this;
    }

    auto& operator=(base_handler&& source) noexcept(NO_EXCEPT) {
        if(&source != this) {
            if constexpr(allocator_traits::propagate_on_container_move_assignment::value) {
                this->_allocator = source._allocator;
            }
        }
        return *this;
    }
};


} // namespace internal


template<class Allocator>
struct cloneable {
    template<class NodeType>
    struct handler : internal::base_handler<Allocator, NodeType> {
        using internal::base_handler<Allocator, NodeType>::base_handler;

        using node_type = NodeType;
        using node_pointer = std::shared_ptr<node_type>;

        inline static node_pointer nil = std::make_shared<node_type>();

        template<class... Args>
        inline auto create(Args&&... args) noexcept(NO_EXCEPT) {
            return std::allocate_shared<node_type>(this->_allocator, std::forward<Args>(args)...);
        }

        inline auto clone(const node_pointer& ptr) noexcept(NO_EXCEPT) {
            return this->create(*ptr);
        }

        inline constexpr bool disposable(const node_pointer&) const noexcept { return false; }
        inline constexpr void dispose(const node_pointer&) const noexcept {}
    };
};


template<class Allocator>
struct reusing {
    template<class NodeType>
    struct handler : internal::base_handler<Allocator, NodeType> {
        using node_type = NodeType;
        using node_pointer = std::add_pointer_t<node_type>;

      private:
        using base = internal::base_handler<Allocator, NodeType>;
        using node_allocator_traits = typename base::node_allocator_traits;

        inline static int _instance_count = 0;

      public:
        using base::base;

        using allocator_type = typename base::allocator_type;


        inline static node_pointer nil;


        handler(const allocator_type& allocator = allocator_type()) noexcept(NO_EXCEPT) : base(allocator) {
            if(handler::_instance_count++ == 0) {
                handler::nil = new node_type{};
            }
        }

        ~handler() noexcept {
            if(--handler::_instance_count == 0) {
                delete handler::nil;
            }
        }


        template<class... Args>
        inline auto create(Args&&... args) noexcept(NO_EXCEPT) {
            node_pointer node = node_allocator_traits::allocate(this->_allocator, 1);
            node_allocator_traits::construct(this->_allocator, node, std::forward<Args>(args)...);

            return node;
        }

        inline auto clone(const node_pointer ptr) const noexcept { return ptr; }

        inline bool disposable(const node_pointer node) const noexcept(NO_EXCEPT) {
            return node != handler::nil;
        }

        inline void dispose(const node_pointer node) noexcept(NO_EXCEPT) {
            node_allocator_traits::destroy(this->_allocator, node);
            node_allocator_traits::deallocate(this->_allocator, node, 1);
        }
    };
};


} // namespace node_handlers

} // namespace uni
#line 10 "data_structure/persistent_stack.hpp"

#line 2 "internal/types.hpp"

#include <cstdint>

namespace uni {

namespace internal {


using size_t = std::int64_t;

using int128_t = __int128_t;
using uint128_t = __uint128_t;


} // namesapce internal

} // namespace uni
#line 13 "data_structure/persistent_stack.hpp"


namespace uni {


template<class ValueType, class Allocator = std::allocator<ValueType>>
struct persistent_stack {
    using value_type = ValueType;
    using size_type = internal::size_t;


    struct node_type;
    using node_handler = node_handlers::cloneable<Allocator>::template handler<node_type>;

    using allocator_type = typename node_handler::allocator_type;
    using node_pointer = typename node_handler::node_pointer;

    struct node_type {
        value_type value;
        node_pointer next;

        node_type(node_pointer _next, value_type _value) noexcept(NO_EXCEPT)
          : value(_value), next(_next)
        {}

        template<class... Args>
        node_type(node_pointer _next, Args&&... args) noexcept(NO_EXCEPT)
          : value(std::forward<Args>(args)...), next(_next)
        {}
    };

  private:
    size_type _size = 0;
    node_pointer _head;

    [[no_unique_address]] node_handler _node_handler;

  public:
    explicit persistent_stack(const allocator_type& allocator = allocator_type()) noexcept(NO_EXCEPT) : _node_handler(allocator) {};


    persistent_stack(const persistent_stack& source, const allocator_type& allocator) noexcept(NO_EXCEPT)
      : _size(source._size), _head(source._head), _node_handler(allocator)
    {};

    persistent_stack(persistent_stack&& source, const allocator_type& allocator) noexcept(NO_EXCEPT)
      : _size(source._size), _head(source._head), _node_handler(allocator)
    {};


    inline auto clone() const noexcept(NO_EXCEPT) { return *this; }


    inline bool empty() const noexcept(NO_EXCEPT) { return !this->_head; }
    inline size_type size() const noexcept(NO_EXCEPT) { return this->_size; }

    inline value_type top() const noexcept(NO_EXCEPT) {
        assert(!this->empty());
        return this->_head->value;
    }

    template<std::convertible_to<value_type> T = value_type>
        requires std::is_move_constructible_v<T>
    inline value_type top_or(T&& v) const noexcept(NO_EXCEPT) {
        if(this->empty()) return static_cast<value_type>(std::forward<T>(v));
        else return this->top();
    }


    inline auto& clear() noexcept(NO_EXCEPT) {
        this->_head.reset();
        this->_size = 0;
        return *this;
    }


    template<std::convertible_to<value_type> T = value_type>
    inline auto& push(T&& x) noexcept(NO_EXCEPT) {
        this->_head = this->_node_handler.create(this->_head, std::forward<T>(x));
        ++this->_size;
        return *this;
    }

    template<class... Args>
    inline auto& emplace(Args&&... args) noexcept(NO_EXCEPT) {
        this->_head = this->_node_handler.create(this->_head, std::forward<Args>(args)...);
        ++this->_size;
        return this->_head->value;
    }


    inline auto& pop() noexcept(NO_EXCEPT) {
        assert(!this->empty());
        this->_head = this->_head->next;
        --this->_size;
        return *this;
    }
};


namespace pmr {


template<class T>
using persistent_stack = uni::persistent_stack<T, std::pmr::polymorphic_allocator<T>>;


} // namesapce pmr


} // namespace uni