use std::collections::{BTreeSet, HashMap, VecDeque};
use fv_value::Value;
use crate::acc::{as_num, value_key, Acc};
use crate::{snapshot, Agg, WindowOperator, WindowRow};
fn outranks(descending: bool, a: &Ranked, b: &Ranked) -> bool {
if a.order != b.order {
return if descending {
a.order > b.order
} else {
a.order < b.order
};
}
if a.tie != b.tie {
return a.tie < b.tie;
}
a.seq < b.seq
}
fn group_key(row: &[(String, Value)], group_by: &[String]) -> (String, Vec<Value>) {
let mut ks = String::new();
let mut vals = Vec::with_capacity(group_by.len());
for (i, g) in group_by.iter().enumerate() {
let v = row.iter().find(|(k, _)| k == g).map(|(_, v)| v);
if i > 0 {
ks.push('\u{1}');
}
ks.push_str(&value_key(v));
vals.push(v.cloned().unwrap_or(Value::Null));
}
(ks, vals)
}
#[derive(Debug, Clone)]
struct Ranked {
order: f64,
tie: f64,
seq: u64,
row: Vec<(String, Value)>,
}
#[derive(Debug, Default)]
struct TopEntry {
key: Vec<Value>,
rows: Vec<Ranked>, }
pub struct TopN {
group_by: Vec<String>,
order_by: String,
descending: bool,
n: usize,
tie_by: Option<String>,
state: HashMap<String, TopEntry>,
pending: BTreeSet<String>, seq: u64,
}
impl TopN {
pub fn new(
group_by: Vec<String>,
order_by: impl Into<String>,
descending: bool,
n: usize,
tie_by: Option<String>,
) -> Self {
Self {
group_by,
order_by: order_by.into(),
descending,
n: n.max(1),
tie_by,
state: HashMap::new(),
pending: BTreeSet::new(),
seq: 0,
}
}
fn cfg_fingerprint(&self) -> String {
format!(
"group_by={:?};order_by={};desc={};n={};tie_by={:?}",
self.group_by, self.order_by, self.descending, self.n, self.tie_by
)
}
fn push_row(&mut self, row: &[(String, Value)]) -> bool {
let Some(order) = row
.iter()
.find(|(k, _)| k == &self.order_by)
.and_then(|(_, v)| as_num(v))
else {
return false; };
let tie = self
.tie_by
.as_ref()
.and_then(|c| row.iter().find(|(k, _)| k == c).and_then(|(_, v)| as_num(v)))
.unwrap_or(0.0);
let cand = Ranked {
order,
tie,
seq: self.seq,
row: row.to_vec(),
};
self.seq += 1;
let (ks, key_vals) = group_key(row, &self.group_by);
let entry = self.state.entry(ks.clone()).or_insert_with(|| TopEntry {
key: key_vals,
rows: Vec::new(),
});
if entry.rows.len() >= self.n {
let worst = entry.rows.last().expect("n >= 1");
if !outranks(self.descending, &cand, worst) {
return true; }
}
let pos = entry
.rows
.iter()
.position(|r| outranks(self.descending, &cand, r))
.unwrap_or(entry.rows.len());
entry.rows.insert(pos, cand);
entry.rows.truncate(self.n);
self.pending.insert(ks);
true
}
fn drain(&mut self) -> Vec<WindowRow> {
let mut out = Vec::new();
for ks in std::mem::take(&mut self.pending) {
let Some(entry) = self.state.get(&ks) else { continue };
for (i, r) in entry.rows.iter().enumerate() {
let mut key = entry.key.clone();
key.push(Value::Num((i + 1) as f64));
let aggs: Vec<(String, Value)> = r
.row
.iter()
.filter(|(k, _)| !self.group_by.contains(k))
.cloned()
.collect();
out.push(WindowRow {
window_start: 0,
window_end: 0,
key,
aggs,
});
}
}
out
}
}
impl WindowOperator for TopN {
fn expect_partitions(&mut self, _partitions: &[i32], _now_ms: i64) {}
fn push(&mut self, _partition: i32, _event_ms: i64, row: &[(String, Value)]) -> bool {
self.push_row(row)
}
fn advance(&mut self, _now_ms: i64) -> Vec<WindowRow> {
self.drain()
}
fn advance_to(&mut self, _watermark_ms: i64) -> Vec<WindowRow> {
self.drain()
}
fn flush(&mut self) -> Vec<WindowRow> {
self.drain()
}
fn snapshot(&mut self) -> Result<Vec<u8>, crate::StateError> {
use serde_json::json;
let entries: Vec<serde_json::Value> = self
.state
.iter()
.map(|(ks, e)| {
json!([
ks,
e.key.iter().map(fv_value::value_to_json).collect::<Vec<_>>(),
e.rows
.iter()
.map(|r| json!([r.order, r.tie, r.seq, snapshot::row_to_json(&r.row)]))
.collect::<Vec<_>>(),
])
})
.collect();
let pending: Vec<&String> = self.pending.iter().collect();
Ok(snapshot::envelope(
"topn",
&self.cfg_fingerprint(),
json!({ "seq": self.seq, "entries": entries, "pending": pending }),
))
}
fn load_snapshot(&mut self, bytes: &[u8]) -> Result<(), String> {
let st = snapshot::open_envelope("topn", &self.cfg_fingerprint(), bytes)?;
self.seq = st["seq"].as_u64().ok_or("topn: missing seq")?;
self.state.clear();
for e in st["entries"].as_array().ok_or("topn: missing entries")? {
let t = e.as_array().filter(|a| a.len() == 3).ok_or("topn: bad entry")?;
let ks = t[0].as_str().ok_or("topn: bad entry key")?.to_string();
let key: Vec<Value> = t[1]
.as_array()
.ok_or("topn: bad key vals")?
.iter()
.map(fv_value::json_to_value)
.collect();
let mut rows = Vec::new();
for r in t[2].as_array().ok_or("topn: bad rows")? {
let q = r.as_array().filter(|a| a.len() == 4).ok_or("topn: bad ranked row")?;
rows.push(Ranked {
order: q[0].as_f64().ok_or("topn: bad order")?,
tie: q[1].as_f64().ok_or("topn: bad tie")?,
seq: q[2].as_u64().ok_or("topn: bad seq")?,
row: snapshot::row_from_json(&q[3])?,
});
}
self.state.insert(ks, TopEntry { key, rows });
}
self.pending = st["pending"]
.as_array()
.ok_or("topn: missing pending")?
.iter()
.map(|p| p.as_str().map(String::from).ok_or("topn: bad pending key".to_string()))
.collect::<Result<_, _>>()?;
Ok(())
}
}
#[derive(Debug, Default)]
struct RingEntry {
key: Vec<Value>,
rows: VecDeque<Vec<(String, Value)>>, }
pub struct LastN {
group_by: Vec<String>,
n: usize,
aggs: Vec<Agg>,
state: HashMap<String, RingEntry>,
pending: BTreeSet<String>,
}
impl LastN {
pub fn new(group_by: Vec<String>, n: usize, aggs: Vec<Agg>) -> Self {
Self {
group_by,
n: n.max(1),
aggs,
state: HashMap::new(),
pending: BTreeSet::new(),
}
}
fn cfg_fingerprint(&self) -> String {
format!("group_by={:?};n={};aggs={:?}", self.group_by, self.n, self.aggs)
}
fn drain(&mut self) -> Vec<WindowRow> {
let mut out = Vec::new();
for ks in std::mem::take(&mut self.pending) {
let Some(entry) = self.state.get(&ks) else { continue };
let mut acc = Acc::new(
self.aggs.len(),
crate::acc::needs_sets(&self.aggs),
crate::acc::needs_welford(&self.aggs),
);
for r in &entry.rows {
acc.add(&self.aggs, r);
}
out.push(WindowRow {
window_start: 0,
window_end: 0,
key: entry.key.clone(),
aggs: acc.finalize_aggs(&self.aggs),
});
}
out
}
}
impl WindowOperator for LastN {
fn expect_partitions(&mut self, _partitions: &[i32], _now_ms: i64) {}
fn push(&mut self, _partition: i32, _event_ms: i64, row: &[(String, Value)]) -> bool {
let (ks, key_vals) = group_key(row, &self.group_by);
let entry = self.state.entry(ks.clone()).or_insert_with(|| RingEntry {
key: key_vals,
rows: VecDeque::new(),
});
entry.rows.push_back(row.to_vec());
while entry.rows.len() > self.n {
entry.rows.pop_front();
}
self.pending.insert(ks);
true
}
fn advance(&mut self, _now_ms: i64) -> Vec<WindowRow> {
self.drain()
}
fn advance_to(&mut self, _watermark_ms: i64) -> Vec<WindowRow> {
self.drain()
}
fn flush(&mut self) -> Vec<WindowRow> {
self.drain()
}
fn snapshot(&mut self) -> Result<Vec<u8>, crate::StateError> {
use serde_json::json;
let entries: Vec<serde_json::Value> = self
.state
.iter()
.map(|(ks, e)| {
json!([
ks,
e.key.iter().map(fv_value::value_to_json).collect::<Vec<_>>(),
e.rows.iter().map(|r| snapshot::row_to_json(r)).collect::<Vec<_>>(),
])
})
.collect();
let pending: Vec<&String> = self.pending.iter().collect();
Ok(snapshot::envelope(
"lastn",
&self.cfg_fingerprint(),
json!({ "entries": entries, "pending": pending }),
))
}
fn load_snapshot(&mut self, bytes: &[u8]) -> Result<(), String> {
let st = snapshot::open_envelope("lastn", &self.cfg_fingerprint(), bytes)?;
self.state.clear();
for e in st["entries"].as_array().ok_or("lastn: missing entries")? {
let t = e.as_array().filter(|a| a.len() == 3).ok_or("lastn: bad entry")?;
let ks = t[0].as_str().ok_or("lastn: bad entry key")?.to_string();
let key: Vec<Value> = t[1]
.as_array()
.ok_or("lastn: bad key vals")?
.iter()
.map(fv_value::json_to_value)
.collect();
let rows: VecDeque<Vec<(String, Value)>> = t[2]
.as_array()
.ok_or("lastn: bad rows")?
.iter()
.map(snapshot::row_from_json)
.collect::<Result<_, _>>()?;
self.state.insert(ks, RingEntry { key, rows });
}
self.pending = st["pending"]
.as_array()
.ok_or("lastn: missing pending")?
.iter()
.map(|p| p.as_str().map(String::from).ok_or("lastn: bad pending key".to_string()))
.collect::<Result<_, _>>()?;
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::AggOp;
fn row(pairs: &[(&str, Value)]) -> Vec<(String, Value)> {
pairs.iter().map(|(k, v)| (k.to_string(), v.clone())).collect()
}
fn bid(auction: &str, price: f64, ts: f64) -> Vec<(String, Value)> {
row(&[
("auction", Value::Str(auction.into())),
("price", Value::Num(price)),
("ts", Value::Num(ts)),
])
}
fn ranks(fired: &[WindowRow], auction: &str) -> Vec<(f64, f64)> {
fired
.iter()
.filter(|w| w.key.first() == Some(&Value::Str(auction.into())))
.map(|w| {
let rank = match w.key.last() {
Some(Value::Num(r)) => *r,
_ => panic!("no rank"),
};
let price = w
.aggs
.iter()
.find(|(k, _)| k == "price")
.map(|(_, v)| match v {
Value::Num(p) => *p,
_ => 0.0,
})
.unwrap();
(rank, price)
})
.collect()
}
#[test]
fn topn_keeps_best_n_and_emits_on_change_only() {
let mut op = TopN::new(vec!["auction".into()], "price", true, 2, Some("ts".into()));
assert!(op.push(0, 0, &bid("a1", 10.0, 1.0)));
assert!(op.push(0, 0, &bid("a1", 30.0, 2.0)));
let fired = op.advance(0);
assert_eq!(ranks(&fired, "a1"), vec![(1.0, 30.0), (2.0, 10.0)]);
assert!(op.push(0, 0, &bid("a1", 5.0, 3.0)));
assert!(op.advance(0).is_empty());
assert!(op.push(0, 0, &bid("a1", 40.0, 4.0)));
assert_eq!(ranks(&op.advance(0), "a1"), vec![(1.0, 40.0), (2.0, 30.0)]);
}
#[test]
fn topn_tie_breaks_by_tie_column_then_arrival() {
let mut op = TopN::new(vec!["auction".into()], "price", true, 1, Some("ts".into()));
op.push(0, 0, &bid("a1", 10.0, 5.0));
op.advance(0);
op.push(0, 0, &bid("a1", 10.0, 3.0)); let fired = op.advance(0);
let ts = fired[0].aggs.iter().find(|(k, _)| k == "ts").map(|(_, v)| v.clone());
assert_eq!(ts, Some(Value::Num(3.0)));
op.push(0, 0, &bid("a1", 10.0, 3.0)); assert!(op.advance(0).is_empty());
}
#[test]
fn topn_non_numeric_order_is_rejected() {
let mut op = TopN::new(vec!["auction".into()], "price", true, 1, None);
assert!(!op.push(
0,
0,
&row(&[
("auction", Value::Str("a1".into())),
("price", Value::Str("high".into()))
])
));
assert!(op.advance(0).is_empty());
}
#[test]
fn topn_keys_are_independent_and_drained_deterministically() {
let mut op = TopN::new(vec!["auction".into()], "price", true, 1, None);
op.push(0, 0, &bid("a2", 7.0, 1.0));
op.push(0, 0, &bid("a1", 9.0, 1.0));
let fired = op.advance(0);
assert_eq!(fired.len(), 2);
assert_eq!(ranks(&fired, "a1"), vec![(1.0, 9.0)]);
assert_eq!(ranks(&fired, "a2"), vec![(1.0, 7.0)]);
}
#[test]
fn topn_snapshot_restore_fires_identically_to_uninterrupted() {
let head = [bid("a1", 10.0, 1.0), bid("a1", 30.0, 2.0), bid("a2", 5.0, 1.0)];
let tail = [bid("a1", 20.0, 3.0), bid("a2", 50.0, 2.0)];
let mk = || TopN::new(vec!["auction".into()], "price", true, 2, Some("ts".into()));
let mut uninterrupted = mk();
for r in head.iter().chain(tail.iter()) {
uninterrupted.push(0, 0, r);
}
let expected = uninterrupted.advance(0);
let mut original = mk();
for r in &head {
original.push(0, 0, r);
}
original.advance(0); let snap = original.snapshot().unwrap();
let mut restored = mk();
restored.load_snapshot(&snap).unwrap();
for r in &tail {
restored.push(0, 0, r);
}
let got = restored.advance(0);
assert_eq!(format!("{expected:?}"), format!("{got:?}"));
}
#[test]
fn topn_snapshot_refuses_config_change() {
let mut op = TopN::new(vec!["auction".into()], "price", true, 2, None);
let snap = op.snapshot().unwrap();
let mut other = TopN::new(vec!["auction".into()], "price", true, 3, None);
assert!(other.load_snapshot(&snap).unwrap_err().contains("config changed"));
}
#[test]
fn lastn_ring_evicts_oldest_and_aggregates_over_the_window_of_n() {
let mut op = LastN::new(
vec!["seller".into()],
3,
vec![Agg::of(AggOp::Avg, "price", "avgPrice"), Agg::count("n")],
);
for p in [10.0, 20.0, 30.0, 40.0] {
op.push(
0,
0,
&row(&[("seller", Value::Str("s1".into())), ("price", Value::Num(p))]),
);
}
let fired = op.advance(0);
assert_eq!(fired.len(), 1); let avg = fired[0]
.aggs
.iter()
.find(|(k, _)| k == "avgPrice")
.map(|(_, v)| v.clone());
assert_eq!(avg, Some(Value::Num(30.0))); let n = fired[0].aggs.iter().find(|(k, _)| k == "n").map(|(_, v)| v.clone());
assert_eq!(n, Some(Value::Num(3.0)));
}
#[test]
fn lastn_snapshot_restore_fires_identically() {
let mk = || LastN::new(vec!["seller".into()], 2, vec![Agg::of(AggOp::Sum, "price", "total")]);
let head = [row(&[("seller", Value::Str("s1".into())), ("price", Value::Num(5.0))])];
let tail = [row(&[("seller", Value::Str("s1".into())), ("price", Value::Num(7.0))])];
let mut uninterrupted = mk();
for r in head.iter().chain(tail.iter()) {
uninterrupted.push(0, 0, r);
}
let expected = uninterrupted.advance(0);
let mut original = mk();
for r in &head {
original.push(0, 0, r);
}
original.advance(0);
let snap = original.snapshot().unwrap();
let mut restored = mk();
restored.load_snapshot(&snap).unwrap();
for r in &tail {
restored.push(0, 0, r);
}
assert_eq!(format!("{expected:?}"), format!("{:?}", restored.advance(0)));
}
}