← snapshot

//! The `MinHash` sketch itself.

use core::fmt;

use serde::{Deserialize, Serialize};

/// Number of lanes (independent min-hash functions) in a sketch.
///
/// 64 lanes bounds the standard error of the Jaccard estimate at
/// `1/sqrt(64) = 12.5%`. Enough to separate "same topic" from "unrelated";
/// deliberately not enough to fingerprint fine structure.
pub const SKETCH_LANES: usize = 64;

/// Estimated Jaccard similarity in `[0, 1]`, stored as permille.
///
/// A `u16` rather than a float so similarity is `Eq`/`Ord` and thresholds
/// never hit float-comparison traps.
#[derive(
    Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize, Default,
)]
#[serde(transparent)]
pub struct Similarity(u16);

impl Similarity {
    /// No lanes agree.
    pub const NONE: Self = Self(0);

    /// Every lane agrees.
    pub const IDENTICAL: Self = Self(1000);

    /// Constructs a similarity from permille, saturating at 1000.
    #[must_use]
    pub const fn from_permille(v: u16) -> Self {
        if v > 1000 { Self(1000) } else { Self(v) }
    }

    /// The value in permille (0..=1000).
    #[must_use]
    pub const fn permille(self) -> u16 {
        self.0
    }
}

impl fmt::Display for Similarity {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}.{:01}%", self.0 / 10, self.0 % 10)
    }
}

/// A `MinHash` sketch: 64 `u64` minima over the input's shingles.
///
/// There is no accessor that returns, reconstructs, or iterates input
/// content, because none can exist: the minima are one-way images of the
/// shingles that produced them. The only observations a holder can make are
/// equality and [`similarity`](Self::similarity).
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct MinHashSketch(pub(crate) [u64; SKETCH_LANES]);

// Serde impls are written by hand because derive stops at 32-element arrays.
// The wire form is a fixed-length sequence of 64 u64 lane minima.
impl Serialize for MinHashSketch {
    fn serialize<S: serde::Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
        use serde::ser::SerializeTuple as _;
        let mut t = s.serialize_tuple(SKETCH_LANES)?;
        for lane in &self.0 {
            t.serialize_element(lane)?;
        }
        t.end()
    }
}

impl<'de> Deserialize<'de> for MinHashSketch {
    fn deserialize<D: serde::Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
        struct V;
        impl<'de> serde::de::Visitor<'de> for V {
            type Value = MinHashSketch;

            fn expecting(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
                write!(f, "a sequence of {SKETCH_LANES} u64 lane minima")
            }

            fn visit_seq<A: serde::de::SeqAccess<'de>>(
                self,
                mut seq: A,
            ) -> Result<MinHashSketch, A::Error> {
                let mut lanes = [0u64; SKETCH_LANES];
                for (i, lane) in lanes.iter_mut().enumerate() {
                    *lane = seq
                        .next_element()?
                        .ok_or_else(|| serde::de::Error::invalid_length(i, &self))?;
                }
                Ok(MinHashSketch(lanes))
            }
        }
        d.deserialize_tuple(SKETCH_LANES, V)
    }
}

impl MinHashSketch {
    /// Estimated Jaccard similarity: the fraction of lanes that agree.
    #[must_use]
    pub fn similarity(&self, other: &Self) -> Similarity {
        let equal = self
            .0
            .iter()
            .zip(other.0.iter())
            .filter(|(a, b)| a == b)
            .count();
        // equal <= 64, so the arithmetic stays far inside u16.
        let permille = (equal * 1000) / SKETCH_LANES;
        Similarity::from_permille(u16::try_from(permille).unwrap_or(1000))
    }

    /// Number of lanes. Exposed so narration can say what a sketch is.
    #[must_use]
    pub const fn lanes(&self) -> usize {
        SKETCH_LANES
    }
}

impl fmt::Debug for MinHashSketch {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        // Deliberately abbreviated: even the debug form shows the shape, not
        // the 64 minima, so a stray log line stays boring.
        write!(f, "MinHashSketch({SKETCH_LANES} lanes)")
    }
}

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

    #[test]
    fn identical_sketches_are_identical() {
        let s = MinHashSketch([7; SKETCH_LANES]);
        assert_eq!(s.similarity(&s), Similarity::IDENTICAL);
    }

    #[test]
    fn disjoint_sketches_score_zero() {
        let a = MinHashSketch(core::array::from_fn(|i| i as u64));
        let b = MinHashSketch(core::array::from_fn(|i| (i + 1000) as u64));
        assert_eq!(a.similarity(&b), Similarity::NONE);
    }

    #[test]
    fn similarity_saturates() {
        assert_eq!(Similarity::from_permille(2000), Similarity::IDENTICAL);
    }
}