neberu 0.0.0

// ============================================================
// SIZE — MEASUREMENT OF TRIT-WORD OBJECTS
// ============================================================
//
// Pure measurement. No rewriting. No governance applied.
// Every function returns a count of trits needed to represent
// an object in the from-axiom Trit-word encoding.
//
// The encoding (from the axiom derivation):
//   A generator  = its Trit signature (1 trit)
//   A word       = sequence of generator Trits (grade trits)
//   An Expr term = (coefficient encoding) + word trits
//   A Rat        = numerator Tern + denominator Tern (in balanced ternary)
//   A TraceGen   = [P*rule_idx] INV [P*start] INV [matched trits]
//   A TraceWalk  = concatenation of TraceGen words
//   A Governance = sum over relations of (source trits + target trits)
//
// The "size" of an object is how many Trits are needed to
// represent it exactly, from the axiom alone.

use crate::expr::Expr;
use crate::governance::Governance;
use crate::rat::Rat;
use crate::trace::{TraceGen, TraceWalk};
use crate::word::Word;

// ── Primitive sizes ───────────────────────────────────────────────────────────

/// A Trit is 1 trit. (The axiom itself — irreducible.)
pub const TRIT_SIZE: usize = 1;

/// A Gen is 1 trit — its signature.
/// The index is addressing overhead, not mathematical content.
/// From the axiom: the generator IS its type.
pub fn gen_size() -> usize {
    TRIT_SIZE
}

/// A Word of grade k is k trits — one per generator's type.
pub fn word_size(w: &Word) -> usize {
    w.grade()
}

// ── Rational number size ──────────────────────────────────────────────────────

/// A Tern integer of value v needs ceil(log₃(|v|+1)) trits.
/// For v=0: 1 trit (the zero trit).
/// For v≠0: the number of balanced ternary digits.
pub fn tern_size(v: i64) -> usize {
    if v == 0 {
        return 1;
    }
    let mut abs = v.unsigned_abs();
    let mut digits = 0usize;
    while abs > 0 {
        abs = (abs + 1) / 3; // ceiling division accounts for balanced encoding
        digits += 1;
    }
    digits.max(1)
}

/// A Rat p/q needs tern_size(p) + tern_size(q) trits.
/// Reduced to lowest terms, so no redundancy.
pub fn rat_size(r: &Rat) -> usize {
    tern_size(r.numerator().to_i64()) + tern_size(r.denominator().to_i64())
}

// ── Expression size ───────────────────────────────────────────────────────────

/// A single term (coefficient × word) in an Expr:
/// rat_size(coefficient) + word_size(word) trits.
pub fn term_size(coeff: &Rat, word: &Word) -> usize {
    rat_size(coeff) + word_size(word)
}

/// An Expr is the sum of its term sizes.
/// Each term is independent; the sparse representation matches the encoding.
pub fn expr_size(e: &Expr) -> usize {
    e.terms().map(|(w, c)| term_size(c, w)).sum()
}

// ── TraceGen size ─────────────────────────────────────────────────────────────

/// A TraceGen encoded as a Trit word:
///   [P × rule_idx]  INV  [P × start]  INV  [matched trits]
///
/// Size = rule_idx (unary count) + 1 (INV separator)
///      + start (unary count)    + 1 (INV separator)
///      + matched.grade()
///
/// Note: rule_idx=0 → 0 P-trits; start=0 → 0 P-trits.
/// The INV separators are always present.
pub fn tracegen_size(tg: &TraceGen) -> TritWordSize {
    let rule_trits = tg.rule_idx; // unary: n P-trits for index n
    let start_trits = tg.start; // unary: n P-trits for position n
    let sep_trits = 2; // two INV separators
    let matched_trits = tg.matched.grade(); // one trit per generator type
    let total = rule_trits + sep_trits + start_trits + matched_trits;
    TritWordSize {
        rule_idx_trits: rule_trits,
        start_trits,
        sep_trits: 2,
        matched_trits,
        total_trits: total,
        bits: total * 2,
        bytes: (total * 2).div_ceil(8),
    }
}

