rich_ext/table/
sort.rs

1//! Stable multi-column sorting of table rows.
2//!
3//! Rows are any `AsRef<[Value]>` (a `Vec<Value>`, an array, a slice). Each
4//! [`SortKey`] names a column, a direction and a [`Compare`] mode; later keys
5//! break ties of earlier ones and rows equal on every key keep their order
6//! (the sort is stable). Empty cells ([`Value::is_empty`]) sort last in both
7//! directions.
8//!
9//! [`Compare::Natural`] (the default) compares numbers numerically, strings
10//! that are numbers as numbers, and other strings with digit runs by value, so
11//! `file9` sorts before `file10`. Numbers sort before text.
12//!
13//! ```
14//! use rich_ext::table::sort::{sort_rows, SortKey};
15//! use rich_ext::table::Value;
16//!
17//! let mut rows = vec![
18//!     vec![Value::from("b"), Value::from("file10")],
19//!     vec![Value::from("a"), Value::from("file9")],
20//!     vec![Value::from("b"), Value::from("file2")],
21//!     vec![Value::from("a"), Value::Null],
22//! ];
23//! sort_rows(&mut rows, &[SortKey::desc(0), SortKey::asc(1)]);
24//! let plain: Vec<String> = rows.iter().map(|r| r[1].plain()).collect();
25//! assert_eq!(plain, ["file2", "file10", "file9", ""]);
26//! ```
27
28use std::cmp::Ordering;
29
30use super::Value;
31
32/// A sort direction.
33#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
34pub enum Order {
35    /// Smallest first.
36    #[default]
37    Ascending,
38    /// Largest first.
39    Descending,
40}
41
42/// How two non-empty cells compare.
43#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
44pub enum Compare {
45    /// Numbers numerically, numeric strings as numbers, other strings
46    /// case-insensitively with digit runs by value (`a2 < a10`).
47    #[default]
48    Natural,
49    /// The plain display strings, byte by byte.
50    Lexical,
51}
52
53/// One sort criterion: a column index, a direction and a comparison.
54#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
55pub struct SortKey {
56    /// The column index.
57    pub column: usize,
58    /// The direction.
59    pub order: Order,
60    /// The comparison.
61    pub compare: Compare,
62}
63
64impl SortKey {
65    /// Ascending, natural comparison.
66    pub fn asc(column: usize) -> Self {
67        SortKey {
68            column,
69            order: Order::Ascending,
70            compare: Compare::Natural,
71        }
72    }
73
74    /// Descending, natural comparison.
75    pub fn desc(column: usize) -> Self {
76        SortKey {
77            order: Order::Descending,
78            ..SortKey::asc(column)
79        }
80    }
81
82    /// Compare this key's cells as plain strings.
83    pub fn lexical(mut self) -> Self {
84        self.compare = Compare::Lexical;
85        self
86    }
87}
88
89/// The header indicator for a direction: `▲`/`▼`, or `^`/`v` when `ascii`.
90pub fn indicator(order: Order, ascii: bool) -> &'static str {
91    match (order, ascii) {
92        (Order::Ascending, false) => "▲",
93        (Order::Descending, false) => "▼",
94        (Order::Ascending, true) => "^",
95        (Order::Descending, true) => "v",
96    }
97}
98
99/// A number parsed from a string that is only a number (`-1.5`, `42`,
100/// `1e3`); words such as `inf` or `nan` are not numbers here.
101fn numeric_str(s: &str) -> Option<f64> {
102    let s = s.trim();
103    let digits = s.trim_start_matches(['-', '+']).trim_start_matches('.');
104    if !digits.starts_with(|c: char| c.is_ascii_digit()) {
105        return None;
106    }
107    s.parse::<f64>().ok()
108}
109
110/// The number a cell stands for under natural comparison.
111fn numeric(value: &Value) -> Option<f64> {
112    match value {
113        Value::Int(n) => Some(*n as f64),
114        Value::Float(f) => Some(*f),
115        Value::Str(s) => numeric_str(s),
116        Value::Text(t) => numeric_str(t.plain()),
117        Value::Null => None,
118    }
119}
120
121/// Compare two cells under `compare`, ascending. Empty cells sort after
122/// non-empty ones; two empty cells are equal.
123pub fn compare_values(a: &Value, b: &Value, compare: Compare) -> Ordering {
124    match (a.is_empty(), b.is_empty()) {
125        (true, true) => return Ordering::Equal,
126        (true, false) => return Ordering::Greater,
127        (false, true) => return Ordering::Less,
128        (false, false) => {}
129    }
130    match compare {
131        Compare::Lexical => a.plain().cmp(&b.plain()),
132        Compare::Natural => {
133            if let (Value::Int(x), Value::Int(y)) = (a, b) {
134                return x.cmp(y);
135            }
136            match (numeric(a), numeric(b)) {
137                (Some(x), Some(y)) => x.total_cmp(&y),
138                (Some(_), None) => Ordering::Less,
139                (None, Some(_)) => Ordering::Greater,
140                (None, None) => natural_cmp(&a.plain(), &b.plain()),
141            }
142        }
143    }
144}
145
146/// Natural string order: digit runs compare by value, other runs
147/// case-insensitively; exact ties fall back to byte order.
148///
149/// ```
150/// use std::cmp::Ordering;
151/// use rich_ext::table::sort::natural_cmp;
152///
153/// assert_eq!(natural_cmp("v1.9", "v1.10"), Ordering::Less);
154/// assert_eq!(natural_cmp("Beta", "alpha"), Ordering::Greater);
155/// ```
156pub fn natural_cmp(a: &str, b: &str) -> Ordering {
157    let (mut x, mut y) = (a, b);
158    loop {
159        match (x.chars().next(), y.chars().next()) {
160            (None, None) => return a.cmp(b),
161            (None, Some(_)) => return Ordering::Less,
162            (Some(_), None) => return Ordering::Greater,
163            (Some(c), Some(d)) if c.is_ascii_digit() && d.is_ascii_digit() => {
164                let (run_x, rest_x) = split_digits(x);
165                let (run_y, rest_y) = split_digits(y);
166                let (value_x, value_y) =
167                    (run_x.trim_start_matches('0'), run_y.trim_start_matches('0'));
168                let order = value_x
169                    .len()
170                    .cmp(&value_y.len())
171                    .then_with(|| value_x.cmp(value_y));
172                if order != Ordering::Equal {
173                    return order;
174                }
175                (x, y) = (rest_x, rest_y);
176            }
177            (Some(c), Some(d)) => {
178                let order = c.to_lowercase().cmp(d.to_lowercase());
179                if order != Ordering::Equal {
180                    return order;
181                }
182                (x, y) = (&x[c.len_utf8()..], &y[d.len_utf8()..]);
183            }
184        }
185    }
186}
187
188fn split_digits(s: &str) -> (&str, &str) {
189    let end = s.find(|c: char| !c.is_ascii_digit()).unwrap_or(s.len());
190    s.split_at(end)
191}
192
193/// Compare two rows by `keys`, in priority order. Empty cells (and missing
194/// ones) sort last whatever the key's direction.
195pub fn compare_rows(a: &[Value], b: &[Value], keys: &[SortKey]) -> Ordering {
196    const NULL: Value = Value::Null;
197    for key in keys {
198        let x = a.get(key.column).unwrap_or(&NULL);
199        let y = b.get(key.column).unwrap_or(&NULL);
200        let order = match (x.is_empty(), y.is_empty()) {
201            (false, false) => {
202                let order = compare_values(x, y, key.compare);
203                match key.order {
204                    Order::Ascending => order,
205                    Order::Descending => order.reverse(),
206                }
207            }
208            // Empties stay last in both directions.
209            _ => compare_values(x, y, key.compare),
210        };
211        if order != Ordering::Equal {
212            return order;
213        }
214    }
215    Ordering::Equal
216}
217
218/// Sort rows in place by `keys`. Stable: rows equal on every key keep their
219/// relative order.
220pub fn sort_rows<R: AsRef<[Value]>>(rows: &mut [R], keys: &[SortKey]) {
221    if keys.is_empty() {
222        return;
223    }
224    rows.sort_by(|a, b| compare_rows(a.as_ref(), b.as_ref(), keys));
225}
226
227/// The indices of `rows` in sorted order, leaving the rows where they are.
228/// Stable, as [`sort_rows`].
229pub fn sorted_indices<R: AsRef<[Value]>>(rows: &[R], keys: &[SortKey]) -> Vec<usize> {
230    let mut order: Vec<usize> = (0..rows.len()).collect();
231    if !keys.is_empty() {
232        order.sort_by(|&a, &b| compare_rows(rows[a].as_ref(), rows[b].as_ref(), keys));
233    }
234    order
235}
236
237#[cfg(test)]
238mod tests {
239    use super::*;
240
241    #[test]
242    fn natural_order_handles_digits_case_and_leading_zeros() {
243        let mut words = vec!["a10", "A2", "a2", "a02", "b", "a1b", ""];
244        words.sort_by(|a, b| natural_cmp(a, b));
245        assert_eq!(words, ["", "a1b", "A2", "a02", "a2", "a10", "b"]);
246    }
247
248    #[test]
249    fn numbers_sort_before_text_and_numeric_strings_as_numbers() {
250        let mut values = [
251            Value::from("x"),
252            Value::from("10"),
253            Value::Float(2.5),
254            Value::Int(-3),
255            Value::from("-4.5"),
256            Value::Null,
257        ];
258        values.sort_by(|a, b| compare_values(a, b, Compare::Natural));
259        let plain: Vec<String> = values.iter().map(Value::plain).collect();
260        assert_eq!(plain, ["-4.5", "-3", "2.5", "10", "x", ""]);
261        values.sort_by(|a, b| compare_values(a, b, Compare::Lexical));
262        let plain: Vec<String> = values.iter().map(Value::plain).collect();
263        assert_eq!(plain, ["-3", "-4.5", "10", "2.5", "x", ""]);
264    }
265}
rich_ext/table/sort.rs

rich_ext/table/
sort.rs
