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    #[must_use]
84    pub fn lexical(mut self) -> Self {
85        self.compare = Compare::Lexical;
86        self
87    }
88}
89
90/// The header indicator for a direction: `▲`/`▼`, or `^`/`v` when `ascii`.
91pub fn indicator(order: Order, ascii: bool) -> &'static str {
92    match (order, ascii) {
93        (Order::Ascending, false) => "▲",
94        (Order::Descending, false) => "▼",
95        (Order::Ascending, true) => "^",
96        (Order::Descending, true) => "v",
97    }
98}
99
100/// A number parsed from a string that is only a number (`-1.5`, `42`,
101/// `1e3`); words such as `inf` or `nan` are not numbers here.
102fn numeric_str(s: &str) -> Option<f64> {
103    let s = s.trim();
104    let digits = s.trim_start_matches(['-', '+']).trim_start_matches('.');
105    if !digits.starts_with(|c: char| c.is_ascii_digit()) {
106        return None;
107    }
108    s.parse::<f64>().ok()
109}
110
111/// The number a cell stands for under natural comparison.
112fn numeric(value: &Value) -> Option<f64> {
113    match value {
114        Value::Int(n) => Some(*n as f64),
115        Value::Float(f) => Some(*f),
116        Value::Str(s) => numeric_str(s),
117        Value::Text(t) => numeric_str(t.plain()),
118        Value::Null => None,
119    }
120}
121
122/// Compare two cells under `compare`, ascending. Empty cells sort after
123/// non-empty ones; two empty cells are equal.
124pub fn compare_values(a: &Value, b: &Value, compare: Compare) -> Ordering {
125    match (a.is_empty(), b.is_empty()) {
126        (true, true) => return Ordering::Equal,
127        (true, false) => return Ordering::Greater,
128        (false, true) => return Ordering::Less,
129        (false, false) => {}
130    }
131    match compare {
132        Compare::Lexical => a.plain().cmp(&b.plain()),
133        Compare::Natural => {
134            if let (Value::Int(x), Value::Int(y)) = (a, b) {
135                return x.cmp(y);
136            }
137            match (numeric(a), numeric(b)) {
138                (Some(x), Some(y)) => x.total_cmp(&y),
139                (Some(_), None) => Ordering::Less,
140                (None, Some(_)) => Ordering::Greater,
141                (None, None) => natural_cmp(&a.plain(), &b.plain()),
142            }
143        }
144    }
145}
146
147/// Natural string order: digit runs compare by value, other runs
148/// case-insensitively; exact ties fall back to byte order.
149///
150/// ```
151/// use std::cmp::Ordering;
152/// use rich_ext::table::sort::natural_cmp;
153///
154/// assert_eq!(natural_cmp("v1.9", "v1.10"), Ordering::Less);
155/// assert_eq!(natural_cmp("Beta", "alpha"), Ordering::Greater);
156/// ```
157pub fn natural_cmp(a: &str, b: &str) -> Ordering {
158    let (mut x, mut y) = (a, b);
159    loop {
160        match (x.chars().next(), y.chars().next()) {
161            (None, None) => return a.cmp(b),
162            (None, Some(_)) => return Ordering::Less,
163            (Some(_), None) => return Ordering::Greater,
164            (Some(c), Some(d)) if c.is_ascii_digit() && d.is_ascii_digit() => {
165                let (run_x, rest_x) = split_digits(x);
166                let (run_y, rest_y) = split_digits(y);
167                let (value_x, value_y) =
168                    (run_x.trim_start_matches('0'), run_y.trim_start_matches('0'));
169                let order = value_x
170                    .len()
171                    .cmp(&value_y.len())
172                    .then_with(|| value_x.cmp(value_y));
173                if order != Ordering::Equal {
174                    return order;
175                }
176                (x, y) = (rest_x, rest_y);
177            }
178            (Some(c), Some(d)) => {
179                let order = c.to_lowercase().cmp(d.to_lowercase());
180                if order != Ordering::Equal {
181                    return order;
182                }
183                (x, y) = (&x[c.len_utf8()..], &y[d.len_utf8()..]);
184            }
185        }
186    }
187}
188
189fn split_digits(s: &str) -> (&str, &str) {
190    let end = s.find(|c: char| !c.is_ascii_digit()).unwrap_or(s.len());
191    s.split_at(end)
192}
193
194/// Compare two rows by `keys`, in priority order. Empty cells (and missing
195/// ones) sort last whatever the key's direction.
196pub fn compare_rows(a: &[Value], b: &[Value], keys: &[SortKey]) -> Ordering {
197    const NULL: Value = Value::Null;
198    for key in keys {
199        let x = a.get(key.column).unwrap_or(&NULL);
200        let y = b.get(key.column).unwrap_or(&NULL);
201        let order = match (x.is_empty(), y.is_empty()) {
202            (false, false) => {
203                let order = compare_values(x, y, key.compare);
204                match key.order {
205                    Order::Ascending => order,
206                    Order::Descending => order.reverse(),
207                }
208            }
209            // Empties stay last in both directions.
210            _ => compare_values(x, y, key.compare),
211        };
212        if order != Ordering::Equal {
213            return order;
214        }
215    }
216    Ordering::Equal
217}
218
219/// Sort rows in place by `keys`. Stable: rows equal on every key keep their
220/// relative order.
221pub fn sort_rows<R: AsRef<[Value]>>(rows: &mut [R], keys: &[SortKey]) {
222    if keys.is_empty() {
223        return;
224    }
225    rows.sort_by(|a, b| compare_rows(a.as_ref(), b.as_ref(), keys));
226}
227
228/// The indices of `rows` in sorted order, leaving the rows where they are.
229/// Stable, as [`sort_rows`].
230pub fn sorted_indices<R: AsRef<[Value]>>(rows: &[R], keys: &[SortKey]) -> Vec<usize> {
231    let mut order: Vec<usize> = (0..rows.len()).collect();
232    if !keys.is_empty() {
233        order.sort_by(|&a, &b| compare_rows(rows[a].as_ref(), rows[b].as_ref(), keys));
234    }
235    order
236}
237
238#[cfg(test)]
239mod tests {
240    use super::*;
241
242    #[test]
243    fn natural_order_handles_digits_case_and_leading_zeros() {
244        let mut words = vec!["a10", "A2", "a2", "a02", "b", "a1b", ""];
245        words.sort_by(|a, b| natural_cmp(a, b));
246        assert_eq!(words, ["", "a1b", "A2", "a02", "a2", "a10", "b"]);
247    }
248
249    #[test]
250    fn numbers_sort_before_text_and_numeric_strings_as_numbers() {
251        let mut values = [
252            Value::from("x"),
253            Value::from("10"),
254            Value::Float(2.5),
255            Value::Int(-3),
256            Value::from("-4.5"),
257            Value::Null,
258        ];
259        values.sort_by(|a, b| compare_values(a, b, Compare::Natural));
260        let plain: Vec<String> = values.iter().map(Value::plain).collect();
261        assert_eq!(plain, ["-4.5", "-3", "2.5", "10", "x", ""]);
262        values.sort_by(|a, b| compare_values(a, b, Compare::Lexical));
263        let plain: Vec<String> = values.iter().map(Value::plain).collect();
264        assert_eq!(plain, ["-3", "-4.5", "10", "2.5", "x", ""]);
265    }
266}
rich_ext/table/sort.rs

rich_ext/table/
sort.rs