/// A TraceWalk is the concatenation of its TraceGen words.
pub fn tracewalk_size(tw: &TraceWalk) -> WalkSize {
    let step_sizes: Vec<TritWordSize> = tw.steps().iter().map(tracegen_size).collect();
    let total_trits: usize = step_sizes.iter().map(|s| s.total_trits).sum();
    WalkSize {
        steps: tw.len(),
        step_sizes,
        total_trits,
        bits: total_trits * 2,
        bytes: (total_trits * 2).div_ceil(8),
    }
}

// ── Governance size ───────────────────────────────────────────────────────────

/// A Governance is the sum over its relations of
/// (source word trits + target expr trits).
pub fn governance_size(gov: &Governance) -> GovSize {
    let mut total_trits = 0usize;
    let mut relation_sizes = Vec::new();
    for rel in gov.relations() {
        let src = word_size(&rel.source);
        let tgt = expr_size(&rel.target);
        total_trits += src + tgt;
        relation_sizes.push(RelSize {
            source_trits: src,
            target_trits: tgt,
        });
    }
    GovSize {
        num_relations: gov.num_relations(),
        relation_sizes,
        total_trits,
        bits: total_trits * 2,
        bytes: (total_trits * 2).div_ceil(8),
    }
}

// ── Full certificate size ─────────────────────────────────────────────────────

/// The complete KOT certificate size: N₁ (trace) + N₂ (KOT governance) + N₃ (total).
pub fn certificate_size(walk: &TraceWalk, kot_gov: &Governance) -> CertSize {
    let n1 = tracewalk_size(walk);
    let n2 = governance_size(kot_gov);
    let n3_trits = n1.total_trits + n2.total_trits;
    CertSize {
        n1,
        n2,
        n3_trits,
        n3_bits: n3_trits * 2,
        n3_bytes: (n3_trits * 2).div_ceil(8),
    }
}

// ── Size types ────────────────────────────────────────────────────────────────

#[derive(Debug, Clone)]
pub struct TritWordSize {
    pub rule_idx_trits: usize,
    pub start_trits: usize,
    pub sep_trits: usize,
    pub matched_trits: usize,
    pub total_trits: usize,
    pub bits: usize,
    pub bytes: usize,
}

#[derive(Debug, Clone)]
pub struct WalkSize {
    pub steps: usize,
    pub step_sizes: Vec<TritWordSize>,
    pub total_trits: usize,
    pub bits: usize,
    pub bytes: usize,
}

#[derive(Debug, Clone)]
pub struct RelSize {
    pub source_trits: usize,
    pub target_trits: usize,
}

#[derive(Debug, Clone)]
pub struct GovSize {
    pub num_relations: usize,
    pub relation_sizes: Vec<RelSize>,
    pub total_trits: usize,
    pub bits: usize,
    pub bytes: usize,
}

#[derive(Debug, Clone)]
pub struct CertSize {
    pub n1: WalkSize,    // trace encoding
    pub n2: GovSize,     // KOT governance
    pub n3_trits: usize, // total
    pub n3_bits: usize,
    pub n3_bytes: usize,
}

// ── Tests ─────────────────────────────────────────────────────────────────────

#[cfg(test)]
mod tests {
    use super::*;
    use crate::expr::Expr;
    use crate::gen::Gen;
    use crate::rat::Rat;
    use crate::trace::TraceGen;
    use crate::word::Word;

    #[test]
    fn gen_is_one_trit() {
        assert_eq!(gen_size(), 1);
    }

    #[test]
    fn word_grade2_is_2_trits() {
        let w = Word::from_gens(&[Gen::imaginary(0), Gen::imaginary(1)]);
        assert_eq!(word_size(&w), 2);
    }

    #[test]
    fn scalar_word_is_0_trits() {
        assert_eq!(word_size(&Word::scalar()), 0);
    }

    #[test]
    fn tern_zero_is_1_trit() {
        assert_eq!(tern_size(0), 1);
    }

    #[test]
    fn tern_one_is_1_trit() {
        assert_eq!(tern_size(1), 1);
    }

    #[test]
    fn tern_neg_one_is_1_trit() {
        assert_eq!(tern_size(-1), 1);
    }

