geoit 0.0.2

//! Blade representation for geometric algebra.
//!
//! A blade is a sorted set of generator indices. The grade is the length.
//! The scalar blade is empty.
//!
//! For algebras with ≤ 8 generators per blade (covers CGA(3) and below),
//! all storage is inline — no heap allocation. For larger blades
//! (Veronese/QGA and above), spills to heap automatically.

use std::cmp::Ordering;

// ═══════════════════════════════════════════════════════════
// INLINE VEC
// ═══════════════════════════════════════════════════════════

const INLINE_CAP: usize = 8;

/// A small sorted vector of u16, inline for up to 8 elements.
/// Zero dependencies. Zero heap allocation for grade ≤ 8.
#[derive(Clone)]
#[allow(clippy::box_collection)]
pub struct BladeKey {
    /// Inline storage for up to INLINE_CAP elements.
    inline: [u16; INLINE_CAP],
    /// Number of elements (grade). If len > INLINE_CAP, `heap` is used.
    len: u8,
    /// Heap overflow for grade > INLINE_CAP.
    heap: Option<Vec<u16>>,
}

impl BladeKey {
    /// The scalar blade (grade 0, empty).
    pub const SCALAR: BladeKey = BladeKey {
        inline: [0; INLINE_CAP],
        len: 0,
        heap: None,
    };

    /// Create from a single generator index.
    #[inline]
    pub fn generator(k: u16) -> Self {
        let mut b = Self::SCALAR;
        b.inline[0] = k;
        b.len = 1;
        b
    }

    /// Create from a sorted slice of generator indices.
    /// Caller guarantees: sorted, no duplicates.
    pub fn from_sorted(indices: &[u16]) -> Self {
        debug_assert!(
            indices.windows(2).all(|w| w[0] < w[1]),
            "BladeKey::from_sorted: indices must be strictly sorted"
        );
        if indices.len() <= INLINE_CAP {
            let mut inline = [0u16; INLINE_CAP];
            inline[..indices.len()].copy_from_slice(indices);
            BladeKey {
                inline,
                len: indices.len() as u8,
                heap: None,
            }
        } else {
            BladeKey {
                inline: [0; INLINE_CAP],
                len: indices.len() as u8,
                heap: Some(indices.to_vec()),
            }
        }
    }

    /// Create the pseudoscalar blade for n generators: [0, 1, 2, ..., n-1].
    pub fn pseudoscalar(n: u32) -> Self {
        let indices: Vec<u16> = (0..n as u16).collect();
        Self::from_sorted(&indices)
    }

    /// Grade (number of participating generators).
    #[inline]
    pub fn grade(&self) -> u8 {
        self.len
    }

    /// Access the sorted generator indices as a slice.
    #[inline]
    pub fn indices(&self) -> &[u16] {
        if let Some(ref h) = self.heap {
            h.as_slice()
        } else {
            &self.inline[..self.len as usize]
        }
    }

    /// Is this the scalar blade (grade 0)?
    #[inline]
    pub fn is_scalar(&self) -> bool {
        self.len == 0
    }

    /// Does generator k participate in this blade?
    #[inline]
    pub fn contains_generator(&self, k: u16) -> bool {
        self.indices().binary_search(&k).is_ok()
    }

    /// Symmetric difference of two sorted blade keys.
    /// Result is the blade of generators in exactly one of `a` or `b`.
    /// This is the blade mask of the geometric product result.
    pub fn symmetric_difference(a: &BladeKey, b: &BladeKey) -> BladeKey {
        let ai = a.indices();
        let bi = b.indices();
        let mut result = Vec::with_capacity(ai.len() + bi.len());
        let (mut i, mut j) = (0, 0);
        while i < ai.len() && j < bi.len() {
            match ai[i].cmp(&bi[j]) {
                Ordering::Less => {
                    result.push(ai[i]);
                    i += 1;
                }
                Ordering::Greater => {
                    result.push(bi[j]);
                    j += 1;
                }
                Ordering::Equal => {
                    i += 1;
                    j += 1;
                } // cancel
            }
        }
        result.extend_from_slice(&ai[i..]);
        result.extend_from_slice(&bi[j..]);
        BladeKey::from_sorted(&result)
    }

    /// Intersection of two sorted blade keys.
    /// These are the generators that cancel in the geometric product.
    pub fn intersection(a: &BladeKey, b: &BladeKey) -> BladeKey {
        let ai = a.indices();
        let bi = b.indices();
        let mut result = Vec::with_capacity(ai.len().min(bi.len()));
        let (mut i, mut j) = (0, 0);
        while i < ai.len() && j < bi.len() {
            match ai[i].cmp(&bi[j]) {
                Ordering::Less => {
                    i += 1;
                }
                Ordering::Greater => {
                    j += 1;
                }
                Ordering::Equal => {
                    result.push(ai[i]);
                    i += 1;
                    j += 1;
                }
            }
        }
        BladeKey::from_sorted(&result)
    }
}

// ═══════════════════════════════════════════════════════════
// CANONICAL REORDER SIGN
// ═══════════════════════════════════════════════════════════

