aede_core/playback/
shuffle.rs

1//! Deterministic, metadata-based musical journeys over a selection.
2//!
3//! Smart shuffle plans a permutation of **occurrences**, not a new selection.
4//! It keeps duplicate playlist entries, never reads audio and never changes the
5//! catalog. A small undirected style-affinity graph is supplemented by local
6//! tag co-occurrences. Its links express playback heuristics, not a historical
7//! genealogy or an objective measurement of how two recordings sound.
8//!
9//! The planner prefers short genre steps, varied artists and albums, and
10//! candidates with an available onward step. An arbitrary finite selection can
11//! have disconnected styles or exhaust its bridge recordings. It then includes
12//! every remaining occurrence and reports the discontinuity explicitly. Missing
13//! genre tags are reported separately rather than treated as musical similarity.
14
15use std::collections::{BTreeSet, VecDeque};
16
17use crate::model::{Catalog, Id};
18
19#[path = "shuffle_graph.rs"]
20mod graph;
21#[path = "shuffle_profiles.rs"]
22mod profiles;
23
24use graph::GenreGraph;
25use profiles::Profile;
26
27/// Version of the deterministic metadata rules and order planner.
28///
29/// A seed reproduces an order for this version, the same selection and the same
30/// catalog metadata. Retagging or changing the algorithm can change the order.
31pub const ALGORITHM_VERSION: u32 = 1;
32
33/// Largest preferred style step on the planner's `0..=1000` distance scale.
34///
35/// This is a heuristic threshold, not a measured acoustic distance. The planner
36/// reports larger steps instead of dropping tracks or silently looping a subset.
37pub const MAX_STYLE_STEP: u16 = 300;
38
39/// Extra distance admitted around the nearest available genre-safe candidate.
40///
41/// A nearer bridge should be used before a more distant style is selected simply
42/// because both fit the global ceiling. Seeded weighting still varies choices
43/// inside this local neighborhood.
44pub const NEIGHBORHOOD_WINDOW: u16 = 60;
45
46const CANDIDATE_LIMIT: usize = 96;
47const NEARBY_GENRES: usize = 12;
48const PER_GENRE_CANDIDATES: usize = 6;
49const RECENT_ARTISTS: usize = 5;
50const RECENT_ALBUMS: usize = 3;
51
52/// What could not be made into a smooth, fully informed journey.
53#[derive(Clone, Debug, Default, Eq, PartialEq)]
54pub struct SmartShuffleReport {
55    /// Known-style transitions longer than [`MAX_STYLE_STEP`].
56    pub style_breaks: usize,
57    /// Transitions where at least one occurrence has no usable genre.
58    pub unknown_transitions: usize,
59    /// Selection occurrences without usable genre metadata.
60    pub unknown_tracks: usize,
61    /// Occurrences whose genre, artist or label metadata reached a safety limit.
62    pub limited_tracks: usize,
63    /// Distinct canonical genre names omitted from the bounded graph.
64    pub omitted_genres: usize,
65}
66
67/// One reported style discontinuity in a planned order.
68#[derive(Clone, Debug, Eq, PartialEq)]
69pub struct StyleBreak {
70    /// Position of `next` in [`SmartOrder::order`], including a cycle boundary.
71    pub position: usize,
72    /// Previous occurrence's index in the original selection.
73    pub previous: usize,
74    /// Next occurrence's index in the original selection.
75    pub next: usize,
76    /// Heuristic genre distance, or `None` when metadata is missing.
77    pub distance: Option<u16>,
78}
79
80/// A reproducible occurrence permutation and its limitations.
81#[derive(Clone, Debug, Eq, PartialEq)]
82pub struct SmartOrder {
83    /// Indices into the original selection, each appearing exactly once.
84    pub order: Vec<usize>,
85    /// Summary suitable for a player or its diagnostics.
86    pub report: SmartShuffleReport,
87    /// Discontinuities, including unknown genre transitions.
88    pub breaks: Vec<StyleBreak>,
89}
90
91/// Read-only metadata prepared once for repeated journey planning.
92#[derive(Clone, Debug)]
93pub struct SmartShuffle {
94    profiles: Vec<Profile>,
95    graph: GenreGraph,
96    report: SmartShuffleReport,
97}
98
99impl SmartShuffle {
100    /// Prepare a selection using catalog identities when they are available.
101    ///
102    /// `None` and invalid track IDs retain their occurrences with unknown
103    /// metadata. Genres attached directly to a track take precedence over the
104    /// release's union of genres, so a mixed compilation does not make all its
105    /// tracks stylistically identical. The graph has at most 512 nodes; profiles
106    /// retain at most eight genres, eight artists and four labels. Raw and
107    /// normalized genre labels over 256 UTF-8 bytes are omitted before planning.
108    /// Any limited metadata is counted in the resulting report.
109    pub fn from_catalog(catalog: &Catalog, tracks: &[Option<Id>]) -> Self {
110        let (mut profiles, contexts) = profiles::from_catalog(catalog, tracks);
111        let graph = GenreGraph::new(&mut profiles, &contexts);
112        let report = SmartShuffleReport {
113            unknown_tracks: profiles.iter().filter(|p| p.genres.is_empty()).count(),
114            limited_tracks: profiles.iter().filter(|p| p.limited).count(),
115            omitted_genres: graph.omitted_genres,
116            ..SmartShuffleReport::default()
117        };
118        Self {
119            profiles,
120            graph,
121            report,
122        }
123    }
124
125    /// Number of occurrences, including duplicates and uncatalogued files.
126    pub fn len(&self) -> usize {
127        self.profiles.len()
128    }
129
130    /// Whether the original selection was empty.
131    pub fn is_empty(&self) -> bool {
132        self.profiles.is_empty()
133    }
134
135    /// Genre distance between two selection occurrences.
136    ///
137    /// Returns `None` for an invalid index or missing genre metadata. Known but
138    /// disconnected genres have distance `1000`. Artist, year and label scoring
139    /// cannot override this genre distance or turn missing tags into evidence.
140    pub fn transition_distance(&self, from: usize, to: usize) -> Option<u16> {
141        self.graph
142            .distance(self.profiles.get(from)?, self.profiles.get(to)?)
143    }
144
145    /// Plan one complete journey with an optional pinned first occurrence.
146    ///
147    /// `start_index` keeps a player's current occurrence first when changing
148    /// mode. `previous_index` supplies the preceding cycle's final occurrence,
149    /// so the next cycle prefers a smooth opening and reports its boundary too.
150    /// Out-of-range optional indices are ignored. Every occurrence still appears
151    /// once. No random source, wall clock, hash iteration or floating point is
152    /// involved; all choices use the same SplitMix64 generator as classic shuffle.
153    pub fn plan(
154        &self,
155        seed: u64,
156        start_index: Option<usize>,
157        previous_index: Option<usize>,
158    ) -> SmartOrder {
159        let remaining: Vec<usize> = (0..self.len()).collect();
160        self.plan_selection(seed, start_index, previous_index, &remaining)
161    }
162
163    /// Plan only the still-unplayed occurrences after an interactive mode change.
164    ///
165    /// Indices refer to the original selection. Duplicate indices or indices
166    /// outside that selection are errors; duplicate **track identities** remain
167    /// valid when they are distinct playlist occurrences. Planning the remainder
168    /// itself, rather than filtering a full plan afterwards, prevents already
169    /// played bridge tracks from influencing a transition they cannot provide.
170    pub fn plan_remaining(
171        &self,
172        seed: u64,
173        remaining: &[usize],
174        previous_index: Option<usize>,
175    ) -> Result<SmartOrder, String> {
176        let mut seen = BTreeSet::new();
177        for &index in remaining {
178            if index >= self.len() {
179                return Err("smart shuffle occurrence is outside the selection".into());
180            }
181            if !seen.insert(index) {
182                return Err("smart shuffle remainder repeats an occurrence index".into());
183            }
184        }
185        Ok(self.plan_selection(seed, None, previous_index, remaining))
186    }
187
188    fn plan_selection(
189        &self,
190        seed: u64,
191        start_index: Option<usize>,
192        previous_index: Option<usize>,
193        remaining: &[usize],
194    ) -> SmartOrder {
195        let mut priorities = remaining.to_vec();
196        super::shuffle(&mut priorities, seed);
197        let mut result = SmartOrder {
198            order: Vec::with_capacity(remaining.len()),
199            report: SmartShuffleReport {
200                unknown_tracks: remaining
201                    .iter()
202                    .filter(|&&i| self.profiles[i].genres.is_empty())
203                    .count(),
204                limited_tracks: remaining
205                    .iter()
206                    .filter(|&&i| self.profiles[i].limited)
207                    .count(),
208                omitted_genres: self.report.omitted_genres,
209                ..SmartShuffleReport::default()
210            },
211            breaks: Vec::new(),
212        };
213        if remaining.is_empty() {
214            return result;
215        }
216
217        let mut previous = previous_index.filter(|&i| i < self.len());
218        let mut pinned = start_index.filter(|i| remaining.contains(i));
219        if result.report.unknown_tracks == remaining.len() {
220            if let Some(pinned) = pinned
221                && let Some(position) = priorities.iter().position(|&i| i == pinned)
222            {
223                priorities.swap(0, position);
224            }
225            for next in priorities {
226                if let Some(previous) = previous {
227                    self.record_transition(previous, next, &mut result);
228                }
229                result.order.push(next);
230                previous = Some(next);
231            }
232            return result;
233        }
234
235        let mut pools = Pools::new(&self.profiles, &priorities, self.graph.len());
236        let mut state = seed;
237        let mut history = VecDeque::new();
238        if let Some(previous) = previous {
239            history.push_back(previous);
240        }
241        while !pools.remaining.is_empty() {
242            let next = if let Some(index) = pinned.take() {
243                index
244            } else if let Some(previous) = previous {
245                let candidates =
246                    pools.candidates(&self.profiles[previous], &self.graph, &mut state);
247                self.choose(previous, &candidates, &pools, &history, &mut state)
248            } else {
249                // Classic seeded priority gives an unbiased initial occurrence.
250                priorities[0]
251            };
252            if let Some(previous) = previous {
253                self.record_transition(previous, next, &mut result);
254            }
255            pools.remove(next, &self.profiles[next]);
256            result.order.push(next);
257            history.push_back(next);
258            if history.len() > RECENT_ARTISTS {
259                history.pop_front();
260            }
261            previous = Some(next);
262        }
263        result
264    }
265
266    fn record_transition(&self, previous: usize, next: usize, result: &mut SmartOrder) {
267        let distance = self.transition_distance(previous, next);
268        match distance {
269            Some(distance) if distance <= MAX_STYLE_STEP => return,
270            Some(_) => result.report.style_breaks += 1,
271            None => result.report.unknown_transitions += 1,
272        }
273        result.breaks.push(StyleBreak {
274            position: result.order.len(),
275            previous,
276            next,
277            distance,
278        });
279    }
280
281    fn choose(
282        &self,
283        previous: usize,
284        candidates: &[usize],
285        pools: &Pools,
286        history: &VecDeque<usize>,
287        state: &mut u64,
288    ) -> usize {
289        let radius = candidates
290            .iter()
291            .filter_map(|&i| self.transition_distance(previous, i))
292            .min()
293            .filter(|&d| d <= MAX_STYLE_STEP)
294            .map(|d| d.saturating_add(NEIGHBORHOOD_WINDOW).min(MAX_STYLE_STEP));
295        let has_known = candidates
296            .iter()
297            .any(|&i| self.transition_distance(previous, i).is_some());
298        let mut weighted = Vec::with_capacity(candidates.len());
299        let mut total = 0u64;
300        for &next in candidates {
301            let distance = self.transition_distance(previous, next);
302            if radius.is_some_and(|radius| distance.is_none_or(|d| d > radius)) {
303                continue;
304            }
305            if radius.is_none() && has_known && distance.is_none() {
306                continue;
307            }
308            let weight = self.weight(previous, next, distance, pools, history);
309            total += weight;
310            weighted.push((next, weight));
311        }
312        // Pools always supplies at least one remaining candidate; positive
313        // weights guarantee a choice without a platform-sensitive RNG.
314        let mut draw = bounded_random(state, total);
315        for (index, weight) in weighted {
316            if draw < weight {
317                return index;
318            }
319            draw -= weight;
320        }
321        candidates.first().copied().unwrap_or(previous)
322    }
323
324    fn weight(
325        &self,
326        previous: usize,
327        next: usize,
328        distance: Option<u16>,
329        pools: &Pools,
330        history: &VecDeque<usize>,
331    ) -> u64 {
332        let profile = &self.profiles[next];
333        let before = &self.profiles[previous];
334        let distance = u64::from(distance.unwrap_or(600));
335        let closeness = 1_100 - distance;
336        let mut weight = closeness * closeness;
337
338        // Metadata can refine a genre-safe step, never permit a genre jump.
339        if intersects(&profile.labels, &before.labels) {
340            weight += weight / 10;
341        }
342        if let (Some(a), Some(b)) = (profile.year, before.year) {
343            let gap = a.abs_diff(b).min(50);
344            weight += weight * u64::from(50 - gap) / 500;
345        }
346        if self.graph.collaborators(profile, before) {
347            weight += weight / 8;
348        }
349
350        for (age, &recent) in history.iter().rev().enumerate() {
351            let recent = &self.profiles[recent];
352            if !profile.artists.is_empty() && intersects(&profile.artists, &recent.artists) {
353                weight = weight * (age as u64 + 1) / (age as u64 + 6);
354            }
355            if age < RECENT_ALBUMS && profile.album.is_some() && profile.album == recent.album {
356                weight = weight * (age as u64 + 1) / (age as u64 + 5);
357            }
358        }
359        if profile.identity.is_some()
360            && history
361                .iter()
362                .any(|&recent| self.profiles[recent].identity == profile.identity)
363        {
364            weight /= 16;
365        }
366
367        if pools.remaining.len() > 1
368            && pools.onward_distance(profile, next, &self.graph) > MAX_STYLE_STEP
369        {
370            // Preserve scarce exits when taking this occurrence now would
371            // strand the next step. This bounded one-step lookahead is a
372            // preference, not a Hamiltonian-path guarantee.
373            weight /= 16;
374        }
375        weight.max(1)
376    }
377}
378
379fn intersects<T: Ord>(left: &[T], right: &[T]) -> bool {
380    let (mut a, mut b) = (0, 0);
381    while a < left.len() && b < right.len() {
382        match left[a].cmp(&right[b]) {
383            std::cmp::Ordering::Less => a += 1,
384            std::cmp::Ordering::Greater => b += 1,
385            std::cmp::Ordering::Equal => return true,
386        }
387    }
388    false
389}
390
391fn bounded_random(state: &mut u64, bound: u64) -> u64 {
392    if bound <= 1 {
393        return 0;
394    }
395    let threshold = bound.wrapping_neg() % bound;
396    loop {
397        let value = super::next_random(state);
398        if value >= threshold {
399            return value % bound;
400        }
401    }
402}
403
404struct Pools {
405    priorities: Vec<usize>,
406    ranks: Vec<usize>,
407    remaining: BTreeSet<usize>,
408    genres: Vec<BTreeSet<usize>>,
409    active_genres: BTreeSet<usize>,
410    unknown: BTreeSet<usize>,
411}
412
413impl Pools {
414    fn new(profiles: &[Profile], priorities: &[usize], genres: usize) -> Self {
415        let mut pools = Self {
416            priorities: priorities.to_vec(),
417            ranks: vec![0; profiles.len()],
418            remaining: (0..priorities.len()).collect(),
419            genres: vec![BTreeSet::new(); genres],
420            active_genres: BTreeSet::new(),
421            unknown: BTreeSet::new(),
422        };
423        for (rank, &index) in priorities.iter().enumerate() {
424            pools.ranks[index] = rank;
425            if profiles[index].genres.is_empty() {
426                pools.unknown.insert(rank);
427            }
428            for &genre in &profiles[index].genres {
429                pools.genres[genre].insert(rank);
430                pools.active_genres.insert(genre);
431            }
432        }
433        pools
434    }
435
436    fn remove(&mut self, index: usize, profile: &Profile) {
437        let rank = self.ranks[index];
438        self.remaining.remove(&rank);
439        self.unknown.remove(&rank);
440        for &genre in &profile.genres {
441            self.genres[genre].remove(&rank);
442            if self.genres[genre].is_empty() {
443                self.active_genres.remove(&genre);
444            }
445        }
446    }
447
448    fn candidates(&self, previous: &Profile, graph: &GenreGraph, state: &mut u64) -> Vec<usize> {
449        let mut ranks = BTreeSet::new();
450        let pivot = bounded_random(state, self.priorities.len() as u64) as usize;
451        if previous.genres.is_empty() {
452            sample_pool(&self.remaining, pivot, CANDIDATE_LIMIT, &mut ranks);
453            return ranks
454                .into_iter()
455                .map(|rank| self.priorities[rank])
456                .collect();
457        }
458        let mut nearby: Vec<(u16, usize)> = self
459            .active_genres
460            .iter()
461            .map(|&genre| (graph.to_genre(previous, genre), genre))
462            .collect();
463        nearby.sort_unstable();
464        for (_, genre) in nearby.into_iter().take(NEARBY_GENRES) {
465            sample_pool(&self.genres[genre], pivot, PER_GENRE_CANDIDATES, &mut ranks);
466        }
467        sample_pool(&self.unknown, pivot, 8, &mut ranks);
468        sample_pool(&self.remaining, pivot, 16, &mut ranks);
469        ranks
470            .into_iter()
471            .take(CANDIDATE_LIMIT)
472            .map(|rank| self.priorities[rank])
473            .collect()
474    }
475
476    fn onward_distance(&self, profile: &Profile, index: usize, graph: &GenreGraph) -> u16 {
477        let rank = self.ranks[index];
478        let mut best = 1_000;
479        for &source in &profile.genres {
480            for &genre in graph.nearest(source) {
481                let distance = graph.genre_distance(source, genre);
482                if distance >= best {
483                    break;
484                }
485                let pool = &self.genres[genre];
486                if pool.len() > usize::from(pool.contains(&rank)) {
487                    best = distance;
488                    break;
489                }
490            }
491        }
492        best
493    }
494}
495
496fn sample_pool(pool: &BTreeSet<usize>, pivot: usize, limit: usize, output: &mut BTreeSet<usize>) {
497    for &rank in pool.range(pivot..).chain(pool.range(..pivot)).take(limit) {
498        output.insert(rank);
499    }
500}
501
502#[cfg(test)]
503#[path = "shuffle_tests.rs"]
504mod tests;
aede_core/playback/shuffle.rs

aede_core/playback/
shuffle.rs
