ogdoad 1.0.0

//! The Λ-engine: [`GameExterior`], the exterior algebra of the game group.

use crate::clifford::{bits, CliffordAlgebra, Metric, Multivector};
use crate::games::partizan::Game;
use crate::linalg::integer::reduce_integer_vector;
use crate::scalar::Integer;
use std::collections::{BTreeMap, BTreeSet};

use super::relations::{
    eval_relation, relation_search_certificate, GameRelation, RelationSearchCertificate,
};

pub(super) const DEFAULT_RELATION_BOUND: i128 = 3;
const MAX_AUTO_RELATION_CANDIDATES: usize = 100;

/// The exterior algebra generated by a chosen tuple of games, quotienting the
/// free Grassmann algebra by known integer relations among those games.
///
/// The raw [`algebra`](Self::algebra) is still the free Grassmann engine. The
/// quotient-aware operations ([`reduce`](Self::reduce), [`wedge`](Self::wedge),
/// [`add`](Self::add), [`is_zero`](Self::is_zero)) impose the exterior ideal
/// generated by the stored grade-1 relations, so a relation such as `2⋆ = 0`
/// propagates to `2(⋆∧↑) = 0`.
#[derive(Clone)]
pub struct GameExterior {
    alg: CliffordAlgebra<Integer>,
    gens: Vec<Game>,
    relations: Vec<GameRelation>,
    relation_search_complete: bool,
    relation_certificate: RelationSearchCertificate,
}

impl GameExterior {
    pub fn new(gens: Vec<Game>) -> GameExterior {
        GameExterior::with_relation_search(gens, DEFAULT_RELATION_BOUND)
    }

    /// The free Grassmann algebra on the chosen generators, with no game-group
    /// relations imposed. Useful as the ambient object when explicit quotienting
    /// is not desired.
    pub fn free(gens: Vec<Game>) -> GameExterior {
        GameExterior::with_relations(gens, vec![])
    }

    /// Build the quotient using all bounded discovered relations `Σ c_i g_i = 0`
    /// with coefficients in `[-bound, bound]`, when that finite search is small
    /// enough to run exhaustively. If the coefficient box is too large, automatic
    /// discovery falls back to singleton torsion and
    /// [`relation_search_complete`](Self::relation_search_complete) reports
    /// `false`; use [`with_relations`](Self::with_relations) for known larger
    /// cross-generator relations.
    pub fn with_relation_search(gens: Vec<Game>, bound: i128) -> GameExterior {
        let (relations, complete, candidate_count) = discover_relations(&gens, bound);
        let rel_certificate =
            relation_search_certificate(&gens, bound, complete, candidate_count, &relations, true);
        let mut ext = GameExterior::with_relations(gens, relations);
        ext.relation_search_complete = complete;
        ext.relation_certificate = rel_certificate;
        ext
    }

    /// Build the quotient from explicit integer relations among the supplied
    /// generators. Each relation is verified against the game group before it is
    /// accepted.
    pub fn with_relations(gens: Vec<Game>, relations: Vec<GameRelation>) -> GameExterior {
        let n = gens.len();
        for rel in &relations {
            assert_eq!(
                rel.coeffs.len(),
                n,
                "game relation length must match generator count"
            );
            assert!(
                eval_relation(&gens, &rel.coeffs).eq(&Game::zero()),
                "declared game relation does not evaluate to zero"
            );
        }
        let rel_certificate = relation_search_certificate(&gens, 0, true, None, &relations, false);
        GameExterior {
            alg: CliffordAlgebra::new(n, Metric::grassmann(n)),
            gens,
            relation_certificate: rel_certificate,
            relations,
            relation_search_complete: true,
        }
    }

    /// The underlying free Grassmann algebra. Use the quotient-aware methods on
    /// `GameExterior` when game-group relations should be imposed.
    pub fn algebra(&self) -> &CliffordAlgebra<Integer> {
        &self.alg
    }

    pub fn relations(&self) -> &[GameRelation] {
        &self.relations
    }

    pub fn relation_search_complete(&self) -> bool {
        self.relation_search_complete
    }

    pub fn relation_search_certificate(&self) -> &RelationSearchCertificate {
        &self.relation_certificate
    }

