#pragma once 

#include <type_traits>
#include <unordered_set>
#include <concepts>

struct iter_capability_t {
	template <typename Iter>
	constexpr static iter_capability_t create() {
		constexpr bool lt = requires(Iter const& l, Iter const& r) {
			{l < r} -> std::same_as<bool>;
		};
		constexpr bool gt = requires(Iter const& l, Iter const& r) {
			{l > r} -> std::same_as<bool>;
		};
		constexpr bool deref = requires(Iter const& it) {
			*it;
		};
		constexpr bool incr = requires(Iter& it) {
			++it;
		};
		constexpr bool decr = requires(Iter& it) {
			--it;
		};
		constexpr bool dist = requires(Iter const& l, Iter const& r) {
			l - r;
		};
		constexpr bool adv = dist and requires(Iter& it, decltype(it-it) n) {
			it += n;
		};

		iter_capability_t capability {};
		if constexpr (std::is_destructible_v<Iter>)	
			capability.destroy = true;
		if constexpr (std::is_copy_constructible_v<Iter>)	
			capability.copy = true;
		if constexpr (std::equality_comparable<Iter>)
			capability.eq = true;
		if constexpr (lt)	
			capability.lt = true;
		if constexpr (gt)	
			capability.gt = true;
		if constexpr (deref)	
			capability.deref = true;
		if constexpr (incr)	
			capability.incr = true;
		if constexpr (decr)	
			capability.decr = true;
		if constexpr (dist)	
			capability.dist = true;
		if constexpr (adv)	
			capability.adv = true;
		return capability;
	}

	bool destroy = false;
	bool copy    = false;
	bool eq      = false;
	bool lt      = false;
	bool gt      = false;
	bool deref   = false;
	bool incr    = false;
	bool decr    = false;
	bool dist    = false;
	bool adv     = false;
};

namespace _ {
template <auto A, auto B>
struct weaker_than;
}

template <iter_capability_t A, iter_capability_t B>
struct _::weaker_than<B, A> {
	static constexpr bool value = 
		A.destroy <= B.destroy &&
		A.copy    <= B.copy    &&
		A.eq      <= B.eq      &&
		A.lt      <= B.lt      &&
		A.gt      <= B.gt      &&
		A.deref   <= B.deref   &&
		A.incr    <= B.incr    &&
		A.decr    <= B.decr    &&
		A.dist    <= B.dist    &&
		A.adv     <= B.adv;
};

template <auto A, auto B>
concept weaker_than = _::weaker_than<A,B>::value;

template <typename Ref, typename Diff, iter_capability_t capability>
class iter_vtable_t {
	bool (*_eq)     (void const*, void const*) = nullptr;
	bool (*_lt)     (void const*, void const*) = nullptr;
	bool (*_gt)     (void const*, void const*) = nullptr;
	Diff (*_dist)   (void const*, void const*) = nullptr;
	Ref& (*_deref)  (void const*)              = nullptr;
	void*(*_copy)   (void const*)              = nullptr;
	void (*_adv)    (void*, Diff)              = nullptr;
	void (*_incr)   (void*)                    = nullptr;
	void (*_decr)   (void*)                    = nullptr;
	void (*_destroy)(void*)                    = nullptr;

	public:
	void destroy(void* p) const 
	requires (capability.destroy) { _destroy(p); }

	void* copy(void const* p) const
	requires (capability.copy) {return _copy(p);}

	bool eq(void const* p, void const* q) const
	requires (capability.eq) {return _eq(p, q);}

	bool lt(void const* p, void const* q) const
	requires (capability.lt) {return _lt(p,q);}

	bool gt(void const* p, void const* q) const
	requires (capability.gt) {return _gt(p,q);}

	Ref& deref(void const* p) const
	requires (capability.deref) {return _deref(p);}

	void incr(void* p) const
	requires (capability.incr) {_incr(p);}

	void decr(void* p) const
	requires (capability.decr) {_decr(p);}

	Diff dist(void const* p, void const* q) const
	requires (capability.dist) {return _dist(p,q);}

