Playlist randomizer helper

Playlist helper to manage random playback. More...

Collaboration diagram for Playlist randomizer helper:

Data Structures
struct	randomizer
	Playlist helper to manage random playback. More...

Functions
void	randomizer_Init (struct randomizer *randomizer)
	Initialize an empty randomizer. More...
void	randomizer_Destroy (struct randomizer *randomizer)
	Destroy a randomizer. More...
void	randomizer_SetLoop (struct randomizer *randomizer, bool loop)
	Enable or disable "loop" mode. More...
bool	randomizer_Count (struct randomizer *randomizer)
	Return the number of items in the randomizer. More...
void	randomizer_Reshuffle (struct randomizer *randomizer)
	Start a new random cycle. More...
bool	randomizer_HasPrev (struct randomizer *randomizer)
	Indicate whether there is a previous item. More...
bool	randomizer_HasNext (struct randomizer *randomizer)
	Indicate whether there is a next item. More...
vlc_playlist_item_t *	randomizer_PeekPrev (struct randomizer *randomizer)
	Peek the previous item (without changing the current one). More...
vlc_playlist_item_t *	randomizer_PeekNext (struct randomizer *randomizer)
	Peek the next item (without changing the current one). More...
vlc_playlist_item_t *	randomizer_Prev (struct randomizer *randomizer)
	Go back to the previous item. More...
vlc_playlist_item_t *	randomizer_Next (struct randomizer *randomizer)
	Go back to the next item. More...
void	randomizer_Select (struct randomizer *randomizer, const vlc_playlist_item_t *item)
	Force the selection of a specific item. More...
bool	randomizer_Add (struct randomizer *randomizer, vlc_playlist_item_t *items[], size_t count)
	Add items to the randomizer. More...
void	randomizer_Remove (struct randomizer *randomizer, vlc_playlist_item_t *const items[], size_t count)
	Remove items from the randomizer. More...
void	randomizer_Clear (struct randomizer *randomizer)
	Clear the randomizer. More...

Detailed Description

Playlist helper to manage random playback.

The purpose is to guarantee the following rules:

• an item must never be selected twice
• "prev" navigates back in the history of previously selected items
• insertions and removals can occur at any time; all these rules must still apply
• the user can request to select a specific item (typically by double-clicking on an item in the playlist)

If loop (repeat) is enabled:

• the random order must be "reshuffled" on every cycle
• an item must never be selected twice in each cycle
• the same item must never be selected twice in a row; in particular, it must not be the first item of a new cycle if it was the last item of the previous one (except if the playlist contains only one item)
• crossing a new "cycle" is invisible to the user (e.g. it is still possible to navigate to previous selected items)

To achieve these goals, a "randomizer" stores a single vector containing all the items of the playlist, along with 3 indexes.

The whole vector is not shuffled at once: instead, steps of the Fisher-Yates algorithm are executed one-by-one on demand. This has several advantages:

• on insertions and removals, there is no need to reshuffle or shift the whole array;
• if loop is enabled, the history of the last cycle can be kept in place.

'head' indicates the end of the items already determined for the current cycle (if loop is disabled, there is only one cycle). (0 <= head <= size)

'next' points to the item after the current one (we use 'next' instead of 'current' so that all indexes are unsigned, while 'current' could be -1). The current item is the one returned by the previous call to _Prev() or _Next(). Each call to _Next() makes 'next' (and possibly 'head') move forward, each call to _Prev() makes it move back (modulo size). 'next' is always in the determined range (0 <= next <= head) or in the "history" range (history < next < size).

'history' is only used in loop mode, and references the first item of the ordered history from the last cycle.

0 next head history size |------------—|--—|.............|----------—| <----------------—> <--------—> determinated range history range

Here is a sample scenario to understand how it works.

The playlist initially adds 5 items (A, B, C, D and E).

                                     history
            next                     |
            head                     |
            |                        |
            A    B    C    D    E

The playlist calls _Next() to retrieve the next random item. The randomizer picks one item (say, D), and swaps it with the current head (A). _Next() returns D.

                                     history
                 next                |
                 head                |
                 |                   |
            D    B    C    A    E
          <--->
       determined range

