chromy_core/
order.rs

1//! Ordering the frame before selection: serpentine and nested sorts.
2//!
3//! A sequential procedure buys variance from the order of the list: units
4//! that sit together are selected apart, so the sample spreads over
5//! whatever the sort keys encode — implicit stratification. A plain nested
6//! sort leaves a seam at every boundary where the last unit of one group
7//! meets the first of the next and the two could not be less alike. The
8//! serpentine sort removes the seams by reversing direction at each
9//! boundary, so the list meanders through the frame and every neighbouring
10//! pair of units is actually similar.
11//!
12//! Categorical keys are ranked by byte order of their UTF-8 encoding —
13//! the C locale — deliberately: a sort that follows the machine's locale
14//! produces a different sample on a different machine.
15
16use crate::error::Error;
17
18/// One sort key: a column of the frame.
19#[derive(Debug, Clone)]
20pub enum Key<'a> {
21    /// A numeric key, used as is. Must be finite.
22    Numeric(&'a [f64]),
23    /// A categorical key, ranked by byte order of its values.
24    Categorical(&'a [String]),
25}
26
27impl Key<'_> {
28    fn len(&self) -> usize {
29        match self {
30            Key::Numeric(v) => v.len(),
31            Key::Categorical(v) => v.len(),
32        }
33    }
34
35    /// The key as ranks: the numeric values themselves, or the 1-based
36    /// position of each category in the byte-ordered set of categories.
37    fn ranks(&self) -> Result<Vec<f64>, Error> {
38        match self {
39            Key::Numeric(v) => {
40                if let Some(bad) = v.iter().find(|x| !x.is_finite()) {
41                    return Err(Error::Input(format!(
42                        "sort keys must be finite; found {bad}"
43                    )));
44                }
45                Ok(v.to_vec())
46            }
47            Key::Categorical(v) => {
48                let mut levels: Vec<&str> = v.iter().map(String::as_str).collect();
49                levels.sort_unstable();
50                levels.dedup();
51                Ok(v.iter()
52                    .map(|s| (levels.binary_search(&s.as_str()).unwrap() + 1) as f64)
53                    .collect())
54            }
55        }
56    }
57}
58
59fn rank_columns(keys: &[Key]) -> Result<(Vec<Vec<f64>>, usize), Error> {
60    if keys.is_empty() {
61        return Err(Error::Input("at least one sort key is needed".into()));
62    }
63    let n = keys[0].len();
64    if n == 0 {
65        return Err(Error::Input("sort keys must not be empty".into()));
66    }
67    let mut ranks = Vec::with_capacity(keys.len());
68    for key in keys {
69        if key.len() != n {
70            return Err(Error::Input(format!(
71                "sort keys of different lengths: {} and {}",
72                n,
73                key.len()
74            )));
75        }
76        ranks.push(key.ranks()?);
77    }
78    Ok((ranks, n))
79}
80
81/// Stable ascending order of `0..n` by the given columns, compared in turn.
82fn multi_key_order(ranks: &[Vec<f64>], n: usize) -> Vec<usize> {
83    let mut order: Vec<usize> = (0..n).collect();
84    order.sort_by(|&a, &b| {
85        for col in ranks {
86            match col[a].partial_cmp(&col[b]).unwrap() {
87                std::cmp::Ordering::Equal => continue,
88                other => return other,
89            }
90        }
91        std::cmp::Ordering::Equal
92    });
93    order
94}
95
96/// The nested sort: plain lexicographic order over the keys.
97///
98/// Returns the 0-based order in which to list the frame.
99pub fn nested(keys: &[Key]) -> Result<Vec<usize>, Error> {
100    let (ranks, n) = rank_columns(keys)?;
101    Ok(multi_key_order(&ranks, n))
102}
103
104/// The hierarchical serpentine sort.
105///
106/// The first key orders the list; each further key runs forward through
107/// the first group the keys above it define, backward through the second,
108/// and so on, so the list never jumps. With a single key the serpentine
109/// and nested sorts coincide. Returns the 0-based order in which to list
110/// the frame.
111pub fn serpentine(keys: &[Key]) -> Result<Vec<usize>, Error> {
112    let (ranks, n) = rank_columns(keys)?;
113    if ranks.len() == 1 {
114        return Ok(multi_key_order(&ranks, n));
115    }
116
117    let mut order = multi_key_order(&ranks[..1], n);
118    for j in 1..ranks.len() {
119        // A group boundary is any change in the keys above this one; the
120        // direction alternates with the running count of boundaries.
121        let mut changes = vec![false; n];
122        changes[0] = true;
123        for col in &ranks[..j] {
124            for p in 1..n {
125                changes[p] = changes[p] || col[order[p]] != col[order[p - 1]];
126            }
127        }
128        let mut level = vec![0_i64; n];
129        let mut running = 0_i64;
130        for p in 0..n {
131            running += i64::from(changes[p]);
132            level[p] = running;
133        }
134
135        let mut positions: Vec<usize> = (0..n).collect();
136        positions.sort_by(|&a, &b| {
137            level[a].cmp(&level[b]).then_with(|| {
138                let direction = |p: usize| if level[p] % 2 == 1 { 1.0 } else { -1.0 };
139                let ka = direction(a) * ranks[j][order[a]];
140                let kb = direction(b) * ranks[j][order[b]];
141                ka.partial_cmp(&kb).unwrap()
142            })
143        });
144        order = positions.iter().map(|&p| order[p]).collect();
145    }
146    Ok(order)
147}
chromy_core/order.rs

chromy_core/
order.rs
