use std::collections::BTreeMap;
use std::io;
use crate::link::Link;
mod command;
pub(crate) use command::run_on;
#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
#[non_exhaustive]
pub struct Overlap {
pub owners: usize,
pub names: usize,
pub shared: usize,
pub examples: Vec<(String, Vec<String>)>,
pub skipped: usize,
}
pub fn overlap(client: &mut dyn Link, prefix: &str) -> io::Result<Overlap> {
let keys = crate::collections::scan_prefix(client, prefix)?;
let mut owners_of: BTreeMap<Vec<u8>, Vec<String>> = BTreeMap::new();
let (mut owners, mut skipped) = (0usize, 0usize);
for k in &keys {
let owner = String::from_utf8_lossy(k).into_owned();
let Some(ms) = crate::collections::members_if_collection(client, &owner)? else {
skipped += 1;
continue;
};
owners += 1;
for m in ms {
owners_of.entry(m).or_default().push(owner.clone());
}
}
let mut o = tally(owners, &owners_of);
o.skipped = skipped;
Ok(o)
}
fn tally(owners: usize, owners_of: &BTreeMap<Vec<u8>, Vec<String>>) -> Overlap {
let shared: Vec<_> = owners_of.iter().filter(|(_, o)| o.len() > 1).collect();
Overlap {
owners,
skipped: 0,
names: owners_of.len(),
shared: shared.len(),
examples: shared
.iter()
.take(5)
.map(|(n, o)| (String::from_utf8_lossy(n).into_owned(), (*o).clone()))
.collect(),
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
#[non_exhaustive]
pub struct Coincidence {
pub a: String,
pub b: String,
pub same: usize,
pub compared: usize,
}
impl Coincidence {
pub fn percent(&self) -> u32 {
(self.same * 100).checked_div(self.compared).unwrap_or(0) as u32
}
}
pub fn column_pairs(
client: &mut dyn Link,
prefix: &str,
sample: usize,
threshold: u32,
) -> io::Result<(usize, Vec<Coincidence>)> {
let keys = crate::collections::scan_prefix(client, prefix)?;
let mut rows = Vec::new();
for k in keys.iter().take(sample) {
let row = hgetall(client, k)?;
if !row.is_empty() {
rows.push(row);
}
}
Ok((rows.len(), coincidences(&rows, threshold)))
}
fn coincidences(rows: &[BTreeMap<String, Vec<u8>>], threshold: u32) -> Vec<Coincidence> {
let mut pairs: BTreeMap<(String, String), (usize, usize)> = BTreeMap::new();
for row in rows {
let cols: Vec<&String> = row.keys().collect();
for (i, a) in cols.iter().enumerate() {
for b in &cols[i + 1..] {
let e = pairs.entry(((*a).clone(), (*b).clone())).or_insert((0, 0));
e.1 += 1;
if row[*a] == row[*b] {
e.0 += 1;
}
}
}
}
let mut out: Vec<Coincidence> = pairs
.into_iter()
.map(|((a, b), (same, compared))| Coincidence { a, b, same, compared })
.filter(|c| c.percent() >= threshold)
.collect();
out.sort_by(|x, y| y.percent().cmp(&x.percent()).then(x.a.cmp(&y.a)));
out
}
fn hgetall(client: &mut dyn Link, key: &[u8]) -> io::Result<BTreeMap<String, Vec<u8>>> {
let reply = client.request_borrowed(&[b"HGETALL", key])?;
let flat = crate::collections::bulks(reply);
Ok(flat
.chunks(2)
.filter(|c| c.len() == 2)
.map(|c| (String::from_utf8_lossy(&c[0]).into_owned(), c[1].clone()))
.collect())
}
#[cfg(test)]
mod tests {
use super::*;
fn under(pairs: &[(&str, &[&str])]) -> BTreeMap<Vec<u8>, Vec<String>> {
let mut m: BTreeMap<Vec<u8>, Vec<String>> = BTreeMap::new();
for (name, owners) in pairs {
m.insert(name.as_bytes().to_vec(), owners.iter().map(|o| o.to_string()).collect());
}
m
}
fn row(fields: &[(&str, &str)]) -> BTreeMap<String, Vec<u8>> {
fields.iter().map(|(k, v)| (k.to_string(), v.as_bytes().to_vec())).collect()
}
#[test]
fn a_name_under_two_owners_is_the_multi_valued_signal() {
let o = tally(2, &under(&[("t1", &["m:1"]), ("t2", &["m:1", "m:2"]), ("t3", &["m:2"])]));
assert_eq!((o.names, o.shared), (3, 1));
assert_eq!(o.examples[0].0, "t2");
assert_eq!(o.examples[0].1, ["m:1", "m:2"]);
}
#[test]
fn disjoint_owners_leave_nothing_shared() {
let o = tally(2, &under(&[("x", &["a"]), ("y", &["b"])]));
assert_eq!(o.shared, 0);
}
#[test]
fn a_copied_column_shows_up_below_perfect_agreement() {
let mut rows: Vec<_> =
(0..9).map(|i| row(&[("a", "1"), ("b", "1"), ("c", &format!("{i}"))])).collect();
rows.push(row(&[("a", "1"), ("b", "2"), ("c", "9")]));
let found = coincidences(&rows, 90);
let named: Vec<&str> = found.iter().map(|c| c.a.as_str()).collect();
assert_eq!(found.len(), 1, "only a/b agree enough, got {named:?}");
assert_eq!((found[0].a.as_str(), found[0].b.as_str()), ("a", "b"));
assert_eq!(found[0].percent(), 90);
}
#[test]
fn a_threshold_above_the_agreement_reports_nothing() {
let rows = vec![row(&[("a", "1"), ("b", "1")]), row(&[("a", "1"), ("b", "2")])];
assert!(coincidences(&rows, 60).is_empty());
assert_eq!(coincidences(&rows, 50).len(), 1);
}
}