fda.h

#ifndef FDA_H_INCLUDED
#define FDA_H_INCLUDED

#include "kblib/kblib.h"

#include <iterator>
#include <optional>
#include <type_traits>
#include <utility>
#include <variant>
#include <vector>

#include <iostream>

namespace wg_containers {

/*
class falldown_array & helpers.

Purpose: falldown_array implements the particular overloading
   strategy used for template-node-names in WordGen/cpp2. In
   that system, a node has a declared number of arguments, and
   can also be variadic, which means it will accept any number
   of extra arguments. Overload resolution proceeds as follows:
   - Given a reference to node N with K arguments:
   - If a node N_K exists (which has exactly K arguments,
     variadically or not), select that node.
   - Otherwise:
     - If not NV_Shadow_V: Search for any node N_vJ, where J is the
       largest positive number less than K where a variadic node
       is found. Return N_vJ if it exists.
     - If NV_Shadow_V: Search for any node N_J, where J is the
       largest positive number less than K where a node is found,
       even if it is not variadic.
       - If N_J is variadic, the search is successful, and N_J is
         returned.
       - Else, the search is unsuccessful.
   - On failure, either null is returned or an exception is
     thrown, depending on the interface used.

   Insertion requires an index and a boolean. Lookup uses only
   the index. This assymmetry, as well as the lookup strategy,
   which can find a non-exact match, mean that this container is
   not strictly a sequence or associative container.

Note: falldown_array satisfies ReversibleContainer and
   AllocatorAwareContainer, but not SequenceContainer or
   AssociativeContainer. If the DenyIteration policy is set,
   falldown_array does not satisfy Container at all, but most
   of the interface still works, and there (should) be marginal
   gains in efficiency.

Policy rationale: There are two policies that can be specified
   orthogonally; both default to false.
   DenyIteration: disables the iterator part of the interface, and
      removes all unnecessary bookkeeping data. In theory, this
      improves performance, but I have not tested for that.
   NV_Shadow_V: stands for "nonvariadic shadows variadic". If set,
      the container implements the mathematically simpler lookup
      strategy of always checking the closest element to the
      requested index in the downward direction, and it will fail
      to look up if that node is non-variadic, ignoring anything
      further down. This means that there is less bookkeeping to
      do on insertion, and should speed it up slightly. Again,
      this performance claim is untested.

Complexity:
   Insertion: Worst-case linear in size of container.
   Lookup: Constant.
   Iteration: Increment and decrement are constant time.

*/

template <typename T, bool SaveNext>
class el_impl {
 public:
    T val;
    bool variadic;
    std::ptrdiff_t next;
};
template <typename T>
class el_impl<T, false> {
 public:
    template <typename Ti>
    el_impl(Ti&& v, bool var, [[maybe_unused]] std::ptrdiff_t _)
        : val(std::forward(v)), variadic(var) {}
    T val;
    bool variadic;
};

struct tombstone_t {
    // The tombstone is not templated because this bookkeeping
    //   information does not increase the size of the container.
    // Distance to the last element, for iteration.
    std::ptrdiff_t dist{};
};

// using backref_t = std::ptrdiff_t;
struct backref_t {
    std::ptrdiff_t dist_var;
    std::ptrdiff_t dist_nvar;
};

template <typename T, bool I>
using element = std::variant<tombstone_t, el_impl<T, I>, backref_t>;

enum class fda_policy : unsigned {
    Default = 0,
    NV_Shadow_V = 1,
    DenyIteration = 2,
};

[[nodiscard]] constexpr fda_policy operator|(fda_policy l,
                                             fda_policy r) noexcept {
    using kblib::etoi;
    return static_cast<fda_policy>(etoi(l) | etoi(r));
}

[[nodiscard]] constexpr fda_policy operator&(fda_policy l,
                                             fda_policy r) noexcept {
    using kblib::etoi;
    return static_cast<fda_policy>(etoi(l) & etoi(r));
}

template <typename T, typename BI>
class f_iterator {
 private:
    using live_type = el_impl<std::remove_const_t<T>, true>;

 public:
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using pointer = T*;
    using reference = T&;
    using iterator_category = std::bidirectional_iterator_tag;

    f_iterator() = default;
    explicit f_iterator(BI p) noexcept : _p(p) {}

    [[nodiscard]] reference operator*() { return std::get<live_type>(*_p).val; }
    [[nodiscard]] pointer operator->() { return &std::get<live_type>(*_p).val; }

    f_iterator& operator++() {
        _p += std::get<live_type>(*_p).next;
        return *this;
    }
    const f_iterator operator++(int) {
        auto tmp = *this;
        operator++();
        return tmp;
    }