    #[test]
    fn tern_4_needs_2_trits() {
        // 4 in balanced ternary: 1 + 1*3 = 4 → digits P, P → 2 trits
        assert_eq!(tern_size(4), 2);
    }

    #[test]
    fn rat_one_is_2_trits() {
        // 1/1: tern_size(1)=1 + tern_size(1)=1 = 2
        assert_eq!(rat_size(&Rat::one()), 2);
    }

    #[test]
    fn rat_neg_one_is_2_trits() {
        assert_eq!(rat_size(&Rat::neg_one()), 2);
    }

    #[test]
    fn expr_int_neg1_size() {
        // Expr::int(-1) = -1 * scalar_word
        // term_size = rat_size(-1/1) + word_size(scalar) = 2 + 0 = 2
        assert_eq!(expr_size(&Expr::int(-1)), 2);
    }

    #[test]
    fn expr_gen_size() {
        // Expr::gen(ei(0)) = 1 * Word([N])
        // term_size = rat_size(1/1) + word_size([N]) = 2 + 1 = 3
        let e = Expr::gen(Gen::imaginary(0));
        assert_eq!(expr_size(&e), 3);
    }

    #[test]
    fn tracegen_e1e1_step_size() {
        // Step: rule 0 at position 0, matched = [N, N] (two imaginary gens)
        // Encoding: [] INV [] INV [N N]
        // rule_trits=0, sep=2, start=0, matched=2 → total=4
        let tg = TraceGen::new(
            0,
            0,
            Word::from_gens(&[Gen::imaginary(0), Gen::imaginary(0)]),
        );
        let size = tracegen_size(&tg);
        assert_eq!(size.rule_idx_trits, 0);
        assert_eq!(size.start_trits, 0);
        assert_eq!(size.sep_trits, 2);
        assert_eq!(size.matched_trits, 2);
        assert_eq!(size.total_trits, 4);
        assert_eq!(size.bits, 8);
    }

    #[test]
    fn tracegen_with_nonzero_rule_and_start() {
        // Rule 3 at position 2, matched = [P] (one hyperbolic gen)
        // Encoding: [P P P] INV [P P] INV [P]
        // rule_trits=3, sep=2, start=2, matched=1 → total=8
        let tg = TraceGen::new(3, 2, Word::from_gens(&[Gen::hyperbolic(0)]));
        let size = tracegen_size(&tg);
        assert_eq!(size.total_trits, 8);
    }

    #[test]
    fn walk_single_step_e1e1_is_4_trits() {
        use crate::trace::TraceWalk;
        let tg = TraceGen::new(
            0,
            0,
            Word::from_gens(&[Gen::imaginary(0), Gen::imaginary(0)]),
        );
        let walk = TraceWalk::singleton(tg);
        let size = tracewalk_size(&walk);
        assert_eq!(size.steps, 1);
        assert_eq!(size.total_trits, 4);
        assert_eq!(size.bits, 8);
        assert_eq!(size.bytes, 1);
    }

    #[test]
    fn empty_walk_is_0_trits() {
        use crate::trace::TraceWalk;
        let walk = TraceWalk::empty();
        let size = tracewalk_size(&walk);
        assert_eq!(size.total_trits, 0);
    }

    #[test]
    fn governance_cl100_size() {
        use crate::governance::Governance;
        let gov = Governance::cl(1, 0, 0);
        let size = governance_size(&gov);
        // Cl(1,0,0) has 1 relation: [N,N] → -1
        // source: word [N,N] = 2 trits
        // target: Expr::int(-1) = 2 trits
        // total: 4 trits
        assert_eq!(size.num_relations, 1);
        assert_eq!(size.total_trits, 4);
    }

    #[test]
    fn size_scales_with_algebra() {
        use crate::governance::Governance;
        let g1 = governance_size(&Governance::cl(1, 0, 0));
        let g2 = governance_size(&Governance::cl(2, 0, 0));
        let g3 = governance_size(&Governance::cl(3, 0, 0));
        // More generators → more relations → larger governance
        assert!(g2.total_trits > g1.total_trits);
        assert!(g3.total_trits > g2.total_trits);
    }
}