    /// The grade-1 generator `e_i` (corresponding to the game `g_i`).
    pub fn generator(&self, i: usize) -> Multivector<Integer> {
        self.reduce(&self.alg.e(i))
    }

    /// The game `g_i` a generator stands for.
    pub fn game(&self, i: usize) -> &Game {
        &self.gens[i]
    }

    /// The module map `Λ¹ → (game group)`: send a grade-1 element `Σ c_i e_i` to
    /// the game `Σ c_i · g_i`. Defined entirely with the game *group* operations
    /// (sum, negation, integer multiple) and no game product — so it is valid for
    /// non-number generators. Panics if `mv` is not purely grade 1.
    pub fn value_of_grade1(&self, mv: &Multivector<Integer>) -> Game {
        let mut acc = Game::zero();
        let mv = self.reduce(mv);
        for (&blade, coeff) in &mv.terms {
            assert_eq!(
                blade.count_ones(),
                1,
                "value_of_grade1 expects a grade-1 element"
            );
            let i = blade.trailing_zeros() as usize;
            acc = acc.add(&self.gens[i].times_int(coeff.0));
        }
        acc
    }

    pub fn add(&self, a: &Multivector<Integer>, b: &Multivector<Integer>) -> Multivector<Integer> {
        self.reduce(&self.alg.add(a, b))
    }

    pub fn scalar_mul(&self, s: i128, a: &Multivector<Integer>) -> Multivector<Integer> {
        self.reduce(&self.alg.scalar_mul(&Integer(s), a))
    }

    pub fn wedge(
        &self,
        a: &Multivector<Integer>,
        b: &Multivector<Integer>,
    ) -> Multivector<Integer> {
        self.reduce(&self.alg.wedge(a, b))
    }

    pub fn is_zero(&self, mv: &Multivector<Integer>) -> bool {
        self.reduce(mv).is_zero()
    }

    /// Reduce a free Grassmann multivector modulo the exterior ideal generated by
    /// the stored game relations.
    pub fn reduce(&self, mv: &Multivector<Integer>) -> Multivector<Integer> {
        if self.relations.is_empty() || mv.is_zero() {
            return mv.clone();
        }
        let mut out = self.alg.zero();
        let mut by_grade: BTreeMap<usize, BTreeMap<u128, i128>> = BTreeMap::new();
        for (&blade, coeff) in &mv.terms {
            by_grade
                .entry(blade.count_ones() as usize)
                .or_default()
                .insert(blade, coeff.0);
        }
        for (grade, terms) in by_grade {
            let reduced = self.reduce_grade(grade, &terms);
            for (blade, coeff) in reduced {
                if coeff != 0 {
                    out.terms.insert(blade, Integer(coeff));
                }
            }
        }
        out
    }

    fn reduce_grade(&self, grade: usize, terms: &BTreeMap<u128, i128>) -> BTreeMap<u128, i128> {
        if grade == 0 {
            return terms.clone();
        }
        let basis = grade_masks(self.gens.len(), grade);
        if basis.is_empty() {
            return BTreeMap::new();
        }
        let index: BTreeMap<u128, usize> = basis.iter().enumerate().map(|(i, &m)| (m, i)).collect();
        let mut v = vec![0i128; basis.len()];
        for (&blade, &coeff) in terms {
            if let Some(&i) = index.get(&blade) {
                v[i] += coeff;
            }
        }
        let rows = self.relation_rows_for_grade(grade, &basis, &index);
        reduce_integer_vector(&mut v, rows);
        basis.into_iter().zip(v).filter(|&(_, c)| c != 0).collect()
    }

    fn relation_rows_for_grade(
        &self,
        grade: usize,
        basis: &[u128],
        index: &BTreeMap<u128, usize>,
    ) -> Vec<Vec<i128>> {
        let mut rows = Vec::new();
        let lower_basis = grade_masks(self.gens.len(), grade - 1);
        for rel in &self.relations {
            let rel_mv = relation_multivector(rel);
            for mask in &lower_basis {
                let blade = self.alg.blade(&bits(*mask));
                let wedged = self.alg.wedge(&rel_mv, &blade);
                let mut row = vec![0i128; basis.len()];
                for (&b, coeff) in &wedged.terms {
                    if let Some(&i) = index.get(&b) {
                        row[i] += coeff.0;
                    }
                }
                if row.iter().any(|&x| x != 0) {
                    rows.push(row);
                }
            }
        }
        rows
    }
}

