maxrave-dev Custom shuffle order
A media engine keeps items in timeline order and plays them through a shuffle order: a
permutation array shuffled, where shuffled[playPosition] = timelineIndex. The engine asks it for
next/previous and for the first/last entry, and asks it to clone itself whenever the queue changes.
The default implementation shuffles newly inserted items into random positions across the whole remaining order. That is defensible for "shuffle the album" and wrong for everything else: a user who hits "play next" wants the track next, and a queue that grows by appending a continuation page wants that page to stay in one block. Replacing it is a small class:
class BetterShuffleOrder(private val shuffled: IntArray) : ShuffleOrder {
// reverse map: indexInShuffled[timelineIndex] = playPosition
private val indexInShuffled = IntArray(shuffled.size).also {
for (i in shuffled.indices) it[shuffled[i]] = i
}
override fun getNextIndex(index: Int): Int {
val next = indexInShuffled[index] + 1
return if (next < shuffled.size) shuffled[next] else INDEX_UNSET
}
}
Two arrays, always built together: the forward map answers "what plays at position N", the reverse map answers "where in the play order does timeline item N sit". Every operation below has to leave both consistent.
Traps
The reverse map is derived, never edited in place. Every constructor path must rebuild
indexInShuffled from shuffled — deriving it in the property initialiser, as above (an init
block does the same job), makes that structural rather than a rule someone has to remember. An insert or remove that patches only the forward array
leaves the reverse one describing the previous queue, and the symptom is not a failure: playback
simply jumps to an unrelated track at the next boundary.
Insert has to do two different things at once, and it is easy to do only one. Existing entries whose timeline index sits at or after the insertion point shift up by the insert count; separately, the new entries must be placed at a play position next to the pivot. Both, or the order is corrupt:
override fun cloneAndInsert(insertionIndex: Int, insertionCount: Int): ShuffleOrder {
val pivot = if (insertionIndex < shuffled.size) indexInShuffled[insertionIndex]
else indexInShuffled.size
val out = IntArray(shuffled.size + insertionCount)
for (i in shuffled.indices) {
val timelineIndex = shuffled[i].let { if (it > insertionIndex) it + insertionCount else it }
if (i <= pivot) out[i] = timelineIndex else out[i + insertionCount] = timelineIndex
}
for (i in 0 until insertionCount) {
if (insertionIndex < shuffled.size) {
out[pivot + i + 1] = insertionIndex + i + 1 // insert after the pivot entry
} else {
out[pivot + i] = insertionIndex + i // append past the end: no pivot entry
}
}
return BetterShuffleOrder(out)
}
Both branches on insertionIndex < shuffled.size are load-bearing: appending past the end has no
pivot entry to read, so the new items start at pivot rather than pivot + 1 and their timeline
indices are not shifted. Dropping the append branch either leaves an uninitialised 0 in the middle
of the order — which plays the first track again at a random moment — or writes one slot past the
end of the array.
Remove has to renumber survivors, not just drop entries. Timeline indices above the removed range all shift down by the removed count. Dropping the entries and leaving the rest as-is produces an order that points past the end of a shrinking queue.
newShuffled[i - foundSoFar] =
if (shuffled[i] >= indexFrom) shuffled[i] - removedCount else shuffled[i]
These are cloneAnd*, not insert/remove. The engine holds the old instance while building
the new timeline and may discard the result. Mutating this and returning it appears to work until
a queue edit is rolled back, and then the order describes a queue that never existed. Return a new
instance from every one of them, including cloneAndClear.
The start index must be swapped to the front, not just included. Shuffling a queue while a track plays must keep that track first, or turning shuffle on restarts playback from something else:
if (startIndex != -1) {
val pos = shuffled.indexOf(startIndex)
shuffled[0] = shuffled[pos].also { shuffled[pos] = shuffled[0] }
}
Generate the permutation with the inside-out variant, not List.shuffle() on a copy. The
inside-out Fisher–Yates fills and permutes in one pass over 0 until length, which keeps the
allocation to the single output array:
for (i in 0 until length) {
val swap = (0..i).random()
shuffled[i] = shuffled[swap]
shuffled[swap] = i
}
Every entry point must survive an empty order. getFirstIndex, getLastIndex and
cloneAndInsert are all reachable with shuffled.size == 0 — a queue cleared while shuffle stays
on. Each needs an explicit branch (INDEX_UNSET, or a fresh order built from the insert count);
an unguarded shuffled[0] there stops playback with an out-of-range read.
Un-shuffling does not restore your custom insert positions. The engine reverts to timeline order when shuffle is turned off, so a track that was "played next" reappears wherever it was inserted in the timeline. Deciding whether that is acceptable is a product call — it is not something the shuffle order can fix, because timeline order is the other authority.
Verifying it
Log the array itself, not the behaviour: print shuffled after each clone and check by hand that
it is a permutation of 0 until size (no repeats, no gaps) with the inserted block contiguous right
after the current play position. A corrupted order is almost always a repeated or missing value, and
that is visible in one printed line long before it is visible as a skipped track.
Provenance: the design shown here follows the GPL-3.0 BetterShuffleOrder from the Auxio project
(Alexander Capehart). Reproducing the code — rather than the pattern — in your own project carries
that license and its attribution with it.