adaptor/deque_by_stack.hpp

• View this file on GitHub
• Last update: 2024-07-27 23:01:00+09:00
• Include: #include "adaptor/deque_by_stack.hpp"

Depends on

• internal/dev_env.hpp
• macro/basic.hpp
• macro/overload.hpp
• snippet/iterations.hpp

Required by

• data_structure/foldable_deque.hpp
• data_structure/foldable_queue.hpp
• data_structure/foldable_stack.hpp
• include/adaptors.hpp
• include/all.hpp
• include/data_structures.hpp
• include/template.hpp
• template/standard.hpp
• template/using.hpp

Verified with

• verify/aizu-online-judge/itp1_1_a/0000.test.cpp
• verify/aizu-online-judge/itp1_1_a/0001.test.cpp
• verify/yosupo-judge/deque_operate_all_composite/0000.test.cpp
• verify/yosupo-judge/deque_operate_all_composite/0004.test.cpp
• verify/yosupo-judge/deque_operate_all_composite/0005.test.cpp
• verify/yosupo-judge/queue_operate_all_composite/0000.test.cpp
• verify/yosupo-judge/queue_operate_all_composite/0001.test.cpp
• verify/yosupo-judge/queue_operate_all_composite/0002.test.cpp

Code

#pragma once


#include <concepts>
#include <utility>
#include <vector>
#include <ranges>
#include <algorithm>


#include "snippet/iterations.hpp"

#include "internal/dev_env.hpp"


namespace uni {


template<class Front, class Back = Front>
struct deque_by_stack {
    static_assert(std::same_as<typename Front::value_type, typename Back::value_type>);
    static_assert(std::common_reference_with<typename Front::size_type, typename Back::size_type>);

    using value_type = Front::value_type;
    using size_type = std::common_type_t<typename Front::size_type, typename Back::size_type>;

  protected:
    Front _front;
    Back _back;

  private:
    template<std::ptrdiff_t OFFSET>
    inline void _distribute() noexcept(NO_EXCEPT) {
        if(this->empty()) return;

        std::vector<value_type> temp;
        temp.reserve(this->size());

        if(this->_front.empty()) {
            while(!this->_back.empty()) {
                temp.push_back(this->_back.top());
                this->_back.pop();
            }
            std::ranges::reverse(temp);
        }
        else if(this->_back.empty()) {
            while(!this->_front.empty()) {
                temp.push_back(this->_front.top());
                this->_front.pop();
            }
        }
        else {
            return;
        }

        assert(this->empty());

        const auto size = std::ranges::ssize(temp);
        const auto mid = (size + OFFSET) / 2;

        REPD(i, mid) this->_front.push(temp[i]);
        REP(i, mid, size) this->_back.push(temp[i]);
    }

  public:
    deque_by_stack() noexcept = default;

    inline bool empty() const noexcept(NO_EXCEPT) {
        return this->_front.empty() && this->_back.empty();
    }

    inline auto size() const noexcept(NO_EXCEPT) {
        return this->_front.size() + this->_back.size();
    }


    inline decltype(auto) front() const noexcept(NO_EXCEPT) {
        this->_distribute<1>();
        assert(!this->_front.empty());
        return this->_front.top();
    }

    inline decltype(auto) back() const noexcept(NO_EXCEPT) {
        this->_distribute<0>();
        assert(!this->_back.empty());
        return this->_back.top();
    }


    template<std::convertible_to<value_type> T = value_type>
        requires std::is_move_constructible_v<T>
    inline decltype(auto) front_or(T&& val) const noexcept(NO_EXCEPT) {
        if(this->empty()) return static_cast<value_type>(std::forward<T>(val));
        else return this->front();
    }

    template<std::convertible_to<value_type> T = value_type>
        requires std::is_move_constructible_v<T>
    inline decltype(auto) back_or(T&& val) const noexcept(NO_EXCEPT) {
        if(this->empty()) return static_cast<value_type>(std::forward<T>(val));
        else return this->back();
    }


    inline auto& clear() noexcept(NO_EXCEPT) {
        this->_front.clear(), this->_back.clear();
        return *this;
    }


    template<std::convertible_to<value_type> T = value_type>
    inline auto& push_front(T&& val) noexcept(NO_EXCEPT) {
        this->_front.push(std::forward<T>(val));
        return *this;
    }

    template<std::convertible_to<value_type> T = value_type>
    inline auto& push_back(T&& val) noexcept(NO_EXCEPT) {
        this->_back.push(std::forward<T>(val));
        return *this;
    }


    template<class... Args>
    inline decltype(auto) emplace_front(Args&&... args) noexcept(NO_EXCEPT) {
        return this->_front.emplace(std::forward<Args>(args)...);
    }

