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