geographdb-core 0.5.4

//! Fractal-dimension utilities for geometric signals.
//!
//! These helpers are intentionally small and deterministic: they operate on
//! finite 1-D samples and estimate the box-counting (Minkowski–Bouligand)
//! dimension.  The intended use in the attention experiment is to quantify how
//! "spread out" a local geometric attention distribution is: a sharply peaked
//! distribution has low dimension, while a uniform or noisy distribution has
//! dimension close to one.

use std::collections::HashSet;

/// Estimate the box-counting dimension of a 1-D signal.
///
/// The signal is first normalised to the unit interval.  For a range of box
/// counts `b` (powers of two from 2 up to at most `signal.len() / 2`) we count
/// how many boxes of side `1/b` are occupied by at least one sample.  The
/// dimension is the slope of `log N(ε)` versus `log(1/ε)`.
///
/// Returns a value in `[0.0, 1.0]`.  Very short or constant signals return
/// conservative defaults (`1.0` and `0.0` respectively) so the caller can
/// decide what to do with them.
pub fn box_counting_dimension_1d(signal: &[f32]) -> f32 {
    if signal.len() < 4 {
        // Too few samples for a meaningful regression: assume line-like.
        return 1.0;
    }

    let min = signal.iter().copied().fold(f32::INFINITY, f32::min);
    let max = signal.iter().copied().fold(f32::NEG_INFINITY, f32::max);
    if !min.is_finite() || !max.is_finite() || max <= min {
        return 0.0;
    }

    let span = max - min;
    let normalised: Vec<f32> = signal.iter().map(|x| (x - min) / span).collect();

    let mut log_inv_eps = Vec::new();
    let mut log_n = Vec::new();

    let mut boxes = 2usize;
    while boxes <= signal.len() / 2 {
        let eps = 1.0 / boxes as f32;
        let mut occupied = HashSet::with_capacity(normalised.len());
        for &v in &normalised {
            let idx = (v * boxes as f32).min((boxes - 1) as f32) as usize;
            occupied.insert(idx);
        }
        let n = occupied.len().max(1);
        log_inv_eps.push((1.0 / eps).ln());
        log_n.push((n as f32).ln());
        boxes *= 2;
    }

    if log_n.len() < 2 {
        return 1.0;
    }

    let n = log_n.len() as f32;
    let sum_x: f32 = log_inv_eps.iter().sum();
    let sum_y: f32 = log_n.iter().sum();
    let sum_xy: f32 = log_inv_eps
        .iter()
        .zip(log_n.iter())
        .map(|(x, y)| x * y)
        .sum();
    let sum_x2: f32 = log_inv_eps.iter().map(|x| x * x).sum();

    let denom = n * sum_x2 - sum_x * sum_x;
    if denom.abs() < 1e-12 {
        return 1.0;
    }

    let slope = (n * sum_xy - sum_x * sum_y) / denom;
    slope.clamp(0.0, 1.0)
}

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

    #[test]
    fn constant_signal_has_dimension_zero() {
        let signal = vec![3.0f32; 16];
        assert!(box_counting_dimension_1d(&signal).abs() < 1e-6);
    }

    #[test]
    fn linear_ramp_has_dimension_near_one() {
        let signal: Vec<f32> = (0..64).map(|i| i as f32).collect();
        let dim = box_counting_dimension_1d(&signal);
        assert!(
            dim > 0.85,
            "expected linear ramp to have high dimension, got {}",
            dim
        );
    }

    #[test]
    fn single_spike_has_low_dimension() {
        let mut signal = vec![0.0f32; 32];
        signal[16] = 1.0;
        let dim = box_counting_dimension_1d(&signal);
        assert!(
            dim < 0.4,
            "expected single spike to have low dimension, got {}",
            dim
        );
    }

    #[test]
    fn shuffled_values_are_high_dimensional() {
        // A permutation-like sequence with many distinct values covers most
        // boxes at every scale, giving a dimension close to one.
        let signal: Vec<f32> = (0..64).map(|i| ((i * 31) % 64) as f32).collect();
        let dim = box_counting_dimension_1d(&signal);
        assert!(
            dim > 0.75,
            "expected shuffled sequence to be high dimensional, got {}",
            dim
        );
    }

    #[test]
    fn short_signal_defaults_to_one() {
        assert_eq!(box_counting_dimension_1d(&[1.0, 2.0]), 1.0);
    }
}