1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//! The sealed admissible order `deglex-arrowid-v1` on path words.
//!
//! The crate has exactly one order, identified by [`ORDER_ID`]. Completion,
//! certificates, and the verifier all use it. There is no user-supplied
//! comparator.
//!
//! The order is admissible:
//!
//! - Well-founded: a quiver has finitely many arrows, so only finitely many
//! words are smaller than any given word. Every strictly decreasing chain
//! is finite.
//! - Total on the paths between any two fixed vertices, because it is total
//! on all arrow sequences.
//! - Compatible with concatenation on both sides where products are defined:
//! `a < b` implies `w·a < w·b` and `a·w < b·w`. Lengths grow by the same
//! amount, and on equal length the shared factor `w` never decides the
//! lexicographic comparison.
use std::cmp::Ordering;
use crate::quiver::ArrowId;
/// Identifies the sealed order in certificates.
pub const ORDER_ID: &str = "deglex-arrowid-v1";
/// Degree-lexicographic comparison of arrow words.
///
/// Compares length first: the longer word is the larger word. On equal
/// length, compares the arrow sequences lexicographically by [`ArrowId`]
/// numeric order: the larger sequence is the larger word.
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()
}
/// All words over arrows `0` and `1` with length at most `max_len`.
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);
}
}
}
}
}