//! Shuffled play orders. Every function returns a permutation: positions into //! the queue as it plays now, in the order it should play next. The caller //! applies the same permutation to the songs, to their original positions and //! to the player's URLs, so the three never disagree. //! //! `fixed` is how many tracks at the head of the queue stay where they are: //! those played, the one playing and one already handed to playbin. use std::collections::HashMap; use fastrand::Rng; use serde::{Deserialize, Serialize}; use crate::subsonic::Song; #[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)] #[serde(rename_all = "camelCase")] pub enum Mode { #[default] Off, Tracks, Albums, } impl Mode { pub fn next(self) -> Mode { match self { Mode::Off => Mode::Tracks, Mode::Tracks => Mode::Albums, Mode::Albums => Mode::Off, } } } /// Library shuffle: the queue is topped up with random tracks from the /// server as it runs low. #[derive(Debug, Clone, Copy, Default, PartialEq, Eq, Serialize, Deserialize)] #[serde(rename_all = "camelCase")] pub struct Library { /// Where the random tracks carry on after those queued by hand, which go /// after the playing track and after any queued before them. pub added_end: usize, } /// Which album a song belongs to. The album name alone would merge different /// albums of the same title, so it is only the fallback for songs saved /// without an album id. A song with neither is an album of its own. #[derive(Debug, Clone, PartialEq, Eq, Hash)] enum AlbumKey<'a> { Id(&'a str), Name(&'a str, Option<&'a str>), Alone(usize), } fn album_key(song: &Song, pos: usize) -> AlbumKey<'_> { match (&song.album_id, &song.album) { (Some(id), _) => AlbumKey::Id(id), (None, Some(name)) if !name.is_empty() => AlbumKey::Name(name, song.artist.as_deref()), _ => AlbumKey::Alone(pos), } } /// Keeps the first `fixed` tracks and shuffles the rest. pub fn tracks(rng: &mut Rng, len: usize, fixed: usize) -> Vec { let fixed = fixed.min(len); let mut perm: Vec = (0..len).collect(); rng.shuffle(&mut perm[fixed..]); perm } /// Keeps the first `fixed` tracks, then plays the rest of the playing track's /// album, then the other albums in random order. Each album plays in disc and /// track order, and tracks without numbers keep their original order. /// `original` holds each track's position in the original order. pub fn albums(rng: &mut Rng, songs: &[Song], original: &[usize], playing: Option, fixed: usize) -> Vec { let fixed = fixed.min(songs.len()); let mut groups = album_groups(songs, original, fixed..songs.len()); let first = playing .and_then(|p| songs.get(p).map(|s| album_key(s, p))) .and_then(|key| groups.iter().position(|(k, _)| *k == key)) .map(|i| groups.remove(i)); rng.shuffle(&mut groups); (0..fixed) .chain(first.into_iter().chain(groups).flat_map(|(_, g)| g)) .collect() } /// The tracks in `range` grouped by album, in the order each album first /// appears, each sorted by disc and track. fn album_groups<'a>( songs: &'a [Song], original: &[usize], range: std::ops::Range, ) -> Vec<(AlbumKey<'a>, Vec)> { let mut groups: Vec<(AlbumKey<'a>, Vec)> = Vec::new(); let mut index: HashMap, usize> = HashMap::new(); for pos in range { let key = album_key(&songs[pos], pos); let i = *index.entry(key.clone()).or_insert_with(|| { groups.push((key, Vec::new())); groups.len() - 1 }); groups[i].1.push(pos); } for (_, g) in &mut groups { g.sort_by_key(|&p| { let s = &songs[p]; ( s.disc_number.unwrap_or(0), s.track.unwrap_or(0), original.get(p).copied().unwrap_or(p), ) }); } groups } /// Places the tracks from `added` on (just appended to the queue) at random /// positions after the first `fixed`. Under album shuffle each added album /// goes in as one block, and only between albums, never inside one. pub fn insert(rng: &mut Rng, mode: Mode, songs: &[Song], original: &[usize], fixed: usize, added: usize) -> Vec { let added = added.min(songs.len()); let fixed = fixed.min(added); let mut tail: Vec = (fixed..added).collect(); if mode == Mode::Albums { let mut blocks: Vec> = Vec::new(); for pos in tail { let key = album_key(&songs[pos], pos); match blocks.last_mut() { Some(b) if album_key(&songs[b[0]], b[0]) == key => b.push(pos), _ => blocks.push(vec![pos]), } } // The rest of the album playing now still plays first. let lo = match (fixed.checked_sub(1), blocks.first()) { (Some(last), Some(b)) if album_key(&songs[last], last) == album_key(&songs[b[0]], b[0]) => 1, _ => 0, }; for (_, g) in album_groups(songs, original, added..songs.len()) { let at = rng.usize(lo..=blocks.len()); blocks.insert(at, g); } tail = blocks.concat(); } else { for pos in added..songs.len() { let at = rng.usize(..=tail.len()); tail.insert(at, pos); } } (0..fixed).chain(tail).collect() } /// Back to the original order, given each track's original position. A /// `pinned` track (handed to playbin already) is moved to play right after /// `playing`, so the track that plays next is the one the player expects. pub fn unshuffle(original: &[usize], playing: Option, pinned: Option) -> Vec { let mut perm: Vec = (0..original.len()).collect(); perm.sort_by_key(|&p| original[p]); if let (Some(playing), Some(pinned)) = (playing, pinned) && playing != pinned && let Some(from) = perm.iter().position(|&p| p == pinned) { perm.remove(from); let at = perm.iter().position(|&p| p == playing).map_or(perm.len(), |i| i + 1); perm.insert(at, pinned); } perm } /// `items` reordered by `perm`. pub fn apply(items: &[T], perm: &[usize]) -> Vec { perm.iter().map(|&p| items[p].clone()).collect() } #[cfg(test)] mod tests { use super::*; fn song(id: &str, album: Option<&str>, track: u32) -> Song { serde_json::from_value(serde_json::json!({ "id": id, "title": id, "album": album.map(|a| format!("Album {a}")), "albumId": album, "artist": "A", "track": track, })) .unwrap() } fn is_permutation(perm: &[usize], len: usize) -> bool { let mut sorted = perm.to_vec(); sorted.sort(); sorted == (0..len).collect::>() } #[test] fn tracks_keeps_the_fixed_head_and_plays_the_rest_once() { let mut rng = Rng::with_seed(1); for fixed in [0, 1, 3, 10, 12] { let perm = tracks(&mut rng, 10, fixed); assert!(is_permutation(&perm, 10)); let fixed = fixed.min(10); assert_eq!(perm[..fixed], (0..fixed).collect::>()[..]); } } #[test] fn tracks_actually_shuffles() { let mut rng = Rng::with_seed(7); let perm = tracks(&mut rng, 50, 1); assert_ne!(perm, (0..50).collect::>()); } #[test] fn albums_finish_the_playing_album_then_play_whole_albums_in_track_order() { // Track shuffled already: b2, a1, b1 | a2, c1, b3, a3, c2. let songs = vec![ song("b2", Some("b"), 2), song("a1", Some("a"), 1), song("b1", Some("b"), 1), song("a2", Some("a"), 2), song("c2", Some("c"), 2), song("b3", Some("b"), 3), song("a3", Some("a"), 3), song("c1", Some("c"), 1), ]; let original: Vec = (0..songs.len()).collect(); for seed in 0..20 { let mut rng = Rng::with_seed(seed); let perm = albums(&mut rng, &songs, &original, Some(0), 3); assert!(is_permutation(&perm, songs.len())); let ids: Vec<&str> = perm.iter().map(|&p| songs[p].id.as_str()).collect(); assert_eq!(ids[..3], ["b2", "a1", "b1"]); assert_eq!(ids[3], "b3", "the playing album goes on first"); let rest = &ids[4..]; assert!( rest == ["a2", "a3", "c1", "c2"] || rest == ["c1", "c2", "a2", "a3"], "seed {seed}: {rest:?}" ); } } #[test] fn albums_with_the_same_name_stay_apart_and_saved_songs_fall_back_to_the_name() { let mut same_name = song("x1", Some("x"), 1); same_name.album = Some("Album y".into()); let mut saved = song("y2", None, 2); saved.album = Some("Album y".into()); let mut saved1 = song("y1", None, 1); saved1.album = Some("Album y".into()); let songs = vec![song("p", Some("p"), 1), saved, same_name, saved1]; let original: Vec = (0..songs.len()).collect(); let mut rng = Rng::with_seed(3); let perm = albums(&mut rng, &songs, &original, Some(0), 1); let ids: Vec<&str> = perm.iter().map(|&p| songs[p].id.as_str()).collect(); let y = ids.iter().position(|&i| i == "y1").unwrap(); assert_eq!(ids[y + 1], "y2", "{ids:?}"); assert!(ids.contains(&"x1")); } #[test] fn tracks_without_numbers_keep_their_original_order() { let mut songs: Vec = ["a", "b", "c"].iter().map(|id| song(id, Some("al"), 0)).collect(); for s in &mut songs { s.track = None; } // Played as c, a, b; originally a, b, c. let songs = vec![songs[2].clone(), songs[0].clone(), songs[1].clone()]; let original = vec![2, 0, 1]; let mut rng = Rng::with_seed(0); let perm = albums(&mut rng, &songs, &original, None, 0); let ids: Vec<&str> = perm.iter().map(|&p| songs[p].id.as_str()).collect(); assert_eq!(ids, ["a", "b", "c"]); } #[test] fn insert_scatters_added_tracks_after_the_fixed_head() { let songs: Vec = (0..20).map(|i| song(&i.to_string(), None, 0)).collect(); let original: Vec = (0..20).collect(); let mut rng = Rng::with_seed(5); let perm = insert(&mut rng, Mode::Tracks, &songs, &original, 2, 15); assert!(is_permutation(&perm, 20)); assert_eq!(perm[..2], [0, 1]); let old: Vec = perm.iter().copied().filter(|&p| p < 15).collect(); assert_eq!(old, (0..15).collect::>(), "the queued tracks keep their order"); assert_ne!(perm[15..], [15, 16, 17, 18, 19], "added tracks are not all at the end"); } #[test] fn insert_under_album_shuffle_adds_whole_albums_between_albums() { let songs = vec![ song("p1", Some("p"), 1), song("q1", Some("q"), 1), song("q2", Some("q"), 2), song("r1", Some("r"), 1), song("r2", Some("r"), 2), song("n2", Some("n"), 2), song("n1", Some("n"), 1), ]; let original: Vec = (0..songs.len()).collect(); for seed in 0..20 { let mut rng = Rng::with_seed(seed); let perm = insert(&mut rng, Mode::Albums, &songs, &original, 1, 5); let ids: Vec<&str> = perm.iter().map(|&p| songs[p].id.as_str()).collect(); let n = ids.iter().position(|&i| i == "n1").unwrap(); assert_eq!(ids[n + 1], "n2", "seed {seed}: {ids:?}"); assert!( n >= 1 && ids[n - 1] != "q1" && ids[n - 1] != "r1", "seed {seed}: {ids:?}" ); } } #[test] fn insert_under_album_shuffle_leaves_the_playing_album_first() { let songs = vec![ song("p1", Some("p"), 1), song("p2", Some("p"), 2), song("q1", Some("q"), 1), song("n1", Some("n"), 1), ]; let original: Vec = (0..songs.len()).collect(); for seed in 0..20 { let mut rng = Rng::with_seed(seed); let perm = insert(&mut rng, Mode::Albums, &songs, &original, 1, 3); assert_eq!(perm[1], 1, "seed {seed}: {perm:?}"); } } #[test] fn unshuffle_restores_the_original_order() { let original = vec![3, 0, 4, 1, 2]; let perm = unshuffle(&original, Some(0), None); assert_eq!(apply(&original, &perm), [0, 1, 2, 3, 4]); } #[test] fn unshuffle_plays_the_pinned_track_next() { // Playing original 3, playbin already has original 0. let original = vec![1, 3, 0, 4, 2]; let perm = unshuffle(&original, Some(1), Some(2)); assert_eq!(apply(&original, &perm), [1, 2, 3, 0, 4]); } #[test] fn modes_cycle_off_tracks_albums() { assert_eq!(Mode::Off.next(), Mode::Tracks); assert_eq!(Mode::Tracks.next(), Mode::Albums); assert_eq!(Mode::Albums.next(), Mode::Off); } }