/// Sign from reordering generators of blade `a` past generators of blade `b`
/// into canonical (sorted) order. Returns +1 or -1.
///
/// For each element in b, count how many elements in a are greater.
/// The parity of the total count determines the sign.
pub fn canonical_reorder(a: &BladeKey, b: &BladeKey) -> i8 {
    let ai = a.indices();
    let bi = b.indices();
    let mut swaps = 0u32;
    // For each element in b, count elements in a that are strictly greater
    // Using the fact that both are sorted, we can do this efficiently
    let mut a_ptr = ai.len(); // start from the end
    for &bk in bi.iter().rev() {
        // Count elements in a > bk
        while a_ptr > 0 && ai[a_ptr - 1] > bk {
            a_ptr -= 1;
        }
        swaps += (ai.len() - a_ptr) as u32;
    }
    if swaps & 1 == 0 {
        1
    } else {
        -1
    }
}

// ═══════════════════════════════════════════════════════════
// TRAIT IMPLEMENTATIONS
// ═══════════════════════════════════════════════════════════

impl PartialEq for BladeKey {
    fn eq(&self, other: &Self) -> bool {
        self.indices() == other.indices()
    }
}

impl Eq for BladeKey {}

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

impl Ord for BladeKey {
    fn cmp(&self, other: &Self) -> Ordering {
        // Grade first (lower grade comes first), then lexicographic on indices
        self.grade()
            .cmp(&other.grade())
            .then_with(|| self.indices().cmp(other.indices()))
    }
}

impl std::hash::Hash for BladeKey {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.indices().hash(state);
    }
}

impl std::fmt::Debug for BladeKey {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "Blade{:?}", self.indices())
    }
}

impl std::fmt::Display for BladeKey {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        if self.is_scalar() {
            write!(f, "1")
        } else {
            write!(f, "e")?;
            for &k in self.indices() {
                write!(f, "{}", k)?;
            }
            Ok(())
        }
    }
}

// ═══════════════════════════════════════════════════════════
// LEGACY COMPATIBILITY
// ═══════════════════════════════════════════════════════════

/// Type alias preserved for migration. Will be removed in v0.1.0.
pub type BladeMask = u64;

/// Convert a legacy u64 bitmask to a BladeKey.
/// Bit k set means generator k participates.
pub fn mask_to_blade(mask: BladeMask) -> BladeKey {
    if mask == 0 {
        return BladeKey::SCALAR;
    }
    let mut indices = Vec::new();
    let mut m = mask;
    while m != 0 {
        let k = m.trailing_zeros() as u16;
        indices.push(k);
        m &= m - 1;
    }
    BladeKey::from_sorted(&indices)
}

/// Convert a BladeKey back to a u64 bitmask.
/// Only valid for generators < 64.
pub fn blade_to_mask(blade: &BladeKey) -> BladeMask {
    let mut mask: u64 = 0;
    for &k in blade.indices() {
        debug_assert!(k < 64, "blade_to_mask: generator {} exceeds u64 range", k);
        mask |= 1u64 << k;
    }
    mask
}

/// Grade of a legacy bitmask (popcount).
#[inline]
pub fn grade(mask: BladeMask) -> u8 {
    mask.count_ones() as u8
}

/// Does generator k participate in this legacy bitmask?
#[inline]
pub fn contains_generator(mask: BladeMask, gen: u8) -> bool {
    mask & (1u64 << gen) != 0
}

