From a265d17f5472469d5d4b55d7d97c8940eff32885 Mon Sep 17 00:00:00 2001 From: ByteHamster Date: Sat, 20 Aug 2022 18:13:54 +0200 Subject: Rework smart shuffle --- .../antennapod/core/util/FeedItemPermutors.java | 102 ++++++++------------- 1 file changed, 38 insertions(+), 64 deletions(-) (limited to 'core') diff --git a/core/src/main/java/de/danoeh/antennapod/core/util/FeedItemPermutors.java b/core/src/main/java/de/danoeh/antennapod/core/util/FeedItemPermutors.java index 7f2742ab0..12377791e 100644 --- a/core/src/main/java/de/danoeh/antennapod/core/util/FeedItemPermutors.java +++ b/core/src/main/java/de/danoeh/antennapod/core/util/FeedItemPermutors.java @@ -8,6 +8,7 @@ import java.util.Collections; import java.util.Comparator; import java.util.Date; import java.util.HashMap; +import java.util.Iterator; import java.util.List; import java.util.Locale; import java.util.Map; @@ -116,38 +117,23 @@ public class FeedItemPermutors { * 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 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. + * Assume the queue looks like this: `ABCDDEEEEEEEEEE`. + * This method first starts with a queue of the final size, where each slot is empty (null). + * It takes the podcast with most episodes (`E`) and places the episodes spread out in the queue: `EE_E_EE_E_EE_EE`. + * The podcast with the second-most number of episodes (`D`) is then + * placed spread-out in the *available* slots: `EE_EDEE_EDEE_EE`. + * This continues, until we end up with: `EEBEDEECEDEEAEE`. * - * 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 aren't strictly ordered in terms of pubdate, but episodes - * of each feed do appear in pubdate order) + * Note that episodes aren't strictly ordered in terms of pubdate, but episodes of each feed are. * * @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 queue, boolean ascending) { - // Divide FeedItems into lists by feed - Map> map = new HashMap<>(); - - while (!queue.isEmpty()) { - FeedItem item = queue.remove(0); + for (FeedItem item : queue) { Long id = item.getFeedId(); if (!map.containsKey(id)) { map.put(id, new ArrayList<>()); @@ -156,55 +142,43 @@ public class FeedItemPermutors { } // Sort each individual list by PubDate (ascending/descending) - Comparator itemComparator = ascending - ? (f1, f2) -> f1.getPubDate().compareTo(f2.getPubDate()) - : (f1, f2) -> f2.getPubDate().compareTo(f1.getPubDate()); - - // Calculate the spread - - long spread = 0; + ? (f1, f2) -> f1.getPubDate().compareTo(f2.getPubDate()) + : (f1, f2) -> f2.getPubDate().compareTo(f1.getPubDate()); + List> feeds = new ArrayList<>(); for (Map.Entry> mapEntry : map.entrySet()) { - List feedItems = mapEntry.getValue(); - Collections.sort(feedItems, itemComparator); - if (spread == 0) { - spread = feedItems.size(); - } else if (spread % feedItems.size() != 0){ - spread *= feedItems.size(); - } + Collections.sort(mapEntry.getValue(), itemComparator); + feeds.add(mapEntry.getValue()); } - // 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> feeds = new ArrayList<>(map.values()); - Collections.sort(feeds, - (f1, f2) -> f1.get(0).getFeed().getTitle().compareTo(f2.get(0).getFeed().getTitle())); + ArrayList emptySlots = new ArrayList<>(); + for (int i = 0; i < queue.size(); i++) { + queue.set(i, null); + emptySlots.add(i); + } - // Spread each episode out - Map> spreadItems = new HashMap<>(); + // Starting with the largest feed, place items spread out through the empty slots in the queue + Collections.sort(feeds, (f1, f2) -> Integer.compare(f2.size(), f1.size())); for (List feedItems : feeds) { - long thisSpread = spread / feedItems.size(); - if (thisSpread == 0) { - thisSpread = 1; - } - // 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<>()); + double spread = (double) emptySlots.size() / (feedItems.size() + 1); + Iterator emptySlotIterator = emptySlots.iterator(); + int skipped = 0; + int placed = 0; + while (emptySlotIterator.hasNext()) { + int nextEmptySlot = emptySlotIterator.next(); + skipped++; + if (skipped >= spread * (placed + 1)) { + if (queue.get(nextEmptySlot) != null) { + throw new RuntimeException("Slot to be placed in not empty"); + } + queue.set(nextEmptySlot, feedItems.get(placed)); + emptySlotIterator.remove(); + placed++; + if (placed == feedItems.size()) { + break; + } } - spreadItems.get(itemSpread).add(feedItem); - itemSpread += thisSpread; } } - - // Go through the spread items and add them to the queue - List spreads = new ArrayList<>(spreadItems.keySet()); - Collections.sort(spreads); - for (long itemSpread : spreads) { - queue.addAll(spreadItems.get(itemSpread)); - } } } -- cgit v1.2.3