    template<class... Args>
    inline decltype(auto) emplace_back(Args&&... args) noexcept(NO_EXCEPT) {
        return this->_back.emplace(std::forward<Args>(args)...);
    }


    auto& pop_front() noexcept(NO_EXCEPT) {
        this->_distribute<1>();
        assert(!this->_front.empty());

        this->_front.pop();
        return *this;
    }

    auto& pop_back() noexcept(NO_EXCEPT) {
        this->_distribute<0>();
        assert(!this->_back.empty());

        this->_back.pop();
        return *this;
    }
};



} // namespace uni

#line 2 "adaptor/deque_by_stack.hpp"


#include <concepts>
#include <utility>
#include <vector>
#include <ranges>
#include <algorithm>


#line 2 "snippet/iterations.hpp"

#include <type_traits>
#line 2 "macro/overload.hpp"

#define $OVERLOAD2(arg0, arg1, cmd, ...) cmd
#define $OVERLOAD3(arg0, arg1, arg2, cmd, ...) cmd
#define $OVERLOAD4(arg0, arg1, arg2, arg3, cmd, ...) cmd
#define $OVERLOAD5(arg0, arg1, arg2, arg3, arg4, cmd, ...) cmd
#define $OVERLOAD6(arg0, arg1, arg2, arg3, arg4, arg5, cmd, ...) cmd
#line 2 "macro/basic.hpp"

#define TO_STRING_AUX(x) #x
#define TO_STRING(x) TO_STRING_AUX(x)

#define CONCAT_AUX(x, y) x##y
#define CONCAT(x, y) CONCAT_AUX(x, y)

#define UNPAREN_AUX(...) __VA_ARGS__
#define UNPAREN(...) __VA_ARGS__
#line 6 "snippet/iterations.hpp"


#define LOOP(n) REPI(CONCAT(_$, __COUNTER__), n)

#define REPI(i,n) for(std::remove_cvref_t<decltype(n)> i=0, CONCAT(i, $)=(n); i<CONCAT(i, $); ++i)
#define REPF(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); ++i)
#define REPIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<CONCAT(i, $); i+=(s))

#define REPR(i,n) for(auto i=(n); --i>=0;)
#define REPB(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); --i>=CONCAT(i, $);)
#define REPRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l)-1)/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); (i-=(s)))

#define REP(...) $OVERLOAD4(__VA_ARGS__, REPIS, REPF, REPI, LOOP)(__VA_ARGS__)
#define REPD(...) $OVERLOAD4(__VA_ARGS__, REPRS, REPB, REPR)(__VA_ARGS__)

#define FORO(i,n) for(int i=0, CONCAT(i, $)=static_cast<int>(n); i<=CONCAT(i, $); ++i)
#define FORI(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); ++i)
#define FORIS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l), CONCAT(i, $)=(r); i<=CONCAT(i, $); i+=(s))

#define FORRO(i,n) for(auto i=(n); i>=0; --i)
#define FORR(i,l,r) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>> i=(r), CONCAT(i, $)=(l); i>=CONCAT(i, $); --i)
#define FORRS(i,l,r,s) for(std::common_type_t<std::remove_cvref_t<decltype(l)>,std::remove_cvref_t<decltype(r)>,std::remove_cvref_t<decltype(s)>> i=(l)+((r)-(l))/(s)*(s), CONCAT(i, $)=(l); i>=CONCAT(i, $); i-=(s))

#define FOR(...) $OVERLOAD4(__VA_ARGS__, FORIS, FORI, FORO)(__VA_ARGS__)
#define FORD(...) $OVERLOAD4(__VA_ARGS__, FORRS, FORR, FORRO)(__VA_ARGS__)

#define ITR1(e0,v) for(const auto &e0 : (v))
#define ITRP1(e0,v) for(auto e0 : (v))
#define ITRR1(e0,v) for(auto &e0 : (v))

#define ITR2(e0,e1,v) for(const auto [e0, e1] : (v))
#define ITRP2(e0,e1,v) for(auto [e0, e1] : (v))
#define ITRR2(e0,e1,v) for(auto &[e0, e1] : (v))

#define ITR3(e0,e1,e2,v) for(const auto [e0, e1, e2] : (v))
#define ITRP3(e0,e1,e2,v) for(auto [e0, e1, e2] : (v))
#define ITRR3(e0,e1,e2,v) for(auto &[e0, e1, e2] : (v))

#define ITR4(e0,e1,e2,e3,v) for(const auto [e0, e1, e2, e3] : (v))
#define ITRP4(e0,e1,e2,e3,v) for(auto [e0, e1, e2, e3] : (v))
#define ITRR4(e0,e1,e2,e3,v) for(auto &[e0, e1, e2, e3] : (v))