    f_iterator& operator--() {
        --_p;
        _p -= kblib::visit2(
            *_p, [](tombstone_t t) { return t.dist; },
            [](const live_type&) { return 0; },
            [](backref_t d) { return d.dist_nvar; });
        return *this;
    }
    const f_iterator operator--(int) {
        auto tmp = *this;
        operator--();
        return tmp;
    }

    template <typename T1, typename BI1>
    friend void swap(f_iterator& a, f_iterator& b) noexcept {
        std::swap(a._p, b._p);
    }

    template <typename T1, typename BI1>
    friend bool operator==(f_iterator<T1, BI1> a,
                           f_iterator<T1, BI1> b) noexcept;
    template <typename T1, typename BI1>
    friend bool operator<(f_iterator<T1, BI1> a, f_iterator<T1, BI1> b) noexcept;

    [[nodiscard]] auto get() const noexcept {
        return &static_cast<const std::decay_t<decltype(*_p)>&>(*_p);
    }

 private:
    template <typename T1, fda_policy policy, typename Alloc>
    friend class falldown_array;
    BI _p;
};

inline namespace comp {

    template <typename T1, typename BI1>
    [[nodiscard]] bool operator==(const f_iterator<T1, BI1> a,
                                  const f_iterator<T1, BI1> b) noexcept {
        return a._p == b._p;
    }

    template <typename T1, typename BI1>
    [[nodiscard]] bool operator!=(const f_iterator<T1, BI1> a,
                                  const f_iterator<T1, BI1> b) noexcept {
        return !(a == b);
    }

    template <typename T1, typename BI1>
    [[nodiscard]] bool operator<(const f_iterator<T1, BI1> a,
                                 const f_iterator<T1, BI1> b) noexcept {
        return a._p < b._p;
    }

    template <typename T1, typename BI1>
    [[nodiscard]] bool operator>(const f_iterator<T1, BI1> a,
                                 const f_iterator<T1, BI1> b) noexcept {
        return b < a;
    }

    template <typename T1, typename BI1>
    [[nodiscard]] bool operator>=(const f_iterator<T1, BI1> a,
                                  const f_iterator<T1, BI1> b) noexcept {
        return !(a < b);
    }

    template <typename T1, typename BI1>
    [[nodiscard]] bool operator<=(const f_iterator<T1, BI1> a,
                                  const f_iterator<T1, BI1> b) noexcept {
        return !(b < a);
    }

} // namespace comp

template <typename P>
struct info_t {
    P ptr;
    std::ptrdiff_t idx;
    bool variadic;
    operator bool() const noexcept { return ptr; }
};
template <typename P>
std::ostream& operator<<(std::ostream& os, const info_t<P>& i) {
    return os << "{ptr: " << i.ptr << ", idx: " << i.idx
              << ", variadic: " << i.variadic << "}";
}

template <typename T, fda_policy policy = fda_policy::Default,
          typename Alloc = void>
class falldown_array {
    constexpr static bool AllowIteration =
        (policy & fda_policy::DenyIteration) != fda_policy::DenyIteration;
    constexpr static bool DoShadow =
        (policy & fda_policy::NV_Shadow_V) == fda_policy::NV_Shadow_V;

 public:
    /* Boilerplate stuff */
    using size_type = std::size_t;
    using index_type = std::ptrdiff_t;
    using difference_type = index_type;

    static_assert(
        std::is_same_v<T, std::remove_reference_t<std::remove_cv_t<T>>>);
    using value_type = T;
    using reference = value_type&;
    using const_reference = const T&;

 private:
    using pointer = T*;
    using const_pointer = const T*;

    using element_type = element<value_type, AllowIteration>;
    using live_type = el_impl<value_type, AllowIteration>;

 public:
    using allocator_type =
        std::conditional_t<std::is_void_v<Alloc>, std::allocator<element_type>,
                           Alloc>;

 private:
    using BC = std::vector<element_type, allocator_type>;

 public:
    static constexpr index_type npos =
        std::numeric_limits<difference_type>::max() / 2;

    using iterator =
        std::conditional_t<AllowIteration,
                           f_iterator<value_type, typename BC::iterator>, void>;
    using const_iterator = std::conditional_t<
        AllowIteration,
        f_iterator<const value_type, typename BC::const_iterator>, void>;

    using reverse_iterator =
        std::conditional_t<AllowIteration, std::reverse_iterator<iterator>,
                           void>;
    using const_reverse_iterator =
        std::conditional_t<AllowIteration, std::reverse_iterator<const_iterator>,
                           void>;

