Permutation.hpp

/// Generic helper functions for handling permutations.
/// @a _n Specifies the size of the permutation.
/// @a _getTargetPosition A function that takes an offset as unsigned integer as argument and returns the desired target position
///                       of the element at that offset as integer or -1, if the element is to be discarded.
/// @a _swap Takes a (zero-based) depth as unsigned integer as argument and swaps the currently last element with the
///          element at the given depth.
/// @a _pop Pops the last element.
template<typename GetTargetPosition, typename Swap, typename Pop>
void permute(unsigned _n, GetTargetPosition _getTargetPosition, Swap _swap, Pop _pop)
{
	static_assert(
		std::is_same_v<std::invoke_result_t<GetTargetPosition, unsigned>, int>,
		"_getTargetPosition needs to have the signature int(unsigned)"
	);
	static_assert(
		std::is_same_v<std::invoke_result_t<Swap, unsigned>, void>,
		"_swap needs to have the signature void(unsigned)"
	);
	static_assert(
		std::is_same_v<std::invoke_result_t<Pop>, void>,
		"_pop needs to have the signature void()"
	);
	int targetPositionTop = _getTargetPosition(_n - 1);

	if (targetPositionTop < 0)
	{
		// The last element should not be kept.
		// Pop it and recurse.
		_pop();
		permute(_n - 1, _getTargetPosition, _swap);
		return;
	}
	// TODO: custom exception?
	assertThrow(static_cast<unsigned>(targetPositionTop) < _n, langutil::InternalCompilerError, "Invalid permutation.");
	if (static_cast<unsigned>(targetPositionTop) == _n - 1)
	{
		// The last element is in position.
		// Seach for the deepest element that is not in position.
		// If there is none, we are done. Otherwise swap it up and recurse.
		for (unsigned i = 0; i < _n - 1; ++i)
			if (_getTargetPosition(i) != i)
			{
				_swap(_n - i - 1);
				permute(_n, _getTargetPosition, _swap);
				return;
			}
	}
	else
	{
		// The last element is not in position.
		// Move it to its position and recurse.
		_swap(_n - static_cast<unsigned>(targetPositionTop) - 1);
		permute(_n, _getTargetPosition, _swap);
	}
}