Playlist shuffle on/off

I am programming in java, but I could also adopt C++ (or even pseudo) code, no problem. Here is what I'm at:

I have something like a playlist such as List<MyPlayListItem> lsMyPlaylist. Now I want to give the user the opportunity to shuffle the items, but then also come back to the ordered list. I mean, let's say the user is in "shuffle mode", the player e.g. jumps from song 7 to 5, but then the user turns the "shuffle mode" off, 'cause he wants to hear song 6 next. How would you approach this prob开发者_JS百科lem?

I have several ideas:

• to use two lists, one original, one shuffled (too much storage)
• have a list of int's that I shuffle and then use as index to get the elements (a little better, maybe)
• use a hashtable (the solution? I could need some advise on that, though)

Oh, and this is not a homework assignment (I wish I was that age again :-D).

EDIT:

I just finished an implementation like this:

PlayList<E> implements List {

   private List<E> lsObjs = null;
   private List<Integer> lsIdxs = null;

   boolean bShuffleMode = false;
   int Pos = 0;
}

However now, I'm thinking of something like:

PlayListItem<E> {

   int iNextItem = 0;

}

PlayList<PlayListItem> implements List {

   private List<PlayListItem> lsObjs = null;

   boolean bShuffleMode = false;
   int Pos = 0;

}

Not sure about this...Could still need advice. Can I even implement List if I specify the objects in the list? Hm...

I assume you have a mobile device which doesn't have a couple of K to spare. Having two lists will not duplicate the elements of the list which will be far larger.

Add the orginal index as a field to the MyPlayListItem. After shuffling them you can sort them on the index with a comparator to turn them back into the original order. note: unless the index is less than 4 bytes this will use as much memory as having two lists.

On a 32-bit system, an int[] and a List consume almost the same amount of memory. (about 16 bytes difference)

I'd suggest that you have one main container for a list of songs (Library), and a container per playlist. Of course, playlist should point to elements in Library.

After that, there are many approaches to shuffling, one of the best that I like is to have a list of songs in a container where you pick songs at random and remove picked songs. So it will be random, but non-repeating playing.

It's been a long time since I programmed in Java, so I will give a working C++ example. I hope it is simple and self-explaining:

// --*-- C++ --*--

#include <ctime>
#include <cassert>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <vector>
#include <list>

struct Song
{
    std::string name;

    Song (const std::string & name) :
        name (name)
    {
    }

    void play ()
    {
        printf ("Playing '%s'...\n", name.c_str ());
    }
};

typedef std::vector<Song> Library;
typedef std::vector<Song *> Playlist;
typedef std::vector<size_t> SongIDSet;

int
main ()
{
    srand (time (NULL));

    Library library;

    library.push_back (Song ("Lady Gaga - Bad Romance"));
    library.push_back (Song ("Rihanna - Only Girl"));
    library.push_back (Song ("Nelly - Just a Dream"));
    library.push_back (Song ("Animal - Neon Trees"));
    library.push_back (Song ("Eminem ft. Rihanna - Love The Way You Lie"));

    Playlist playlist;

    for (Library::iterator it = library.begin (),
             end_it = library.end (); it != end_it; ++it)
    {
        printf ("Added song -> %s\n", it->name.c_str ());
        playlist.push_back (&(*it));
    }

    SongIDSet shuffle;
    for (size_t i = 0, end_i = playlist.size (); i < end_i; ++i)
    {
        shuffle.push_back (i);
    }

    size_t nowPlaying = 0;

    while (!shuffle.empty ())
    {
        size_t songIndex = 0;
            printf ("Shuffle? [Y/n] ");
        switch (fgetc (stdin))
        {
            case 'N':
            case 'n':
                songIndex = nowPlaying + 1;
                fgetc (stdin); // Skip newline.
                break;
            case 'Y':
            case 'y':
                fgetc (stdin); // Skip newline.
            default:
            {
                printf ("Shuffling...\n");
                size_t index = rand () % shuffle.size ();
                assert (index >= 0);
                assert (index < shuffle.size ());
                songIndex = shuffle[index];
                shuffle.erase (shuffle.begin () + index);
            }
        }
        assert (songIndex >= 0);
        if (songIndex < playlist.size ())
        {
            nowPlaying = songIndex;
            playlist[nowPlaying]->play ();
        }
        else
        {
            break; // Done playing.. Repeat maybe?
        }
    }
}

Here is an example run/output:

$ ./test 
Added song -> Lady Gaga - Bad Romance
Added song -> Rihanna - Only Girl
Added song -> Nelly - Just a Dream
Added song -> Animal - Neon Trees
Added song -> Eminem ft. Rihanna - Love The Way You Lie
Shuffle? [Y/n] 
Shuffling...
Playing 'Eminem ft. Rihanna - Love The Way You Lie'...
Shuffle? [Y/n] 
Shuffling...
Playing 'Nelly - Just a Dream'...
Shuffle? [Y/n] 
Shuffling...
Playing 'Rihanna - Only Girl'...
Shuffle? [Y/n] 
Shuffling...
Playing 'Animal - Neon Trees'...
Shuffle? [Y/n] 
Shuffling...
Playing 'Lady Gaga - Bad Romance'...
$ ./test 
Added song -> Lady Gaga - Bad Romance
Added song -> Rihanna - Only Girl
Added song -> Nelly - Just a Dream
Added song -> Animal - Neon Trees
Added song -> Eminem ft. Rihanna - Love The Way You Lie
Shuffle? [Y/n] 
S    huffling...
Playing 'Nelly - Just a Dream'...
Shuffle? [Y/n] n
Playing 'Animal - Neon Trees'...
Shuffle? [Y/n] n
Playing 'Eminem ft. Rihanna - Love The Way You Lie'...
Shuffle? [Y/n] n

How about add nextSong property on MyPlayListItem that will hold a reference to next song in original playlist. Everytime user shuffles the playlist, the List will be shuffled but the original playlist will be kept. But of course you need something to hold a reference to the first MyPlayListItem in original playlist.

If memory is your biggest restriction you could just choose a random song to play at the end of each song. It obviously means you will not necessarily play every song before starting the list again. :)

If you need to play every song before starting to play songs again then store a bitstring of length equal to the number of songs. As you play songs set the bit corresponding to that index. Never play a song if it's bit is set, instead at that point increment the index until you find a bit in the string that isn't set. If all bits in the string are set then reset the bit string.

What about something simple?

Use an index pointer into the list, say an integer. This is the current song being played. When the player is in shuffle mode, this pointer gets set to a random number between 0 and the number of items in the list - 1. When the player is in sequential mode, this pointer is simply incremented.

If you want to prevent repetition of songs, there are two strategies. One is to use a bit string, as another person suggested above. The other would be to use a set. Each time the pointer is set, check for membership in the set. If it's in the set already, get another index. If it's not, then add it and play the song. Either will accomplish the same effect.

You will run into problems when the ratio of played songs to unplayed songs becomes high with a random index always being in the list.

You can have two items :
1) list of real items in a list
2) vector with integer indexes

When the shuffle is activated, you shuffle indexes. When it is off, sort indexes. When accessing elements in the list, use indexes.

something like this :

std::list< MyListElement > elements = ...;
std::vector< int > indexes = ...;

// shuffle off
sort( indexes.begin(), indexes.end() );

// get elements
elements[ indexes[ i ] ];