use std::cmp::Ordering;
use crate::quiver::ArrowId;
pub const ORDER_ID: &str = "deglex-arrowid-v1";
pub fn word_cmp(a: &[ArrowId], b: &[ArrowId]) -> Ordering {
a.len().cmp(&b.len()).then_with(|| a.cmp(b))
}
#[cfg(test)]
mod tests {
use super::*;
fn w(ids: &[u32]) -> Vec<ArrowId> {
ids.iter().copied().map(ArrowId).collect()
}
fn words_up_to(max_len: usize) -> Vec<Vec<ArrowId>> {
let mut all = vec![Vec::new()];
let mut level = vec![Vec::new()];
for _ in 0..max_len {
let mut next = Vec::new();
for word in &level {
for id in [ArrowId(0), ArrowId(1)] {
let mut extended = word.clone();
extended.push(id);
next.push(extended);
}
}
all.extend(next.iter().cloned());
level = next;
}
all
}
#[test]
fn longer_word_is_larger() {
assert_eq!(word_cmp(&w(&[1, 1]), &w(&[0, 0, 0])), Ordering::Less);
assert_eq!(word_cmp(&w(&[0, 0, 0]), &w(&[1, 1])), Ordering::Greater);
assert_eq!(word_cmp(&w(&[]), &w(&[0])), Ordering::Less);
}
#[test]
fn equal_length_compares_lexicographically_by_arrow_id() {
assert_eq!(word_cmp(&w(&[0, 1]), &w(&[1, 0])), Ordering::Less);
assert_eq!(word_cmp(&w(&[1, 0]), &w(&[0, 1])), Ordering::Greater);
assert_eq!(word_cmp(&w(&[0, 2, 5]), &w(&[0, 3, 0])), Ordering::Less);
}
#[test]
fn equal_words_compare_equal() {
for word in words_up_to(3) {
assert_eq!(word_cmp(&word, &word), Ordering::Equal);
}
}
#[test]
fn antisymmetric_on_all_short_words() {
let all = words_up_to(3);
for a in &all {
for b in &all {
assert_eq!(word_cmp(a, b), word_cmp(b, a).reverse(), "{a:?} {b:?}");
}
}
}
#[test]
fn transitive_on_all_short_words() {
let all = words_up_to(3);
for a in &all {
for b in &all {
for c in &all {
if word_cmp(a, b) == Ordering::Less && word_cmp(b, c) == Ordering::Less {
assert_eq!(word_cmp(a, c), Ordering::Less, "{a:?} {b:?} {c:?}");
}
}
}
}
}
#[test]
fn compatible_with_concatenation_on_both_sides() {
let all = words_up_to(3);
let contexts = words_up_to(2);
for a in &all {
for b in &all {
if word_cmp(a, b) != Ordering::Less {
continue;
}
for ctx in &contexts {
let left_a: Vec<ArrowId> = ctx.iter().chain(a).copied().collect();
let left_b: Vec<ArrowId> = ctx.iter().chain(b).copied().collect();
assert_eq!(word_cmp(&left_a, &left_b), Ordering::Less);
let right_a: Vec<ArrowId> = a.iter().chain(ctx).copied().collect();
let right_b: Vec<ArrowId> = b.iter().chain(ctx).copied().collect();
assert_eq!(word_cmp(&right_a, &right_b), Ordering::Less);
}
}
}
}
}