#pragma once

#include <psemek/util/range.hpp>

#include <cstddef>
#include <type_traits>
#include <limits>
#include <array>
#include <algorithm>
#include <numeric>

namespace psemek::group
{

	template <std::size_t N, typename Repr = std::size_t>
	struct permutation
	{
		static_assert(std::is_integral_v<Repr> && std::is_unsigned_v<Repr>);
		static_assert(std::numeric_limits<Repr>::max() > N);

		using repr_type = std::array<Repr, N>;

		static constexpr std::size_t size()
		{
			return N;
		}

		permutation() = default;

		static permutation identity()
		{
			return permutation{};
		}

		static permutation from_repr(repr_type const & value)
		{
			return permutation{value};
		}

		repr_type const & value() const
		{
			return repr_;
		}

		repr_type operator() (repr_type const & value) const
		{
			repr_type result;
			for (Repr i = 0; i < N; ++i)
				result[repr_[i]] = value[i];
			return result;
		}

		struct value_iterator
		{
			using difference_type = Repr;
			using value_type = permutation<N, Repr>;
			using pointer = value_type *;
			using reference	= value_type &;
			using iterator_category = std::forward_iterator_tag;

			repr_type repr;
			bool end;

			permutation<N, Repr> operator *() const
			{
				return permutation<N, Repr>{repr};
			}

			value_iterator & operator++()
			{
				end = std::next_permutation(repr.begin(), repr.end());
				return *this;
			}

			friend bool operator == (value_iterator const & it1, value_iterator const & it2)
			{
				return it1.repr == it2.repr && it1.end == it2.end;
			}
		};

		static auto values()
		{
			repr_type repr;
			std::iota(repr.begin(), repr.end(), Repr{0});
			return util::range{value_iterator{repr, false}, value_iterator{repr, true}};
		}

	private:
		repr_type repr_{0};

		explicit permutation(repr_type const & repr)
			: repr_(repr)
		{}
	};

	template <std::size_t N, typename Repr>
	bool operator == (permutation<N, Repr> const & g1, permutation<N, Repr> const & g2)
	{
		return g1.value() == g2.value();
	}

	template <std::size_t N, typename Repr>
	auto operator <=> (permutation<N, Repr> const & g1, permutation<N, Repr> const & g2)
	{
		return g1.value() <=> g2.value();
	}

	template <std::size_t N, typename Repr>
	permutation<N, Repr> operator * (permutation<N, Repr> const & g1, permutation<N, Repr> const & g2)
	{
		typename permutation<N, Repr>::repr_type repr;
		for (Repr i = 0; i < N; ++i)
			repr[i] = g1.value()[g2.value()[i]];
		return permutation<N, Repr>::from_repr(repr);
	}

	template <std::size_t N, typename Repr>
	permutation<N, Repr> inverse(permutation<N, Repr> const & g)
	{
		typename permutation<N, Repr>::repr_type repr;
		for (Repr i = 0; i < N; ++i)
			repr[g.value()[i]] = i;
		return permutation<N, Repr>::from_repr(repr);
	}

	template <typename OStream, std::size_t N, typename Repr>
	OStream & operator << (OStream & os, permutation<N, Repr> const & g)
	{
		os << 'S' << N << '(';
		for (Repr i = 0; i < N; ++i)
		{
			if (i > 0)
				os << ", ";
			os << g.value()[i];
		}
		os << ')';
		return os;
	}

	template <typename OStream, std::size_t N, typename Repr>
	void write(OStream & out, permutation<N, Repr> const & g)
	{
		write(out, g.value());
	}

	template <typename IStream, std::size_t N, typename Repr>
	void read(IStream & in, permutation<N, Repr> & g)
	{
		typename permutation<N, Repr>::repr_type value;
		read(in, value);
		g = permutation<N, Repr>::from_repr(value);
	}

}
