#pragma once 

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

namespace magic {

namespace _ {

template <typename Iter>
struct iter_table_t {
	static constexpr auto destroy() 
	requires (std::is_destructible_v<Iter>)
	{
		return +[](Iter*p){delete p;};
	}
	
	static constexpr auto copy() 
	requires (std::is_copy_constructible_v<Iter>)
	{
		return +[](Iter const*p){return new Iter(*p);};
	}

	static constexpr auto eq() 
	requires (std::equality_comparable<Iter>)
	{
		return +[](Iter const*p, Iter const*q){return *p == *q;};
	}

	static constexpr auto lt()
	requires requires (Iter const& l, Iter const& r){{l<r}->std::same_as<bool>;}
	{
		return +[](Iter const*p, Iter const*q){return *p < *q;};
	}

	static constexpr auto gt()
	requires requires (Iter const& l, Iter const& r){{l>r}->std::same_as<bool>;}
	{
		 return +[](Iter const*p, Iter const*q){return *p > *q;};
	}

	static constexpr auto deref()
	requires requires (Iter const& i){*i;}
	{
		return +[](Iter const*p)->decltype(auto){return **p;};
	}

	static constexpr auto incr()
	requires requires (Iter& i){++i;}
	{
		return +[](Iter*p) {++*p;};
	}

	static constexpr auto decr()
	requires requires (Iter& i){--i;}
	{
		return +[](Iter*p) {--*p;};
	}

	static constexpr auto dist() 
	requires requires (Iter const& a, Iter const& b) {a-b;}
	{
		return +[](Iter const*p,Iter const*q){return *p-*q;};
	}

