[banshee] Add weighted random-by-rating mode

[Gabriel Burt <gburt src gnome org>]

commit e9df7586406f61c746ba42abac19e3496d89f3b5
Author: Elena Grassi <grassi e gmail com>
Date:   Fri Jun 12 19:40:11 2009 -0500

    Add weighted random-by-rating mode
    
    Patch from Elena Grassi, revised by Alexander Kojevnikov.  Higher rated
    songs are more likely to be picked.
    
    Signed-off-by: Gabriel Burt <gabriel burt gmail com>

 .../DatabaseTrackListModel.cs                      |   80 ++++++++++++++++++++
 .../PlaybackShuffleMode.cs                         |    3 +-
 .../Banshee.Gui/PlaybackShuffleActions.cs          |   11 ++-
 3 files changed, 91 insertions(+), 3 deletions(-)
---
diff --git a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs
index adb03d6..e5e2757 100644
--- a/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs
+++ b/src/Core/Banshee.Services/Banshee.Collection.Database/DatabaseTrackListModel.cs
@@ -31,6 +31,7 @@ using System;
 using System.Data;
 using System.Text;
 using System.Collections.Generic;
+using System.Linq;
 
 using Mono.Unix;
 
@@ -343,6 +344,11 @@ namespace Banshee.Collection.Database
         private static string random_fragment = String.Format ("{0} ORDER BY RANDOM()", random_condition);
         private static string random_by_album_fragment = String.Format ("AND CoreTracks.AlbumID = ? {0} ORDER BY Disc ASC, TrackNumber ASC", random_condition);
         private static string random_by_artist_fragment = String.Format ("AND CoreAlbums.ArtistID = ? {0} ORDER BY CoreTracks.Year, CoreTracks.AlbumID ASC, Disc ASC, TrackNumber ASC", random_condition);
+        private static string random_by_rating_fragment = @"
+            AND (LastPlayedStamp < ? OR LastPlayedStamp IS NULL)
+            AND (LastSkippedStamp < ? OR LastSkippedStamp IS NULL)
+            AND (CoreTracks.Rating = ? OR (? = 3 AND CoreTracks.Rating = 0))
+            ORDER BY RANDOM()";
 
         private DateTime random_began_at = DateTime.MinValue;
         private DateTime last_random = DateTime.MinValue;
@@ -407,6 +413,17 @@ namespace Banshee.Collection.Database
                     return cache.GetSingle (random_by_artist_fragment, (int)random_artist_id, random_began_at, random_began_at);
                 }
                 return null;
+            } else if (mode == PlaybackShuffleMode.Rating) {
+                int random_rating = GetRandomRating (random_began_at);
+                if (random_rating == 0 && repeat) {
+                    random_began_at = last_random;
+                    random_rating = GetRandomRating (random_began_at);
+                }
+
+                if (random_rating != 0) {
+                    return cache.GetSingle (random_by_rating_fragment, random_began_at, random_began_at, random_rating, random_rating);
+                }
+                return null;
             } else {
                 random_album_id = random_artist_id = null;
             }
@@ -472,6 +489,69 @@ namespace Banshee.Collection.Database
             return artist_id;
         }
 
