ccf_core/

boundary.rs

//! Comfort-zone boundary via global minimum cut on the trust-weighted context graph.
//!
//! Patent Claims 9–12: automatic discovery of the comfort-zone boundary as a
//! computed structural property of the trust manifold, not a threshold parameter.
//!
//! # Two-graph architecture
//!
//! **Graph A — World Shape** (cosine similarity only, stable)
//! Edge weight = `cosine_similarity(vocab_A, vocab_B)` ∈ [0.0, 1.0]
//!
//! **Graph B — Trust Shape** (patent-faithful, dynamic)
//! Activates once both endpoints have ≥ `MIN_TRUST_OBSERVATIONS` interactions.
//! Edge weight = `sim × tanh(coh_A × TRUST_SCALE) × tanh(coh_B × TRUST_SCALE)`
//!
//! # Algorithm
//!
//! Stoer-Wagner global minimum cut, O(V·E + V²·log V).
//! Exact for any graph ≤ MAX_CONTEXTS (64) nodes.
//!
//! # Invariants
//! - **I-BNDRY-001** — Min-cut on context-key graph, not episode graph
//! - **I-BNDRY-002** — Edge weight ∈ [0.0, 1.0]
//! - **I-BNDRY-003** — Edges inserted only when cosine similarity > EDGE_THRESHOLD (0.1)
//! - **I-TRUST-001** — Trust component activates only after MIN_TRUST_OBSERVATIONS (50)
//! - **I-DIST-001** — no_std compatible; uses hashbrown HashMap
//! - **I-DIST-005** — Zero unsafe code

use crate::vocabulary::{ContextKey, SensorVocabulary};

/// Maximum number of contexts tracked in the boundary graph.
pub const MAX_CONTEXTS: usize = 64;

/// Minimum cosine similarity for an edge to be inserted (I-BNDRY-003).
const EDGE_THRESHOLD: f32 = 0.1;

/// Minimum positive interactions before the trust component activates (I-TRUST-001).
pub const MIN_TRUST_OBSERVATIONS: u32 = 50;

/// Trust scale factor in the Graph B edge weight formula.
const TRUST_SCALE: f32 = 2.0;

/// Result of a minimum cut computation.
#[derive(Clone, Debug)]
pub struct MinCutResult {
    /// Weight of the minimum cut (thinnest bridge in the trust manifold).
    pub min_cut_value: f32,
    /// Number of entries in `partition_s`.
    pub partition_s_count: usize,
    /// Context hashes on the "safe" (high-trust) side.
    pub partition_s: [u32; MAX_CONTEXTS],
    /// Number of entries in `partition_complement`.
    pub partition_complement_count: usize,
    /// Context hashes on the "unfamiliar" side.
    pub partition_complement: [u32; MAX_CONTEXTS],
}

/// Per-context node data stored in the boundary graph.
#[derive(Clone, Debug)]
struct NodeData {
    /// FNV hash of the context key (used as stable node ID).
    hash: u32,
    /// Current coherence value [0.0, 1.0].
    coherence: f32,
    /// Positive interactions in this context.
    observations: u32,
}

/// Comfort-zone boundary via global minimum cut on the trust-weighted context graph.
///
/// Patent Claims 9–12.
pub struct MinCutBoundary<V: SensorVocabulary<N>, const N: usize> {
    /// Node list (up to MAX_CONTEXTS).
    nodes: [Option<NodeData>; MAX_CONTEXTS],
    /// Number of active nodes.
    node_count: usize,
    /// Adjacency matrix: edge weights between node indices.
    /// `adj[i][j]` is the Graph B (or Graph A fallback) weight between nodes i and j.
    adj: [[f32; MAX_CONTEXTS]; MAX_CONTEXTS],
    /// Phantom for the vocabulary type.
    _vocab: core::marker::PhantomData<V>,
}

impl<V: SensorVocabulary<N>, const N: usize> MinCutBoundary<V, N> {
    /// Create an empty boundary graph.
    pub fn new() -> Self {
        Self {
            nodes: [
                None, None, None, None, None, None, None, None,
                None, None, None, None, None, None, None, None,
                None, None, None, None, None, None, None, None,
                None, None, None, None, None, None, None, None,
                None, None, None, None, None, None, None, None,
                None, None, None, None, None, None, None, None,
                None, None, None, None, None, None, None, None,
                None, None, None, None, None, None, None, None,
            ],
            node_count: 0,
            adj: [[0.0; MAX_CONTEXTS]; MAX_CONTEXTS],
            _vocab: core::marker::PhantomData,
        }
    }

