permoot 0.2.1

use crate::error::InvalidArrFnRepr;
use crate::reprs::FunctionCompositionOrder;
use crate::sign::PermutationSign;
use crate::util::range_array;
use crate::Permutation;

/// [Group Structure](https://en.wikipedia.org/wiki/Symmetric_group)
impl<const N: usize> Permutation<N> {
	/// The identity permutation that doesn't reorder anything (leaves everything unchanged)
	pub fn identity() -> Self {
		Self {
			arr_repr: range_array(),
		}
	}

	/// Check if the permutation is equal to the [identity](Self::identity)
	pub fn is_identity(&self) -> bool {
		self.arr_repr.iter().enumerate().all(|(i, x)| *x == i)
	}

	/// Compute the permutation that is equivalent to first applying `self` and then `rhs`
	pub fn compose(self, rhs: Self) -> Self {
		let f1 = self.as_fn();
		let f2 = rhs.as_fn();

		Self::from_fn(move |i| f1(f2(i))).expect("composed permutation is valid")
	}

	/// Compute the permutation that reverts the changes made by `self`
	pub fn inverse(self) -> Self {
		let mut arr: [_; N] = core::array::from_fn(|i| (i, self.arr_repr[i]));

		// stability doesn't matter because there are no equal elements
		arr.sort_unstable_by_key(|tup| tup.1);

		Self {
			arr_repr: arr.map(|tup| tup.0),
		}
	}
}

/// Misc. Math
impl<const N: usize> Permutation<N> {
	/// The permutation corresponding to [`slice::rotate_left(n)`](https://doc.rust-lang.org/std/primitive.slice.html#method.rotate_left)
	pub fn rotate_left(n: usize) -> Self {
		let mut arr_repr = range_array();
		arr_repr.rotate_left(n);
		Self { arr_repr }
	}

	/// The permutation corresponding to [`slice::rotate_right(n)`](https://doc.rust-lang.org/std/primitive.slice.html#method.rotate_right)
	pub fn rotate_right(n: usize) -> Self {
		let mut arr_repr = range_array();
		arr_repr.rotate_right(n);
		Self { arr_repr }
	}

	/// Computes the `M` such that `self` only changes the first `M` elements and leaves the rest alone
	pub fn min_subperm_len(&self) -> usize {
		self.arr_repr
			.iter()
			.enumerate()
			.rposition(|(i, x)| *x != i)
			.map_or(0, |x| x + 1)
	}

	/// Constructs a permutation that changes the first `M` elements according to `sub` and leaves the rest alone
	///
	/// # Panics
	/// - if `M > N`
	pub fn from_subperm<const M: usize>(sub: Permutation<M>) -> Self {
		if M > N {
			panic!("Permutation::from_subperm called with permutation of more objects");
		} else {
			let mut arr_repr = range_array();
			arr_repr[..M].copy_from_slice(&sub.arr_repr[..]);
			Self { arr_repr }
		}
	}

	/// Constructs a permutation from its function representation
	///
	/// The function representation is basically the same as the array representation:
	/// The equivalence is `arr[i] == f(i)`.
	pub fn from_fn<F: FnMut(usize) -> usize>(f: F) -> Result<Self, InvalidArrFnRepr> {
		let arr_repr = core::array::from_fn(f);

		Self::from_array_repr(arr_repr)
	}

	/// Converts a permutation to its function representation, borrowing from `self`
	pub fn as_fn(&self) -> impl Fn(usize) -> usize + '_ {
		|i| self.arr_repr.get(i).copied().unwrap_or(i)
	}

	/// Converts a permutation to its function representation, moving `self`
	pub fn to_fn(self) -> impl Fn(usize) -> usize + 'static {
		move |i| self.arr_repr.get(i).copied().unwrap_or(i)
	}

	/// Applies the reordering given by `self` to `array`
	pub fn apply<T>(&self, array: [T; N]) -> [T; N] {
		let mut opts = array.map(Some);

		core::array::from_fn(|i| {
			let j = self.arr_repr[i];
			opts[j].take().unwrap_or_else(|| unreachable!())
		})
	}

	/// Applies the permutation `self` to the first `N` elements of `slice`
	///
	/// See also [`Swaps::apply_in_place`](crate::reprs::Swaps::apply_in_place)
	///
	/// # Panics
	/// - if `slice.len() > self.min_subperm_len()`
	pub fn apply_in_place<T>(&self, slice: &mut [T]) {
		self.to_swaps_repr()
			.into_equivalent_with_order::<FunctionCompositionOrder>()
			.apply_in_place(slice);
	}

	/// Computes the permutation sign
	pub fn sign(&self) -> PermutationSign {
		let num_swaps = self.to_swaps_repr().len();
		match num_swaps % 2 {
			0 => PermutationSign::Positive,
			1 => PermutationSign::Negative,
			_ => unreachable!(),
		}
	}

	/// Checks if the permutation is even, i.e. if the sign is positive
	pub fn is_even(&self) -> bool {
		self.sign().is_positive()
	}

	/// Checks if the permutation is odd, i.e. if the sign is negative
	pub fn is_odd(&self) -> bool {
		self.sign().is_negative()
	}
}

#[cfg(test)]
mod tests {
	use crate::sign::PermutationSign;
	use crate::util::{range_array, with_random_perms};
	use crate::Permutation;

	#[test]
	fn compose() {
		with_random_perms::<100>(10, |p1| {
			with_random_perms::<100>(10, |p2| {
				let pc = p1.compose(p2);

				let pfc = {
					let pf1 = p1.as_fn();
					let pf2 = p2.as_fn();
					move |i| pf1(pf2(i))
				};
				let pcf = pc.as_fn();

				for i in 0..100 {
					assert_eq!(pfc(i), pcf(i));
				}

				let arr = range_array();

				let tmp = p1.apply(arr);
				let r1 = p2.apply(tmp);

				let r2 = pc.apply(arr);
				assert_eq!(r1, r2);
			})
		})
	}

	#[test]
	fn inverse() {
		with_random_perms::<100>(100, |p| {
			let pi = p.inverse();

			assert!(pi.compose(p).is_identity());
			assert!(p.compose(pi).is_identity());
			assert_eq!(pi.inverse(), p);
		})
	}

	#[test]
	fn apply() {
		with_random_perms::<100>(100, |p| {
			let arr = range_array();

			assert_eq!(p.apply(arr), p.arr_repr);

			let mut arr_inplace = arr;
			p.apply_in_place(&mut arr_inplace);
			assert_eq!(arr_inplace, p.arr_repr);

			let arr2 = range_array::<200>();
			let mut arr2_inplace = arr2;
			p.apply_in_place(&mut arr2_inplace[..100]);
			assert_eq!(arr2_inplace[..100], p.arr_repr[..]);
			assert_eq!(arr2_inplace[100..], arr2[100..]);
		})
	}

	#[test]
	fn sign() {
		// baka test
		assert_eq!(
			Permutation::<10>::identity().sign(),
			PermutationSign::Positive
		);

		let p1 = Permutation::from_array_repr([2, 1, 0]).unwrap();
		assert_eq!(p1.sign(), PermutationSign::Negative);

		let p2 = Permutation::from_array_repr([4, 3, 1, 2, 0]).unwrap();
		assert_eq!(p2.sign(), PermutationSign::Negative);
	}
}