The playlist calls _Next() one more time. The randomizer selects one item outside the determined range (say, E). _Next() returns E.

                                     history
                      next           |
                      head           |
                      |              |
            D    E    C    A    B
          <-------->
       determined range

The playlist calls _Next() one more time. The randomizer selects C (already in place). _Next() returns C.

                                     history
                           next      |
                           head      |
                           |         |
            D    E    C    A    B
          <------------->
        determined range

The playlist then calls _Prev(). Since the "current" item is C, the previous one is E, so _Prev() returns E, and 'next' moves back.

                                     history
                      next           |
                      |    head      |
                      |    |         |
            D    E    C    A    B
          <------------->
        determined range

The playlist calls _Next(), which returns C, as expected.

                                     history
                           next      |
                           head      |
                           |         |
            D    E    C    A    B
          <------------->
        determined range

The playlist calls _Next(), the randomizer selects B, and returns it.

                                     history
                                next |
                                head |
                                |    |
            D    E    C    B    A
          <------------------>
           determined range

The playlist calls _Next(), the randomizer selects the last item (it has no choice). 'next' and 'head' now point one item past the end (their value is the vector size).

                                     history
                                     next
                                     head
                                     |
            D    E    C    B    A
          <----------------------->
             determined range

At this point, if loop is disabled, it is not possible to call _Next() anymore (_HasNext() returns false). So let's enable it by calling _SetLoop(), then let's call _Next() again.

This will start a new loop cycle. Firstly, 'next' and 'head' are reset, and the whole vector belongs to the last cycle history.

             history
             next
             head
             |
             D    E    C    B    A
          <------------------------>
                history range

Secondly, to avoid selecting A twice in a row (as the last item of the previous cycle and the first item of the new one), the randomizer will immediately determine another item in the vector (say C) to be the first of the new cycle. The items that belong to the history are kept in order. 'head' and 'history' move forward.

                 history
            next |
            |    head
            |    |
            C    D    E    B    A
          <---><------------------>
    determined     history range
         range

Finally, it will actually select and return the first item (C).

                 history
                 next
                 head
                 |
            C    D    E    B    A
          <---><------------------>
    determined     history range
         range

Then, the user adds an item to the playlist (F). This item is added in front of history.

                      history
                 next |
                 head |
                 |    |
            C    F    D    E    B    A
          <--->     <------------------>
    determined          history range
         range

The playlist calls _Next(), the randomizer randomly selects E. E "disappears" from the history of the last cycle. This is a general property: each item may not appear more than once in the "history" (both from the last and the new cycle). The history order is preserved.

                           history
                      next |
                      head |
                      |    |
            C    E    F    D    B    A
          <-------->     <-------------->
          determined      history range
            range

The playlist then calls _Prev() 3 times, that yields C, then A, then B. 'next' is decremented (modulo size) on each call.

                           history
                           |    next
                      head |    |
                      |    |    |
            C    E    F    D    B    A
          <-------->     <-------------->
          determined      history range
            range

Function Documentation

randomizer_Add()

bool randomizer_Add	(	struct randomizer *	randomizer,
		vlc_playlist_item_t *	items[],
		size_t	count
	)

Add items to the randomizer.

This function should be called when items are added to the playlist.

References count, randomizer::history, randomizer::items, randomizer::next, and vlc_vector_insert_all.

Referenced by vlc_playlist_ItemsInserted(), vlc_playlist_PlaybackOrderChanged(), and vlc_playlist_Replace().

randomizer_Clear()

void randomizer_Clear

(

struct randomizer *

randomizer

)

Clear the randomizer.

References randomizer::head, randomizer::history, randomizer::items, randomizer::next, and vlc_vector_clear.

Referenced by vlc_playlist_ItemsReset(), and vlc_playlist_PlaybackOrderChanged().

randomizer_Count()

bool randomizer_Count

(

struct randomizer *

randomizer

)

Return the number of items in the randomizer.

References randomizer::items, and randomizer::size.

Referenced by vlc_playlist_PlaybackOrderChanged().

randomizer_Destroy()

void randomizer_Destroy

(

struct randomizer *

randomizer

)