    falldown_array() = default;
    falldown_array(const falldown_array&) = default;
    falldown_array(falldown_array&&) noexcept = default;

    struct el_val {
        index_type idx;
        bool var;
        T val;
    };
    falldown_array(std::initializer_list<el_val> v) : falldown_array() {
        assign(v);
    }

    falldown_array& operator=(const falldown_array&) = default;
    falldown_array& operator=(falldown_array&&) noexcept = default;
    falldown_array& operator=(std::initializer_list<el_val> v) { assign(v); }

    allocator_type get_allocator() const { return backing.get_allocator(); }

    void assign(std::initializer_list<el_val> v) {
        clear();
        for (auto& e : v) {
            set(e.idx, e.var, e.val);
        }
    }
    auto set(index_type idx, bool variadic, const_reference val) noexcept(
        std::is_nothrow_copy_constructible_v<value_type>) {
        return emplace(idx, variadic, val);
    }

    template <typename... Args>
    auto emplace(index_type idx, bool variadic, Args&&... args) noexcept(
        std::is_nothrow_constructible_v<value_type, Args...>) {
        assert_conditions();
        // the offset is 2 because backing is required to hold one additional
        // element after the last live_type
        if (idx > static_cast<difference_type>(backing.size()) - 2) {
            const auto start_adjusting =
                static_cast<index_type>(backing.size()) - 1;
            backing.resize(idx + 2);
            if (start_adjusting >= 0) {
                propagate_ref_end(start_adjusting);
            }
            assert_conditions();
        }

        const typename BC::iterator pos = backing.begin() + idx;
        bool need_adjust = !(std::holds_alternative<live_type>(*pos) &&
                             (std::get<live_type>(*pos).variadic == variadic));

        if (need_adjust) {
            *pos =
                live_type{value_type(std::forward<Args...>(args...)), variadic, 0};
            propagate_ref_mid(idx);
        } else {
            std::get<live_type>(*pos).val =
                value_type(std::forward<Args...>(args...));
        }

        _first = std::min(_first, idx);
        _size = std::count_if(backing.begin() + _first, backing.end(),
                              [](const element_type& e) {
                                  return std::holds_alternative<live_type>(e);
                              });

        assert_conditions();

        if constexpr (AllowIteration) {
            return iterator{pos};
        } else {
            return;
        }
    }

    [[nodiscard]] size_type size() const noexcept { return _size; }
    [[nodiscard]] size_type capacity() const noexcept {
        return backing.capacity();
    }
    [[nodiscard]] size_type empty() const noexcept { return backing.empty(); }
    [[nodiscard]] size_type max_size() const noexcept {
        return std::min(backing.max_size(), static_cast<size_type>(npos) - 1);
    }

    void reserve(size_type s) { backing.reserve(s); }
    void shrink_to_fit() { backing.shrink_to_fit(); }

    void clear() noexcept {
        backing = {{tombstone_t{}}};
        _first = npos;
        _size = 0;
    }

    const_reference operator[](index_type idx) const noexcept(false) {
        // throws std::out_of_range on hitting tombstone
        const auto pos = adjust_down<false>(
            backing.begin() +
            std::min(idx, static_cast<index_type>(backing.size()) - 1));
        return std::get<live_type>(*pos).val;
    }
    reference operator[](index_type idx) noexcept(false) {
        // throws std::out_of_range on hitting tombstone
        const auto pos = adjust_down<false>(
            backing.begin() +
            std::min(idx, static_cast<index_type>(backing.size()) - 1));
        return std::get<live_type>(*pos).val;
    }

    info_t<pointer> info(index_type idx) noexcept {
        const auto pos = adjust_down<true>(
            backing.begin() +
            std::min(idx, static_cast<index_type>(backing.size()) - 1));
        if (auto p = std::get_if<live_type>(&*pos)) {
            return {&p->val, pos - backing.begin(), p->variadic};
        } else {
            return {nullptr, pos - backing.begin(), false};
        }
    }

    info_t<const_pointer> info(index_type idx) const noexcept {
        const auto pos = adjust_down<true>(
            backing.begin() +
            std::min(idx, static_cast<index_type>(backing.size()) - 1));
        if (auto p = std::get_if<live_type>(&*pos)) {
            return {&p->val, pos - backing.begin(), p->variadic};
        } else {
            return {nullptr, pos - backing.begin(), false};
        }
    }

    pointer get(index_type idx) noexcept { return info(idx).ptr; }

    const_pointer get(index_type idx) const noexcept { return info(idx).ptr; }