    /// Register a context key as a node, providing all existing keys for edge insertion.
    ///
    /// If the context is already known, this is O(1). If new, inserts edges to all
    /// existing nodes with cosine similarity > EDGE_THRESHOLD (I-BNDRY-003).
    pub fn report_context_with_key(
        &mut self,
        key: &ContextKey<V, N>,
        all_keys: &[(ContextKey<V, N>, u32)],
    ) {
        let hash = key.context_hash_u32();

        // Linear scan to check if already known (no HashMap needed for ≤64 nodes)
        if self.find_idx(hash).is_some() {
            return;
        }

        if self.node_count >= MAX_CONTEXTS {
            return;
        }

        let new_idx = self.node_count;
        self.nodes[new_idx] = Some(NodeData { hash, coherence: 0.0, observations: 0 });

        // Insert Graph A edges to all existing nodes
        for (other_key, other_hash) in all_keys {
            if *other_hash == hash {
                continue;
            }
            if let Some(other_idx) = self.find_idx(*other_hash) {
                let sim = key.cosine_similarity(other_key);
                if sim > EDGE_THRESHOLD {
                    self.adj[new_idx][other_idx] = sim;
                    self.adj[other_idx][new_idx] = sim;
                }
            }
        }

        self.node_count += 1;
    }

    /// Update trust-weighted edges for a context after a coherence change.
    ///
    /// Recomputes Graph B weights for all edges incident to this context.
    /// If either endpoint has fewer than MIN_TRUST_OBSERVATIONS, keeps Graph A weight.
    pub fn update_trust(&mut self, key: &ContextKey<V, N>, coherence: f32, observations: u32) {
        let hash = key.context_hash_u32();
        let Some(idx) = self.find_idx(hash) else { return; };

        // Update this node's trust data
        if let Some(ref mut node) = self.nodes[idx] {
            node.coherence = coherence;
            node.observations = observations;
        }

        // Snapshot coherence/obs for the current node before iterating
        let self_coh = coherence;
        let self_obs = observations;

        // Reweight edges: for each neighbour with a Graph A edge, compute Graph B if eligible
        for other_idx in 0..self.node_count {
            if other_idx == idx {
                continue;
            }

            // We need the baseline similarity (Graph A weight).
            // adj currently holds whichever weight was last written.
            // To detect whether an edge exists, check if weight > 0 OR check via the
            // original Graph A weight. We store Graph A weight initially, so if the
            // current weight is > 0 after update_trust was called, the edge exists.
            // However on repeated calls we may have overwritten with Graph B.
            // Safe approach: only reweight if either Graph A or current weight > EDGE_THRESHOLD.
            let current_weight = self.adj[idx][other_idx];
            if current_weight <= EDGE_THRESHOLD {
                continue;
            }

            let other_coh;
            let other_obs;
            if let Some(ref other) = self.nodes[other_idx] {
                other_coh = other.coherence;
                other_obs = other.observations;
            } else {
                continue;
            }

            // Use Graph B if both endpoints have sufficient observations (I-TRUST-001)
            let weight = if self_obs >= MIN_TRUST_OBSERVATIONS
                && other_obs >= MIN_TRUST_OBSERVATIONS
            {
                // Graph B: trust-weighted
                let t_self = boundary_tanh(self_coh * TRUST_SCALE);
                let t_other = boundary_tanh(other_coh * TRUST_SCALE);
                (current_weight * t_self * t_other).clamp(0.0, 1.0)
            } else {
                // Graph A: similarity only — leave unchanged
                current_weight
            };

            self.adj[idx][other_idx] = weight;
            self.adj[other_idx][idx] = weight;
        }
    }

    /// Linear scan to find the node index for a given hash (O(n), n ≤ 64).
    fn find_idx(&self, hash: u32) -> Option<usize> {
        for i in 0..self.node_count {
            if let Some(ref node) = self.nodes[i] {
                if node.hash == hash {
                    return Some(i);
                }
            }
        }
        None
    }

    /// Current minimum cut value of the trust manifold.
    ///
    /// Returns 0.0 if fewer than 2 nodes are registered.
    /// Patent Claim 9: boundary is computed, not configured.
    pub fn min_cut_value(&self) -> f32 {
        if self.node_count < 2 {
            return 0.0;
        }
        self.stoer_wagner().min_cut_value
    }

