aede_core/query/
sorting.rs

1//! Deterministic ordering of query results, with absent numeric values last.
2
3use super::*;
4
5/// How a result is ordered.
6///
7/// A query with no order is a query whose second page means nothing: paging is
8/// only meaningful while the order is the same on every run. Catalog order is
9/// the default because it is deterministic; everything else is asked for.
10#[derive(Debug, Clone, Copy, PartialEq, Eq)]
11pub struct Sort {
12    /// What to order on.
13    pub key: SortKey,
14    /// `true` to put the largest, latest or highest first.
15    pub descending: bool,
16}
17
18/// What a result can be ordered on.
19#[derive(Debug, Clone, Copy, PartialEq, Eq)]
20pub enum SortKey {
21    /// The order the catalog was built in, which groups an album together.
22    Catalog,
23    /// Track title.
24    Title,
25    /// Main artist, by filing name. Uncredited tracks precede named artists in
26    /// ascending order and follow them in descending order.
27    Artist,
28    /// Album title, then disc and track number.
29    Album,
30    /// Year of the album.
31    Year,
32    /// Playing time.
33    Duration,
34    /// Size on disk.
35    Size,
36    /// Stars given to the track.
37    Rating,
38    /// How many times it was played.
39    Played,
40}
41
42/// The sort keys, by the name they are typed under.
43const SORT_KEYS: &[(&str, SortKey)] = &[
44    ("catalog", SortKey::Catalog),
45    ("title", SortKey::Title),
46    ("artist", SortKey::Artist),
47    ("album", SortKey::Album),
48    ("year", SortKey::Year),
49    ("duration", SortKey::Duration),
50    ("length", SortKey::Duration),
51    ("size", SortKey::Size),
52    ("rating", SortKey::Rating),
53    ("played", SortKey::Played),
54];
55
56impl Sort {
57    /// Reads `year`, `year-` or `-year`; the sign is the direction.
58    pub fn parse(input: &str) -> Result<Sort, QueryError> {
59        let raw = input.trim();
60        let (name, descending) = match raw.strip_suffix('-').or_else(|| raw.strip_prefix('-')) {
61            Some(rest) => (rest, true),
62            None => (raw.trim_end_matches('+').trim_start_matches('+'), false),
63        };
64        let wanted = name.trim().to_lowercase();
65        let Some((_, key)) = SORT_KEYS.iter().find(|(n, _)| *n == wanted) else {
66            return Err(error(format!(
67                "\"{name}\" is not something to sort on.\nTry: {}",
68                sort_key_names().join(", ")
69            )));
70        };
71        Ok(Sort {
72            key: *key,
73            descending,
74        })
75    }
76}
77
78/// The sort keys, for a help message.
79pub fn sort_key_names() -> Vec<&'static str> {
80    SORT_KEYS.iter().map(|(name, _)| *name).collect()
81}
82
83/// Puts a result in order.
84///
85/// Ties retain the selection's input order, which is catalog order for query
86/// results. The same query therefore keeps rows in the same places twice
87/// running — without which `--offset` would show a track twice and hide another.
88pub fn sort(tracks: &mut [Id], sort: Sort, context: &Context) {
89    match sort.key {
90        SortKey::Catalog => {
91            if sort.descending {
92                tracks.reverse();
93            }
94        }
95        SortKey::Title => sort_cached(tracks, sort.descending, |track| {
96            context
97                .catalog
98                .track(track)
99                .map(|row| text::normalize(&row.title))
100        }),
101        SortKey::Artist => sort_cached(tracks, sort.descending, |track| {
102            main_artist(context, track).map(|artist| artist.sort_name.as_str())
103        }),
104        SortKey::Album => {
105            sort_cached(tracks, sort.descending, |track| {
106                album_position(context, track)
107            });
108        }
109        SortKey::Year | SortKey::Duration | SortKey::Size | SortKey::Rating | SortKey::Played => {
110            let Some(field) = sort_field(sort.key) else {
111                return;
112            };
113            sort_numbers(tracks, sort.descending, &field, context);
114        }
115    }
116}
117
118fn sort_cached<Key: Ord>(tracks: &mut [Id], descending: bool, mut key: impl FnMut(Id) -> Key) {
119    // Normalizing a title during every comparison repeats allocations and
120    // text processing O(n log n) times. The cached-key sort computes it once
121    // per result and preserves input order for equal keys in both directions.
122    if descending {
123        tracks.sort_by_cached_key(|&track| std::cmp::Reverse(key(track)));
124    } else {
125        tracks.sort_by_cached_key(|&track| key(track));
126    }
127}
128
129fn sort_numbers(tracks: &mut [Id], descending: bool, field: &Field, context: &Context) {
130    use std::cmp::Ordering;
131
132    let mut keyed: Vec<_> = tracks
133        .iter()
134        .map(|&track| (track, number_of(field, context, track)))
135        .collect();
136    keyed.sort_by(|(_, left), (_, right)| {
137        // "Unknown" is not "smallest", and it is not "largest" either: a track
138        // with nothing to compare goes last **whichever way round the sort was
139        // asked**, which is why this sits outside the reversal. Sorting by year
140        // must not open with everything nobody ever tagged.
141        match (left, right) {
142            (None, None) => Ordering::Equal,
143            (None, Some(_)) => Ordering::Greater,
144            (Some(_), None) => Ordering::Less,
145            (Some(left), Some(right)) => {
146                let order = left.partial_cmp(right).unwrap_or(Ordering::Equal);
147                if descending { order.reverse() } else { order }
148            }
149        }
150    });
151    for (track, (ordered, _)) in tracks.iter_mut().zip(keyed) {
152        *track = ordered;
153    }
154}
155
156/// The field a numeric sort key reads, if it is a numeric one.
157fn sort_field(key: SortKey) -> Option<Field> {
158    Some(match key {
159        SortKey::Year => Field::Year,
160        SortKey::Duration => Field::Duration,
161        SortKey::Size => Field::Size,
162        SortKey::Rating => Field::Rating(Scope::Track),
163        SortKey::Played => Field::Played,
164        _ => return None,
165    })
166}
167
168/// Album title, then where the track sits in it: sorting by album and getting
169/// the tracks shuffled inside it would be half an answer.
170fn album_position(context: &Context, track: Id) -> (String, u32, u32) {
171    let catalog = context.catalog;
172    let Some(row) = catalog.track(track) else {
173        return (String::new(), 0, 0);
174    };
175    let title = row
176        .release_id
177        .and_then(|r| catalog.release(r))
178        .map(|r| text::normalize(&r.title))
179        .unwrap_or_default();
180    (title, row.disc_no.unwrap_or(1), row.track_no.unwrap_or(0))
181}
aede_core/query/sorting.rs

aede_core/query/
sorting.rs
