src/playlist/randomizer.c

   1 /*****************************************************************************
   2  * randomizer.c
   3  *****************************************************************************
   4  * Copyright (C) 2018 VLC authors and VideoLAN
   5  *
   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.
  10  *
  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.
  15  *
  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  *****************************************************************************/
  20
  21 #ifdef HAVE_CONFIG_H
  22 # include "config.h"
  23 #endif
  24
  25 #ifdef TEST_RANDOMIZER
  26 # undef NDEBUG
  27 #endif
  28
  29 #include <assert.h>
  30
  31 #include <vlc_common.h>
  32 #include <vlc_rand.h>
  33 #include "randomizer.h"
  34
  35 /**
  36  * \addtogroup playlist_randomizer Playlist randomizer helper
  37  * \ingroup playlist
  38  *
  39  * Playlist helper to manage random playback.
  40  *
  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
  45  *    apply
  46  *  - the user can request to select a specific item (typically by
  47  *    double-clicking on an item in the playlist)
  48  *
  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)
  57  *
  58  * To achieve these goals, a "randomizer" stores a single vector containing all
  59  * the items of the playlist, along with 3 indexes.
  60  *
  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
  64  *    whole array;
  65  *  - if loop is enabled, the history of the last cycle can be kept in place.
  66  *
  67  * 'head' indicates the end of the items already determinated for the current
  68  * cycle (if loop is disabled, there is only one cycle).
  69  * (0 <= head <= size)
  70  *
  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).
  78  *
  79  * 'history' is only used in loop mode, and references the first item of the
  80  * ordered history from the last cycle.
  81  *
  82  * 0              next  head          history       size
  83  * |---------------|-----|.............|-------------|
  84  *  <------------------->               <----------->
  85  *   determinated range                 history range
  86  *
  87  * Here is a sample scenario to understand how it works.
  88  *
  89  * The playlist initially adds 5 items (A, B, C, D and E).
  90  *
  91  *                                          history
  92  *                 next                     |
  93  *                 head                     |
  94  *                 |                        |
  95  *                 A    B    C    D    E
  96  *
  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()
  99  * returns D.
 100  *
 101  *                                          history
 102  *                      next                |
 103  *                      head                |
 104  *                      |                   |
 105  *                 D    B    C    A    E
 106  *               <--->
 107  *            determinated range
 108  *
 109  * The playlist calls _Next() one more time. The randomizer selects one item
 110  * outside the determinated range (say, E). _Next() returns E.
 111  *
 112  *                                          history
 113  *                           next           |
 114  *                           head           |
 115  *                           |              |
 116  *                 D    E    C    A    B
 117  *               <-------->
 118  *            determinated range
 119  *
 120  * The playlist calls _Next() one more time. The randomizer selects C (already
 121  * in place). _Next() returns C.
 122  *
 123  *                                          history
 124  *                                next      |
 125  *                                head      |
 126  *                                |         |
 127  *                 D    E    C    A    B
 128  *               <------------->
 129  *             determinated range
 130  *
 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.
 133  *
 134  *                                          history
 135  *                           next           |
 136  *                           |    head      |
 137  *                           |    |         |
 138  *                 D    E    C    A    B
 139  *               <------------->
 140  *             determinated range
 141  *
 142  * The playlist calls _Next(), which returns C, as expected.
 143  *
 144  *                                          history
 145  *                                next      |
 146  *                                head      |
 147  *                                |         |
 148  *                 D    E    C    A    B
 149  *               <------------->
 150  *             determinated range
 151  *
 152  * The playlist calls _Next(), the randomizer selects B, and returns it.
 153  *
 154  *                                          history
 155  *                                     next |
 156  *                                     head |
 157  *                                     |    |
 158  *                 D    E    C    B    A
 159  *               <------------------>
 160  *                determinated range
 161  *
 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
 164  * the vector size).
 165  *
 166  *                                          history
 167  *                                          next
 168  *                                          head
 169  *                                          |
 170  *                 D    E    C    B    A
 171  *               <----------------------->
 172  *                  determinated range
 173  *
 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.
 177  *
 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.
 180  *
 181  *                  history
 182  *                  next
 183  *                  head
 184  *                  |
 185  *                  D    E    C    B    A
 186  *               <------------------------>
 187  *                     history range
 188  *
 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.
 194  *
 195  *                      history
 196  *                 next |
 197  *                 |    head
 198  *                 |    |
 199  *                 C    D    E    B    A
 200  *               <---><------------------>
 201  *       determinated     history range
 202  *              range
 203  *
 204  * Finally, it will actually select and return the first item (C).
 205  *
 206  *                      history
 207  *                      next
 208  *                      head
 209  *                      |
 210  *                 C    D    E    B    A
 211  *               <---><------------------>
 212  *       determinated     history range
 213  *              range
 214  *
 215  * Then, the user adds an item to the playlist (F). This item is added in front
 216  * of history.
 217  *
 218  *                           history
 219  *                      next |
 220  *                      head |
 221  *                      |    |
 222  *                 C    F    D    E    B    A
 223  *               <--->     <------------------>
 224  *       determinated          history range
 225  *              range
 226  *
 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.
 231  *
 232  *                                history
 233  *                           next |
 234  *                           head |
 235  *                           |    |
 236  *                 C    E    F    D    B    A
 237  *               <-------->     <-------------->
 238  *              determinated     history range
 239  *                 range
 240  *
 241  * The playlist then calls _Prev() 3 times, that yield C, then A, then B.
 242  * 'next' is decremented (modulo size) on each call.
 243  *
 244  *                                history
 245  *                                |    next
 246  *                           head |    |
 247  *                           |    |    |
 248  *                 C    E    F    D    B    A
 249  *               <-------->     <-------------->
 250  *              determinated     history range
 251  *                 range
 252  */
 253
 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
 258
 259 void
 260 randomizer_Init(struct randomizer *r)
 261 {
 262     vlc_vector_init(&r->items);
 263
 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));
 267
 268     r->loop = false;
 269     r->head = 0;
 270     r->next = 0;
 271     r->history = 0;
 272 }
 273
 274 void
 275 randomizer_Destroy(struct randomizer *r)
 276 {
 277     vlc_vector_destroy(&r->items);
 278 }
 279
 280 void
 281 randomizer_SetLoop(struct randomizer *r, bool loop)
 282 {
 283     r->loop = loop;
 284 }
 285
 286 static inline ssize_t
 287 randomizer_IndexOf(struct randomizer *r, const vlc_playlist_item_t *item)
 288 {
 289     ssize_t index;
 290     vlc_vector_index_of(&r->items, item, &index);
 291     return index;
 292 }
 293
 294 bool
 295 randomizer_Count(struct randomizer *r)
 296 {
 297     return r->items.size;
 298 }
 299
 300 void
 301 randomizer_Reshuffle(struct randomizer *r)
 302 {
 303     /* yeah, it's that simple */
 304     r->head = 0;
 305     r->next = 0;
 306     r->history = r->items.size;
 307 }
 308
 309 static inline void
 310 swap_items(struct randomizer *r, int i, int j)
 311 {
 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;
 315 }
 316
 317 static inline void
 318 randomizer_DetermineOne_(struct randomizer *r, size_t avoid_last_n)
 319 {
 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);
 325
 326     if (r->head == r->history)
 327         r->history++;
 328     r->head++;
 329 }
 330
 331 static inline void
 332 randomizer_DetermineOne(struct randomizer *r)
 333 {
 334     randomizer_DetermineOne_(r, 0);
 335 }
 336
 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. */
 340 static void
 341 randomizer_AutoReshuffle(struct randomizer *r)
 342 {
 343     assert(r->items.size > 0);
 344     r->head = 0;
 345     r->next = 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;
 351     while (avoid_last_n)
 352         randomizer_DetermineOne_(r, avoid_last_n--);
 353 }
 354
 355 bool
 356 randomizer_HasPrev(struct randomizer *r)
 357 {
 358     if (!r->loop)
 359         /* a previous exists if the current is > 0, i.e. next > 1 */
 360         return r->next > 1;
 361
 362     if (!r->items.size)
 363         /* avoid modulo 0 */
 364         return false;
 365
 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;
 369 }
 370
 371 bool
 372 randomizer_HasNext(struct randomizer *r)
 373 {
 374     return r->loop || r->next < r->items.size;
 375 }
 376
 377 vlc_playlist_item_t *
 378 randomizer_PeekPrev(struct randomizer *r)
 379 {
 380     assert(randomizer_HasPrev(r));
 381     size_t index = (r->next + r->items.size - 2) % r->items.size;
 382     return r->items.data[index];
 383 }
 384
 385 vlc_playlist_item_t *
 386 randomizer_PeekNext(struct randomizer *r)
 387 {
 388     assert(randomizer_HasNext(r));
 389
 390     if (r->next == r->items.size && r->next == r->history)
 391     {
 392         assert(r->loop);
 393         randomizer_AutoReshuffle(r);
 394     }
 395
 396     if (r->next == r->head)
 397         /* execute 1 step of the Fisher-Yates shuffle */
 398         randomizer_DetermineOne(r);
 399
 400     return r->items.data[r->next];
 401 }
 402
 403 vlc_playlist_item_t *
 404 randomizer_Prev(struct randomizer *r)
 405 {
 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;
 409     return item;
 410 }
 411
 412 vlc_playlist_item_t *
 413 randomizer_Next(struct randomizer *r)
 414 {
 415     assert(randomizer_HasNext(r));
 416     vlc_playlist_item_t *item = randomizer_PeekNext(r);
 417     r->next++;
 418     if (r->next == r->items.size && r->next != r->head)
 419         r->next = 0;
 420     return item;
 421 }
 422
 423 bool
 424 randomizer_Add(struct randomizer *r, vlc_playlist_item_t *items[], size_t count)
 425 {
 426     if (!vlc_vector_insert_all(&r->items, r->history, items, count))
 427         return false;
 428     /* the insertion shifted history (and possibly next) */
 429     if (r->next > r->history)
 430         r->next += count;
 431     r->history += count;
 432     return true;
 433 }
 434
 435 static void
 436 randomizer_SelectIndex(struct randomizer *r, size_t index)
 437 {
 438     vlc_playlist_item_t *selected = r->items.data[index];
 439     if (r->history && index >= r->history)
 440     {
 441         if (index > r->history)
 442         {
 443             memmove(&r->items.data[r->history + 1],
 444                     &r->items.data[r->history],
 445                     (index - r->history) * sizeof(selected));
 446             index = r->history;
 447         }
 448         r->history = (r->history + 1) % r->items.size;
 449     }
 450
 451     if (index >= r->head)
 452     {
 453         r->items.data[index] = r->items.data[r->head];
 454         r->items.data[r->head] = selected;
 455         r->head++;
 456     }
 457     else if (index < r->items.size - 1)
 458     {
 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;
 463     }
 464
 465     r->next = r->head;
 466 }
 467
 468 void
 469 randomizer_Select(struct randomizer *r, const vlc_playlist_item_t *item)
 470 {
 471     ssize_t index = randomizer_IndexOf(r, item);
 472     assert(index != -1); /* item must exist */
 473     randomizer_SelectIndex(r, (size_t) index);
 474 }
 475
 476 static void
 477 randomizer_RemoveAt(struct randomizer *r, size_t index)
 478 {
 479     /*
 480      * 0          head                                history   next  size
 481      * |-----------|...................................|---------|-----|
 482      * |<--------->|                                   |<------------->|
 483      *    ordered            order irrelevant               ordered
 484      */
 485
 486     /* update next before index may be updated */
 487     if (index < r->next)
 488         r->next--;
 489
 490     if (index < r->head)
 491     {
 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));
 496         r->head--;
 497         index = r->head; /* the new index to remove */
 498     }
 499
 500     if (index < r->history)
 501     {
 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;
 505         r->history--;
 506     }
 507
 508     if (index < r->items.size - 1)
 509     {
 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));
 514     }
 515
 516     r->items.size--;
 517 }
 518
 519 static void
 520 randomizer_RemoveOne(struct randomizer *r, const vlc_playlist_item_t *item)
 521 {
 522     ssize_t index = randomizer_IndexOf(r, item);
 523     assert(index >= 0); /* item must exist */
 524     randomizer_RemoveAt(r, index);
 525 }
 526
 527 void
 528 randomizer_Remove(struct randomizer *r, vlc_playlist_item_t *const items[],
 529                   size_t count)
 530 {
 531     for (size_t i = 0; i < count; ++i)
 532         randomizer_RemoveOne(r, items[i]);
 533
 534     vlc_vector_autoshrink(&r->items);
 535 }
 536
 537 void
 538 randomizer_Clear(struct randomizer *r)
 539 {
 540     vlc_vector_clear(&r->items);
 541     r->head = 0;
 542     r->next = 0;
 543     r->history = 0;
 544 }
 545
 546 #ifndef DOC
 547 #ifdef TEST_RANDOMIZER
 548
 549 /* fake structure to simplify tests */
 550 struct vlc_playlist_item {
 551     size_t index;
 552 };
 553
 554 static void
 555 ArrayInit(vlc_playlist_item_t *array[], size_t len)
 556 {
 557     for (size_t i = 0; i < len; ++i)
 558     {
 559         array[i] = malloc(sizeof(*array[i]));
 560         assert(array[i]);
 561         array[i]->index = i;
 562     }
 563 }
 564
 565 static void
 566 ArrayDestroy(vlc_playlist_item_t *array[], size_t len)
 567 {
 568     for (size_t i = 0; i < len; ++i)
 569         free(array[i]);
 570 }
 571
 572 static void
 573 test_all_items_selected_exactly_once(void)
 574 {
 575     struct randomizer randomizer;
 576     randomizer_Init(&randomizer);
 577
 578     #define SIZE 100
 579     vlc_playlist_item_t *items[SIZE];
 580     ArrayInit(items, SIZE);
 581
 582     bool ok = randomizer_Add(&randomizer, items, SIZE);
 583     assert(ok);
 584
 585     bool selected[SIZE] = {0};
 586     for (int i = 0; i < SIZE; ++i)
 587     {
 588         assert(randomizer_HasNext(&randomizer));
 589         vlc_playlist_item_t *item = randomizer_Next(&randomizer);
 590         assert(item);
 591         assert(!selected[item->index]); /* never selected twice */
 592         selected[item->index] = true;
 593     }
 594
 595     assert(!randomizer_HasNext(&randomizer)); /* no more items */
 596
 597     for (int i = 0; i < SIZE; ++i)
 598         assert(selected[i]); /* all selected */
 599
 600     ArrayDestroy(items, SIZE);
 601     randomizer_Destroy(&randomizer);
 602     #undef SIZE
 603 }
 604
 605 static void
 606 test_all_items_selected_exactly_once_per_cycle(void)
 607 {
 608     struct randomizer randomizer;
 609     randomizer_Init(&randomizer);
 610     randomizer_SetLoop(&randomizer, true);
 611
 612     #define SIZE 100
 613     vlc_playlist_item_t *items[SIZE];
 614     ArrayInit(items, SIZE);
 615
 616     bool ok = randomizer_Add(&randomizer, items, SIZE);
 617     assert(ok);
 618
 619     for (int cycle = 0; cycle < 4; ++cycle)
 620     {
 621         bool selected[SIZE] = {0};
 622         for (int i = 0; i < SIZE; ++i)
 623         {
 624             assert(randomizer_HasNext(&randomizer));
 625             vlc_playlist_item_t *item = randomizer_Next(&randomizer);
 626             assert(item);
 627             assert(!selected[item->index]); /* never selected twice */
 628             selected[item->index] = true;
 629         }
 630
 631         assert(randomizer_HasNext(&randomizer)); /* still has items in loop */
 632
 633         for (int i = 0; i < SIZE; ++i)
 634             assert(selected[i]); /* all selected */
 635     }
 636
 637     ArrayDestroy(items, SIZE);
 638     randomizer_Destroy(&randomizer);
 639     #undef SIZE
 640 }
 641
 642 static void
 643 test_all_items_selected_exactly_once_with_additions(void)
 644 {
 645     struct randomizer randomizer;
 646     randomizer_Init(&randomizer);
 647
 648     #define SIZE 100
 649     vlc_playlist_item_t *items[SIZE];
 650     ArrayInit(items, SIZE);
 651
 652     bool ok = randomizer_Add(&randomizer, items, 75);
 653     assert(ok);
 654
 655     bool selected[SIZE] = {0};
 656     for (int i = 0; i < 50; ++i)
 657     {
 658         assert(randomizer_HasNext(&randomizer));
 659         vlc_playlist_item_t *item = randomizer_Next(&randomizer);
 660         assert(item);
 661         assert(!selected[item->index]); /* never selected twice */
 662         selected[item->index] = true;
 663     }
 664
 665     ok = randomizer_Add(&randomizer, &items[75], 25);
 666     assert(ok);
 667     for (int i = 50; i < SIZE; ++i)
 668     {
 669         assert(randomizer_HasNext(&randomizer));
 670         vlc_playlist_item_t *item = randomizer_Next(&randomizer);
 671         assert(item);
 672         assert(!selected[item->index]); /* never selected twice */
 673         selected[item->index] = true;
 674     }
 675
 676     assert(!randomizer_HasNext(&randomizer)); /* no more items */
 677
 678     for (int i = 0; i < SIZE; ++i)
 679         assert(selected[i]); /* all selected */
 680
 681     ArrayDestroy(items, SIZE);
 682     randomizer_Destroy(&randomizer);
 683     #undef SIZE
 684 }
 685
 686 static void
 687 test_all_items_selected_exactly_once_with_removals(void)
 688 {
 689     struct randomizer randomizer;
 690     randomizer_Init(&randomizer);
 691
 692     #define SIZE 100
 693     vlc_playlist_item_t *items[SIZE];
 694     ArrayInit(items, SIZE);
 695
 696     bool ok = randomizer_Add(&randomizer, items, SIZE);
 697     assert(ok);
 698
 699     bool selected[SIZE] = {0};
 700     for (int i = 0; i < 50; ++i)
 701     {
 702         assert(randomizer_HasNext(&randomizer));
 703         vlc_playlist_item_t *item = randomizer_Next(&randomizer);
 704         assert(item);
 705         assert(!selected[item->index]); /* never selected twice */
 706         selected[item->index] = true;
 707     }
 708
 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));
 714
 715     randomizer_Remove(&randomizer, to_remove, 20);
 716
 717     for (int i = 50; i < SIZE - 10; ++i)
 718     {
 719         assert(randomizer_HasNext(&randomizer));
 720         vlc_playlist_item_t *item = randomizer_Next(&randomizer);
 721         assert(item);
 722         assert(!selected[item->index]); /* never selected twice */
 723         selected[item->index] = true;
 724     }
 725
 726     assert(!randomizer_HasNext(&randomizer)); /* no more items */
 727
 728     int count = 0;
 729     for (int i = 0; i < SIZE; ++i)
 730         if (selected[i])
 731             count++;
 732
 733     assert(count == SIZE - 10);
 734
 735     ArrayDestroy(items, SIZE);
 736     randomizer_Destroy(&randomizer);
 737     #undef SIZE
 738 }
 739
 740 static void
 741 test_cycle_after_manual_selection(void)
 742 {
 743     struct randomizer randomizer;
 744     randomizer_Init(&randomizer);
 745     randomizer_SetLoop(&randomizer, true);
 746
 747     #define SIZE 100
 748     vlc_playlist_item_t *items[SIZE];
 749     ArrayInit(items, SIZE);
 750
 751     bool ok = randomizer_Add(&randomizer, items, 100);
 752     assert(ok);
 753
 754     /* force selection of the first item */
 755     randomizer_Select(&randomizer, randomizer.items.data[0]);
 756
 757     for (int i = 0; i < 2 * SIZE; ++i)
 758     {
 759         assert(randomizer_HasNext(&randomizer));
 760         vlc_playlist_item_t *item = randomizer_Next(&randomizer);
 761         assert(item);
 762     }
 763
 764     assert(randomizer_HasNext(&randomizer)); /* still has items in loop */
 765
 766     ArrayDestroy(items, SIZE);
 767     randomizer_Destroy(&randomizer);
 768     #undef SIZE
 769 }
 770
 771 static void
 772 test_cycle_with_additions_and_removals(void)
 773 {
 774     struct randomizer randomizer;
 775     randomizer_Init(&randomizer);
 776     randomizer_SetLoop(&randomizer, true);
 777
 778     #define SIZE 100
 779     vlc_playlist_item_t *items[SIZE];
 780     ArrayInit(items, SIZE);
 781
 782     bool ok = randomizer_Add(&randomizer, items, 80);
 783     assert(ok);
 784
 785     for (int i = 0; i < 30; ++i)
 786     {
 787         assert(randomizer_HasNext(&randomizer));
 788         vlc_playlist_item_t *item = randomizer_Next(&randomizer);
 789         assert(item);
 790     }
 791
 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));
 797
 798     randomizer_Remove(&randomizer, to_remove, 20);
 799
 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)
 803     {
 804         assert(randomizer_HasNext(&randomizer));
 805         vlc_playlist_item_t *item = randomizer_Next(&randomizer);
 806         assert(item);
 807     }
 808
 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);
 813     assert(item);
 814
 815     assert(randomizer.items.size == 60);
 816     assert(randomizer.history == 1);
 817
 818     /* save current history */
 819     vlc_playlist_item_t *history[59];
 820     memcpy(history, &randomizer.items.data[1], 59 * sizeof(*history));
 821
 822     /* insert 20 new items */
 823     ok = randomizer_Add(&randomizer, &items[80], 20);
 824     assert(ok);
 825
 826     assert(randomizer.items.size == 80);
 827     assert(randomizer.history == 21);
 828
 829     for (int i = 0; i < 59; ++i)
 830         assert(history[i] == randomizer.items.data[21 + i]);
 831
 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);
 835
 836     assert(randomizer.items.size == 70);
 837     assert(randomizer.history == 21);
 838
 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]);
 844
 845     ArrayDestroy(items, SIZE);
 846     randomizer_Destroy(&randomizer);
 847     #undef SIZE
 848 }
 849
 850 static void
 851 test_force_select_new_item(void)
 852 {
 853     struct randomizer randomizer;
 854     randomizer_Init(&randomizer);
 855
 856     #define SIZE 100
 857     vlc_playlist_item_t *items[SIZE];
 858     ArrayInit(items, SIZE);
 859
 860     bool ok = randomizer_Add(&randomizer, items, SIZE);
 861     assert(ok);
 862
 863     bool selected[SIZE] = {0};
 864     for (int i = 0; i < SIZE; ++i)
 865     {
 866         vlc_playlist_item_t *item;
 867         if (i != 50)
 868         {
 869             assert(randomizer_HasNext(&randomizer));
 870             item = randomizer_Next(&randomizer);
 871         }
 872         else
 873         {
 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);
 879         }
 880         assert(item);
 881         assert(!selected[item->index]); /* never selected twice */
 882         selected[item->index] = true;
 883     }
 884
 885     assert(!randomizer_HasNext(&randomizer)); /* no more items */
 886
 887     for (int i = 0; i < SIZE; ++i)
 888         assert(selected[i]); /* all selected */
 889
 890     ArrayDestroy(items, SIZE);
 891     randomizer_Destroy(&randomizer);
 892 }
 893
 894 static void
 895 test_force_select_item_already_selected(void)
 896 {
 897     struct randomizer randomizer;
 898     randomizer_Init(&randomizer);
 899
 900     #define SIZE 100
 901     vlc_playlist_item_t *items[SIZE];
 902     ArrayInit(items, SIZE);
 903
 904     bool ok = randomizer_Add(&randomizer, items, SIZE);
 905     assert(ok);
 906
 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)
 910     {
 911         vlc_playlist_item_t *item;
 912         if (i != 50)
 913         {
 914             assert(randomizer_HasNext(&randomizer));
 915             item = randomizer_Next(&randomizer);
 916         }
 917         else
 918         {
 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);
 924         }
 925         assert(item);
 926         /* never selected twice, except for item 50 */
 927         assert((i != 50) ^ selected[item->index]);
 928         selected[item->index] = true;
 929     }
 930
 931     assert(!randomizer_HasNext(&randomizer)); /* no more items */
 932
 933     for (int i = 0; i < SIZE; ++i)
 934         assert(selected[i]); /* all selected */
 935
 936     ArrayDestroy(items, SIZE);
 937     randomizer_Destroy(&randomizer);
 938     #undef SIZE
 939 }
 940
 941 static void
 942 test_prev(void)
 943 {
 944     struct randomizer randomizer;
 945     randomizer_Init(&randomizer);
 946
 947     #define SIZE 10
 948     vlc_playlist_item_t *items[SIZE];
 949     ArrayInit(items, SIZE);
 950
 951     bool ok = randomizer_Add(&randomizer, items, SIZE);
 952     assert(ok);
 953
 954     assert(!randomizer_HasPrev(&randomizer));
 955
 956     vlc_playlist_item_t *actual[SIZE];
 957     for (int i = 0; i < SIZE; ++i)
 958     {
 959         assert(randomizer_HasNext(&randomizer));
 960         actual[i] = randomizer_Next(&randomizer);
 961         assert(actual[i]);
 962     }
 963
 964     assert(!randomizer_HasNext(&randomizer));
 965
 966     for (int i = SIZE - 2; i >= 0; --i)
 967     {
 968         assert(randomizer_HasPrev(&randomizer));
 969         vlc_playlist_item_t *item = randomizer_Prev(&randomizer);
 970         assert(item == actual[i]);
 971     }
 972
 973     assert(!randomizer_HasPrev(&randomizer));
 974
 975     for (int i = 1; i < SIZE; ++i)
 976     {
 977         assert(randomizer_HasNext(&randomizer));
 978         vlc_playlist_item_t *item = randomizer_Next(&randomizer);
 979         assert(item == actual[i]);
 980     }
 981
 982     ArrayDestroy(items, SIZE);
 983     randomizer_Destroy(&randomizer);
 984     #undef SIZE
 985 }
 986
 987 static void
 988 test_prev_with_select(void)
 989 {
 990     struct randomizer randomizer;
 991     randomizer_Init(&randomizer);
 992
 993     #define SIZE 10
 994     vlc_playlist_item_t *items[SIZE];
 995     ArrayInit(items, SIZE);
 996
 997     bool ok = randomizer_Add(&randomizer, items, SIZE);
 998     assert(ok);
 999
1000     assert(!randomizer_HasPrev(&randomizer));
1001
1002     vlc_playlist_item_t *actual[SIZE];
1003     for (int i = 0; i < 5; ++i)
1004     {
1005         assert(randomizer_HasNext(&randomizer));
1006         actual[i] = randomizer_Next(&randomizer);
1007         assert(actual[i]);
1008     }
1009
1010     randomizer_Select(&randomizer, actual[2]);
1011
1012     vlc_playlist_item_t *item;
1013
1014     assert(randomizer_HasPrev(&randomizer));
1015     item = randomizer_Prev(&randomizer);
1016     assert(item == actual[4]);
1017
1018     assert(randomizer_HasPrev(&randomizer));
1019     item = randomizer_Prev(&randomizer);
1020     assert(item == actual[3]);
1021
1022     assert(randomizer_HasPrev(&randomizer));
1023     item = randomizer_Prev(&randomizer);
1024     assert(item == actual[1]);
1025
1026     assert(randomizer_HasPrev(&randomizer));
1027     item = randomizer_Prev(&randomizer);
1028     assert(item == actual[0]);
1029
1030     assert(!randomizer_HasPrev(&randomizer));
1031
1032     ArrayDestroy(items, SIZE);
1033     randomizer_Destroy(&randomizer);
1034     #undef SIZE
1035 }
1036
1037 static void
1038 test_prev_across_reshuffle_loops(void)
1039 {
1040     struct randomizer randomizer;
1041     randomizer_Init(&randomizer);
1042
1043     #define SIZE 10
1044     vlc_playlist_item_t *items[SIZE];
1045     ArrayInit(items, SIZE);
1046
1047     bool ok = randomizer_Add(&randomizer, items, SIZE);
1048     assert(ok);
1049
1050     assert(!randomizer_HasPrev(&randomizer));
1051
1052     vlc_playlist_item_t *actual[SIZE];
1053     for (int i = 0; i < SIZE; ++i)
1054     {
1055         assert(randomizer_HasNext(&randomizer));
1056         actual[i] = randomizer_Next(&randomizer);
1057         assert(actual[i]);
1058     }
1059
1060     assert(!randomizer_HasNext(&randomizer));
1061     randomizer_SetLoop(&randomizer, true);
1062     assert(randomizer_HasNext(&randomizer));
1063
1064     vlc_playlist_item_t *actualnew[4];
1065     /* determine the 4 first items */
1066     for (int i = 0; i < 4; ++i)
1067     {
1068         assert(randomizer_HasNext(&randomizer));
1069         actualnew[i] = randomizer_Next(&randomizer);
1070         assert(actualnew[i]);
1071     }
1072
1073     /* go back to the first */
1074     for (int i = 2; i >= 0; --i)
1075     {
1076         assert(randomizer_HasPrev(&randomizer));
1077         actualnew[i] = randomizer_Prev(&randomizer);
1078         assert(actualnew[i]);
1079     }
1080
1081     assert(actualnew[0] == randomizer.items.data[0]);
1082
1083     /* from now, any "prev" goes back to the history */
1084
1085     int index_in_actual = 9;
1086     for (int i = 0; i < 6; ++i)
1087     {
1088         assert(randomizer_HasPrev(&randomizer));
1089         vlc_playlist_item_t *item = randomizer_Prev(&randomizer);
1090
1091         int j;
1092         for (j = 3; j >= 0; --j)
1093             if (item == actualnew[j])
1094                 break;
1095         bool in_actualnew = j != 0;
1096
1097         if (in_actualnew)
1098             /* the item has been selected for the new order, it is not in the
1099              * history anymore */
1100             index_in_actual--;
1101         else
1102             /* the remaining previous items are retrieved in reverse order in
1103              * the history */
1104             assert(item == actual[index_in_actual]);
1105     }
1106
1107     /* no more history: 4 in the current shuffle, 6 in the history */
1108     assert(!randomizer_HasPrev(&randomizer));
1109
1110     ArrayDestroy(items, SIZE);
1111     randomizer_Destroy(&randomizer);
1112     #undef SIZE
1113 }
1114
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 */
1117 static void
1118 test_loop_respect_not_same_before(void)
1119 {
1120     struct randomizer randomizer;
1121     randomizer_Init(&randomizer);
1122     randomizer_SetLoop(&randomizer, true);
1123
1124     #define SIZE (NOT_SAME_BEFORE + 2)
1125     vlc_playlist_item_t *items[SIZE];
1126     ArrayInit(items, SIZE);
1127
1128     bool ok = randomizer_Add(&randomizer, items, SIZE);
1129     assert(ok);
1130
1131     vlc_playlist_item_t *actual[SIZE];
1132     for (int i = 0; i < SIZE; ++i)
1133     {
1134         assert(randomizer_HasNext(&randomizer));
1135         actual[i] = randomizer_Next(&randomizer);
1136     }
1137
1138     for (int cycle = 0; cycle < 20; cycle++)
1139     {
1140         /* check that the first items are not the same as the last ones of the
1141          * previous order */
1142         for (int i = 0; i < NOT_SAME_BEFORE; ++i)
1143         {
1144             assert(randomizer_HasNext(&randomizer));
1145             actual[i] = randomizer_Next(&randomizer);
1146             for (int j = (i + SIZE - NOT_SAME_BEFORE) % SIZE;
1147                  j != i;
1148                  j = (j + 1) % SIZE)
1149             {
1150                 assert(actual[i] != actual[j]);
1151             }
1152         }
1153         for (int i = NOT_SAME_BEFORE; i < SIZE; ++i)
1154         {
1155             assert(randomizer_HasNext(&randomizer));
1156             actual[i] = randomizer_Next(&randomizer);
1157         }
1158     }
1159
1160     ArrayDestroy(items, SIZE);
1161     randomizer_Destroy(&randomizer);
1162     #undef SIZE
1163 }
1164
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 */
1167 static void
1168 test_loop_respect_not_same_before_impossible(void)
1169 {
1170     struct randomizer randomizer;
1171     randomizer_Init(&randomizer);
1172     randomizer_SetLoop(&randomizer, true);
1173
1174     #define SIZE NOT_SAME_BEFORE
1175     vlc_playlist_item_t *items[SIZE];
1176     ArrayInit(items, SIZE);
1177
1178     bool ok = randomizer_Add(&randomizer, items, SIZE);
1179     assert(ok);
1180
1181     for (int i = 0; i < 10 * SIZE; ++i)
1182     {
1183         assert(randomizer_HasNext(&randomizer));
1184         vlc_playlist_item_t *item = randomizer_Next(&randomizer);
1185         assert(item);
1186     }
1187
1188     ArrayDestroy(items, SIZE);
1189     randomizer_Destroy(&randomizer);
1190     #undef SIZE
1191 }
1192
1193 static void
1194 test_has_prev_next_empty(void)
1195 {
1196     struct randomizer randomizer;
1197     randomizer_Init(&randomizer);
1198
1199     assert(!randomizer_HasPrev(&randomizer));
1200     assert(!randomizer_HasNext(&randomizer));
1201
1202     randomizer_SetLoop(&randomizer, true);
1203
1204     assert(!randomizer_HasPrev(&randomizer));
1205
1206     /* there are always next items in loop mode */
1207     assert(randomizer_HasNext(&randomizer));
1208
1209     randomizer_Destroy(&randomizer);
1210 }
1211
1212 int main(void)
1213 {
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();
1222     test_prev();
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();
1228 }
1229
1230 #endif
1231 #endif