Smart shuffle: spread episodes evenly

This reworks the sort algorithm used in smart shuffle so that episodes
are spread out evenly, which avoids episodes bunching up at the bottom
of the queue when one feed has more episodes than others, and avoids
running through feeds with few episodes very quickly.

Signed-off-by: Stephen Kitt <steve@sk2.org>

1 files changed, 36 insertions, 26 deletions

diff --git a/core/src/main/java/de/danoeh/antennapod/core/util/QueueSorter.java b/core/src/main/java/de/danoeh/antennapod/core/util/QueueSorter.java
index 5c827dfe9..8680b2d2e 100644
--- a/core/src/main/java/de/danoeh/antennapod/core/util/QueueSorter.java
+++ b/core/src/main/java/de/danoeh/antennapod/core/util/QueueSorter.java
@@ -104,13 +104,10 @@ public class QueueSorter {
      * prefer a more balanced ordering that avoids having to listen to clusters of consecutive
      * episodes from the same feed. This is what "Smart Shuffle" tries to accomplish.
      *
-     * The Smart Shuffle algorithm involves choosing episodes (in round-robin fashion) from a
-     * collection of individual, pubdate-sorted lists that each contain only items from a specific
-     * feed.
-     *
-     * Of course, clusters of consecutive episodes <i>at the end of the queue</i> may be
-     * unavoidable. This seems unlikely to be an issue for most users who presumably maintain
-     * large queues with new episodes continuously being added.
+     * The Smart Shuffle algorithm involves spreading episodes from each feed out over the whole
+     * queue. To do this, we calculate the number of episodes in each feed, then a common multiple
+     * (not the smallest); each episode is then spread out, and we sort the resulting list of
+     * episodes by "spread out factor" and feed name.
      *
      * For example, given a queue containing three episodes each from three different feeds
      * (A, B, and C), a simple pubdate sort might result in a queue that looks like the following:
@@ -152,8 +149,17 @@ public class QueueSorter {
             ? (f1, f2) -> f1.getPubDate().compareTo(f2.getPubDate())
             : (f1, f2) -> f2.getPubDate().compareTo(f1.getPubDate());
 
-        for (Long id : map.keySet()) {
-            Collections.sort(map.get(id), itemComparator);
+        // Calculate the spread
+
+        long spread = 0;
+        for (Map.Entry<Long, List<FeedItem>> mapEntry : map.entrySet()) {
+            List<FeedItem> feedItems = mapEntry.getValue();
+            Collections.sort(feedItems, itemComparator);
+            if (spread == 0) {
+                spread = feedItems.size();
+            } else if (feedItems.size() % spread != 0){
+                spread *= feedItems.size();
+            }
         }
 
         // Create a list of the individual FeedItems lists, and sort it by feed title (ascending).
@@ -161,25 +167,29 @@ public class QueueSorter {
 
         List<List<FeedItem>> feeds = new ArrayList<>(map.values());
         Collections.sort(feeds,
-            // (we use a desc sort here, since we're iterating back-to-front below)
-            (f1, f2) -> f2.get(0).getFeed().getTitle().compareTo(f1.get(0).getFeed().getTitle()));
-
-        // Cycle through the (sorted) feed lists in a round-robin fashion, removing the first item
-        // and adding it back into to the original queue
-
-        while (!feeds.isEmpty()) {
-            // Iterate across the (sorted) list of feeds, removing the first item in each, and
-            // appending it to the queue. Note that we're iterating back-to-front here, since we
-            // will be deleting feed lists as they become empty.
-            for (int i = feeds.size() - 1; i >= 0; --i) {
-                List<FeedItem> items = feeds.get(i);
-                queue.add(items.remove(0));
-                // Removed the last item in this particular feed? Then remove this feed from the
-                // list of feeds.
-                if (items.isEmpty()) {
-                    feeds.remove(i);
+                (f1, f2) -> f1.get(0).getFeed().getTitle().compareTo(f2.get(0).getFeed().getTitle()));
+
+        // Spread each episode out
+        Map<Long, List<FeedItem>> spreadItems = new HashMap<>();
+        for (List<FeedItem> feedItems : feeds) {
+            long thisSpread = spread / feedItems.size();
+            // Starting from 0 ensures we front-load, so the queue starts with one episode from
+            // each feed in the queue
+            long itemSpread = 0;
+            for (FeedItem feedItem : feedItems) {
+                if (!spreadItems.containsKey(itemSpread)) {
+                    spreadItems.put(itemSpread, new ArrayList<>());
                 }
+                spreadItems.get(itemSpread).add(feedItem);
+                itemSpread += thisSpread;
             }
         }
+
+        // Go through the spread items and add them to the queue
+        List<Long> spreads = new ArrayList<>(spreadItems.keySet());
+        Collections.sort(spreads);
+        for (long itemSpread : spreads) {
+            queue.addAll(spreadItems.get(itemSpread));
+        }
     }
 }