use alloc::vec::Vec;
use crate::bits::Bits;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum MatchMode {
Exact,
LongestSubset,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Tie {
AuthorOrder,
Refuse,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Hit<'a, T> {
Miss,
Hit {
mask: Bits,
priority: i16,
value: &'a T,
},
Tie {
length: u32,
n: usize,
},
}
#[derive(Clone, Debug)]
struct Row<T> {
mask: Bits,
priority: i16,
value: T,
}
#[derive(Clone, Debug)]
pub struct ChordTable<T> {
rows: Vec<Row<T>>,
mode: MatchMode,
tie: Tie,
}
impl<T> ChordTable<T> {
pub fn new() -> Self {
Self {
rows: Vec::new(),
mode: MatchMode::LongestSubset,
tie: Tie::Refuse,
}
}
pub fn exact() -> Self {
Self {
rows: Vec::new(),
mode: MatchMode::Exact,
tie: Tie::AuthorOrder,
}
}
pub fn mode(&self) -> MatchMode {
self.mode
}
pub fn tie(&self) -> Tie {
self.tie
}
pub fn set_mode(&mut self, mode: MatchMode) -> &mut Self {
self.mode = mode;
self
}
pub fn set_tie(&mut self, tie: Tie) -> &mut Self {
self.tie = tie;
self
}
pub fn insert(&mut self, mask: Bits, value: T) -> Option<T> {
self.insert_pri(mask, 0, value)
}
pub fn insert_pri(&mut self, mask: Bits, priority: i16, value: T) -> Option<T> {
if let Some(row) = self.rows.iter_mut().find(|r| r.mask == mask) {
row.priority = priority;
return Some(core::mem::replace(&mut row.value, value));
}
self.rows.push(Row {
mask,
priority,
value,
});
None
}
pub fn len(&self) -> usize {
self.rows.len()
}
pub fn is_empty(&self) -> bool {
self.rows.is_empty()
}
pub fn lookup(&self, pool: Bits) -> Hit<'_, T> {
match self.mode {
MatchMode::Exact => self.lookup_exact(pool),
MatchMode::LongestSubset => self.lookup_longest(pool),
}
}
fn lookup_exact(&self, pool: Bits) -> Hit<'_, T> {
for row in &self.rows {
if row.mask == pool {
return Hit::Hit {
mask: row.mask,
priority: row.priority,
value: &row.value,
};
}
}
Hit::Miss
}
fn lookup_longest(&self, pool: Bits) -> Hit<'_, T> {
let mut best_len = 0u32;
let mut best_pri = i16::MIN;
let mut best: Option<usize> = None;
let mut n_at_best = 0usize;
for (i, row) in self.rows.iter().enumerate() {
if !pool.contains(row.mask) {
continue;
}
let len = row.mask.count();
if best.is_none() || len > best_len || (len == best_len && row.priority > best_pri) {
best_len = len;
best_pri = row.priority;
best = Some(i);
n_at_best = 1;
} else if len == best_len && row.priority == best_pri {
n_at_best += 1;
}
}
match best {
None => Hit::Miss,
Some(_) if n_at_best > 1 && self.tie == Tie::Refuse => Hit::Tie {
length: best_len,
n: n_at_best,
},
Some(i) => {
let row = &self.rows[i];
Hit::Hit {
mask: row.mask,
priority: row.priority,
value: &row.value,
}
}
}
}
}
impl<T> Default for ChordTable<T> {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::{ChordTable, Hit, MatchMode, Tie};
use crate::bits::Bits;
fn ab() -> Bits {
Bits::from_indices([0, 1])
}
fn acd() -> Bits {
Bits::from_indices([0, 2, 3])
}
fn abd() -> Bits {
Bits::from_indices([0, 1, 3])
}
fn abcd() -> Bits {
Bits::from_indices([0, 1, 2, 3])
}
fn ac() -> Bits {
Bits::from_indices([0, 2])
}
fn table() -> ChordTable<&'static str> {
let mut t = ChordTable::new();
t.insert(ab(), "AB");
t.insert(acd(), "ACD");
t.insert(abd(), "ABD");
t
}
#[test]
fn pool_ab_hits_ab() {
match table().lookup(ab()) {
Hit::Hit { value, .. } => assert_eq!(*value, "AB"),
other => panic!("{other:?}"),
}
}
#[test]
fn pool_abcd_longer_beats_shorter() {
let mut t = ChordTable::new();
t.insert(ab(), "AB");
t.insert(abd(), "ABD");
match t.lookup(abcd()) {
Hit::Hit { value, mask, .. } => {
assert_eq!(*value, "ABD");
assert_eq!(mask, abd());
}
other => panic!("{other:?}"),
}
}
#[test]
fn pool_abcd_acd_abd_tie() {
match table().lookup(abcd()) {
Hit::Tie { length, n } => {
assert_eq!(length, 3);
assert_eq!(n, 2);
}
other => panic!("{other:?}"),
}
}
#[test]
fn same_length_refuse_is_tie() {
let mut t = ChordTable::new();
t.insert(ab(), "AB");
t.insert(ac(), "AC");
match t.lookup(Bits::from_indices([0, 1, 2])) {
Hit::Tie { length, n } => {
assert_eq!(length, 2);
assert_eq!(n, 2);
}
other => panic!("{other:?}"),
}
}
#[test]
fn same_length_author_order_picks_first() {
let mut t = ChordTable::new();
t.set_tie(Tie::AuthorOrder);
t.insert(ab(), "AB");
t.insert(ac(), "AC");
match t.lookup(Bits::from_indices([0, 1, 2])) {
Hit::Hit { value, .. } => assert_eq!(*value, "AB"),
other => panic!("{other:?}"),
}
}
#[test]
fn priority_beats_author_order() {
let mut t = ChordTable::new();
t.set_tie(Tie::AuthorOrder);
t.insert(ab(), "AB");
t.insert_pri(ac(), 1, "AC");
match t.lookup(Bits::from_indices([0, 1, 2])) {
Hit::Hit { value, .. } => assert_eq!(*value, "AC"),
other => panic!("{other:?}"),
}
}
#[test]
fn exact_unauthored_is_miss() {
let mut t = ChordTable::exact();
t.insert(ab(), "AB");
assert!(matches!(t.lookup(abcd()), Hit::Miss));
match t.lookup(ab()) {
Hit::Hit { value, .. } => assert_eq!(*value, "AB"),
other => panic!("{other:?}"),
}
}
#[test]
fn empty_table_misses() {
let t = ChordTable::<&str>::new();
assert!(matches!(t.lookup(ab()), Hit::Miss));
}
#[test]
fn exact_mode_round_trip() {
let mut t = ChordTable::new();
t.set_mode(MatchMode::Exact);
t.insert(abcd(), "ALL");
match t.lookup(abcd()) {
Hit::Hit { value, .. } => assert_eq!(*value, "ALL"),
other => panic!("{other:?}"),
}
}
}