1 /*****************************************************************************
3 *****************************************************************************
4 * Copyright (C) 2018 VLC authors and VideoLAN
6 * This program is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as published by
8 * the Free Software Foundation; either version 2.1 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public License
17 * along with this program; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
19 *****************************************************************************/
25 #ifdef TEST_RANDOMIZER
31 #include <vlc_common.h>
33 #include "randomizer.h"
36 * \addtogroup playlist_randomizer Playlist randomizer helper
39 * Playlist helper to manage random playback.
41 * The purpose is to guarantee the following rules:
42 * - an item must never be selected twice
43 * - "prev" navigates back in the history of previously selected items
44 * - insertions and removals can occur at any time; all these rules must still
46 * - the user can request to select a specific item (typically by
47 * double-clicking on an item in the playlist)
49 * If loop (repeat) is enabled:
50 * - the random order must be "reshuffled" on every cycle
51 * - an item must never be selected twice in each cycle
52 * - the same item must never be selected twice in a row; in particular, it
53 * must not be the first item of a new cycle if it was the last item of the
54 * previous one (except if the playlist contains only one item)
55 * - crossing a new "cycle" is invisible to the user (e.g. it is still
56 * possible to navigate to previous selected items)
58 * To achieve these goals, a "randomizer" stores a single vector containing all
59 * the items of the playlist, along with 3 indexes.
61 * The whole vector is not shuffled at once: instead, steps of the Fisher-Yates
62 * algorithm are executed one-by-one on demand. This has several advantages:
63 * - on insertions and removals, there is no need to reshuffle or shift the
65 * - if loop is enabled, the history of the last cycle can be kept in place.
67 * 'head' indicates the end of the items already determinated for the current
68 * cycle (if loop is disabled, there is only one cycle).
71 * 'next' points to the item after the current one (we use 'next' instead of
72 * 'current' so that all indexes are unsigned, while 'current' could be -1).
73 * The current item is the one returned by the previous call to _Prev() or
74 * _Next(). Each call to _Next() makes 'next' (and possibly 'head') move
75 * forward, each call to _Prev() makes it move back (modulo size).
76 * 'next' is always in the determinated range (0 <= next <= head) or in the
77 * "history" range (history < next < size).
79 * 'history' is only used in loop mode, and references the first item of the
80 * ordered history from the last cycle.
82 * 0 next head history size
83 * |---------------|-----|.............|-------------|
84 * <-------------------> <----------->
85 * determinated range history range
87 * Here is a sample scenario to understand how it works.
89 * The playlist initially adds 5 items (A, B, C, D and E).
97 * The playlist calls _Next() to retrieve the next random item. The randomizer
98 * picks one item (say, D), and swaps it with the current head (A). _Next()
109 * The playlist calls _Next() one more time. The randomizer selects one item
110 * outside the determinated range (say, E). _Next() returns E.
120 * The playlist calls _Next() one more time. The randomizer selects C (already
121 * in place). _Next() returns C.
131 * The playlist then calls _Prev(). Since the "current" item is C, the previous
132 * one is E, so _Prev() returns E, and 'next' moves back.
142 * The playlist calls _Next(), which returns C, as expected.
152 * The playlist calls _Next(), the randomizer selects B, and returns it.
159 * <------------------>
162 * The playlist calls _Next(), the randomizer selects the last item (it has no
163 * choice). 'next' and 'head' now point one item past the end (their value is
171 * <----------------------->
174 * At this point, if loop is disabled, it is not possible to call _Next()
175 * anymore (_HasNext() returns false). So let's enable it by calling
176 * _SetLoop(), then let's call _Next() again.
178 * This will start a new loop cycle. Firstly, 'next' and 'head' are reset, and
179 * the whole vector belongs to the last cycle history.
186 * <------------------------>
189 * Secondly, to avoid to select A twice in a row (as the last item of the
190 * previous cycle and the first item of the new one), the randomizer will
191 * immediately determine another item in the vector (say C) to be the first of
192 * the new cycle. The items that belong to the history are kept in order.
193 * 'head' and 'history' move forward.
200 * <---><------------------>
201 * determinated history range
204 * Finally, it will actually select and return the first item (C).
211 * <---><------------------>
212 * determinated history range
215 * Then, the user adds an item to the playlist (F). This item is added in front
223 * <---> <------------------>
224 * determinated history range
227 * The playlist calls _Next(), the randomizer randomly selects E. E
228 * "disappears" from the history of the last cycle. This is a general property:
229 * each item may not appear more than one in the "history" (both from the last
230 * and the new cycle). The history order is preserved.
237 * <--------> <-------------->
238 * determinated history range
241 * The playlist then calls _Prev() 3 times, that yield C, then A, then B.
242 * 'next' is decremented (modulo size) on each call.
249 * <--------> <-------------->
250 * determinated history range
254 /* On auto-reshuffle, avoid to select the same item before at least
255 * NOT_SAME_BEFORE other items have been selected (between the end of the
256 * previous shuffle and the start of the new shuffle). */
257 #define NOT_SAME_BEFORE 1
260 randomizer_Init(struct randomizer
*r
)
262 vlc_vector_init(&r
->items
);
264 /* initialize separately instead of using vlc_lrand48() to avoid locking
265 * the mutex for every random number generation */
266 vlc_rand_bytes(r
->xsubi
, sizeof(r
->xsubi
));
275 randomizer_Destroy(struct randomizer
*r
)
277 vlc_vector_destroy(&r
->items
);
281 randomizer_SetLoop(struct randomizer
*r
, bool loop
)
286 static inline ssize_t
287 randomizer_IndexOf(struct randomizer
*r
, const vlc_playlist_item_t
*item
)
290 vlc_vector_index_of(&r
->items
, item
, &index
);
295 randomizer_Count(struct randomizer
*r
)
297 return r
->items
.size
;
301 randomizer_Reshuffle(struct randomizer
*r
)
303 /* yeah, it's that simple */
306 r
->history
= r
->items
.size
;
310 swap_items(struct randomizer
*r
, int i
, int j
)
312 vlc_playlist_item_t
*item
= r
->items
.data
[i
];
313 r
->items
.data
[i
] = r
->items
.data
[j
];
314 r
->items
.data
[j
] = item
;
318 randomizer_DetermineOne_(struct randomizer
*r
, size_t avoid_last_n
)
320 assert(r
->head
< r
->items
.size
);
321 assert(r
->items
.size
- r
->head
> avoid_last_n
);
322 size_t range_len
= r
->items
.size
- r
->head
- avoid_last_n
;
323 size_t selected
= r
->head
+ (nrand48(r
->xsubi
) % range_len
);
324 swap_items(r
, r
->head
, selected
);
326 if (r
->head
== r
->history
)
332 randomizer_DetermineOne(struct randomizer
*r
)
334 randomizer_DetermineOne_(r
, 0);
337 /* An autoreshuffle occurs if loop is enabled, once all item have been played.
338 * In that case, we reshuffle and determine first items so that the same item
339 * may not be selected before NOT_SAME_BEFORE selections. */
341 randomizer_AutoReshuffle(struct randomizer
*r
)
343 assert(r
->items
.size
> 0);
346 r
->history
= 0; /* the whole content is history */
347 size_t avoid_last_n
= NOT_SAME_BEFORE
;
348 if (avoid_last_n
> r
->items
.size
- 1)
349 /* cannot ignore all */
350 avoid_last_n
= r
->items
.size
- 1;
352 randomizer_DetermineOne_(r
, avoid_last_n
--);
356 randomizer_HasPrev(struct randomizer
*r
)
359 /* a previous exists if the current is > 0, i.e. next > 1 */
366 /* there is no previous only if (current - history) == 0 (modulo size),
367 * i.e. (next - history) == 1 (modulo size) */
368 return (r
->next
+ r
->items
.size
- r
->history
) % r
->items
.size
!= 1;
372 randomizer_HasNext(struct randomizer
*r
)
374 return r
->loop
|| r
->next
< r
->items
.size
;
377 vlc_playlist_item_t
*
378 randomizer_PeekPrev(struct randomizer
*r
)
380 assert(randomizer_HasPrev(r
));
381 size_t index
= (r
->next
+ r
->items
.size
- 2) % r
->items
.size
;
382 return r
->items
.data
[index
];
385 vlc_playlist_item_t
*
386 randomizer_PeekNext(struct randomizer
*r
)
388 assert(randomizer_HasNext(r
));
390 if (r
->next
== r
->items
.size
&& r
->next
== r
->history
)
393 randomizer_AutoReshuffle(r
);
396 if (r
->next
== r
->head
)
397 /* execute 1 step of the Fisher-Yates shuffle */
398 randomizer_DetermineOne(r
);
400 return r
->items
.data
[r
->next
];
403 vlc_playlist_item_t
*
404 randomizer_Prev(struct randomizer
*r
)
406 assert(randomizer_HasPrev(r
));
407 vlc_playlist_item_t
*item
= randomizer_PeekPrev(r
);
408 r
->next
= r
->next
? r
->next
- 1 : r
->items
.size
- 1;
412 vlc_playlist_item_t
*
413 randomizer_Next(struct randomizer
*r
)
415 assert(randomizer_HasNext(r
));
416 vlc_playlist_item_t
*item
= randomizer_PeekNext(r
);
418 if (r
->next
== r
->items
.size
&& r
->next
!= r
->head
)
424 randomizer_Add(struct randomizer
*r
, vlc_playlist_item_t
*items
[], size_t count
)
426 if (!vlc_vector_insert_all(&r
->items
, r
->history
, items
, count
))
428 /* the insertion shifted history (and possibly next) */
429 if (r
->next
> r
->history
)
436 randomizer_SelectIndex(struct randomizer
*r
, size_t index
)
438 vlc_playlist_item_t
*selected
= r
->items
.data
[index
];
439 if (r
->history
&& index
>= r
->history
)
441 if (index
> r
->history
)
443 memmove(&r
->items
.data
[r
->history
+ 1],
444 &r
->items
.data
[r
->history
],
445 (index
- r
->history
) * sizeof(selected
));
448 r
->history
= (r
->history
+ 1) % r
->items
.size
;
451 if (index
>= r
->head
)
453 r
->items
.data
[index
] = r
->items
.data
[r
->head
];
454 r
->items
.data
[r
->head
] = selected
;
457 else if (index
< r
->items
.size
- 1)
459 memmove(&r
->items
.data
[index
],
460 &r
->items
.data
[index
+ 1],
461 (r
->head
- index
- 1) * sizeof(selected
));
462 r
->items
.data
[r
->head
- 1] = selected
;
469 randomizer_Select(struct randomizer
*r
, const vlc_playlist_item_t
*item
)
471 ssize_t index
= randomizer_IndexOf(r
, item
);
472 assert(index
!= -1); /* item must exist */
473 randomizer_SelectIndex(r
, (size_t) index
);
477 randomizer_RemoveAt(struct randomizer
*r
, size_t index
)
480 * 0 head history next size
481 * |-----------|...................................|---------|-----|
482 * |<--------->| |<------------->|
483 * ordered order irrelevant ordered
486 /* update next before index may be updated */
492 /* item was selected, keep the selected part ordered */
493 memmove(&r
->items
.data
[index
],
494 &r
->items
.data
[index
+ 1],
495 (r
->head
- index
- 1) * sizeof(*r
->items
.data
));
497 index
= r
->head
; /* the new index to remove */
500 if (index
< r
->history
)
502 /* this part is unordered, no need to shift all items */
503 r
->items
.data
[index
] = r
->items
.data
[r
->history
- 1];
504 index
= r
->history
- 1;
508 if (index
< r
->items
.size
- 1)
510 /* shift the ordered history part by one */
511 memmove(&r
->items
.data
[index
],
512 &r
->items
.data
[index
+ 1],
513 (r
->items
.size
- index
- 1) * sizeof(*r
->items
.data
));
520 randomizer_RemoveOne(struct randomizer
*r
, const vlc_playlist_item_t
*item
)
522 ssize_t index
= randomizer_IndexOf(r
, item
);
523 assert(index
>= 0); /* item must exist */
524 randomizer_RemoveAt(r
, index
);
528 randomizer_Remove(struct randomizer
*r
, vlc_playlist_item_t
*const items
[],
531 for (size_t i
= 0; i
< count
; ++i
)
532 randomizer_RemoveOne(r
, items
[i
]);
534 vlc_vector_autoshrink(&r
->items
);
538 randomizer_Clear(struct randomizer
*r
)
540 vlc_vector_clear(&r
->items
);
547 #ifdef TEST_RANDOMIZER
549 /* fake structure to simplify tests */
550 struct vlc_playlist_item
{
555 ArrayInit(vlc_playlist_item_t
*array
[], size_t len
)
557 for (size_t i
= 0; i
< len
; ++i
)
559 array
[i
] = malloc(sizeof(*array
[i
]));
566 ArrayDestroy(vlc_playlist_item_t
*array
[], size_t len
)
568 for (size_t i
= 0; i
< len
; ++i
)
573 test_all_items_selected_exactly_once(void)
575 struct randomizer randomizer
;
576 randomizer_Init(&randomizer
);
579 vlc_playlist_item_t
*items
[SIZE
];
580 ArrayInit(items
, SIZE
);
582 bool ok
= randomizer_Add(&randomizer
, items
, SIZE
);
585 bool selected
[SIZE
] = {0};
586 for (int i
= 0; i
< SIZE
; ++i
)
588 assert(randomizer_HasNext(&randomizer
));
589 vlc_playlist_item_t
*item
= randomizer_Next(&randomizer
);
591 assert(!selected
[item
->index
]); /* never selected twice */
592 selected
[item
->index
] = true;
595 assert(!randomizer_HasNext(&randomizer
)); /* no more items */
597 for (int i
= 0; i
< SIZE
; ++i
)
598 assert(selected
[i
]); /* all selected */
600 ArrayDestroy(items
, SIZE
);
601 randomizer_Destroy(&randomizer
);
606 test_all_items_selected_exactly_once_per_cycle(void)
608 struct randomizer randomizer
;
609 randomizer_Init(&randomizer
);
610 randomizer_SetLoop(&randomizer
, true);
613 vlc_playlist_item_t
*items
[SIZE
];
614 ArrayInit(items
, SIZE
);
616 bool ok
= randomizer_Add(&randomizer
, items
, SIZE
);
619 for (int cycle
= 0; cycle
< 4; ++cycle
)
621 bool selected
[SIZE
] = {0};
622 for (int i
= 0; i
< SIZE
; ++i
)
624 assert(randomizer_HasNext(&randomizer
));
625 vlc_playlist_item_t
*item
= randomizer_Next(&randomizer
);
627 assert(!selected
[item
->index
]); /* never selected twice */
628 selected
[item
->index
] = true;
631 assert(randomizer_HasNext(&randomizer
)); /* still has items in loop */
633 for (int i
= 0; i
< SIZE
; ++i
)
634 assert(selected
[i
]); /* all selected */
637 ArrayDestroy(items
, SIZE
);
638 randomizer_Destroy(&randomizer
);
643 test_all_items_selected_exactly_once_with_additions(void)
645 struct randomizer randomizer
;
646 randomizer_Init(&randomizer
);
649 vlc_playlist_item_t
*items
[SIZE
];
650 ArrayInit(items
, SIZE
);
652 bool ok
= randomizer_Add(&randomizer
, items
, 75);
655 bool selected
[SIZE
] = {0};
656 for (int i
= 0; i
< 50; ++i
)
658 assert(randomizer_HasNext(&randomizer
));
659 vlc_playlist_item_t
*item
= randomizer_Next(&randomizer
);
661 assert(!selected
[item
->index
]); /* never selected twice */
662 selected
[item
->index
] = true;
665 ok
= randomizer_Add(&randomizer
, &items
[75], 25);
667 for (int i
= 50; i
< SIZE
; ++i
)
669 assert(randomizer_HasNext(&randomizer
));
670 vlc_playlist_item_t
*item
= randomizer_Next(&randomizer
);
672 assert(!selected
[item
->index
]); /* never selected twice */
673 selected
[item
->index
] = true;
676 assert(!randomizer_HasNext(&randomizer
)); /* no more items */
678 for (int i
= 0; i
< SIZE
; ++i
)
679 assert(selected
[i
]); /* all selected */
681 ArrayDestroy(items
, SIZE
);
682 randomizer_Destroy(&randomizer
);
687 test_all_items_selected_exactly_once_with_removals(void)
689 struct randomizer randomizer
;
690 randomizer_Init(&randomizer
);
693 vlc_playlist_item_t
*items
[SIZE
];
694 ArrayInit(items
, SIZE
);
696 bool ok
= randomizer_Add(&randomizer
, items
, SIZE
);
699 bool selected
[SIZE
] = {0};
700 for (int i
= 0; i
< 50; ++i
)
702 assert(randomizer_HasNext(&randomizer
));
703 vlc_playlist_item_t
*item
= randomizer_Next(&randomizer
);
705 assert(!selected
[item
->index
]); /* never selected twice */
706 selected
[item
->index
] = true;
709 vlc_playlist_item_t
*to_remove
[20];
710 /* copy 10 items already selected */
711 memcpy(to_remove
, &randomizer
.items
.data
[20], 10 * sizeof(*to_remove
));
712 /* copy 10 items not already selected */
713 memcpy(&to_remove
[10], &randomizer
.items
.data
[70], 10 * sizeof(*to_remove
));
715 randomizer_Remove(&randomizer
, to_remove
, 20);
717 for (int i
= 50; i
< SIZE
- 10; ++i
)
719 assert(randomizer_HasNext(&randomizer
));
720 vlc_playlist_item_t
*item
= randomizer_Next(&randomizer
);
722 assert(!selected
[item
->index
]); /* never selected twice */
723 selected
[item
->index
] = true;
726 assert(!randomizer_HasNext(&randomizer
)); /* no more items */
729 for (int i
= 0; i
< SIZE
; ++i
)
733 assert(count
== SIZE
- 10);
735 ArrayDestroy(items
, SIZE
);
736 randomizer_Destroy(&randomizer
);
741 test_cycle_after_manual_selection(void)
743 struct randomizer randomizer
;
744 randomizer_Init(&randomizer
);
745 randomizer_SetLoop(&randomizer
, true);
748 vlc_playlist_item_t
*items
[SIZE
];
749 ArrayInit(items
, SIZE
);
751 bool ok
= randomizer_Add(&randomizer
, items
, 100);
754 /* force selection of the first item */
755 randomizer_Select(&randomizer
, randomizer
.items
.data
[0]);
757 for (int i
= 0; i
< 2 * SIZE
; ++i
)
759 assert(randomizer_HasNext(&randomizer
));
760 vlc_playlist_item_t
*item
= randomizer_Next(&randomizer
);
764 assert(randomizer_HasNext(&randomizer
)); /* still has items in loop */
766 ArrayDestroy(items
, SIZE
);
767 randomizer_Destroy(&randomizer
);
772 test_cycle_with_additions_and_removals(void)
774 struct randomizer randomizer
;
775 randomizer_Init(&randomizer
);
776 randomizer_SetLoop(&randomizer
, true);
779 vlc_playlist_item_t
*items
[SIZE
];
780 ArrayInit(items
, SIZE
);
782 bool ok
= randomizer_Add(&randomizer
, items
, 80);
785 for (int i
= 0; i
< 30; ++i
)
787 assert(randomizer_HasNext(&randomizer
));
788 vlc_playlist_item_t
*item
= randomizer_Next(&randomizer
);
792 vlc_playlist_item_t
*to_remove
[20];
793 /* copy 10 items already selected */
794 memcpy(to_remove
, &randomizer
.items
.data
[15], 10 * sizeof(*to_remove
));
795 /* copy 10 items not already selected */
796 memcpy(&to_remove
[10], &randomizer
.items
.data
[60], 10 * sizeof(*to_remove
));
798 randomizer_Remove(&randomizer
, to_remove
, 20);
800 /* it remains 40 items in the first cycle (30 already selected, and 10
801 * removed from the 50 remaining) */
802 for (int i
= 0; i
< 40; ++i
)
804 assert(randomizer_HasNext(&randomizer
));
805 vlc_playlist_item_t
*item
= randomizer_Next(&randomizer
);
809 /* the first cycle is complete */
810 assert(randomizer_HasNext(&randomizer
));
811 /* force the determination of the first item of the next cycle */
812 vlc_playlist_item_t
*item
= randomizer_PeekNext(&randomizer
);
815 assert(randomizer
.items
.size
== 60);
816 assert(randomizer
.history
== 1);
818 /* save current history */
819 vlc_playlist_item_t
*history
[59];
820 memcpy(history
, &randomizer
.items
.data
[1], 59 * sizeof(*history
));
822 /* insert 20 new items */
823 ok
= randomizer_Add(&randomizer
, &items
[80], 20);
826 assert(randomizer
.items
.size
== 80);
827 assert(randomizer
.history
== 21);
829 for (int i
= 0; i
< 59; ++i
)
830 assert(history
[i
] == randomizer
.items
.data
[21 + i
]);
832 /* remove 10 items in the history part */
833 memcpy(to_remove
, &randomizer
.items
.data
[30], 10 * sizeof(*to_remove
));
834 randomizer_Remove(&randomizer
, to_remove
, 10);
836 assert(randomizer
.items
.size
== 70);
837 assert(randomizer
.history
== 21);
839 /* the other items in the history must be kept in order */
840 for (int i
= 0; i
< 9; ++i
)
841 assert(history
[i
] == randomizer
.items
.data
[21 + i
]);
842 for (int i
= 0; i
< 40; ++i
)
843 assert(history
[i
+ 19] == randomizer
.items
.data
[30 + i
]);
845 ArrayDestroy(items
, SIZE
);
846 randomizer_Destroy(&randomizer
);
851 test_force_select_new_item(void)
853 struct randomizer randomizer
;
854 randomizer_Init(&randomizer
);
857 vlc_playlist_item_t
*items
[SIZE
];
858 ArrayInit(items
, SIZE
);
860 bool ok
= randomizer_Add(&randomizer
, items
, SIZE
);
863 bool selected
[SIZE
] = {0};
864 for (int i
= 0; i
< SIZE
; ++i
)
866 vlc_playlist_item_t
*item
;
869 assert(randomizer_HasNext(&randomizer
));
870 item
= randomizer_Next(&randomizer
);
874 /* force the selection of a new item not already selected */
875 item
= randomizer
.items
.data
[62];
876 randomizer_Select(&randomizer
, item
);
877 /* the item should now be the last selected one */
878 assert(randomizer
.items
.data
[randomizer
.next
- 1] == item
);
881 assert(!selected
[item
->index
]); /* never selected twice */
882 selected
[item
->index
] = true;
885 assert(!randomizer_HasNext(&randomizer
)); /* no more items */
887 for (int i
= 0; i
< SIZE
; ++i
)
888 assert(selected
[i
]); /* all selected */
890 ArrayDestroy(items
, SIZE
);
891 randomizer_Destroy(&randomizer
);
895 test_force_select_item_already_selected(void)
897 struct randomizer randomizer
;
898 randomizer_Init(&randomizer
);
901 vlc_playlist_item_t
*items
[SIZE
];
902 ArrayInit(items
, SIZE
);
904 bool ok
= randomizer_Add(&randomizer
, items
, SIZE
);
907 bool selected
[SIZE
] = {0};
908 /* we need an additional loop cycle, since we select the same item twice */
909 for (int i
= 0; i
< SIZE
+ 1; ++i
)
911 vlc_playlist_item_t
*item
;
914 assert(randomizer_HasNext(&randomizer
));
915 item
= randomizer_Next(&randomizer
);
919 /* force the selection of an item already selected */
920 item
= randomizer
.items
.data
[42];
921 randomizer_Select(&randomizer
, item
);
922 /* the item should now be the last selected one */
923 assert(randomizer
.items
.data
[randomizer
.next
- 1] == item
);
926 /* never selected twice, except for item 50 */
927 assert((i
!= 50) ^ selected
[item
->index
]);
928 selected
[item
->index
] = true;
931 assert(!randomizer_HasNext(&randomizer
)); /* no more items */
933 for (int i
= 0; i
< SIZE
; ++i
)
934 assert(selected
[i
]); /* all selected */
936 ArrayDestroy(items
, SIZE
);
937 randomizer_Destroy(&randomizer
);
944 struct randomizer randomizer
;
945 randomizer_Init(&randomizer
);
948 vlc_playlist_item_t
*items
[SIZE
];
949 ArrayInit(items
, SIZE
);
951 bool ok
= randomizer_Add(&randomizer
, items
, SIZE
);
954 assert(!randomizer_HasPrev(&randomizer
));
956 vlc_playlist_item_t
*actual
[SIZE
];
957 for (int i
= 0; i
< SIZE
; ++i
)
959 assert(randomizer_HasNext(&randomizer
));
960 actual
[i
] = randomizer_Next(&randomizer
);
964 assert(!randomizer_HasNext(&randomizer
));
966 for (int i
= SIZE
- 2; i
>= 0; --i
)
968 assert(randomizer_HasPrev(&randomizer
));
969 vlc_playlist_item_t
*item
= randomizer_Prev(&randomizer
);
970 assert(item
== actual
[i
]);
973 assert(!randomizer_HasPrev(&randomizer
));
975 for (int i
= 1; i
< SIZE
; ++i
)
977 assert(randomizer_HasNext(&randomizer
));
978 vlc_playlist_item_t
*item
= randomizer_Next(&randomizer
);
979 assert(item
== actual
[i
]);
982 ArrayDestroy(items
, SIZE
);
983 randomizer_Destroy(&randomizer
);
988 test_prev_with_select(void)
990 struct randomizer randomizer
;
991 randomizer_Init(&randomizer
);
994 vlc_playlist_item_t
*items
[SIZE
];
995 ArrayInit(items
, SIZE
);
997 bool ok
= randomizer_Add(&randomizer
, items
, SIZE
);
1000 assert(!randomizer_HasPrev(&randomizer
));
1002 vlc_playlist_item_t
*actual
[SIZE
];
1003 for (int i
= 0; i
< 5; ++i
)
1005 assert(randomizer_HasNext(&randomizer
));
1006 actual
[i
] = randomizer_Next(&randomizer
);
1010 randomizer_Select(&randomizer
, actual
[2]);
1012 vlc_playlist_item_t
*item
;
1014 assert(randomizer_HasPrev(&randomizer
));
1015 item
= randomizer_Prev(&randomizer
);
1016 assert(item
== actual
[4]);
1018 assert(randomizer_HasPrev(&randomizer
));
1019 item
= randomizer_Prev(&randomizer
);
1020 assert(item
== actual
[3]);
1022 assert(randomizer_HasPrev(&randomizer
));
1023 item
= randomizer_Prev(&randomizer
);
1024 assert(item
== actual
[1]);
1026 assert(randomizer_HasPrev(&randomizer
));
1027 item
= randomizer_Prev(&randomizer
);
1028 assert(item
== actual
[0]);
1030 assert(!randomizer_HasPrev(&randomizer
));
1032 ArrayDestroy(items
, SIZE
);
1033 randomizer_Destroy(&randomizer
);
1038 test_prev_across_reshuffle_loops(void)
1040 struct randomizer randomizer
;
1041 randomizer_Init(&randomizer
);
1044 vlc_playlist_item_t
*items
[SIZE
];
1045 ArrayInit(items
, SIZE
);
1047 bool ok
= randomizer_Add(&randomizer
, items
, SIZE
);
1050 assert(!randomizer_HasPrev(&randomizer
));
1052 vlc_playlist_item_t
*actual
[SIZE
];
1053 for (int i
= 0; i
< SIZE
; ++i
)
1055 assert(randomizer_HasNext(&randomizer
));
1056 actual
[i
] = randomizer_Next(&randomizer
);
1060 assert(!randomizer_HasNext(&randomizer
));
1061 randomizer_SetLoop(&randomizer
, true);
1062 assert(randomizer_HasNext(&randomizer
));
1064 vlc_playlist_item_t
*actualnew
[4];
1065 /* determine the 4 first items */
1066 for (int i
= 0; i
< 4; ++i
)
1068 assert(randomizer_HasNext(&randomizer
));
1069 actualnew
[i
] = randomizer_Next(&randomizer
);
1070 assert(actualnew
[i
]);
1073 /* go back to the first */
1074 for (int i
= 2; i
>= 0; --i
)
1076 assert(randomizer_HasPrev(&randomizer
));
1077 actualnew
[i
] = randomizer_Prev(&randomizer
);
1078 assert(actualnew
[i
]);
1081 assert(actualnew
[0] == randomizer
.items
.data
[0]);
1083 /* from now, any "prev" goes back to the history */
1085 int index_in_actual
= 9;
1086 for (int i
= 0; i
< 6; ++i
)
1088 assert(randomizer_HasPrev(&randomizer
));
1089 vlc_playlist_item_t
*item
= randomizer_Prev(&randomizer
);
1092 for (j
= 3; j
>= 0; --j
)
1093 if (item
== actualnew
[j
])
1095 bool in_actualnew
= j
!= 0;
1098 /* the item has been selected for the new order, it is not in the
1099 * history anymore */
1102 /* the remaining previous items are retrieved in reverse order in
1104 assert(item
== actual
[index_in_actual
]);
1107 /* no more history: 4 in the current shuffle, 6 in the history */
1108 assert(!randomizer_HasPrev(&randomizer
));
1110 ArrayDestroy(items
, SIZE
);
1111 randomizer_Destroy(&randomizer
);
1115 /* when loop is enabled, we must take care that the last items of the
1116 * previous order are not the same as the first items of the new order */
1118 test_loop_respect_not_same_before(void)
1120 struct randomizer randomizer
;
1121 randomizer_Init(&randomizer
);
1122 randomizer_SetLoop(&randomizer
, true);
1124 #define SIZE (NOT_SAME_BEFORE + 2)
1125 vlc_playlist_item_t
*items
[SIZE
];
1126 ArrayInit(items
, SIZE
);
1128 bool ok
= randomizer_Add(&randomizer
, items
, SIZE
);
1131 vlc_playlist_item_t
*actual
[SIZE
];
1132 for (int i
= 0; i
< SIZE
; ++i
)
1134 assert(randomizer_HasNext(&randomizer
));
1135 actual
[i
] = randomizer_Next(&randomizer
);
1138 for (int cycle
= 0; cycle
< 20; cycle
++)
1140 /* check that the first items are not the same as the last ones of the
1142 for (int i
= 0; i
< NOT_SAME_BEFORE
; ++i
)
1144 assert(randomizer_HasNext(&randomizer
));
1145 actual
[i
] = randomizer_Next(&randomizer
);
1146 for (int j
= (i
+ SIZE
- NOT_SAME_BEFORE
) % SIZE
;
1150 assert(actual
[i
] != actual
[j
]);
1153 for (int i
= NOT_SAME_BEFORE
; i
< SIZE
; ++i
)
1155 assert(randomizer_HasNext(&randomizer
));
1156 actual
[i
] = randomizer_Next(&randomizer
);
1160 ArrayDestroy(items
, SIZE
);
1161 randomizer_Destroy(&randomizer
);
1165 /* if there are less items than NOT_SAME_BEFORE, obviously we can't avoid
1166 * repeating last items in the new order, but it must still work */
1168 test_loop_respect_not_same_before_impossible(void)
1170 struct randomizer randomizer
;
1171 randomizer_Init(&randomizer
);
1172 randomizer_SetLoop(&randomizer
, true);
1174 #define SIZE NOT_SAME_BEFORE
1175 vlc_playlist_item_t
*items
[SIZE
];
1176 ArrayInit(items
, SIZE
);
1178 bool ok
= randomizer_Add(&randomizer
, items
, SIZE
);
1181 for (int i
= 0; i
< 10 * SIZE
; ++i
)
1183 assert(randomizer_HasNext(&randomizer
));
1184 vlc_playlist_item_t
*item
= randomizer_Next(&randomizer
);
1188 ArrayDestroy(items
, SIZE
);
1189 randomizer_Destroy(&randomizer
);
1194 test_has_prev_next_empty(void)
1196 struct randomizer randomizer
;
1197 randomizer_Init(&randomizer
);
1199 assert(!randomizer_HasPrev(&randomizer
));
1200 assert(!randomizer_HasNext(&randomizer
));
1202 randomizer_SetLoop(&randomizer
, true);
1204 assert(!randomizer_HasPrev(&randomizer
));
1206 /* there are always next items in loop mode */
1207 assert(randomizer_HasNext(&randomizer
));
1209 randomizer_Destroy(&randomizer
);
1214 test_all_items_selected_exactly_once();
1215 test_all_items_selected_exactly_once_per_cycle();
1216 test_all_items_selected_exactly_once_with_additions();
1217 test_all_items_selected_exactly_once_with_removals();
1218 test_cycle_after_manual_selection();
1219 test_cycle_with_additions_and_removals();
1220 test_force_select_new_item();
1221 test_force_select_item_already_selected();
1223 test_prev_with_select();
1224 test_prev_across_reshuffle_loops();
1225 test_loop_respect_not_same_before();
1226 test_loop_respect_not_same_before_impossible();
1227 test_has_prev_next_empty();