    iterator begin() noexcept { return iterator{backing.begin() + _first}; }
    iterator end() noexcept { return iterator{backing.end()}; }
    const_iterator begin() const noexcept {
        return iterator{backing.begin() + _first};
    }
    const_iterator end() const noexcept { return iterator{backing.end()}; }

    reverse_iterator rbegin() noexcept {
        return std::make_reverse_iterator(iterator{backing.end()});
    }
    reverse_iterator rend() noexcept {
        return std::make_reverse_iterator(iterator{backing.begin() + _first});
    }
    const_reverse_iterator rbegin() const noexcept {
        return std::make_reverse_iterator(iterator{backing.end()});
    }
    const_reverse_iterator rend() const noexcept {
        return std::make_reverse_iterator(iterator{backing.begin() + _first});
    }

    const_iterator cbegin() const noexcept {
        return const_iterator{backing.begin() + _first};
    }
    const_iterator cend() const noexcept {
        return const_iterator{backing.end()};
    }
    const_reverse_iterator crbegin() const noexcept {
        return std::make_reverse_iterator(const_iterator{backing.end()});
    }
    const_reverse_iterator crend() const noexcept {
        return std::make_reverse_iterator(
            const_iterator{backing.begin() + _first});
    }

    // template <typename _T, fda_policy _policy, typename _Alloc>
    friend void swap(falldown_array<T, policy, Alloc>& a,
                     falldown_array<T, policy, Alloc>& b) {
        using std::swap;
        swap(a.backing, b.backing);
        swap(a._first, b._first);
        swap(a._size, b._size);
    }

    ~falldown_array() = default;

 private:
    // Perform a lookup.
    // In constant time, jump to the controlling element for the given index.
    // If there is no such element, or if said element is nonvariadic, then:
    // if nothrow: return the argument unchanged.
    // else: throw std::out_of_range.

    template <typename F>
    struct extract_arg_from;
    template <typename R, typename Arg>
    struct extract_arg_from<R (*)(Arg)> {
        using type = Arg;
    };
    template <typename F>
    struct extract_ret_from;
    template <typename R, typename Arg>
    struct extract_ret_from<R (*)(Arg)> {
        using type = R;
    };

    template <typename... Fs>
    struct Funs : Funs<Fs>... {};
    template <typename F>
    struct Funs<F> {
        using arg = typename extract_arg_from<F>::type;
        using ret = typename extract_ret_from<F>::type;
        ret operator()(arg a) { return f(a); }
        F f;
    };

    template <bool nothrow>
    static typename BC::iterator
    adjust_down(typename BC::iterator pos) noexcept(nothrow) {
        static_assert(std::is_invocable_v<Funs<void (*)(int)>, int>);
        static_assert(kblib::detail::v_invocable_with_all_v<
                      Funs<void (*)(tombstone_t), void (*)(live_type),
                           void (*)(backref_t)>,
                      element_type>);
        return kblib::visit2(
            *pos,
            [&](tombstone_t) -> typename BC::iterator {
                if constexpr (nothrow) {
                    return pos;
                } else {
                    throw std::out_of_range("");
                }
            },
            [&](live_type&) { return pos; },
            [&](backref_t d) { return pos - d.dist_var; });
    }

    // Starting from the previous live value, adjusts all back- and
    // forward-references until it reaches the start position.
    void propagate_ref_end(index_type start) noexcept {
        const auto start_pos = backing.begin() + start;
        const auto end = backing.end();
        auto [count, variadic] = scan_backward_for_last_var(start + 1);
        auto dist_nvar = scan_backward_for_last_entry(start + 1);
        for (auto it = start_pos + 1;
             it != end && !std::holds_alternative<live_type>(*it); ++it) {
            if (variadic) {
                *it = backref_t{count, dist_nvar};
            } else {
                *it = tombstone_t{count};
            }
            ++count;
            ++dist_nvar;
        }
    }
    // Repairs the structure of the falldown_array after a middle-insert. This
    // entails scanning forward to set backreferences, and backward to set next
    // indices.
    void propagate_ref_mid(index_type start) noexcept {
        const typename BC::iterator pos = backing.begin() + start;

        assert(start >= 0 and kblib::to_unsigned(start) < backing.size());
        assert(std::holds_alternative<live_type>(*pos));
        auto& reference = std::get<live_type>(*pos);

        propagate_ref_end(start);
        if constexpr (AllowIteration) {
            reference.next = scan_forward_for_next_entry(start + 1) - start;
            if (reference.next + start == kblib::to_signed(backing.size())) {
                reference.next = npos;
            }
            auto last = scan_backward_for_last_entry(start - 1);
            if (last != start) {
                std::get<live_type>(backing[last]).next = (start - last);
            }
        }

        return;
    }