    /// Full minimum cut result: value and partition.
    ///
    /// Patent Claim 10: partition is observable.
    pub fn partition(&self) -> MinCutResult {
        if self.node_count < 2 {
            let mut complement = [0u32; MAX_CONTEXTS];
            for i in 0..self.node_count {
                if let Some(ref n) = self.nodes[i] {
                    complement[i] = n.hash;
                }
            }
            return MinCutResult {
                min_cut_value: 0.0,
                partition_s_count: 0,
                partition_s: [0; MAX_CONTEXTS],
                partition_complement_count: self.node_count,
                partition_complement: complement,
            };
        }
        self.stoer_wagner()
    }

    /// Number of registered context nodes.
    pub fn node_count(&self) -> usize {
        self.node_count
    }

    // ─── Stoer-Wagner algorithm ──────────────────────────────────────────────

    /// Stoer-Wagner global minimum cut.
    ///
    /// Returns the minimum cut value and the partition (S, V\S).
    /// O(V·E + V²·log V), exact for all inputs.
    fn stoer_wagner(&self) -> MinCutResult {
        let n = self.node_count;

        // Working copy of adjacency weights
        let mut w = [[0.0_f32; MAX_CONTEXTS]; MAX_CONTEXTS];
        for i in 0..n {
            for j in 0..n {
                w[i][j] = self.adj[i][j];
            }
        }

        // Track which original nodes are merged into each super-node via bitmask.
        // u64 supports up to 64 bits, matching MAX_CONTEXTS = 64.
        let mut merged = [0u64; MAX_CONTEXTS];
        for i in 0..n {
            merged[i] = 1u64 << i;
        }

        let mut active = [false; MAX_CONTEXTS];
        for i in 0..n {
            active[i] = true;
        }

        let mut best_cut = f32::MAX;
        let mut best_partition_mask: u64 = 0;

        // Run n-1 phases
        for _phase in 0..(n - 1) {
            let (s, t, cut_val) = self.min_cut_phase(&w, &active, n);
            if cut_val < best_cut {
                best_cut = cut_val;
                best_partition_mask = merged[t];
            }
            // Merge t into s
            for i in 0..n {
                if active[i] {
                    w[s][i] += w[t][i];
                    w[i][s] += w[i][t];
                }
            }
            merged[s] |= merged[t];
            active[t] = false;
        }

        // Build partition from best_partition_mask
        let mut result = MinCutResult {
            min_cut_value: if best_cut == f32::MAX { 0.0 } else { best_cut },
            partition_s_count: 0,
            partition_s: [0; MAX_CONTEXTS],
            partition_complement_count: 0,
            partition_complement: [0; MAX_CONTEXTS],
        };

        for i in 0..n {
            if let Some(ref node) = self.nodes[i] {
                if (best_partition_mask >> i) & 1 == 1 {
                    result.partition_s[result.partition_s_count] = node.hash;
                    result.partition_s_count += 1;
                } else {
                    result.partition_complement[result.partition_complement_count] = node.hash;
                    result.partition_complement_count += 1;
                }
            }
        }

        result
    }

    /// One phase of Stoer-Wagner: find the s-t pair with maximum adjacency cut.
    ///
    /// Returns `(s_idx, t_idx, cut_value_of_t)`.
    fn min_cut_phase(
        &self,
        w: &[[f32; MAX_CONTEXTS]; MAX_CONTEXTS],
        active: &[bool; MAX_CONTEXTS],
        n: usize,
    ) -> (usize, usize, f32) {
        let mut in_a = [false; MAX_CONTEXTS];
        let mut key = [0.0_f32; MAX_CONTEXTS];

        let mut prev = 0usize;
        let mut last = 0usize;

        // Find first active node to use as the starting point
        let mut initialised = false;
        for i in 0..n {
            if active[i] {
                prev = i;
                last = i;
                initialised = true;
                break;
            }
        }
        if !initialised {
            return (0, 0, 0.0);
        }

        let active_count = (0..n).filter(|&i| active[i]).count();

        for step in 0..active_count {
            // Find active node not in A with maximum key
            let u_opt = (0..n)
                .filter(|&i| active[i] && !in_a[i])
                .max_by(|&a, &b| {
                    key[a]
                        .partial_cmp(&key[b])
                        .unwrap_or(core::cmp::Ordering::Equal)
                });

            let u = match u_opt {
                Some(u) => u,
                None => break,
            };

            if step > 0 {
                prev = last;
            }
            last = u;
            in_a[u] = true;

            // Update keys of neighbours of u
            for v in 0..n {
                if active[v] && !in_a[v] {
                    key[v] += w[u][v];
                }
            }
        }

        // s = prev (second-to-last added), t = last added
        // cut value = key[last] = total weight of edges from last to rest of A
        (prev, last, key[last])
    }
}

