//! # Discrete Groups
//!
//! This module provides implementations for common finite groups, such as
//! cyclic groups (C_n), dihedral groups (D_n), and symmetric groups (S_n).
//! It includes functions to construct these groups and define their multiplication tables.
use crate::symbolic::core::Expr;
use crate::symbolic::group_theory::{Group, GroupElement};
use std::collections::HashMap;
/// Creates a cyclic group `C_n` of order `n`.
///
/// The cyclic group is generated by a single element 'g' such that `g^n = e` (the identity).
/// The elements are `{e, g, g^2, ..., g^(n-1)}`. Multiplication is equivalent to addition
/// of exponents modulo `n`.
///
/// # Arguments
/// * `n` - The order of the cyclic group.
///
/// # Returns
/// A `Group` struct representing `C_n`.
pub fn cyclic_group(n: usize) -> Group {
    let elements: Vec<_> = (0..n)
        .map(|i| {
            if i == 0 {
                GroupElement(Expr::Variable("e".to_string()))
            } else {
                GroupElement(Expr::new_pow(
                    Expr::Variable("g".to_string()),
                    Expr::Variable(i.to_string()),
                ))
            }
        })
        .collect();
    let mut multiplication_table = HashMap::new();
    for i in 0..n {
        for j in 0..n {
            let result_idx = (i + j) % n;
            multiplication_table.insert(
                (elements[i].clone(), elements[j].clone()),
                elements[result_idx].clone(),
            );
        }
    }
    Group::new(elements.clone(), multiplication_table, elements[0].clone())
}
/// Creates a dihedral group `D_n` of order `2n`.
///
/// `D_n` is the group of symmetries of a regular n-gon. It consists of `n` rotations
/// (`r^0, ..., r^(n-1)`) and `n` reflections (`s, sr, ..., sr^(n-1)`).
/// The group is defined by the relations: `r^n = e`, `s^2 = e`, and `s*r = r^(-1)*s`.
///
/// # Arguments
/// * `n` - The number of vertices of the regular polygon.
///
/// # Returns
/// A `Group` struct representing `D_n`.
#[allow(clippy::cast_possible_wrap)]
pub fn dihedral_group(n: usize) -> Group {
    let mut elements = Vec::with_capacity(2 * n);
    let rotations: Vec<_> = (0..n)
        .map(|i| GroupElement(Expr::Variable(format!("r{}", i))))
        .collect();
    let reflections: Vec<_> = (0..n)
        .map(|i| GroupElement(Expr::Variable(format!("s{}", i))))
        .collect();
    elements.extend(rotations.clone());
    elements.extend(reflections.clone());
    let mut multiplication_table = HashMap::new();
    for i in 0..n {
        for j in 0..n {
            let res_idx = (i + j) % n;
            multiplication_table.insert(
                (rotations[i].clone(), rotations[j].clone()),
                rotations[res_idx].clone(),
            );
            let res_idx = (j as isize - i as isize).rem_euclid(n as isize) as usize;
            multiplication_table.insert(
                (rotations[i].clone(), reflections[j].clone()),
                reflections[res_idx].clone(),
            );
            let res_idx = (i + j) % n;
            multiplication_table.insert(
                (reflections[i].clone(), rotations[j].clone()),
                reflections[res_idx].clone(),
            );
            let res_idx = (i as isize - j as isize).rem_euclid(n as isize) as usize;
            multiplication_table.insert(
                (reflections[i].clone(), reflections[j].clone()),
                rotations[res_idx].clone(),
            );
        }
    }
    Group::new(elements.clone(), multiplication_table, rotations[0].clone())
}
/// Helper function to generate all permutations for S_n.
pub(crate) fn generate_permutations(n: usize) -> Vec<Vec<usize>> {
    if n == 0 {
        return vec![vec![]];
    }
    let mut result = Vec::new();
    let mut p: Vec<usize> = (0..n).collect();
    let mut c: Vec<usize> = vec![0; n];
    result.push(p.clone());
    let mut i = 1;
    while i < n {
        if c[i] < i {
            if i % 2 == 0 {
                p.swap(0, i);
            } else {
                p.swap(c[i], i);
            }
            result.push(p.clone());
            c[i] += 1;
            i = 1;
        } else {
            c[i] = 0;
            i += 1;
        }
    }
    result
}
/// Composes two permutations.
/// Permutation multiplication is function composition from right to left.
/// For p1 = [1, 2, 0] and p2 = [0, 2, 1], (p1*p2)(0) = p1(p2(0)) = p1(0) = 1.
pub(crate) fn compose_permutations(p1: &[usize], p2: &[usize]) -> Vec<usize> {
    p2.iter().map(|&x| p1[x]).collect()
}
/// Creates a symmetric group `S_n` of order `n!`.
///
/// `S_n` is the group of all permutations of `n` elements. The elements are
/// represented as permutations (e.g., `[1, 2, 0]` for `(0->1, 1->2, 2->0)`).
/// Multiplication is the composition of permutations.
///
/// # Arguments
/// * `n` - The number of elements to permute.
///
/// # Returns
/// A `Group` struct representing `S_n`.
pub fn symmetric_group(n: usize) -> Result<Group, String> {
    let perms_as_indices = generate_permutations(n);
    let elements: Vec<_> = perms_as_indices
        .iter()
        .map(|p| {
            let expr_vec = p.iter().map(|&i| Expr::Variable(i.to_string())).collect();
            GroupElement(Expr::Vector(expr_vec))
        })
        .collect();
    let mut multiplication_table = HashMap::new();
    for (i, p1_indices) in perms_as_indices.iter().enumerate() {
        for (j, p2_indices) in perms_as_indices.iter().enumerate() {
            let result_indices = compose_permutations(p1_indices, p2_indices);
            let result_idx = match perms_as_indices.iter().position(|p| p == &result_indices) {
                Some(idx) => idx,
                None => {
                    return Err("Composed permutation not found in the group elements.".to_string());
                }
            };
            multiplication_table.insert(
                (elements[i].clone(), elements[j].clone()),
                elements[result_idx].clone(),
            );
        }
    }
    let identity_element = match elements.iter().find(|el| {
        if let GroupElement(Expr::Vector(v)) = el {
            v.iter().enumerate().all(|(idx, val)| {
                if let Expr::Variable(s) = val {
                    s.parse::<usize>().unwrap_or(n + 1) == idx
                } else {
                    false
                }
            })
        } else {
            false
        }
    }) {
        Some(el) => el.clone(),
        None => {
            return Err("Identity element not found in the symmetric group.".to_string());
        }
    };
    Ok(Group::new(elements, multiplication_table, identity_element))
}
