face-core 0.1.0

//! §5.3 Top clustering: top-N by frequency plus a synthetic
//! `(other)` cluster for the long tail.
//!
//! - Records group by exact value at the axis path (same coercion rules
//!   as Exact — see [`crate::cluster_tree::util::exact_key`]).
//! - Missing-path records drop silently; present-but-uncoercible
//!   records drop and emit a [`SkipReport`] via the [`Diagnostics`]
//!   sink. This matches Exact.
//! - After grouping, take the top `n` clusters by count (count desc,
//!   label asc on ties — matches Exact). Remaining records collapse
//!   into a single synthetic `(other)` cluster appended last.
//! - When the number of distinct values is `≤ n`, no `(other)` cluster
//!   is emitted (Top behaves like Exact in this case).
//! - When `n == 0`, every record goes into `(other)` — degenerate but
//!   well-defined.
//! - Recursion into `plan.within` follows the Exact pattern; the
//!   `(other)` cluster recurses on its remaining record subset.

use std::{cmp::Reverse, collections::BTreeMap};

use serde_json::Value;

use crate::{
    Cluster, ClusterId, Diagnostics, FaceError, Record, SkipReason, SkipReport, Strategy,
    cluster_tree::{
        AxisPlan, build_tree_impl, extend_id,
        util::{exact_key, json_kind, score_range},
    },
};

/// Label and serialized value for the synthetic long-tail cluster.
const OTHER_LABEL: &str = "(other)";

/// Cluster `items` by top-`n` exact value at `plan.axis.field`,
/// rolling the rest into a single `(other)` cluster.
pub(super) fn cluster<D: Diagnostics + ?Sized>(
    plan: &AxisPlan,
    items: Vec<Record>,
    parent: &ClusterId,
    diag: &mut D,
) -> Result<Vec<Cluster>, FaceError> {
    let Strategy::Top { n } = &plan.axis.strategy else {
        unreachable!("top clusterer is only called for Strategy::Top")
    };
    let n = *n as usize;

    // Group by exact-key. Same drop-with-skip semantics as Exact.
    let mut groups: BTreeMap<String, Vec<Record>> = BTreeMap::new();
    let field = plan.axis.field.as_str();
    for (index, record) in items.into_iter().enumerate() {
        let Ok(resolved) = crate::path::resolve(&record.raw, field) else {
            continue;
        };
        let Some(key) = exact_key(resolved) else {
            // Value present but uncoercible — surface with the value's
            // kind so the user sees what tripped the strategy. (Same
            // policy as Exact.)
            diag.record_skip(SkipReport {
                record_index: index,
                reason: SkipReason::WrongType {
                    field: plan.axis.field.clone(),
                    kind: json_kind(resolved).to_string(),
                },
            });
            continue;
        };
        groups.entry(key).or_default().push(record);
    }

    // Stable sort: count desc; BTreeMap iteration provides label-asc.
    let mut ordered: Vec<(String, Vec<Record>)> = groups.into_iter().collect();
    ordered.sort_by_key(|(_, group)| Reverse(group.len()));

    // Split into top-N and the long tail. `split_off(n)` is bounded by
    // the vector length so it handles `n >= ordered.len()` cleanly.
    let split_at = n.min(ordered.len());
    let tail = ordered.split_off(split_at);
    let top = ordered;

    let mut out = Vec::with_capacity(top.len() + usize::from(!tail.is_empty()));

    for (label, group) in top {
        let id = extend_id(parent, &plan.axis.field, &label);
        let total = group.len() as u64;
        let (score_min, score_max) = score_range(&group);

        let children = recurse_within(plan, &id, &group, diag)?;

        out.push(Cluster {
            id,
            label: label.clone(),
            axis: plan.axis.field.clone(),
            value: Value::String(label),
            total,
            score_min,
            score_max,
            clusters: children,
        });
    }

    if !tail.is_empty() {
        // Flatten remaining records into one synthetic group.
        let mut remaining: Vec<Record> = Vec::new();
        for (_, group) in tail {
            remaining.extend(group);
        }
        let id = extend_id(parent, &plan.axis.field, OTHER_LABEL);
        let total = remaining.len() as u64;
        let (score_min, score_max) = score_range(&remaining);

        let children = recurse_within(plan, &id, &remaining, diag)?;

        out.push(Cluster {
            id,
            label: OTHER_LABEL.to_string(),
            axis: plan.axis.field.clone(),
            value: Value::String(OTHER_LABEL.to_string()),
            total,
            score_min,
            score_max,
            clusters: children,
        });
    }

    Ok(out)
}