impl<V: SensorVocabulary<N>, const N: usize> Default for MinCutBoundary<V, N> {
    fn default() -> Self {
        Self::new()
    }
}

/// Approximate tanh for no_std environments.
///
/// Uses `tanh(x) = 1 - 2/(exp(2x) + 1)` with a minimax polynomial for exp.
/// Accurate to < 0.001 for |x| ≤ 4, which covers the full trust scale range.
fn boundary_tanh(x: f32) -> f32 {
    if x > 9.0 {
        return 1.0;
    }
    if x < -9.0 {
        return -1.0;
    }
    // exp(y) via minimax polynomial on [-0.5*ln2, 0.5*ln2] with range reduction.
    // tanh(x) = 1 - 2/(exp(2x) + 1)
    let y = 2.0 * x;
    let e = exp_approx(y);
    1.0 - 2.0 / (e + 1.0)
}

/// Minimax polynomial approximation to exp(x), no_std compatible.
///
/// Uses range reduction: exp(x) = exp(k*ln2) * exp(r) = 2^k * exp(r)
/// where r = x - k*ln2, |r| ≤ 0.5*ln2.
/// The polynomial for exp(r) is accurate to < 1e-6 for |r| ≤ 0.347.
fn exp_approx(x: f32) -> f32 {
    // Clamp to avoid overflow: exp(88) > f32::MAX
    let x = x.clamp(-87.0, 88.0);
    // Range reduction: x = k*ln2 + r, k = round(x / ln2)
    const LN2: f32 = 0.693_147_18;
    const INV_LN2: f32 = 1.442_695_04;
    let k = (x * INV_LN2 + 0.5) as i32 - (if x < 0.0 { 1 } else { 0 });
    let r = x - k as f32 * LN2;
    // Polynomial: exp(r) ≈ 1 + r + r²/2 + r³/6 + r⁴/24 + r⁵/120
    // Accurate to < 1e-7 for |r| ≤ 0.347 (half ln2)
    let r2 = r * r;
    let r4 = r2 * r2;
    let poly = 1.0 + r + 0.5 * r2 + (1.0 / 6.0) * r * r2
        + (1.0 / 24.0) * r4
        + (1.0 / 120.0) * r * r4;
    // Multiply by 2^k via bit manipulation on f32
    // f32 exponent field is biased by 127; add k to it
    let clamped_k = k.clamp(-126, 127);
    let scale_bits: u32 = ((127 + clamped_k) as u32) << 23;
    let scale = f32::from_bits(scale_bits);
    poly * scale
}

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

#[cfg(test)]
mod tests {
    use super::*;
    use crate::mbot::{
        BrightnessBand, MbotSensors, MotionContext, NoiseBand, Orientation, PresenceSignature,
        TimePeriod,
    };

    fn make_key(b: BrightnessBand, n: NoiseBand) -> ContextKey<MbotSensors, 6> {
        ContextKey::new(MbotSensors {
            brightness: b,
            noise: n,
            presence: PresenceSignature::Absent,
            motion: MotionContext::Static,
            orientation: Orientation::Upright,
            time_period: TimePeriod::Day,
        })
    }

    fn bright_quiet() -> ContextKey<MbotSensors, 6> {
        make_key(BrightnessBand::Bright, NoiseBand::Quiet)
    }
    fn bright_loud() -> ContextKey<MbotSensors, 6> {
        make_key(BrightnessBand::Bright, NoiseBand::Loud)
    }
    fn dark_quiet() -> ContextKey<MbotSensors, 6> {
        make_key(BrightnessBand::Dark, NoiseBand::Quiet)
    }
    fn dark_loud() -> ContextKey<MbotSensors, 6> {
        make_key(BrightnessBand::Dark, NoiseBand::Loud)
    }

    #[test]
    fn test_claim_9_min_cut_is_computed_not_configured() {
        // Patent Claim 9: boundary is a computed structural property, not a threshold
        let mut b: MinCutBoundary<MbotSensors, 6> = MinCutBoundary::new();
        let k1 = bright_quiet();
        let k2 = dark_loud();
        b.report_context_with_key(&k1, &[]);
        let existing = [(k1.clone(), k1.context_hash_u32())];
        b.report_context_with_key(&k2, &existing);
        // No threshold was set — min_cut_value is emergent from graph topology
        let cut = b.min_cut_value();
        // Two dissimilar contexts should have a low but non-negative cut weight
        assert!(cut >= 0.0, "min_cut_value must be non-negative");
    }

