patterns/
order.rs

1use crate::arith::{away, Floor};
2use crate::select::{either, is_below};
3use crate::seq::Ranked;
4use core::cmp::Ordering;
5use patterns_macros::because;
6
7pub fn highest<T: Ranked + Clone>(items: &[T]) -> Option<T> {
8    let mut best: Option<&T> = None;
9    for item in items {
10        let better = match best {
11            Some(held) => item.rank() > held.rank(),
12            None => true,
13        };
14        if better {
15            best = Some(item);
16        }
17    }
18    best.cloned()
19}
20because!(highest, "the element a maximum picks out, kept as an Option so an empty shelf answers with a value, and a tie goes to the earliest so a queue order survives the choice");
21
22pub fn lowest<T: Ranked + Clone>(items: &[T]) -> Option<T> {
23    let mut best: Option<&T> = None;
24    for item in items {
25        let better = match best {
26            Some(held) => item.rank() < held.rank(),
27            None => true,
28        };
29        if better {
30            best = Some(item);
31        }
32    }
33    best.cloned()
34}
35because!(lowest, "the mirror of highest, separate because the smallest rank is the next thing due and a caller asking for it should not negate a rank to get there");
36
37pub fn placed<T: Ranked + Clone>(items: &[T], item: T) -> Vec<T> {
38    let mut out = Vec::new();
39    let mut put = false;
40    for held in items {
41        if !put && held.rank() > item.rank() {
42            out.push(item.clone());
43            put = true;
44        }
45        out.push(held.clone());
46    }
47    if !put {
48        out.push(item);
49    }
50    out
51}
52because!(placed, "insertion that keeps a list sorted by rank, with a tie landing after its equals so arrival order is never lost, which with would break by appending");
53
54pub fn ordered<T: Ranked + Clone>(items: &[T]) -> Vec<T> {
55    let mut out = items.to_vec();
56    out.sort_by(|a, b| a.rank().partial_cmp(&b.rank()).unwrap_or(Ordering::Equal));
57    out
58}
59because!(ordered, "a list sorted by its rank in one stable sort, separate from placed because building a list by repeated insertion copies it once per element, while placed stays the single insert into a list already in order; both land equal ranks in arrival order");
60
61pub fn keep_between<T: Ranked + Clone>(items: &[T], lo: T::Rank, hi: T::Rank) -> Vec<T> {
62    let mut out = Vec::new();
63    for item in items {
64        let rank = item.rank();
65        if rank >= lo && rank < hi {
66            out.push(item.clone());
67        }
68    }
69    out
70}
71because!(keep_between, "the elements inside a window, half open at the top so adjoining windows share no element and a day belongs to one period only");
72
73pub fn split_above<T: Ranked + Clone>(items: &[T], bound: T::Rank) -> (Vec<T>, Vec<T>) {
74    let mut over = Vec::new();
75    let mut under = Vec::new();
76    for item in items {
77        if item.rank() > bound {
78            over.push(item.clone());
79        } else {
80            under.push(item.clone());
81        }
82    }
83    (over, under)
84}
85because!(split_above, "both halves of a partition in one pass, so the two lists are complementary by construction instead of by two filters that may drift apart");
86
87pub fn nearest<T: Floor + Copy + PartialOrd>(want: T, from: &[T]) -> Option<T> {
88    from.iter()
89        .copied()
90        .reduce(|best, one| either(is_below(away(one, want), away(best, want)), one, best))
91}
92because!(nearest, "the candidate closest to what was wanted, which is asked once by anything choosing a note, a step, a bay or a size from a set that does not hold the exact answer; a tie keeps the one found first, so the order of the candidates decides it and the caller can say what that order is");
patterns/order.rs

patterns/
order.rs