+        private readonly Random random = new Random ();
+        private int GetRandomRating (DateTime stamp)
+        {
+            // Default rating for unrated songs.
+            const int unrated_rating = 3;
+            // counts[x] = number of tracks rated x + 1.
+            int[] counts = new int[5];
+            // Get the distribution of ratings for tracks that haven't been played since stamp.
+            using (var reader = connection.Query (@"
+                SELECT t.Rating, COUNT(*)
+                FROM CoreTracks AS t
+                JOIN CoreCache AS c ON c.ItemID = t.TrackID
+                WHERE
+                    c.ModelID = ? AND
+                    t.LastStreamError = 0 AND
+                    (t.LastPlayedStamp < ? OR t.LastPlayedStamp IS NULL) AND
+                    (t.LastSkippedStamp < ? OR t.LastSkippedStamp IS NULL)
+                GROUP BY t.Rating",
+                CacheId, stamp, stamp)) {
+
+                while (reader.Read ()) {
+                    int rating = Convert.ToInt32 (reader[0]);
+                    int count = Convert.ToInt32 (reader[1]);
+
+                    if (rating < 1 || rating > 5) {
+                        rating = unrated_rating;
+                    }
+
+                    counts[rating - 1] += count;
+                }
+            }
+
+            if (counts.Sum () == 0) {
+                return 0;
+            }
+
+            // We will use powers of phi as weights. Such weights result in songs rated R
+            // played as often as songs rated R-1 and R-2 combined.
+            const double phi = 1.618033989;
+
+            // If you change the weights make sure ALL of them are strictly positive.
+            var weights = Enumerable.Range (0, 5).Select (i => Math.Pow (phi, i)).ToArray ();
+
+            // Apply weights to the counts.
+            var weighted_counts = counts.Select ((c, i) => c * weights[i]);
+
+            // Normalise the counts.
+            var weighted_total = weighted_counts.Sum ();
+            weighted_counts = weighted_counts.Select (c => c / weighted_total);
+
+            // Now that we have our counts, get a weighted random rating.
+            double random_value = random.NextDouble ();
+            int current_rating = 0;
+            foreach (var weighted_count in weighted_counts) {
+                current_rating++;
+                random_value -= weighted_count;
+                if (random_value <= 0.0) {
+                    break;
+                }
+            }
+            return current_rating;
+        }
+
 #endregion
 
         public override TrackInfo this[int index] {
diff --git a/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs b/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs
index b7e1ea5..1cd3493 100644
--- a/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs
+++ b/src/Core/Banshee.Services/Banshee.PlaybackController/PlaybackShuffleMode.cs
@@ -35,7 +35,8 @@ namespace Banshee.PlaybackController
         Linear,
         Song,
         Artist,
-        Album
+        Album,
+        Rating
     }
 
     public class ShuffleModeChangedEventArgs : EventArgs
diff --git a/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs b/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs
index 983335d..1702682 100644
--- a/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs
+++ b/src/Core/Banshee.ThickClient/Banshee.Gui/PlaybackShuffleActions.cs
@@ -95,13 +95,19 @@ namespace Banshee.Gui
                 new RadioActionEntry ("ShuffleAlbumAction", null,
                     Catalog.GetString ("Shuffle by A_lbum"), null,
                     Catalog.GetString ("Play all songs from an album, then randomly choose another album"),
-                    (int)PlaybackShuffleMode.Album)
+                    (int)PlaybackShuffleMode.Album),
+
+                new RadioActionEntry ("ShuffleRatingAction", null,
+                    Catalog.GetString ("Shuffle by _Rating"), null,
+                    Catalog.GetString ("Play songs randomly, prefer higher rated songs"),
+                    (int)PlaybackShuffleMode.Rating),
             }, 0, OnActionChanged);
                 
             this["ShuffleOffAction"].IconName = "media-skip-forward";
             this["ShuffleSongAction"].IconName = "media-playlist-shuffle";
             this["ShuffleArtistAction"].IconName = "media-playlist-shuffle";
             this["ShuffleAlbumAction"].IconName = "media-playlist-shuffle";
+            this["ShuffleRatingAction"].IconName = "media-playlist-shuffle";
 
             ServiceManager.PlaybackController.ShuffleModeChanged += OnShuffleModeChanged;
             ServiceManager.PlaybackController.SourceChanged += OnPlaybackSourceChanged;
@@ -198,6 +204,7 @@ namespace Banshee.Gui
             yield return (RadioAction)this["ShuffleSongAction"];
             yield return (RadioAction)this["ShuffleArtistAction"];
             yield return (RadioAction)this["ShuffleAlbumAction"];
+            yield return (RadioAction)this["ShuffleRatingAction"];
         }
 
         IEnumerator IEnumerable.GetEnumerator ()
@@ -220,7 +227,7 @@ namespace Banshee.Gui
             "playback", "shuffle_mode",
             "off",
             "Shuffle playback",
-            "Shuffle mode (shuffle_off, shuffle_song, shuffle_artist, shuffle_album)"
+            "Shuffle mode (shuffle_off, shuffle_song, shuffle_artist, shuffle_album, shuffle_rating)"
         );
     }
 }