#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 auto operator|(fda_policy l, fda_policy r) noexcept
    -> fda_policy {
	using kblib::etoi;
	return static_cast<fda_policy>(etoi(l) | etoi(r));
}

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

inline namespace comp {}

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

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

	auto operator--() -> f_iterator& {
		--_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;
	}
	[[nodiscard]] auto operator--(int) -> const f_iterator {
		auto tmp = *this;
		operator--();
		return tmp;
	}

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

	[[nodiscard]] friend auto operator==(f_iterator a, f_iterator b) noexcept
	    -> bool {
		return a._p == b._p;
	}
	[[nodiscard]] friend auto operator<(f_iterator a, f_iterator b) noexcept
	    -> bool {
		return a._p < b._p;
	}

	[[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]] auto operator!=(const f_iterator<T1, BI1> a,
	                              const f_iterator<T1, BI1> b) noexcept -> bool {
		return not (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;
	}

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

	template <typename T1, typename BI1>
	[[nodiscard]] bool operator<=(const f_iterator<T1, BI1> a,
	                              const f_iterator<T1, BI1> b) noexcept {
		return not (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>
auto operator<<(std::ostream& os, const info_t<P>& i) -> std::ostream& {
	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); }

	auto get_allocator() const -> allocator_type {
		return backing.get_allocator();
	}

	auto assign(std::initializer_list<el_val> v) -> void {
		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
		    = not (std::holds_alternative<live_type>(*pos)
		           and (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]] auto size() const noexcept -> size_type { return _size; }
	[[nodiscard]] auto capacity() const noexcept -> size_type {
		return backing.capacity();
	}
	[[nodiscard]] auto empty() const noexcept -> size_type {
		return backing.empty();
	}
	[[nodiscard]] auto max_size() const noexcept -> size_type {
		return std::min(backing.max_size(), static_cast<size_type>(npos) - 1);
	}

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

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

	[[nodiscard]] auto operator[](index_type idx) const noexcept(false)
	    -> const_reference {
		// 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;
	}
	[[nodiscard]] auto operator[](index_type idx) noexcept(false) -> reference {
		// 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;
	}

	[[nodiscard]] auto info(index_type idx) noexcept -> info_t<pointer> {
		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};
		}
	}

	[[nodiscard]] auto info(index_type idx) const noexcept
	    -> info_t<const_pointer> {
		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};
		}
	}

	[[nodiscard]] auto get(index_type idx) noexcept -> pointer {
		return info(idx).ptr;
	}

	[[nodiscard]] auto get(index_type idx) const noexcept -> const_pointer {
		return info(idx).ptr;
	}

	[[nodiscard]] auto begin() noexcept -> iterator {
		return iterator{backing.begin() + _first};
	}
	[[nodiscard]] auto end() noexcept -> iterator {
		return iterator{backing.end()};
	}
	[[nodiscard]] auto begin() const noexcept -> const_iterator {
		return const_iterator{backing.begin() + _first};
	}
	[[nodiscard]] auto end() const noexcept -> const_iterator {
		return const_iterator{backing.end()};
	}

	[[nodiscard]] auto rbegin() noexcept -> reverse_iterator {
		return std::make_reverse_iterator(end());
	}
	[[nodiscard]] auto rend() noexcept -> reverse_iterator {
		return std::make_reverse_iterator(begin());
	}
	[[nodiscard]] auto rbegin() const noexcept -> const_reverse_iterator {
		return std::make_reverse_iterator(end());
	}
	[[nodiscard]] auto rend() const noexcept -> const_reverse_iterator {
		return std::make_reverse_iterator(begin());
	}

	[[nodiscard]] auto cbegin() const noexcept -> const_iterator {
		return begin();
	}
	[[nodiscard]] auto cend() const noexcept -> const_iterator { return end(); }
	[[nodiscard]] auto crbegin() const noexcept -> const_reverse_iterator {
		return rbegin();
	}
	[[nodiscard]] auto crend() const noexcept -> const_reverse_iterator {
		return rend();
	}

	// template <typename _T, fda_policy _policy, typename _Alloc>
	friend auto swap(falldown_array<T, policy, Alloc>& a,
	                 falldown_array<T, policy, Alloc>& b) -> void {
		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> {
		constexpr operator F() const noexcept { return f; }

		F f;
	};

	template <bool nothrow>
	static auto adjust_down(typename BC::iterator pos) noexcept(nothrow) ->
	    typename BC::iterator {
		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.
	auto propagate_ref_end(index_type start) noexcept -> void {
		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 and not 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.
	auto propagate_ref_mid(index_type start) noexcept -> void {
		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.
	auto scan_backward_for_last_var(index_type start) const noexcept
	    -> std::pair<difference_type, bool> {
		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 (not 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.
	auto scan_forward_for_next_entry(index_type start) const noexcept
	    -> index_type {
		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.
	auto scan_backward_for_last_entry(index_type start) const noexcept
	    -> index_type {
		// 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;
	}

	auto assert_conditions() noexcept -> void {
		using namespace std::literals;
		std::cerr << "--------\n";
		if (not 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(not 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(not std::holds_alternative<live_type>(backing.back()));
		}
		return; // all good
	}

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

auto c_test_func() -> void;

#endif // FDA_H_INCLUDED