shell/rb-play-order-random.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*-
   2  *
   3  *  arch-tag: Implementation of base class for weighted random play orders
   4  *
   5  *  Copyright (C) 2003 Jeffrey Yasskin <jyasskin@mail.utexas.edu>
   6  *
   7  *  This program is free software; you can redistribute it and/or modify
   8  *  it under the terms of the GNU General Public License as published by
   9  *  the Free Software Foundation; either version 2 of the License, or
  10  *  (at your option) any later version.
  11  *
  12  *  This program is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *  GNU General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU General Public License
  18  *  along with this program; if not, write to the Free Software
  19  *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA.
  20  *
  21  */
  22
  23 /* This class is a base case for weighted random play orders. Subclasses only
  24  * need to override get_entry_weight() to return the right weight for a given
  25  * entry.
  26  *
  27  * This class also delays committing any changes until the user moves to the
  28  * next or previous song. So if the user changes the entry-view to contain
  29  * different songs, but changes it back before the current song finishes, they
  30  * will not see any changes to their history of played songs.
  31  */
  32
  33 #include "config.h"
  34
  35 #include <string.h>
  36
  37 #include "rb-play-order-random-by-age.h"
  38
  39 #include "rb-debug.h"
  40 #include "rhythmdb.h"
  41 #include "rb-history.h"
  42
  43 static void rb_random_play_order_class_init (RBRandomPlayOrderClass *klass);
  44 static void rb_random_play_order_init (RBRandomPlayOrder *rorder);
  45
  46 static void rb_random_play_order_finalize (GObject *object);
  47
  48 static RhythmDBEntry* rb_random_play_order_get_next (RBPlayOrder* porder);
  49 static void rb_random_play_order_go_next (RBPlayOrder* porder);
  50 static RhythmDBEntry* rb_random_play_order_get_previous (RBPlayOrder* porder);
  51 static void rb_random_play_order_go_previous (RBPlayOrder* porder);
  52
  53 static void rb_random_db_changed (RBPlayOrder *porder, RhythmDB *db);
  54 static void rb_random_playing_entry_changed (RBPlayOrder *porder,
  55                                              RhythmDBEntry *old_entry,
  56                                              RhythmDBEntry *new_entry);
  57 static void rb_random_query_model_changed (RBPlayOrder *porder);
  58 static void rb_random_db_entry_deleted (RBPlayOrder *porder, RhythmDBEntry *entry);
  59
  60 static void rb_random_handle_query_model_changed (RBRandomPlayOrder *rorder);
  61 static void rb_random_filter_history (RBRandomPlayOrder *rorder, RhythmDBQueryModel *model);
  62
  63 struct RBRandomPlayOrderPrivate
  64 {
  65         RBHistory *history;
  66
  67         gboolean query_model_changed;
  68 };
  69
  70 G_DEFINE_TYPE (RBRandomPlayOrder, rb_random_play_order, RB_TYPE_PLAY_ORDER)
  71 #define RB_RANDOM_PLAY_ORDER_GET_PRIVATE(o) (G_TYPE_INSTANCE_GET_PRIVATE ((o), RB_TYPE_RANDOM_PLAY_ORDER, RBRandomPlayOrderPrivate))
  72
  73 static void
  74 rb_random_play_order_class_init (RBRandomPlayOrderClass *klass)
  75 {
  76         GObjectClass *object_class = G_OBJECT_CLASS (klass);
  77         RBPlayOrderClass *porder;
  78
  79         object_class->finalize = rb_random_play_order_finalize;
  80
  81         porder = RB_PLAY_ORDER_CLASS (klass);
  82         porder->db_changed = rb_random_db_changed;
  83         porder->playing_entry_changed = rb_random_playing_entry_changed;
  84         porder->entry_added = (void (*)(RBPlayOrder*,RhythmDBEntry*))rb_random_query_model_changed;
  85         porder->entry_removed = (void (*)(RBPlayOrder*,RhythmDBEntry*))rb_random_query_model_changed;
  86         porder->query_model_changed = rb_random_query_model_changed;
  87         porder->db_entry_deleted = rb_random_db_entry_deleted;
  88
  89         porder->has_next = rb_play_order_model_not_empty;
  90         porder->get_next = rb_random_play_order_get_next;
  91         porder->go_next = rb_random_play_order_go_next;
  92         porder->get_previous = rb_random_play_order_get_previous;
  93         porder->go_previous = rb_random_play_order_go_previous;
  94
  95         g_type_class_add_private (klass, sizeof (RBRandomPlayOrderPrivate));
  96 }
  97
  98 static void
  99 rb_random_play_order_init (RBRandomPlayOrder *rorder)
 100 {
 101         rorder->priv = RB_RANDOM_PLAY_ORDER_GET_PRIVATE (rorder);
 102
 103         rorder->priv->history = rb_history_new (TRUE,
 104                                                 (GFunc) rhythmdb_entry_unref,
 105                                                 NULL);
 106         rb_history_set_maximum_size (rorder->priv->history, 50);
 107
 108         rorder->priv->query_model_changed = TRUE;
 109 }
 110
 111 static void
 112 rb_random_play_order_finalize (GObject *object)
 113 {
 114         RBRandomPlayOrder *rorder;
 115
 116         g_return_if_fail (object != NULL);
 117         g_return_if_fail (RB_IS_RANDOM_PLAY_ORDER (object));
 118
 119         rorder = RB_RANDOM_PLAY_ORDER (object);
 120
 121         g_object_unref (G_OBJECT (rorder->priv->history));
 122
 123         G_OBJECT_CLASS (rb_random_play_order_parent_class)->finalize (object);
 124 }
 125
 126 static double
 127 rb_random_play_order_get_entry_weight (RBRandomPlayOrder *rorder, RhythmDB *db,
 128                                        RhythmDBEntry *entry)
 129 {
 130         g_return_val_if_fail (rorder != NULL, 1.0);
 131         g_return_val_if_fail (RB_RANDOM_PLAY_ORDER_GET_CLASS (rorder)->get_entry_weight != NULL, 1.0);
 132         return RB_RANDOM_PLAY_ORDER_GET_CLASS (rorder)->get_entry_weight (rorder, db, entry);
 133 }
 134
 135 static inline RBHistory *
 136 get_history (RBRandomPlayOrder *rorder)
 137 {
 138         return rorder->priv->history;
 139 }
 140
 141 typedef struct {
 142         RhythmDBEntry *entry;
 143         double weight;
 144         double cumulative_weight;
 145 } EntryWeight;
 146
 147 static GArray *
 148 get_query_model_contents (RBRandomPlayOrder *rorder, RhythmDBQueryModel *model)
 149 {
 150         guint num_entries;
 151         guint i;
 152         RhythmDB *db;
 153         double weight = 0.0;
 154         double cumulative_weight = 0.0;
 155         GtkTreeIter iter;
 156         GArray *result = g_array_new (FALSE, FALSE, sizeof (EntryWeight));
 157
 158         if (model == NULL)
 159                 return result;
 160
 161         num_entries = gtk_tree_model_iter_n_children (GTK_TREE_MODEL (model), NULL);
 162         if (num_entries == 0)
 163                 return result;
 164
 165         g_array_set_size (result, num_entries);
 166         db = rb_play_order_get_db (RB_PLAY_ORDER (rorder));
 167
 168         if (!gtk_tree_model_get_iter_first (GTK_TREE_MODEL (model), &iter))
 169                 return result;
 170
 171         i = 0;
 172         do {
 173                 RhythmDBEntry *entry = rhythmdb_query_model_iter_to_entry (model, &iter);
 174
 175                 if (entry == NULL)
 176                         continue;
 177
 178                 weight = rb_random_play_order_get_entry_weight (rorder, db, entry);
 179
 180                 g_array_index (result, EntryWeight, i).entry = entry;
 181                 g_array_index (result, EntryWeight, i).weight = weight;
 182                 g_array_index (result, EntryWeight, i).cumulative_weight = cumulative_weight;
 183                 cumulative_weight += weight;
 184                 i++;
 185
 186                 rhythmdb_entry_unref (entry);
 187
 188         } while (gtk_tree_model_iter_next (GTK_TREE_MODEL (model), &iter));
 189
 190         return result;
 191 }
 192
 193 static void
 194 rb_random_handle_query_model_changed (RBRandomPlayOrder *rorder)
 195 {
 196         RhythmDBQueryModel *model;
 197
 198         if (!rorder->priv->query_model_changed)
 199                 return;
 200
 201         model = rb_play_order_get_query_model (RB_PLAY_ORDER (rorder));
 202         rb_random_filter_history (rorder, model);
 203         rorder->priv->query_model_changed = FALSE;
 204 }
 205
 206 static void
 207 rb_random_filter_history (RBRandomPlayOrder *rorder, RhythmDBQueryModel *model)
 208 {
 209         GPtrArray *history_contents;
 210         int i;
 211
 212         history_contents = rb_history_dump (rorder->priv->history);
 213         for (i = 0; i < history_contents->len; ++i) {
 214                 gboolean remove = TRUE;
 215                 if (model) {
 216                         GtkTreeIter iter;
 217                         if (rhythmdb_query_model_entry_to_iter (model, g_ptr_array_index (history_contents, i), &iter))
 218                                 remove = FALSE;
 219                 }
 220
 221                 if (remove) {
 222                         rb_history_remove_entry (rorder->priv->history,
 223                                                  g_ptr_array_index (history_contents, i));
 224                 }
 225         }
 226
 227         g_ptr_array_free (history_contents, TRUE);
 228 }
 229
 230 static inline double
 231 rb_random_get_total_weight (GArray *weights)
 232 {
 233         EntryWeight *last;
 234
 235         g_return_val_if_fail (weights, 0.0);
 236         if (weights->len == 0)
 237                 return 0.0;
 238
 239         last = &g_array_index (weights,
 240                                EntryWeight,
 241                                weights->len - 1);
 242         return last->cumulative_weight + last->weight;
 243 }
 244
 245 static RhythmDBEntry*
 246 rb_random_play_order_pick_entry (RBRandomPlayOrder *rorder)
 247 {
 248         /* This is O(N) because we traverse the query model to get the entries
 249          * and weights.
 250          *
 251          * The general idea of this algorithm is that there is a line segment
 252          * whose length is the sum of all the entries' weights. Each entry gets
 253          * a sub-segment whose length is equal to that entry's weight. A random
 254          * point is picked in the line segment, and the entry that point
 255          * belongs to is returned.
 256          *
 257          * The algorithm was contributed by treed.
 258          */
 259         double total_weight, rnd;
 260         int high, low;
 261         GArray *entry_weights;
 262         RhythmDBEntry *entry;
 263         RhythmDBQueryModel *model;
 264
 265         model = rb_play_order_get_query_model (RB_PLAY_ORDER (rorder));
 266
 267         entry_weights = get_query_model_contents (rorder, model);
 268
 269         total_weight = rb_random_get_total_weight (entry_weights);
 270         if (total_weight == 0.0)
 271                 return NULL;
 272
 273         rnd = g_random_double_range (0, total_weight);
 274         /* Binary search for the entry with cumulative weight closest to but
 275          * less than rnd */
 276         low = -1; high = entry_weights->len;
 277         while (high - low > 1) {
 278                 int mid = (high + low) / 2;
 279                 if (g_array_index (entry_weights, EntryWeight, mid).cumulative_weight > rnd)
 280                         high = mid;
 281                 else
 282                         low = mid;
 283         }
 284         entry = g_array_index (entry_weights, EntryWeight, low).entry;
 285
 286         g_array_free (entry_weights, TRUE);
 287
 288         return entry;
 289 }
 290
 291 static RhythmDBEntry*
 292 rb_random_play_order_get_next (RBPlayOrder* porder)
 293 {
 294         RBRandomPlayOrder *rorder;
 295         RhythmDBEntry *entry, *current;
 296         RBHistory *history;
 297
 298         g_return_val_if_fail (porder != NULL, NULL);
 299         g_return_val_if_fail (RB_IS_RANDOM_PLAY_ORDER (porder), NULL);
 300
 301         rorder = RB_RANDOM_PLAY_ORDER (porder);
 302
 303         rb_random_handle_query_model_changed (rorder);
 304         history = get_history (rorder);
 305
 306         current = rb_play_order_get_playing_entry (porder);
 307         entry = NULL;
 308
 309         if (rb_history_length (history) == 0
 310             || (current == rb_history_current (history)
 311                 && rb_history_current (history) == rb_history_last (history))) {
 312
 313                 rb_debug ("choosing random entry");
 314                 entry = rb_random_play_order_pick_entry (rorder);
 315                 if (entry) {
 316                         rhythmdb_entry_ref (entry);
 317                         rb_history_append (history, rhythmdb_entry_ref (entry));
 318                 }
 319         } else {
 320                 rb_debug ("choosing enqueued entry");
 321
 322                 if (current == rb_history_current (history))
 323                         entry = rb_history_next (history);
 324                 else
 325                         entry = rb_history_current (history);
 326
 327                 if (entry)
 328                         rhythmdb_entry_ref (entry);
 329         }
 330
 331         if (current)
 332                 rhythmdb_entry_unref (current);
 333         return entry;
 334 }
 335
 336 static void
 337 rb_random_play_order_go_next (RBPlayOrder* porder)
 338 {
 339         RBRandomPlayOrder *rorder;
 340         RhythmDBEntry *entry;
 341         RBHistory *history;
 342
 343         g_return_if_fail (porder != NULL);
 344         g_return_if_fail (RB_IS_RANDOM_PLAY_ORDER (porder));
 345
 346         rorder = RB_RANDOM_PLAY_ORDER (porder);
 347         history = get_history (rorder);
 348
 349         /* I think this forces the next track to be added to the history */
 350         entry =  rb_random_play_order_get_next (porder);
 351         if (entry)
 352                 rhythmdb_entry_unref (entry);
 353
 354         if (rb_history_current (history) == NULL)
 355                 rb_history_go_first (history);
 356         else
 357                 rb_history_go_next (history);
 358         rb_play_order_set_playing_entry (porder, rb_history_current (history));
 359 }
 360
 361 static RhythmDBEntry*
 362 rb_random_play_order_get_previous (RBPlayOrder* porder)
 363 {
 364         RBRandomPlayOrder *rorder;
 365         RhythmDBEntry *entry;
 366
 367         g_return_val_if_fail (porder != NULL, NULL);
 368         g_return_val_if_fail (RB_IS_RANDOM_PLAY_ORDER (porder), NULL);
 369
 370         rorder = RB_RANDOM_PLAY_ORDER (porder);
 371
 372         rb_random_handle_query_model_changed (rorder);
 373
 374         rb_debug ("choosing history entry");
 375         entry = rb_history_previous (get_history (rorder));
 376         if (entry)
 377                 rhythmdb_entry_ref (entry);
 378
 379         return entry;
 380 }
 381
 382 static void
 383 rb_random_play_order_go_previous (RBPlayOrder* porder)
 384 {
 385         RBRandomPlayOrder *rorder;
 386         RBHistory *history;
 387
 388         g_return_if_fail (porder != NULL);
 389         g_return_if_fail (RB_IS_RANDOM_PLAY_ORDER (porder));
 390         /* It doesn't make sense to call go_previous when the player is stopped */
 391         g_return_if_fail (rb_play_order_player_is_playing (porder));
 392
 393         rorder = RB_RANDOM_PLAY_ORDER (porder);
 394         history = get_history (rorder);
 395
 396         rb_history_go_previous (history);
 397         rb_play_order_set_playing_entry (porder, rb_history_current (history));
 398 }
 399
 400 static void
 401 rb_random_db_changed (RBPlayOrder *porder, RhythmDB *db)
 402 {
 403         g_return_if_fail (RB_IS_RANDOM_PLAY_ORDER (porder));
 404
 405         rb_history_clear (RB_RANDOM_PLAY_ORDER (porder)->priv->history);
 406 }
 407
 408 static void
 409 rb_random_playing_entry_changed (RBPlayOrder *porder,
 410                                  RhythmDBEntry *old_entry,
 411                                  RhythmDBEntry *new_entry)
 412 {
 413         RBRandomPlayOrder *rorder;
 414
 415         g_return_if_fail (RB_IS_RANDOM_PLAY_ORDER (porder));
 416         rorder = RB_RANDOM_PLAY_ORDER (porder);
 417
 418         if (new_entry) {
 419                 if (new_entry == rb_history_current (get_history (rorder))) {
 420                         /* Do nothing */
 421                 } else {
 422                         rhythmdb_entry_ref (new_entry);
 423                         rb_history_set_playing (get_history (rorder), new_entry);
 424                 }
 425         }
 426 }
 427
 428 static void
 429 rb_random_query_model_changed (RBPlayOrder *porder)
 430 {
 431         g_return_if_fail (RB_IS_RANDOM_PLAY_ORDER (porder));
 432         RB_RANDOM_PLAY_ORDER (porder)->priv->query_model_changed = TRUE;
 433 }
 434
 435 static void
 436 rb_random_db_entry_deleted (RBPlayOrder *porder, RhythmDBEntry *entry)
 437 {
 438         /* When an entry is deleted from the database, it needs to vanish from
 439          * all histories immediately. */
 440         RBRandomPlayOrder *rorder;
 441         g_return_if_fail (RB_IS_RANDOM_PLAY_ORDER (porder));
 442
 443         rorder = RB_RANDOM_PLAY_ORDER (porder);
 444         rb_history_remove_entry (rorder->priv->history, entry);
 445 }
 446