Destroy a randomizer.

References randomizer::items, and vlc_vector_destroy.

Referenced by vlc_playlist_Delete().

randomizer_HasNext()

bool randomizer_HasNext

(

struct randomizer *

randomizer

)

Indicate whether there is a next item.

References randomizer::items, randomizer::loop, randomizer::next, and randomizer::size.

Referenced by randomizer_Next(), randomizer_PeekNext(), and vlc_playlist_RandomOrderHasNext().

randomizer_HasPrev()

bool randomizer_HasPrev

(

struct randomizer *

randomizer

)

Indicate whether there is a previous item.

References randomizer::history, randomizer::items, randomizer::loop, randomizer::next, and randomizer::size.

Referenced by randomizer_PeekPrev(), randomizer_Prev(), and vlc_playlist_RandomOrderHasPrev().

randomizer_Init()

void randomizer_Init

(

struct randomizer *

randomizer

)

Initialize an empty randomizer.

References randomizer::head, randomizer::history, randomizer::items, randomizer::loop, randomizer::next, vlc_rand_bytes(), vlc_vector_init, and randomizer::xsubi.

Referenced by vlc_playlist_New().

randomizer_Next()

vlc_playlist_item_t * randomizer_Next

(

struct randomizer *

randomizer

)

Go back to the next item.

References randomizer::head, randomizer::items, randomizer::next, randomizer_HasNext(), randomizer_PeekNext(), and randomizer::size.

Referenced by vlc_playlist_Next().

randomizer_PeekNext()

vlc_playlist_item_t * randomizer_PeekNext

(

struct randomizer *

randomizer

)

Peek the next item (without changing the current one).

References randomizer::data, randomizer::head, randomizer::history, randomizer::items, randomizer::loop, randomizer::next, randomizer_AutoReshuffle(), randomizer_DetermineOne(), randomizer_HasNext(), and randomizer::size.

Referenced by randomizer_Next(), and vlc_playlist_RandomOrderGetNextIndex().

randomizer_PeekPrev()

vlc_playlist_item_t * randomizer_PeekPrev

(

struct randomizer *

randomizer

)

Peek the previous item (without changing the current one).

References randomizer::data, randomizer::items, randomizer::next, randomizer_HasPrev(), and randomizer::size.

Referenced by randomizer_Prev(), and vlc_playlist_RandomOrderGetPrevIndex().

randomizer_Prev()

vlc_playlist_item_t * randomizer_Prev

(

struct randomizer *

randomizer

)

Go back to the previous item.

References randomizer::items, randomizer::next, randomizer_HasPrev(), randomizer_PeekPrev(), and randomizer::size.

Referenced by vlc_playlist_Prev().

randomizer_Remove()

void randomizer_Remove	(	struct randomizer *	randomizer,
		vlc_playlist_item_t *const	items[],
		size_t	count
	)

Remove items from the randomizer.

This function should be called when items are removed from the playlist.

References count, randomizer::items, randomizer_RemoveOne(), and vlc_vector_autoshrink.

Referenced by vlc_playlist_ItemsRemoving(), and vlc_playlist_Replace().

randomizer_Reshuffle()

void randomizer_Reshuffle

(

struct randomizer *

randomizer

)

Start a new random cycle.

The "history" is lost, and "next" can be called n times if the randomizer contains n items (when loop is disabled).

References randomizer::head, randomizer::history, randomizer::items, randomizer::next, and randomizer::size.

randomizer_Select()

void randomizer_Select	(	struct randomizer *	randomizer,
		const vlc_playlist_item_t *	item
	)

Force the selection of a specific item.

This function should be called when the user requested to play a specific item in the playlist.

References randomizer_IndexOf(), and randomizer_SelectIndex().

Referenced by player_on_current_media_changed(), and vlc_playlist_GoTo().

randomizer_SetLoop()

void randomizer_SetLoop	(	struct randomizer *	randomizer,
		bool	loop
	)

Enable or disable "loop" mode.

This affects the behavior of prev/next.

References randomizer::loop.

Referenced by vlc_playlist_PlaybackOrderChanged(), and vlc_playlist_PlaybackRepeatChanged().