	static constexpr auto adv()
	requires requires (Iter& it, decltype(it-it) n){it += n;}
	{
		return +[](Iter*p, decltype(*p-*p) n){*p += n;};
	}
};

struct iter_capability_t {
	template <typename Iter>
	constexpr static iter_capability_t create() {
		using table = iter_table_t<Iter>;
		/*
		iter_capability_t capability {
			.destroy = requires(){{table::destroy};},
			.copy    = requires(){{table::copy   };},
			.eq      = requires(){{table::eq     };},
			.lt      = requires(){{table::lt     };},
			.gt      = requires(){{table::gt     };},
			.deref   = requires(){{table::deref  };},
			.incr    = requires(){{table::incr   };},
			.decr    = requires(){{table::decr   };},
			.dist    = requires(){{table::dist   };},
			.adv     = requires(){{table::adv    };},
		};
		*/
		iter_capability_t capability {};
		if constexpr (requires {table::destroy();})	
			capability.destroy = true;
		if constexpr (requires {table::copy();})	
			capability.copy = true;
		if constexpr (requires {table::eq();})	
			capability.eq = true;
		if constexpr (requires {table::lt();})	
			capability.lt = true;
		if constexpr (requires {table::gt();})	
			capability.gt = true;
		if constexpr (requires {table::deref();})	
			capability.deref = true;
		if constexpr (requires {table::incr();})	
			capability.incr = true;
		if constexpr (requires {table::decr();})	
			capability.decr = true;
		if constexpr (requires {table::dist();})	
			capability.dist = true;
		if constexpr (requires {table::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;

	constexpr bool contained_in(iter_capability_t const& rhs) const noexcept {
		return (destroy <= rhs.destroy)
			&& (copy    <= rhs.copy   )
			&& (eq      <= rhs.eq     )
			&& (lt      <= rhs.lt     )
			&& (gt      <= rhs.gt     )
			&& (deref   <= rhs.deref  )
			&& (incr    <= rhs.incr   )
			&& (decr    <= rhs.decr   )
			&& (dist    <= rhs.dist   )
			&& (adv     <= rhs.adv    );
	}
};

template <iter_capability_t Cap>
struct iter_destroy {
	virtual ~iter_destroy() = default;
	template <typename Iter> struct model{};
};
template <iter_capability_t Cap> requires (Cap.destroy)
struct iter_destroy<Cap> {
	virtual ~iter_destroy() = default;
	virtual void destroy(void*) const = 0;
	template <typename Iter> struct model;
};

template <iter_capability_t Cap> requires (Cap.destroy)
template <typename Iter> struct iter_destroy<Cap>::model: virtual iter_destroy {
	void destroy(void* ptr) const override {
		iter_table_t<Iter>::destroy()(static_cast<Iter*>(ptr));
	}
};

template <iter_capability_t Cap>
struct iter_copy {
	virtual ~iter_copy() = default;
	template <typename Iter> struct model{};
};
template <iter_capability_t Cap> requires (Cap.copy)
struct iter_copy<Cap> {
	virtual ~iter_copy() = default;
	virtual void* copy(void const*) const = 0;
	template <typename Iter> struct model;
};

template <iter_capability_t Cap> requires (Cap.copy)
template <typename Iter> struct iter_copy<Cap>::model: virtual iter_copy {
	void* copy(void const* ptr) const override {
		return iter_table_t<Iter>::copy()(static_cast<Iter const*>(ptr));
	}
};

template <iter_capability_t Cap>
struct iter_eq {
	virtual ~iter_eq() = default;
	template <typename Iter> struct model{};
};
template <iter_capability_t Cap> requires (Cap.eq)
struct iter_eq<Cap> {
	virtual ~iter_eq() = default;
	virtual bool eq(void const*, void const*) const = 0;
	template <typename Iter> struct model;
};

template <iter_capability_t Cap> requires (Cap.eq)
template <typename Iter> struct iter_eq<Cap>::model: virtual iter_eq {
	bool eq(void const*p,void const*q) const override {
		return iter_table_t<Iter>::eq()(
			static_cast<Iter const*>(p),
			static_cast<Iter const*>(q)
		);
	}
};

template <iter_capability_t Cap>
struct iter_lt {
	virtual ~iter_lt() = default;
	template <typename Iter> struct model{};
};
template <iter_capability_t Cap> requires (Cap.lt)
struct iter_lt<Cap> {
	virtual ~iter_lt() = default;
	virtual bool lt(void const*, void const*) const = 0;
	template <typename Iter> struct model;
};

template <iter_capability_t Cap> requires (Cap.lt)
template <typename Iter> struct iter_lt<Cap>::model: virtual iter_lt {
	bool lt(void const*p,void const*q) const override {
		return iter_table_t<Iter>::lt()(
			static_cast<Iter const*>(p),
			static_cast<Iter const*>(q)
		);
	}
};

template <iter_capability_t Cap>
struct iter_gt {
	virtual ~iter_gt() = default;
	template <typename Iter> struct model{};
};
template <iter_capability_t Cap> requires (Cap.gt)
struct iter_gt<Cap> {
	virtual ~iter_gt() = default;
	virtual bool gt(void const*, void const*) const = 0;
	template <typename Iter> struct model;
};

template <iter_capability_t Cap> requires (Cap.gt)
template <typename Iter> struct iter_gt<Cap>::model: virtual iter_gt {
	bool gt(void const*p,void const*q) const override {
		return iter_table_t<Iter>::gt()(
			static_cast<Iter const*>(p),
			static_cast<Iter const*>(q)
		);
	}
};

template <typename Reference, iter_capability_t Cap>
struct iter_deref {
	virtual ~iter_deref() = default;
	template <typename Iter> struct model{};};
template <typename Reference, iter_capability_t Cap> requires (Cap.deref)
struct iter_deref<Reference, Cap> {
	virtual ~iter_deref() = default;
	virtual Reference& deref(void const*) const = 0;
	template <typename Iter> struct model;
};

template <typename Reference, iter_capability_t Cap> requires (Cap.deref)
template <typename Iter> 
struct iter_deref<Reference, Cap>::model: virtual iter_deref {
	Reference& deref(void const* p) const override {
		return iter_table_t<Iter>::deref()(static_cast<Iter const*>(p));
	}
};

template <iter_capability_t Cap>
struct iter_incr {
	virtual ~iter_incr() = default;
	template <typename Iter> struct model{};
};
template <iter_capability_t Cap> requires (Cap.incr)
struct iter_incr<Cap> {
	virtual ~iter_incr() = default;
	virtual void incr(void*) const = 0;
	template <typename Iter> struct model;
};

template <iter_capability_t Cap> requires (Cap.incr)
template <typename Iter> struct iter_incr<Cap>::model: virtual iter_incr {
	void incr(void* p) const override {
		iter_table_t<Iter>::incr()(static_cast<Iter*>(p));
	}
};

template <iter_capability_t Cap>
struct iter_decr{
	virtual ~iter_decr() = default;
	template <typename Iter> struct model{};
};
template <iter_capability_t Cap> requires (Cap.decr)
struct iter_decr<Cap> {
	virtual ~iter_decr() = default;
	virtual void decr(void*) const = 0;
	template <typename Iter> struct model;
};

template <iter_capability_t Cap> requires (Cap.decr)
template <typename Iter> struct iter_decr<Cap>::model: virtual iter_decr {
	void decr(void* p) const override {
		iter_table_t<Iter>::decr()(static_cast<Iter*>(p));
	}
};

template <typename Diff, iter_capability_t Cap>
struct iter_dist{
	virtual ~iter_dist() = default;
	template <typename Iter> struct model{};
};
template <typename Diff, iter_capability_t Cap> requires (Cap.dist)
struct iter_dist<Diff, Cap> {
	virtual ~iter_dist() = default;
	virtual Diff dist(void const*, void const*) const = 0;
	template <typename Iter> struct model;
};

template <typename Diff, iter_capability_t Cap> requires (Cap.dist)
template <typename Iter> struct iter_dist<Diff, Cap>::model:virtual iter_dist{
	Diff dist(void const*p, void const*q) const override {
		return iter_table_t<Iter>::dist()(
			static_cast<Iter const*>(p),
			static_cast<Iter const*>(q)
		);
	}
};


template <typename Diff, iter_capability_t Cap>
struct iter_adv{
	virtual ~iter_adv() = default;
	template <typename Iter> struct model{};};
template <typename Diff, iter_capability_t Cap> requires (Cap.adv)
struct iter_adv<Diff, Cap> {
	virtual ~iter_adv() = default;
	virtual void adv(void*, Diff) const = 0;
	template <typename Iter> struct model;
};

template <typename Diff, iter_capability_t Cap> requires (Cap.adv)
template <typename Iter> struct iter_adv<Diff, Cap>::model: virtual iter_adv {
	void adv(void*p, Diff n) const override {
		return iter_table_t<Iter>::adv()(static_cast<Iter*>(p), n);
	}
};

template <typename Value, typename Ref, typename Diff, iter_capability_t Cap>
struct iter_vtable_t
	: virtual iter_destroy<Cap>
	, virtual iter_copy<Cap>
	, virtual iter_eq<Cap>
	, virtual iter_gt<Cap>
	, virtual iter_lt<Cap>
	, virtual iter_deref<Ref, Cap>
	, virtual iter_incr<Cap>
	, virtual iter_decr<Cap>
	, virtual iter_dist<Diff, Cap>
	, virtual iter_adv<Diff, Cap>
{
	virtual ~iter_vtable_t() = default;
	template <typename Iter> struct model;
};

template <typename Value, typename Ref, typename Diff, iter_capability_t Cap>
template <typename Iter>
struct iter_vtable_t<Value, Ref, Diff, Cap>::model 
	: iter_vtable_t 
	, virtual iter_destroy<Cap>::template model<Iter>
	, virtual iter_copy<Cap>::template model<Iter>
	, virtual iter_eq<Cap>::template model<Iter>
	, virtual iter_gt<Cap>::template model<Iter>
	, virtual iter_lt<Cap>::template model<Iter>
	, virtual iter_deref<Ref, Cap>::template model<Iter>
	, virtual iter_incr<Cap>::template model<Iter>
	, virtual iter_decr<Cap>::template model<Iter>
	, virtual iter_dist<Diff, Cap>::template model<Iter>
	, virtual iter_adv<Diff, Cap>::template model<Iter>
{
	;	
};

} // namespace _

template <
	typename Value, 
	_::iter_capability_t caps = _::iter_capability_t::create<
		std::unordered_set<int>::iterator
	>(),
	typename Reference = Value&,
	typename Diff = std::ptrdiff_t
> class iterator {
	static constexpr auto capability = caps;
	using vtable_t = _::iter_vtable_t<Value, Reference, Diff, caps>;
	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 (caps.destroy) {
			if (vt) vt->destroy(obj);
		}
		vt = nullptr;
		obj = nullptr;
	}

	public:
	template <typename Iter>
	static vtable_t const& get_model() {
	    static typename vtable_t::template model<Iter> const instance{}; 
	    return dynamic_cast<vtable_t const&>(instance);
	}	

	template <typename Iter>
	requires (not std::same_as<iterator, std::remove_cvref_t<Iter>>)
	iterator(Iter&& iter) {
		vt = &get_model<Iter>(); 
		obj = vt->copy(&iter);
	}

	~iterator() {reset();}
	iterator() = default;
	iterator(iterator const& iter) requires (caps.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 (caps.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 (caps.incr) {
		vt->incr(obj);
		return *this;
	}

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

	Reference operator*() requires (caps.deref) {
		return vt->deref(obj);
	}

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

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

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

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

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

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

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

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

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

	Reference operator[](Diff n) const 
	requires (caps.adv && caps.deref && caps.copy) {
		iterator copy = *this;
		return *(copy += n);
	}

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

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

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

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

template <typename Iter>
constexpr _::iter_capability_t capabilities = 
	_::iter_capability_t::create<Iter>();

}