    // Perform a partial relative backward lookup:
    // If DoShadow, find the nearest live element and return the distance as well
    // as if it is variadic. Else, find the nearest variadic live element and
    // return the distance and true. Else, if there is no nearest variadic live
    // element, return the distance to the nearest nonvariadic live element, and
    // false. Else, the search reached the beginning. Return the distance to the
    // beginning, and false.
    std::pair<difference_type, bool>
    scan_backward_for_last_var(index_type start) const noexcept {
        const typename BC::const_iterator pos = backing.begin() + start,
                                          begin = backing.begin();
        std::optional<difference_type> nvar_pos;
        if (pos != begin) {
            auto it = pos - 1;
            difference_type steps = 0;
            do {
                ++steps;
                if (auto p = std::get_if<live_type>(&*it)) {
                    if constexpr (DoShadow) {
                        return {steps, p->variadic};
                    } else {
                        if (p->variadic) {
                            return {steps, true};
                        } else if (!nvar_pos) {
                            nvar_pos.emplace(steps);
                        }
                    }
                } else if (auto p = std::get_if<backref_t>(&*it)) {
                    return {steps + p->dist_var, true};
                } else if (auto p = std::get_if<tombstone_t>(&*it)) {
                    if (nvar_pos) {
                        return {*nvar_pos, false};
                    }
                    return {steps + p->dist, false};
                }
            } while (--it != begin);
            if (nvar_pos) {
                return {*nvar_pos, false};
            }
            return {start, false};
        } else {
            return {0, false};
        }
    }
    // Return the index of the next live value, starting at start.
    index_type scan_forward_for_next_entry(index_type start) const noexcept {
        return kblib::find_in_if(backing.begin() + start, backing.end(),
                                 [](const element_type& el) {
                                     return std::holds_alternative<live_type>(el);
                                 }) +
               start;
    }
    // Return the index of the previous live value, starting at start.
    index_type scan_backward_for_last_entry(index_type start) const noexcept {
        // Naive search:
        return kblib::find_last_in_if(
            backing.begin(), backing.begin() + start + 1,
            [](const element_type& el) {
                return std::holds_alternative<live_type>(el);
            });

        // Assumes all preconditions are valid:
        // const typename BC::const_iterator
        // begin = backing.begin();
        // typename BC::const_iterator
        // pos = begin+start;
        // for (index_type steps{}; pos != begin; ++steps,--pos) {
        // if (std::holds_alternative<live_type>(*pos)) {
        // return steps;
        // } else if (auto p = std::get_if<backref_t>(&*pos)) {
        // return steps + p->dist_var;
        // } else if (auto p = std::get_if<tombstone_t>(&*pos)) {
        // return steps + p->dist;
        // }
        // }
        // return start;
    }

    void assert_conditions() noexcept {
        using namespace std::literals;
        std::cerr << "--------\n";
        if (!backing.empty()) {
            {
                bool var{false};
                index_type counter{};
                index_type toNext{_first};
                [[maybe_unused]] index_type idx = 0;
                for (const auto& el : backing) {
                    std::cerr << idx++ << " b: -" << counter << " n: " << toNext
                              << " v: " << var << " | ";
                    kblib::visit2(
                        el,
                        [&](tombstone_t) {
                            std::cerr << "X\n";
                            assert(!var);
                        },
                        [&](const live_type& e) {
                            std::cerr << '[' << e.val << ','
                                      << (e.variadic ? 'T' : 'F');
                            if constexpr (AllowIteration) {
                                std::cerr << ',' << e.next;
                            }
                            std::cerr << "]\n";
                            if constexpr (DoShadow) {
                                var = e.variadic;
                                counter = 0;
                            } else {
                                if (e.variadic) {
                                    var = true;
                                    counter = 0;
                                }
                            }
                            assert(toNext == 0);
                            toNext = e.next;
                        },
                        [&](backref_t b) {
                            std::cerr << "b -" << b.dist_var << '\n';
                            assert(b.dist_var == counter);
                            assert(var);
                        });
                    --toNext;
                    ++counter;
                }
            }
            assert(!std::holds_alternative<live_type>(backing.back()));
        }
        return; // all good
    }

    BC backing{tombstone_t{}};
    index_type _first{npos};
    size_type _size{};
};
} // namespace wg_containers

void c_test_func();

#endif // FDA_H_INCLUDED