	void adv(void* p, Diff n) const
	requires (capability.adv) {_adv(p,n);}

	template <typename>
	friend constexpr auto vtable_for();
	
	template <typename, typename, iter_capability_t>
	friend class iter_vtable_t;

	constexpr iter_vtable_t() = default;

	template <iter_capability_t Stronger> 
	requires (weaker_than<Stronger, capability>)
	iter_vtable_t(iter_vtable_t<Ref, Diff, Stronger> const& stronger) {
		_destroy = stronger._destroy;
		_eq      = stronger._eq;
	    _lt      = stronger._lt;
   		_gt      = stronger._gt;
   		_dist    = stronger._dist;
   		_deref   = stronger._deref;
    	_copy    = stronger._copy;
    	_adv     = stronger._adv;
    	_incr    = stronger._incr;
    	_decr    = stronger._decr;
	}
};

template <typename Iter>
constexpr auto vtable_for() {
	using Ref  = std::iter_reference_t<Iter>;
	using Diff = std::iter_difference_t<Iter>;
	constexpr auto capability = iter_capability_t::create<Iter>();
	iter_vtable_t<Ref, Diff, capability> table {};

	if constexpr (capability.destroy)
		table._destroy = +[](void* ptr){
			delete static_cast<Iter*>(ptr);
		};
	if constexpr (capability.copy)
		table._copy = +[](void const* ptr) -> void* {
			return new Iter(*static_cast<Iter const*>(ptr));
		};
	if constexpr (capability.eq)
		table._eq = +[](void const* L, void const* R) -> bool {
			return *static_cast<Iter const*>(L) 
				== *static_cast<Iter const*>(R);	
		};
	if constexpr (capability.lt)
		table._lt = +[](void const* L, void const* R) -> bool {
			return *static_cast<Iter const*>(L) 
				<  *static_cast<Iter const*>(R);	
		};	
	if constexpr (capability.gt)
		table._gt = +[](void const* L, void const* R) -> bool {
			return *static_cast<Iter const*>(L) 
				>  *static_cast<Iter const*>(R);	
		};	
	if constexpr (capability.deref)
		table._deref = +[](void const* ptr) -> decltype(auto) {
			return **static_cast<Iter const*>(ptr);
		};
	if constexpr (capability.incr)
		table._incr = +[](void* ptr) {
			++*static_cast<Iter*>(ptr);
		};
	if constexpr (capability.decr)
		table._decr = +[](void* ptr){
			--*static_cast<Iter*>(ptr);
		};
	if constexpr (capability.dist)
		table._dist = +[](void const* L, void const* R) -> Diff {
			return *static_cast<Iter const*>(L)
				-  *static_cast<Iter const*>(R);
		};
	if constexpr (capability.adv)
		table._adv = +[](void* ptr, Diff n){
			*static_cast<Iter*>(ptr) += n;
		};
	return table;
}

template <typename Iter>
constexpr auto iter_capability = iter_capability_t::create<Iter>();

template <
	typename Value, 
	iter_capability_t _capability = iter_capability<
		std::unordered_set<int>::iterator
	>, 
	typename Reference = Value&, 
	typename Difference = std::ptrdiff_t