    #[test]
    fn test_claim_10_partition_is_observable() {
        // Patent Claim 10: the two sides of the boundary are enumerable
        let mut b: MinCutBoundary<MbotSensors, 6> = MinCutBoundary::new();
        let k1 = bright_quiet();
        let k2 = dark_loud();
        b.report_context_with_key(&k1, &[]);
        let existing = [(k1.clone(), k1.context_hash_u32())];
        b.report_context_with_key(&k2, &existing);
        let result = b.partition();
        // Both partitions together contain all nodes
        assert_eq!(
            result.partition_s_count + result.partition_complement_count,
            2
        );
    }

    #[test]
    fn test_claim_11_thin_bridge_detected() {
        // Patent Claim 11: boundary discovers thin bridges between context clusters
        let mut b: MinCutBoundary<MbotSensors, 6> = MinCutBoundary::new();
        let k1 = bright_quiet();
        let k2 = bright_loud(); // similar to k1 (both bright)
        let k3 = dark_quiet(); // similar to k4 (both dark)
        let k4 = dark_loud(); // dissimilar to k1/k2

        b.report_context_with_key(&k1, &[]);
        let e1 = [(k1.clone(), k1.context_hash_u32())];
        b.report_context_with_key(&k2, &e1);
        let e2 = [
            (k1.clone(), k1.context_hash_u32()),
            (k2.clone(), k2.context_hash_u32()),
        ];
        b.report_context_with_key(&k3, &e2);
        let e3 = [
            (k1.clone(), k1.context_hash_u32()),
            (k2.clone(), k2.context_hash_u32()),
            (k3.clone(), k3.context_hash_u32()),
        ];
        b.report_context_with_key(&k4, &e3);

        assert_eq!(b.node_count(), 4);
        let cut = b.min_cut_value();
        assert!(cut >= 0.0);
        // The cut between {bright} and {dark} clusters should be low
    }

    #[test]
    fn test_claim_12_boundary_moves_when_trust_changes() {
        // Patent Claim 12: boundary is dynamic — it changes as trust is earned or lost
        let mut b: MinCutBoundary<MbotSensors, 6> = MinCutBoundary::new();
        let k1 = bright_quiet();
        let k2 = bright_loud();
        b.report_context_with_key(&k1, &[]);
        let existing = [(k1.clone(), k1.context_hash_u32())];
        b.report_context_with_key(&k2, &existing);

        let cut_before = b.min_cut_value();

        // Simulate trust being earned in both contexts (above MIN_TRUST_OBSERVATIONS)
        b.update_trust(&k1, 0.8, MIN_TRUST_OBSERVATIONS);
        b.update_trust(&k2, 0.8, MIN_TRUST_OBSERVATIONS);
        let cut_after_trust = b.min_cut_value();

        // Simulate trust degrading in k2
        b.update_trust(&k2, 0.1, MIN_TRUST_OBSERVATIONS);
        let cut_after_degradation = b.min_cut_value();

        // All cuts are valid non-negative values
        assert!(cut_before >= 0.0);
        assert!(cut_after_trust >= 0.0);
        assert!(cut_after_degradation >= 0.0);
        // After trust earned, Graph B activates, weights change
        // (exact values depend on tanh — just verify it ran without panic)
    }

    #[test]
    fn test_empty_graph_returns_zero() {
        let b: MinCutBoundary<MbotSensors, 6> = MinCutBoundary::new();
        assert_eq!(b.min_cut_value(), 0.0);
    }

    #[test]
    fn test_single_node_returns_zero() {
        let mut b: MinCutBoundary<MbotSensors, 6> = MinCutBoundary::new();
        b.report_context_with_key(&bright_quiet(), &[]);
        assert_eq!(b.min_cut_value(), 0.0);
    }

    #[test]
    fn test_tanh_values() {
        // tanh(0) = 0, tanh(2) ≈ 0.964, tanh(-2) ≈ -0.964
        assert!(
            boundary_tanh(0.0).abs() < 0.01,
            "tanh(0) = {}",
            boundary_tanh(0.0)
        );
        assert!(
            (boundary_tanh(2.0) - 0.964_f32).abs() < 0.01,
            "tanh(2) = {}",
            boundary_tanh(2.0)
        );
        assert!(
            (boundary_tanh(-2.0) + 0.964_f32).abs() < 0.01,
            "tanh(-2) = {}",
            boundary_tanh(-2.0)
        );
    }
}