/// Legacy canonical reorder on u64 bitmasks.
pub fn canonical_reorder_mask(a: BladeMask, b: BladeMask) -> i8 {
    let mut a = a >> 1;
    let mut swaps = 0u32;
    while a != 0 {
        swaps += (a & b).count_ones();
        a >>= 1;
    }
    if swaps & 1 == 0 {
        1
    } else {
        -1
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    // ─── BladeKey basics ───

    #[test]
    fn scalar_blade() {
        let s = BladeKey::SCALAR;
        assert_eq!(s.grade(), 0);
        assert!(s.is_scalar());
        assert_eq!(s.indices(), &[]);
    }

    #[test]
    fn single_generator() {
        let b = BladeKey::generator(2);
        assert_eq!(b.grade(), 1);
        assert!(!b.is_scalar());
        assert_eq!(b.indices(), &[2]);
        assert!(b.contains_generator(2));
        assert!(!b.contains_generator(0));
    }

    #[test]
    fn from_sorted_inline() {
        let b = BladeKey::from_sorted(&[0, 2, 5]);
        assert_eq!(b.grade(), 3);
        assert_eq!(b.indices(), &[0, 2, 5]);
        assert!(b.heap.is_none());
    }

    #[test]
    fn from_sorted_heap() {
        let indices: Vec<u16> = (0..10).collect();
        let b = BladeKey::from_sorted(&indices);
        assert_eq!(b.grade(), 10);
        assert_eq!(b.indices(), &indices[..]);
        assert!(b.heap.is_some());
    }

    #[test]
    fn pseudoscalar() {
        let ps = BladeKey::pseudoscalar(5);
        assert_eq!(ps.grade(), 5);
        assert_eq!(ps.indices(), &[0, 1, 2, 3, 4]);
    }

    // ─── Symmetric difference ───

    #[test]
    fn sym_diff_disjoint() {
        let a = BladeKey::from_sorted(&[0, 1]);
        let b = BladeKey::from_sorted(&[2, 3]);
        let r = BladeKey::symmetric_difference(&a, &b);
        assert_eq!(r.indices(), &[0, 1, 2, 3]);
    }

    #[test]
    fn sym_diff_overlap() {
        let a = BladeKey::from_sorted(&[0, 1, 2]);
        let b = BladeKey::from_sorted(&[1, 2, 3]);
        let r = BladeKey::symmetric_difference(&a, &b);
        assert_eq!(r.indices(), &[0, 3]);
    }

    #[test]
    fn sym_diff_identical() {
        let a = BladeKey::from_sorted(&[0, 1]);
        let r = BladeKey::symmetric_difference(&a, &a);
        assert!(r.is_scalar());
    }

    #[test]
    fn sym_diff_with_scalar() {
        let a = BladeKey::from_sorted(&[1, 3]);
        let r = BladeKey::symmetric_difference(&a, &BladeKey::SCALAR);
        assert_eq!(r, a);
    }

    // ─── Intersection ───

    #[test]
    fn intersection_overlap() {
        let a = BladeKey::from_sorted(&[0, 1, 2]);
        let b = BladeKey::from_sorted(&[1, 2, 3]);
        let r = BladeKey::intersection(&a, &b);
        assert_eq!(r.indices(), &[1, 2]);
    }

    #[test]
    fn intersection_disjoint() {
        let a = BladeKey::from_sorted(&[0, 1]);
        let b = BladeKey::from_sorted(&[2, 3]);
        let r = BladeKey::intersection(&a, &b);
        assert!(r.is_scalar());
    }

    // ─── Canonical reorder ───

    #[test]
    fn reorder_identity() {
        // e0 * e1 → already sorted → +1
        let a = BladeKey::generator(0);
        let b = BladeKey::generator(1);
        assert_eq!(canonical_reorder(&a, &b), 1);
    }

    #[test]
    fn reorder_swap() {
        // e1 * e0 → one swap → -1
        let a = BladeKey::generator(1);
        let b = BladeKey::generator(0);
        assert_eq!(canonical_reorder(&a, &b), -1);
    }

    #[test]
    fn reorder_e01_e2() {
        let a = BladeKey::from_sorted(&[0, 1]);
        let b = BladeKey::generator(2);
        assert_eq!(canonical_reorder(&a, &b), 1);
    }

    #[test]
    fn reorder_e2_e01() {
        let a = BladeKey::generator(2);
        let b = BladeKey::from_sorted(&[0, 1]);
        assert_eq!(canonical_reorder(&a, &b), 1);
    }

    #[test]
    fn reorder_e1_e02() {
        let a = BladeKey::generator(1);
        let b = BladeKey::from_sorted(&[0, 2]);
        assert_eq!(canonical_reorder(&a, &b), -1);
    }

    #[test]
    fn reorder_self_e01() {
        let a = BladeKey::from_sorted(&[0, 1]);
        assert_eq!(canonical_reorder(&a, &a), -1);
    }

    // ─── Verify new BladeKey reorder matches legacy bitmask reorder ───

    #[test]
    fn reorder_matches_legacy() {
        for a_mask in 0u64..32 {
            for b_mask in 0u64..32 {
                let legacy = canonical_reorder_mask(a_mask, b_mask);
                let a_blade = mask_to_blade(a_mask);
                let b_blade = mask_to_blade(b_mask);
                let new = canonical_reorder(&a_blade, &b_blade);
                assert_eq!(
                    legacy, new,
                    "reorder mismatch: a={:#b} b={:#b} legacy={} new={}",
                    a_mask, b_mask, legacy, new
                );
            }
        }
    }

    // ─── Ordering ───

    #[test]
    fn ord_grade_first() {
        let scalar = BladeKey::SCALAR;
        let vector = BladeKey::generator(0);
        let bivector = BladeKey::from_sorted(&[0, 1]);
        assert!(scalar < vector);
        assert!(vector < bivector);
    }

    #[test]
    fn ord_same_grade_lexicographic() {
        let e01 = BladeKey::from_sorted(&[0, 1]);
        let e02 = BladeKey::from_sorted(&[0, 2]);
        let e12 = BladeKey::from_sorted(&[1, 2]);
        assert!(e01 < e02);
        assert!(e02 < e12);
    }

    // ─── Legacy conversion ───

    #[test]
    fn mask_roundtrip() {
        for mask in 0u64..64 {
            let blade = mask_to_blade(mask);
            let back = blade_to_mask(&blade);
            assert_eq!(mask, back, "roundtrip failed for mask {:#b}", mask);
        }
    }

    #[test]
    fn legacy_grade() {
        assert_eq!(grade(0b000), 0);
        assert_eq!(grade(0b001), 1);
        assert_eq!(grade(0b011), 2);
        assert_eq!(grade(0b111), 3);
    }
}