#ifndef __GBLIBCPP_TUPLE__
#define __GBLIBCPP_TUPLE__

#include <cstddef>
#include <type_traits>
#include <utility>

#include <functional>

#include <bits/tuple_tools>
#include <bits/sequence>

namespace std {

template <std::size_t I, typename T>
struct tuple_element<I, const T> {
    using type = std::add_const_t<tuple_element_t<I, T>>;
};
template <std::size_t I, typename T>
struct tuple_element<I, volatile T> {
    using type = std::add_volatile_t<tuple_element_t<I, T>>;
};
template <std::size_t I, typename T>
struct tuple_element<I, const volatile T> {
    using type = std::add_cv_t<tuple_element_t<I, T>>;
};

namespace __helpers {

template <typename T, typename = void>
struct __const_tuple_size {};

template <typename T>
struct __const_tuple_size<T, void_t<decltype(std::tuple_size<T>::value)>>
    : std::integral_constant<std::size_t, std::tuple_size<T>::value> {};

} // namespace __helpers

template <typename T>
struct tuple_size<const T> : __helpers::__const_tuple_size<T> {};

template <typename... Types>
class tuple;

template <std::size_t I, typename Type, typename... Types>
struct tuple_element<I, std::tuple<Type, Types...>>
    : tuple_element<I-1, std::tuple<Types...>> {};

template <typename Type, typename... Types>
struct tuple_element<0, std::tuple<Type, Types...>> { using type = Type; };

template <typename... Types>
struct tuple_size<std::tuple<Types...>>
    : std::integral_constant<std::size_t, sizeof...(Types)> {};

namespace __helpers {

template <std::size_t I, typename... Types>
class tuple_impl;

template <>
class tuple_impl<0> {
    template <std::size_t, typename...>
    friend class tuple_impl;

    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(std::tuple<UTypes...>& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>>&;
    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(std::tuple<UTypes...>&& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>>&&;
    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(const std::tuple<UTypes...>& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>> const&;
    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(const std::tuple<UTypes...>&& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>> const&&;

    template <std::size_t> constexpr void _getl(void) const = delete;
    template <std::size_t> constexpr void _getr(void) const = delete;
public:
    constexpr tuple_impl() noexcept = default;

    constexpr tuple_impl(const tuple_impl& arg) noexcept = default;
    constexpr tuple_impl(tuple_impl&& arg) noexcept = default;

    template <typename... UTypes>
    constexpr tuple_impl(const std::tuple<UTypes...>& other) = delete;
    template <typename... UTypes>
    constexpr tuple_impl(std::tuple<UTypes...>&& other) = delete;

    constexpr tuple_impl& operator=(const tuple_impl& other) noexcept = default;
    constexpr tuple_impl& operator=(tuple_impl&& other) noexcept = default;
};

template <std::size_t I, typename Type, typename... Types>
class tuple_impl<I, Type, Types...> {
    template <std::size_t, typename...>
    friend class tuple_impl;

    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(std::tuple<UTypes...>& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>>&;
    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(std::tuple<UTypes...>&& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>>&&;
    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(const std::tuple<UTypes...>& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>> const&;
    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(const std::tuple<UTypes...>&& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>> const&&;

    Type val;
    tuple_impl<I+1, Types...> next;

    template <std::size_t J>
    constexpr auto& _getl(void)
    {
        if constexpr (I == J)
            return val;
        else
            return next.template _getl<J>();
    }

    template <std::size_t J>
    constexpr const auto& _getl(void) const
    {
        if constexpr (I == J)
            return val;
        else
            return next.template _getl<J>();
    }

    template <std::size_t J>
    constexpr auto&& _getr(void)
    {
        if constexpr (I == J)
            return std::forward<Type>(val);
        else
            return std::forward<
                decltype(next.template _getr<J>())>(
                    next.template _getr<J>());
    }

    template <std::size_t J>
    constexpr const auto&& _getr(void) const
    {
        if constexpr (I == J)
            return std::forward<Type>(val);
        else
            return std::forward<
                decltype(next.template _getr<J>())>(
                    next.template _getr<J>());
    }

public:
    constexpr tuple_impl()
        : val(), next() {}

    constexpr tuple_impl(const tuple_impl& arg) = default;
    constexpr tuple_impl(tuple_impl&& arg) = default;

    constexpr tuple_impl(const Type& val, const Types&... vals)
        : val(val), next(vals...) {}

    template <typename UType, typename... UTypes>
    constexpr tuple_impl(UType&& val, UTypes&&... vals)
        : val(std::forward<UType>(val)), next(std::forward<UTypes>(vals)...) {}

    template <typename... UTypes>
    constexpr tuple_impl(const std::tuple<UTypes...>& other)
        : val(std::get<I>(other)), next(other) {}
    template <typename... UTypes>
    constexpr tuple_impl(std::tuple<UTypes...>&& other)
        : val(std::get<I>(other)), next(std::move(other)) {}

    constexpr tuple_impl& operator=(const tuple_impl& other) = default;
    constexpr tuple_impl& operator=(tuple_impl&& other) = default;
};

template <std::size_t I, typename Type>
class tuple_impl<I, Type> {
    template <std::size_t, typename...>
    friend class tuple_impl;

    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(std::tuple<UTypes...>& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>>&;
    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(std::tuple<UTypes...>&& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>>&&;
    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(const std::tuple<UTypes...>& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>> const&;
    template <std::size_t J, typename... UTypes>
    friend constexpr auto std::get(const std::tuple<UTypes...>&& tpl) noexcept
        -> tuple_element_t<J, std::tuple<UTypes...>> const&&;

    Type val;

    template <std::size_t J>
    constexpr Type& _getl(void)
    {
        static_assert(J == I);
        return val;
    }
    template <std::size_t J>
    constexpr Type const& _getl(void) const
    {
        static_assert(J == I);
        return val;
    }
    template <std::size_t J>
    constexpr Type&& _getr(void)
    {
        static_assert(J == I);
        return std::forward<Type>(val);
    }
    template <std::size_t J>
    constexpr Type const&& _getr(void) const
    {
        static_assert(J == I);
        return std::forward<Type>(val);
    }

public:
    constexpr tuple_impl()
        : val() {}

    constexpr tuple_impl(const tuple_impl& arg) = default;
    constexpr tuple_impl(tuple_impl&& arg) = default;

    constexpr tuple_impl(const Type& val) : val(val) {}

    template <typename UType>
    constexpr tuple_impl(UType&& val) : val(std::forward<UType>(val)) {}

    template <typename... UTypes>
    constexpr tuple_impl(const std::tuple<UTypes...>& other)
        : val(std::get<I>(other)) {}
    template <typename... UTypes>
    constexpr tuple_impl(std::tuple<UTypes...>&& other)
        : val(std::get<I>(other)) {}

    constexpr tuple_impl& operator=(const tuple_impl& other) = default;
    constexpr tuple_impl& operator=(tuple_impl&& other) = default;
};

template <typename... Types>
struct tuple_constraints {
    static constexpr std::size_t Tsize = sizeof...(Types);

    template <std::size_t... I>
    static constexpr auto idx_seq(std::index_sequence<I...> seq)
    { return seq; }

    template <typename UTuple, typename Seq, typename... UTypes>
    struct tuple_copy_move_constructible_impl;

    template <typename UTuple, typename... UTypes, std::size_t... I>
    struct tuple_copy_move_constructible_impl<UTuple,
        std::index_sequence<I...>, UTypes...> : std::bool_constant<
        Tsize == sizeof...(UTypes)
        && (... && std::is_constructible_v<Types, decltype(
            std::get<I>(std::declval<UTuple>()))>)
        && ((Tsize != 1) || (!(... && std::is_convertible_v<UTuple, Types>)
            && !(... && std::is_constructible_v<Types, UTuple>)
            && !(... && std::is_same_v<Types, UTypes>)))
    > {};

    template <typename UTuple, typename... UTypes>
    struct tuple_copy_move_constructible : tuple_copy_move_constructible_impl<
        UTuple, decltype(idx_seq(std::index_sequence_for<UTypes...>{})), UTypes...> {};

    template <typename Pair, typename = std::index_sequence<0, 1>>
    struct tuple_pair_constructible;

    template <typename Pair, std::size_t... I>
    struct tuple_pair_constructible<Pair, std::index_sequence<I...>>
        : std::bool_constant<sizeof...(Types) == 2
            && (... && std::is_constructible_v<Types,
                decltype(std::get<I>(std::declval<Pair>()))>)
    > {};

    template <typename... Us>
    struct tuple_pair_copy_assignable : std::bool_constant<
        sizeof...(Types) == 2
        && (... && std::is_assignable_v<Types&, const Us&>)
    > {};

    template <typename... Us>
    struct tuple_pair_move_assignable : std::bool_constant<
        sizeof...(Types) == 2
        && (... && std::is_assignable_v<Types&, Us>)
    > {};
};

} // namespace __helpers

template <typename... Types>
class tuple : public __helpers::tuple_impl<0, Types...> {
private:
    using base = __helpers::tuple_impl<0, Types...>;

    template <typename... UTypes, std::size_t... I>
    constexpr void __copy_assignment(
        const tuple<UTypes...>& other, std::index_sequence<I...>)
    { ((std::get<I>(*this) = std::get<I>(other)), ...); }

    template <typename... UTypes, std::size_t... I>
    constexpr void __move_assignment(
        tuple<UTypes...>&& other, std::index_sequence<I...>)
    {
        ((std::get<I>(*this) = std::forward<UTypes>(std::get<I>(other))), ...);
    }

public:
    template <typename _ = void, std::enable_if_t<
        (... && std::is_default_constructible_v<Types>)
        && __helpers::template_true_type<_>::value
    , bool> = true>
    constexpr tuple() : base() {}

    template <typename _ = void, std::enable_if_t<
        sizeof...(Types) >= 1
        && (... && std::is_copy_constructible_v<Types>)
        && __helpers::template_true_type<_>::value
    , bool> = true>
    constexpr tuple(const Types&... args)
        : base(args...) {}

    template <typename... UTypes, std::enable_if_t<
        sizeof...(UTypes) == sizeof...(Types)
        && sizeof...(Types) >= 1
        && (... && std::is_constructible_v<Types, UTypes>)
        && !(sizeof...(Types) == 1
            && (... && std::is_same_v<tuple, std::remove_cvref_t<UTypes>>))
    , bool> = true>
    constexpr tuple(UTypes&&... args)
        : base(std::forward<UTypes>(args)...) {}

    template <typename... UTypes, std::enable_if_t<
        __helpers::tuple_constraints<Types...>::template
            tuple_copy_move_constructible<const tuple<UTypes...>&, UTypes...>::value
    , bool> = true>
    constexpr tuple(const tuple<UTypes...>& other)
        : base(other) {}

    template <typename... UTypes, std::enable_if_t<
        __helpers::tuple_constraints<Types...>::template
            tuple_copy_move_constructible<tuple<UTypes...>&&, UTypes...>::value
    , bool> = true>
    constexpr tuple(tuple<UTypes...>&& other)
        : base(std::move(other)) {}

    template <typename U1, typename U2, std::enable_if_t<
        __helpers::tuple_constraints<Types...>::template
            tuple_pair_constructible<const std::pair<U1, U2>&>::value
    , bool> = true>
    constexpr tuple(const std::pair<U1, U2>& p)
        : base(std::get<0>(p), std::get<1>(p)) {}

    template <typename U1, typename U2, std::enable_if_t<
        __helpers::tuple_constraints<Types...>::template
            tuple_pair_constructible<std::pair<U1, U2>&&>::value
    , bool> = true>
    constexpr tuple(std::pair<U1, U2>&& p)
        : base(std::get<0>(std::move(p)), std::get<1>(std::move(p))) {}

    constexpr tuple(const tuple&) = default;
    constexpr tuple(tuple&&) = default;

    constexpr tuple& operator=(const tuple& other) = default;
    constexpr tuple& operator=(tuple&& other) = default;

    template <typename... UTypes, std::enable_if_t<
        sizeof...(Types) == sizeof...(UTypes)
        && (... && std::is_assignable_v<Types&, const UTypes&>)
        , bool> = true>
    constexpr tuple& operator=(const tuple<UTypes...>& other)
    {
        __copy_assignment(other, index_sequence_for<Types...> {});
        return *this;
    }

    template <typename... UTypes, std::enable_if_t<
        sizeof...(Types) == sizeof...(UTypes)
        && (... && std::is_assignable_v<Types&, UTypes>)
        , bool> = true>
    constexpr tuple& operator=(tuple<UTypes...>&& other)
    {
        __move_assignment(std::move(other), index_sequence_for<Types...> {});
        return *this;
    }

    template <typename U1, typename U2, std::enable_if_t<
        __helpers::tuple_constraints<Types...>::template
            tuple_pair_copy_assignable<U1, U2>::value
    , bool> = true>
    constexpr tuple& operator=(const std::pair<U1, U2>& p)
    {
        std::get<0>(*this) = p.first;
        std::get<1>(*this) = p.second;
        return *this;
    }

    template <typename U1, typename U2, std::enable_if_t<
        __helpers::tuple_constraints<Types...>::template
            tuple_pair_move_assignable<U1, U2>::value
    , bool> = true>
    constexpr tuple& operator=(std::pair<U1, U2>&& p)
    {
        std::get<0>(*this) = std::forward<U1>(p.first);
        std::get<1>(*this) = std::forward<U2>(p.second);
        return *this;
    }

    constexpr void swap(tuple& other) { std::swap(*this, other); }
};

template <typename... Types>
tuple(Types...) -> tuple<Types...>;

namespace __helpers {

struct ignore_t {
    template <typename T>
    constexpr void operator=(T&&) const noexcept {}
};

template <typename Func, typename Tuple, std::size_t... I>
constexpr auto apply_impl(Func&& func, Tuple&& tpl, std::index_sequence<I...>)
{
    return std::invoke(
        std::forward<Func>(func),
        std::get<I>(std::forward<Tuple>(tpl))...);
}

} // namespace __helpers

inline constexpr __helpers::ignore_t ignore;

template <typename... Types>
constexpr void swap(std::tuple<Types...>& lhs, std::tuple<Types...>& rhs)
    noexcept(noexcept(lhs.swap(rhs)))
{
    lhs.swap(rhs);
}

template <typename... Types>
constexpr auto make_tuple(Types&&... args)
    -> std::tuple<__helpers::to_tuple_type_t<Types>...>
{
    return std::tuple<__helpers::to_tuple_type_t<Types>...>
        { std::forward<Types>(args)... };
}

template <typename... Types>
constexpr std::tuple<Types&...> tie(Types&... args) noexcept
{
    return { args... };
}

template <typename... Types>
constexpr std::tuple<Types&&...> forward_as_tuple(Types&&... args) noexcept
{
    return { std::forward<Types>(args)... };
}

template <typename Func, typename Tuple>
constexpr decltype(auto) apply(Func&& func, Tuple&& tpl)
{
    return __helpers::apply_impl(
        std::forward<Func>(func), std::forward<Tuple>(tpl),
        std::make_index_sequence<
            std::tuple_size_v<std::remove_cvref_t<Tuple>>> {}
    );
}

} // namespace std

#endif