/// Run each `plan.within` sub-plan over `group` and concatenate the
/// resulting children, mirroring Exact's recursion.
fn recurse_within<D: Diagnostics + ?Sized>(
    plan: &AxisPlan,
    id: &ClusterId,
    group: &[Record],
    diag: &mut D,
) -> Result<Vec<Cluster>, FaceError> {
    if plan.within.is_empty() {
        return Ok(Vec::new());
    }
    let mut acc: Vec<Cluster> = Vec::new();
    for child_plan in &plan.within {
        let child_clusters = build_tree_impl(child_plan, group.to_vec(), id, diag)?;
        acc.extend(child_clusters);
    }
    Ok(acc)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{Axis, NullDiagnostics, Strategy};
    use serde_json::json;

    fn axis(field: &str, n: u32) -> Axis {
        Axis {
            field: field.into(),
            strategy: Strategy::Top { n },
            auto: false,
        }
    }

    #[test]
    fn keeps_top_n_and_collapses_rest_to_other() {
        let plan = AxisPlan::leaf(axis("kind", 2));
        let items = vec![
            json!({"kind": "a"}),
            json!({"kind": "a"}),
            json!({"kind": "a"}),
            json!({"kind": "b"}),
            json!({"kind": "b"}),
            json!({"kind": "c"}),
            json!({"kind": "d"}),
        ];
        let mut diag = NullDiagnostics;
        let clusters = super::cluster(
            &plan,
            Record::from_items(items, None),
            &ClusterId::default(),
            &mut diag,
        )
        .unwrap();
        // top-2 = a (3), b (2); rest (c, d) collapsed into (other).
        assert_eq!(clusters.len(), 3);
        assert_eq!(clusters[0].label, "a");
        assert_eq!(clusters[0].total, 3);
        assert_eq!(clusters[1].label, "b");
        assert_eq!(clusters[1].total, 2);
        // (other) is always last.
        assert_eq!(clusters[2].label, "(other)");
        assert_eq!(clusters[2].total, 2);
        assert_eq!(clusters[2].value, json!("(other)"));
    }

    #[test]
    fn no_other_when_distinct_values_le_n() {
        let plan = AxisPlan::leaf(axis("kind", 5));
        let items = vec![
            json!({"kind": "a"}),
            json!({"kind": "b"}),
            json!({"kind": "a"}),
        ];
        let mut diag = NullDiagnostics;
        let clusters = super::cluster(
            &plan,
            Record::from_items(items, None),
            &ClusterId::default(),
            &mut diag,
        )
        .unwrap();
        assert_eq!(clusters.len(), 2);
        assert_eq!(clusters[0].label, "a");
        assert_eq!(clusters[1].label, "b");
        assert!(
            clusters.iter().all(|c| c.label != "(other)"),
            "no synthetic cluster expected when distinct values ≤ n",
        );
    }

    #[test]
    fn n_zero_collapses_all_to_other() {
        let plan = AxisPlan::leaf(axis("kind", 0));
        let items = vec![
            json!({"kind": "a"}),
            json!({"kind": "b"}),
            json!({"kind": "a"}),
        ];
        let mut diag = NullDiagnostics;
        let clusters = super::cluster(
            &plan,
            Record::from_items(items, None),
            &ClusterId::default(),
            &mut diag,
        )
        .unwrap();
        assert_eq!(clusters.len(), 1);
        assert_eq!(clusters[0].label, "(other)");
        assert_eq!(clusters[0].total, 3);
    }

    #[test]
    fn other_id_extends_parent() {
        let plan = AxisPlan::leaf(axis("kind", 1));
        let items = vec![
            json!({"kind": "a"}),
            json!({"kind": "a"}),
            json!({"kind": "b"}),
        ];
        let mut diag = NullDiagnostics;
        let clusters = super::cluster(
            &plan,
            Record::from_items(items, None),
            &ClusterId::default(),
            &mut diag,
        )
        .unwrap();
        let other = clusters.iter().find(|c| c.label == "(other)").unwrap();
        assert_eq!(other.id.depth(), 1);
        assert_eq!(other.id.segments()[0].axis, "kind");
        assert_eq!(other.id.segments()[0].value, "(other)");
    }

    #[test]
    fn within_recurses_inside_other() {
        // Top by `kind` with n=1, then exact by `tag` inside each.
        let outer = axis("kind", 1);
        let inner = Axis {
            field: "tag".into(),
            strategy: Strategy::Exact,
            auto: false,
        };
        let plan = AxisPlan::with(outer, AxisPlan::leaf(inner));
        let items = vec![
            json!({"kind": "a", "tag": "x"}),
            json!({"kind": "a", "tag": "x"}),
            json!({"kind": "b", "tag": "y"}),
            json!({"kind": "c", "tag": "y"}),
        ];
        let mut diag = NullDiagnostics;
        let clusters = super::cluster(
            &plan,
            Record::from_items(items, None),
            &ClusterId::default(),
            &mut diag,
        )
        .unwrap();
        // top: a (2); other: b + c (2 records, both tag=y).
        assert_eq!(clusters.len(), 2);
        let other = clusters.iter().find(|c| c.label == "(other)").unwrap();
        assert_eq!(other.total, 2);
        assert_eq!(other.clusters.len(), 1);
        assert_eq!(other.clusters[0].label, "y");
        assert_eq!(other.clusters[0].total, 2);
    }
}