Added "Random" and "Smart Shuffle" items at the bottom of the Queue|Sort menu.

Added "Permutor" interface to allow specification of reordering logic to be specified in QueueSorter (vs. DBWriter), similar to the existing sort logic.

Added "Random" and "Smart Shuffle" strings to core/src/main/res/values (did not add translations for non-English languages)

Closes #2366, Closes #2602

4 files changed, 151 insertions, 1 deletions

diff --git a/core/src/main/java/de/danoeh/antennapod/core/storage/DBWriter.java b/core/src/main/java/de/danoeh/antennapod/core/storage/DBWriter.java
index 75510d2f6..49de7ffe7 100644
--- a/core/src/main/java/de/danoeh/antennapod/core/storage/DBWriter.java
+++ b/core/src/main/java/de/danoeh/antennapod/core/storage/DBWriter.java
@@ -43,6 +43,7 @@ import de.danoeh.antennapod.core.preferences.UserPreferences;
 import de.danoeh.antennapod.core.service.download.DownloadStatus;
 import de.danoeh.antennapod.core.service.playback.PlaybackService;
 import de.danoeh.antennapod.core.util.LongList;
+import de.danoeh.antennapod.core.util.Permutor;
 import de.danoeh.antennapod.core.util.flattr.FlattrStatus;
 import de.danoeh.antennapod.core.util.flattr.FlattrThing;
 import de.danoeh.antennapod.core.util.flattr.SimpleFlattrThing;
@@ -992,6 +993,32 @@ public class DBWriter {
     }
 
     /**
+     * Similar to sortQueue, but allows more complex reordering by providing whole-queue context.
+     * @param permutor        Encapsulates whole-Queue reordering logic.
+     * @param broadcastUpdate <code>true</code> if this operation should trigger a
+     *                        QueueUpdateBroadcast. This option should be set to <code>false</code>
+     *                        if the caller wants to avoid unexpected updates of the GUI.
+     */
+    public static Future<?> reorderQueue(final Permutor<FeedItem> permutor, final boolean broadcastUpdate) {
+        return dbExec.submit(() -> {
+            final PodDBAdapter adapter = PodDBAdapter.getInstance();
+            adapter.open();
+            final List<FeedItem> queue = DBReader.getQueue(adapter);
+
+            if (queue != null) {
+                permutor.reorder(queue);
+                adapter.setQueue(queue);
+                if (broadcastUpdate) {
+                    EventBus.getDefault().post(QueueEvent.sorted(queue));
+                }
+            } else {
+                Log.e(TAG, "reorderQueue: Could not load queue");
+            }
+            adapter.close();
+        });
+    }
+
+    /**
      * Sets the 'auto_download'-attribute of specific FeedItem.
      *
      * @param feedItem  FeedItem.
diff --git a/core/src/main/java/de/danoeh/antennapod/core/util/Permutor.java b/core/src/main/java/de/danoeh/antennapod/core/util/Permutor.java
new file mode 100644
index 000000000..7d6e20ab1
--- /dev/null
+++ b/core/src/main/java/de/danoeh/antennapod/core/util/Permutor.java
@@ -0,0 +1,17 @@
+package de.danoeh.antennapod.core.util;
+
+import java.util.List;
+
+/**
+ * Interface for passing around list permutor method. This is used for cases where a simple comparator
+ * won't work (e.g. Random, Smart Shuffle, etc).
+ *
+ * @param <E> the type of elements in the list
+ */
+public interface Permutor<E> {
+    /**
+     * Reorders the specified list.
+     * @param queue A (modifiable) list of elements to be reordered
+     */
+    void reorder(List<E> queue);
+}
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 c3b4c0e15..40b5bc24d 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
@@ -2,7 +2,12 @@ package de.danoeh.antennapod.core.util;
 
 import android.content.Context;
 
+import java.util.ArrayList;
+import java.util.Collections;
 import java.util.Comparator;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
 
 import de.danoeh.antennapod.core.feed.FeedItem;
 import de.danoeh.antennapod.core.feed.FeedMedia;
