neberu 0.0.0

// ============================================================
// WORD — FREE MONOID OVER GEN
// ============================================================
//
// A Word is a sequence of typed generators: Magma<Gen>.
// The empty word is the multiplicative identity (scalar position).
// Concatenation is the free product.
//
// The type information from Gen flows into every Word.
// A Word knows the type of each generator it contains.
// Grade = word length. A grade-k blade is a k-generator word.

use crate::gen::Gen;

/// A word in the free monoid over Gen: a sequence of typed generators.
/// The empty word is the scalar (grade 0).
#[derive(Clone, PartialEq, Eq, Hash)]
pub struct Word {
    gens: Vec<Gen>,
}

impl Word {
    /// The empty word — scalar, grade 0, multiplicative identity.
    pub fn scalar() -> Word {
        Word { gens: vec![] }
    }

    /// A single-generator word.
    pub fn gen(g: Gen) -> Word {
        Word { gens: vec![g] }
    }

    /// Construct from a slice of generators.
    pub fn from_gens(gens: &[Gen]) -> Word {
        Word {
            gens: gens.to_vec(),
        }
    }

    /// Free product: concatenation.
    pub fn mul(&self, other: &Word) -> Word {
        let mut gens = self.gens.clone();
        gens.extend_from_slice(&other.gens);
        Word { gens }
    }

    /// Is this the scalar (empty word)?
    pub fn is_scalar(&self) -> bool {
        self.gens.is_empty()
    }

    /// Grade = number of generators.
    pub fn grade(&self) -> usize {
        self.gens.len()
    }

    /// Access generators.
    pub fn generators(&self) -> &[Gen] {
        &self.gens
    }

    /// First generator.
    pub fn head(&self) -> Option<Gen> {
        self.gens.first().copied()
    }

    /// Last generator.
    pub fn last(&self) -> Option<Gen> {
        self.gens.last().copied()
    }

    /// Does this word contain a given subword? Returns the start position if so.
    pub fn find_subword(&self, sub: &Word) -> Option<usize> {
        if sub.gens.is_empty() {
            return Some(0);
        }
        self.gens
            .windows(sub.gens.len())
            .position(|w| w == sub.gens.as_slice())
    }

    /// Is this word sorted by Gen ordering?
    pub fn is_sorted(&self) -> bool {
        self.gens.windows(2).all(|w| w[0] <= w[1])
    }

    /// The reverse of this word, with the sign factor (-1)^(k*(k-1)/2).
    pub fn reverse_sign(&self) -> (Word, bool) {
        let k = self.grade();
        let sign_flip = (k * k.wrapping_sub(1) / 2) % 2 == 1;
        let rev: Vec<Gen> = self.gens.iter().rev().copied().collect();
        (Word { gens: rev }, sign_flip)
    }
}

impl PartialOrd for Word {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Word {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        // Grade-first (shorter words before longer), then lexicographic.
        self.gens
            .len()
            .cmp(&other.gens.len())
            .then_with(|| self.gens.cmp(&other.gens))
    }
}

impl std::fmt::Debug for Word {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.gens.is_empty() {
            write!(f, "1")
        } else {
            let parts: Vec<String> = self.gens.iter().map(|g| format!("{g}")).collect();
            write!(f, "{}", parts.join("·"))
        }
    }
}

impl std::fmt::Display for Word {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}", self)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::trit::{N, P};

    fn ei(idx: u32) -> Gen {
        Gen::imaginary(idx)
    }
    fn eh(idx: u32) -> Gen {
        Gen::hyperbolic(idx)
    }

    #[test]
    fn scalar_is_grade0() {
        let s = Word::scalar();
        assert!(s.is_scalar());
        assert_eq!(s.grade(), 0);
    }

    #[test]
    fn single_gen_grade1() {
        let w = Word::gen(ei(0));
        assert_eq!(w.grade(), 1);
        assert_eq!(w.generators(), &[ei(0)]);
    }

    #[test]
    fn free_product_concatenates() {
        let e1 = Word::gen(ei(0));
        let e2 = Word::gen(ei(1));
        let e1e2 = e1.mul(&e2);
        assert_eq!(e1e2.grade(), 2);
        assert_eq!(e1e2.generators(), &[ei(0), ei(1)]);
    }

    #[test]
    fn scalar_is_identity() {
        let e1 = Word::gen(ei(0));
        let s = Word::scalar();
        assert_eq!(e1.mul(&s), e1);
        assert_eq!(s.mul(&e1), e1);
    }

    #[test]
    fn find_subword() {
        let w = Word::from_gens(&[ei(0), ei(1), ei(2)]);
        let sub = Word::from_gens(&[ei(1), ei(2)]);
        assert_eq!(w.find_subword(&sub), Some(1));
        assert_eq!(w.find_subword(&Word::gen(ei(3))), None);
    }

    #[test]
    fn grade_ordering() {
        let e1 = Word::gen(ei(0));
        let e2 = Word::gen(ei(1));
        let e1e2 = e1.mul(&e2);
        assert!(e1 < e1e2); // grade 1 < grade 2
        assert!(e2 < e1e2);
    }

    #[test]
    fn type_flows_into_word() {
        // A word knows the type of each generator.
        let w = Word::from_gens(&[ei(0), Gen::degenerate(0), eh(0)]);
        assert_eq!(w.generators()[0].signature(), N);
        assert_eq!(w.generators()[1].signature(), crate::trit::Z);
        assert_eq!(w.generators()[2].signature(), P);
    }
}