#define ITR5(e0,e1,e2,e3,e4,v) for(const auto [e0, e1, e2, e3, e4] : (v))
#define ITRP5(e0,e1,e2,e3,e4,v) for(auto [e0, e1, e2, e3, e4] : (v))
#define ITRR5(e0,e1,e2,e3,e4,v) for(auto &[e0, e1, e2, e3, e4] : (v))

#define ITR(...) $OVERLOAD6(__VA_ARGS__, ITR5, ITR4, ITR3, ITR2, ITR1)(__VA_ARGS__)
#define ITRP(...) $OVERLOAD6(__VA_ARGS__, ITRP5, ITRP4, ITRP3, ITRP2, ITRP1)(__VA_ARGS__)
#define ITRR(...) $OVERLOAD6(__VA_ARGS__, ITRR5, ITRR4, ITRR3, ITRR2, ITRR1)(__VA_ARGS__)
#line 12 "adaptor/deque_by_stack.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 14 "adaptor/deque_by_stack.hpp"


namespace uni {


template<class Front, class Back = Front>
struct deque_by_stack {
    static_assert(std::same_as<typename Front::value_type, typename Back::value_type>);
    static_assert(std::common_reference_with<typename Front::size_type, typename Back::size_type>);

    using value_type = Front::value_type;
    using size_type = std::common_type_t<typename Front::size_type, typename Back::size_type>;

  protected:
    Front _front;
    Back _back;

  private:
    template<std::ptrdiff_t OFFSET>
    inline void _distribute() noexcept(NO_EXCEPT) {
        if(this->empty()) return;

        std::vector<value_type> temp;
        temp.reserve(this->size());

        if(this->_front.empty()) {
            while(!this->_back.empty()) {
                temp.push_back(this->_back.top());
                this->_back.pop();
            }
            std::ranges::reverse(temp);
        }
        else if(this->_back.empty()) {
            while(!this->_front.empty()) {
                temp.push_back(this->_front.top());
                this->_front.pop();
            }
        }
        else {
            return;
        }

        assert(this->empty());

        const auto size = std::ranges::ssize(temp);
        const auto mid = (size + OFFSET) / 2;

        REPD(i, mid) this->_front.push(temp[i]);
        REP(i, mid, size) this->_back.push(temp[i]);
    }

  public:
    deque_by_stack() noexcept = default;

    inline bool empty() const noexcept(NO_EXCEPT) {
        return this->_front.empty() && this->_back.empty();
    }

    inline auto size() const noexcept(NO_EXCEPT) {
        return this->_front.size() + this->_back.size();
    }


    inline decltype(auto) front() const noexcept(NO_EXCEPT) {
        this->_distribute<1>();
        assert(!this->_front.empty());
        return this->_front.top();
    }

    inline decltype(auto) back() const noexcept(NO_EXCEPT) {
        this->_distribute<0>();
        assert(!this->_back.empty());
        return this->_back.top();
    }


    template<std::convertible_to<value_type> T = value_type>
        requires std::is_move_constructible_v<T>
    inline decltype(auto) front_or(T&& val) const noexcept(NO_EXCEPT) {
        if(this->empty()) return static_cast<value_type>(std::forward<T>(val));
        else return this->front();
    }

    template<std::convertible_to<value_type> T = value_type>
        requires std::is_move_constructible_v<T>
    inline decltype(auto) back_or(T&& val) const noexcept(NO_EXCEPT) {
        if(this->empty()) return static_cast<value_type>(std::forward<T>(val));
        else return this->back();
    }


    inline auto& clear() noexcept(NO_EXCEPT) {
        this->_front.clear(), this->_back.clear();
        return *this;
    }


    template<std::convertible_to<value_type> T = value_type>
    inline auto& push_front(T&& val) noexcept(NO_EXCEPT) {
        this->_front.push(std::forward<T>(val));
        return *this;
    }

    template<std::convertible_to<value_type> T = value_type>
    inline auto& push_back(T&& val) noexcept(NO_EXCEPT) {
        this->_back.push(std::forward<T>(val));
        return *this;
    }


    template<class... Args>
    inline decltype(auto) emplace_front(Args&&... args) noexcept(NO_EXCEPT) {
        return this->_front.emplace(std::forward<Args>(args)...);
    }

    template<class... Args>
    inline decltype(auto) emplace_back(Args&&... args) noexcept(NO_EXCEPT) {
        return this->_back.emplace(std::forward<Args>(args)...);
    }


    auto& pop_front() noexcept(NO_EXCEPT) {
        this->_distribute<1>();
        assert(!this->_front.empty());

        this->_front.pop();
        return *this;
    }

    auto& pop_back() noexcept(NO_EXCEPT) {
        this->_distribute<0>();
        assert(!this->_back.empty());

        this->_back.pop();
        return *this;
    }
};



} // namespace uni

Back to top page