pub(super) fn relation_multivector(rel: &GameRelation) -> Multivector<Integer> {
    let mut terms = BTreeMap::new();
    for (i, &coeff) in rel.coeffs.iter().enumerate() {
        if coeff != 0 {
            terms.insert(1u128 << i, Integer(coeff));
        }
    }
    Multivector { terms }
}

fn canonical_relation(mut coeffs: Vec<i128>) -> Option<Vec<i128>> {
    let first = coeffs.iter().position(|&c| c != 0)?;
    if coeffs[first] < 0 {
        for c in &mut coeffs {
            *c = -*c;
        }
    }
    Some(coeffs)
}

pub(super) fn discover_relations(
    gens: &[Game],
    bound: i128,
) -> (Vec<GameRelation>, bool, Option<usize>) {
    if gens.is_empty() || bound <= 0 {
        return (Vec::new(), true, Some(0));
    }
    let n = gens.len();
    let mut seen = BTreeSet::new();
    let mut out = Vec::new();

    for i in 0..n {
        for c in 1..=bound {
            let mut coeffs = vec![0i128; n];
            coeffs[i] = c;
            if push_relation_if_independent(gens, coeffs, &mut seen, &mut out) {
                break;
            }
        }
    }

    let Some(count) = bounded_relation_candidate_count(n, bound) else {
        return (out, false, None);
    };
    if count > MAX_AUTO_RELATION_CANDIDATES {
        return (out, false, Some(count));
    }

    let mut candidates = Vec::new();
    enumerate_bounded_relations(n, bound, &mut |coeffs| {
        if let Some(key) = canonical_relation(coeffs) {
            candidates.push(key);
        }
    });
    candidates.sort_by_key(|v| (v.iter().map(|c| c.abs()).sum::<i128>(), v.clone()));
    for coeffs in candidates {
        push_relation_if_independent(gens, coeffs, &mut seen, &mut out);
    }
    (out, true, Some(count))
}

fn bounded_relation_candidate_count(n: usize, bound: i128) -> Option<usize> {
    let width = usize::try_from(bound.checked_mul(2)?.checked_add(1)?).ok()?;
    let mut count = 1usize;
    for _ in 0..n {
        count = count.checked_mul(width)?;
    }
    count.checked_sub(1)
}

fn enumerate_bounded_relations(n: usize, bound: i128, f: &mut impl FnMut(Vec<i128>)) {
    fn rec(i: usize, n: usize, bound: i128, coeffs: &mut [i128], f: &mut impl FnMut(Vec<i128>)) {
        if i == n {
            if coeffs.iter().any(|&c| c != 0) {
                f(coeffs.to_vec());
            }
            return;
        }
        for c in -bound..=bound {
            coeffs[i] = c;
            rec(i + 1, n, bound, coeffs, f);
        }
    }
    let mut coeffs = vec![0i128; n];
    rec(0, n, bound, &mut coeffs, f);
}

fn push_relation_if_independent(
    gens: &[Game],
    coeffs: Vec<i128>,
    seen: &mut BTreeSet<Vec<i128>>,
    out: &mut Vec<GameRelation>,
) -> bool {
    let Some(key) = canonical_relation(coeffs) else {
        return false;
    };
    if !seen.insert(key.clone()) {
        return false;
    }
    if !eval_relation(gens, &key).eq(&Game::zero()) {
        return false;
    }
    let mut reduced = key.clone();
    let rows: Vec<Vec<i128>> = out.iter().map(|r| r.coeffs.clone()).collect();
    reduce_integer_vector(&mut reduced, rows);
    if reduced.iter().all(|&c| c == 0) {
        return false;
    }
    out.push(GameRelation::new(key));
    true
}

pub(super) fn grade_masks(n: usize, grade: usize) -> Vec<u128> {
    if grade > n {
        return Vec::new();
    }
    fn rec(n: usize, grade: usize, start: usize, mask: u128, out: &mut Vec<u128>) {
        if grade == 0 {
            out.push(mask);
            return;
        }
        for i in start..=n - grade {
            rec(n, grade - 1, i + 1, mask | (1u128 << i), out);
        }
    }
    let mut out = Vec::new();
    rec(n, grade, 0, 0, &mut out);
    out
}