> class iterator {
	public:
	static constexpr auto capability = _capability;
	using value_type      = Value;
	using reference_type  = Reference;
	using difference_type = Difference;
	using vtable_t        = iter_vtable_t<Reference, Difference, capability>;
	
	private:
	vtable_t const* vt  = nullptr;
	void          * obj = nullptr;
	
	void swap_with(iterator& iter) noexcept {
		std::swap(vt,  iter.vt);
		std::swap(obj, iter.obj);
	}
	
	void reset() {
		if constexpr (capability.destroy) if (vt) vt->destroy(obj);
		vt  = nullptr;
		obj = nullptr;
	}

	public:
	~iterator() { reset(); }
	iterator() = default;

	template <typename Iter>
	requires (
		not std::same_as<iterator, std::remove_cvref_t<Iter>>
		and weaker_than<iter_capability<Iter>, capability>
	)
	iterator (Iter&& iter) {
		// forces conversion
		static vtable_t vtable{vtable_for<Iter>()};
		vt  = &vtable;
		// because iterators constructed from different types of 
		// concrete iterators are never "the same", it's okay if 
		// the pointers actually differ. 
		obj =  vt->copy(new Iter(std::forward<Iter>(iter)));	
	}

	iterator(iterator const& iter) requires (capability.copy) {
		vt  = iter.vt;
		obj = vt->copy(iter.obj);
	}

	iterator(iterator&& iter) noexcept {
		vt  = iter.vt;
		obj = iter.obj;
		iter.vt  = nullptr;
		iter.obj = nullptr;
	}

	iterator& operator=(iterator const& other) 
	requires (capability.copy) {
		if (this == &other) return *this;
		iterator copy {other};
		swap_with(copy);
		return *this;
	}

	iterator& operator=(iterator&& other) noexcept {
		if (this == &other) return *this;
		iterator empty;
		swap_with(other);
		other.swap_with(empty);
		return *this;
	}

	iterator& operator++() 
	requires (capability.incr) {
		vt->incr(obj);
		return *this;
	}

	iterator operator++(int)
	requires (capability.incr && capability.copy) {
		iterator copy;
		vt->incr(obj);
		return copy;
	} 

	reference_type operator*() 
	requires (capability.deref) {
		return vt->deref(obj);
	}

	iterator& operator--() 
	requires (capability.decr) {
		vt->decr(obj);
		return *this;
	}
	
	iterator operator--(int) 
	requires (capability.decr && capability.copy) {
		iterator copy;
		vt->decr(obj);
		return copy;
	}

	bool operator<(iterator const& rhs) const 
	requires (capability.lt) {
		return vt == rhs.vt && vt->lt(obj, rhs.obj);
	}

	bool operator<=(iterator const& rhs) const 
	requires (capability.lt && capability.eq) {
		return (vt == rhs.vt)
			&& (vt->eq(obj, rhs.obj) || vt->lt(obj, rhs.obj));
	}

	bool operator>(iterator const& rhs) const 
	requires (capability.gt) {
		return vt == rhs.vt && vt->gt(obj, rhs.obj);
	}

	bool operator>=(iterator const& rhs) const 
	requires (capability.gt && capability.eq) {
		return (vt == rhs.vt) 
			&& (vt->eq(obj, rhs.obj) || vt->lg(obj, rhs.obj));
	}

	bool operator==(iterator const& rhs) const 
	requires (capability.eq) {
		return vt == rhs.vt && vt->eq(obj, rhs.obj);
	}
	
	bool operator!=(iterator const& rhs) const 
	requires (capability.eq) {
		return !(*this==rhs);
	}

	difference_type operator-(iterator const& rhs) const 
	requires (capability.dist) {
		if (vt != rhs.vt) throw;
		return vt->dist(obj, rhs.obj); 
	}

	iterator& operator+=(difference_type n) 
	requires (capability.adv) {
		vt->adv(obj, n);
		return *this;
	}

	iterator operator-=(difference_type n) 
	requires (capability.adv) {
		vt->adv(obj, -n);
		return *this;
	}

	reference_type operator[](difference_type n) const 
	requires (capability.adv && capability.deref && capability.copy) {
		iterator copy = *this;
		return *(copy += n);
	}

	friend iterator operator+(iterator const& iter, difference_type n) 
	requires(capability.adv && capability.copy) {
		iterator copy = iter;
		copy += n;
		return copy;
	}

	friend iterator operator+(difference_type n, iterator const& iter) 
	requires(capability.adv && capability.copy) {
		iterator copy = iter;
		copy += n;
		return copy;
	}

	friend iterator operator-(iterator const& iter, difference_type n) 
	requires(capability.adv && capability.copy) {
		iterator copy = iter;
		copy -= n;
		return copy;
	}

	friend iterator operator-(difference_type n, iterator const& iter) 
	requires(capability.adv && capability.copy) {
		iterator copy = iter;
		copy -= n;
		return copy;
	}
};