@@ -20,11 +25,15 @@ public class QueueSorter {
         DURATION_ASC,
         DURATION_DESC,
         FEED_TITLE_ASC,
-        FEED_TITLE_DESC
+        FEED_TITLE_DESC,
+        RANDOM,
+        SMART_SHUFFLE_ASC,
+        SMART_SHUFFLE_DESC
     }
 
     public static void sort(final Context context, final Rule rule, final boolean broadcastUpdate) {
         Comparator<FeedItem> comparator = null;
+        Permutor<FeedItem> permutor = null;
 
         switch (rule) {
             case EPISODE_TITLE_ASC:
@@ -68,11 +77,106 @@ public class QueueSorter {
             case FEED_TITLE_DESC:
                 comparator = (f1, f2) -> f2.getFeed().getTitle().compareTo(f1.getFeed().getTitle());
                 break;
+            case RANDOM:
+                permutor = Collections::shuffle;
+                break;
+            case SMART_SHUFFLE_ASC:
+                permutor = (queue) -> SmartShuffle(queue, true);
+                break;
+            case SMART_SHUFFLE_DESC:
+                permutor = (queue) -> SmartShuffle(queue, false);
+                break;
             default:
         }
 
         if (comparator != null) {
             DBWriter.sortQueue(comparator, broadcastUpdate);
+        } else if (permutor != null) {
+            DBWriter.reorderQueue(permutor, broadcastUpdate);
+        }
+    }
+
+    /**
+     * Implements a reordering by pubdate that avoids consecutive episodes from the same feed in
+     * the queue.
+     *
+     * A listener might want to hear episodes from any given feed in pubdate order, but would
+     * 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.
+     *
+     * 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:
+     *
+     * B1, B2, B3, A1, A2, C1, C2, C3, A3
+     *
+     * (note that feed B episodes were all published before the first feed A episode, so a simple
+     * pubdate sort will often result in significant clustering of episodes from a single feed)
+     *
+     * Using Smart Shuffle, the resulting queue would look like the following:
+     *
+     * A1, B1, C1, A2, B2, C2, A3, B3, C3
+     *
+     * (note that episodes above <i>aren't strictly ordered in terms of pubdate</i>, but episodes
+     * of each feed <b>do</b> appear in pubdate order)
+     *
+     * @param queue A (modifiable) list of FeedItem elements to be reordered.
+     * @param ascending {@code true} to use ascending pubdate in the reordering;
+     *                  {@code false} for descending.
+     */
+    private static void SmartShuffle(List<FeedItem> queue, boolean ascending) {
+
+        // Divide FeedItems into lists by feed
+
+        Map<Long, List<FeedItem>> map = new HashMap<>();
+
+        while (!queue.isEmpty()) {
+            FeedItem item = queue.remove(0);
+            Long id = item.getFeedId();
+            if (!map.containsKey(id))
+                map.put(id, new ArrayList<>());
+            map.get(id).add(item);
+        }
+
+        // Sort each individual list by PubDate (ascending/descending)
+
+        Comparator<FeedItem> itemComparator = ascending
+            ? (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);
+
+        // Create a list of the individual FeedItems lists, and sort it by feed title (ascending).
+        // Doing this ensures that the feed order we use is predictable/deterministic.
+
+        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);
+            }
         }
     }
 }
diff --git a/core/src/main/res/values/strings.xml b/core/src/main/res/values/strings.xml
index 2ebc2ad77..46bac68c9 100644
--- a/core/src/main/res/values/strings.xml
+++ b/core/src/main/res/values/strings.xml
@@ -260,6 +260,8 @@
     <string name="duration">Duration</string>
     <string name="episode_title">Episode title</string>
     <string name="feed_title">Feed title</string>
+    <string name="random">Random</string>
+    <string name="smart_shuffle">Smart Shuffle</string>
     <string name="ascending">Ascending</string>
     <string name="descending">Descending</string>
     <string name="clear_queue_confirmation_msg">Please confirm that you want to clear the queue of ALL of the episodes in it</string>