/** shuffle.c -- by James D. Lin (last updated: 2003-02-04)
  *
  *     Implementation of a simple O(n) shuffling algorithm.
  *
  * Why?
  *
  *     Although I almost certainly am not the first person to have thought
  *     of this algorithm, I've seen some really bad and/or needlessly
  *     complex shuffling techniques.
  *
  *     (It's to my understanding that this is essentially Knuth's
  *     shuffling algorithm.)
  *
  * The basic idea:
  *
  *     Imagine you have a deck of cards.  Draw a card at random from the
  *     deck and start a new deck with it.  Continue to remove cards at
  *     random from the original deck and to add them to the new deck.
  *     When done, each card in the new deck has been chosen at random, and
  *     thus the new deck consists entirely of randomly ordered cards.
  *
  *     To implement this, create an array containing all the items to
  *     shuffle (or pointers to the items) and partition the array into two
  *     sides: stuff that's been shuffled and stuff that hasn't.
  *
  *     In the implementation below, the unshuffled side is at the
  *     beginning (at the left) of the array, and the shuffled side is at
  *     the end (at the right).  Initially, everything belongs to the
  *     unshuffled side.
  *
  *         unshuffled  +---+---+---+---+---+---+---+---+---+---+  shuffled
  *            side     | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |    side
  *                     +---+---+---+---+---+---+---+---+---+---+
  *                                                           ^
  *                                                         pivot
  *
  *     We'll define the "pivot point" as the index that divides the two
  *     sides.  All elements to the left of and including the pivot belong
  *     to the unshuffled side; all elements to the right of the pivot
  *     belong to the shuffled side.
  *
  *     Pick an element at random from the unshuffled side and swap it with
  *     the element at the pivot point.  Move the pivot point towards the
  *     unshuffled side by one item.  As a result, a random element has
  *     been removed from the unshuffled side and has been added to the
  *     shuffled side.
  *                                   +-------- SWAP ---------+
  *                                   |                       |
  *                                   v                       v
  *         unshuffled  +---+---+---+---+---+---+---+---+---+---+  shuffled
  *            side     | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |    side
  *                     +---+---+---+---+---+---+---+---+---+---+
  *                                                           ^
  *                                                         pivot
  *
  *
  *         unshuffled  +---+---+---+---+---+---+---+---+---+---+  shuffled
  *            side     | 0 | 1 | 2 | 9 | 4 | 5 | 6 | 7 | 8 | 3 |    side
  *                     +---+---+---+---+---+---+---+---+---+---+
  *                                                       ^
  *                                                     pivot <-- SHIFT
  *
  *     Repeat until the pivot point reaches the beginning of the array.
  *
  *     Note that it doesn't matter that the unshuffled side loses order as
  *     the algorithm progresses.  Since elements from the unshuffled side
  *     are chosen at random, each item has equal chance of being picked
  *     during the next iteration, and therefore the ordering of the
  *     unshuffled side is irrelevant.
  *
  *     An advantage of this algorithm is that the entire array does not
  *     need to be shuffled; each iteration need be performed only when a
  *     new random element is needed.  For example, if implementing a
  *     lottery system, only N iterations are needed to draw N unique items
  *     from a much larger pool.
  */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


enum { stdDeckSize = 52 };


/** Returns a random integer in the range [low, high].
  *
  * Pre : 0 <= low <= high
  */
static int randomInt(int low, int high)
{
    double r;
    do
    {
        r = (double) rand() / RAND_MAX;
    }
    /* Paranoid safeguard against possible floating point rounding error. */
    while (r >= 1.0);

    return (int) (low + (high - low + 1) * r);
}


/** Swaps array[a] and array[b].
  *
  * Pre:  array != NULL
  *       0 <= a, b < array length
  */
static void swapInts(void* array, size_t a, size_t b)
{
    /* (Yes, I am aware of the stupid xor trick to swap
     * integral values.  I choose not to use it.)
     */
    int* intArray = array;
    int temp = intArray[a];
    intArray[a] = intArray[b];
    intArray[b] = temp;
}


/** Shuffles the elements of array.
  *
  * Pre : array != NULL
  *       0 <= length < array length
  */
static void shuffle(void* array, size_t length,
                    void (*swap)(void*, size_t, size_t))
{
    size_t i;
    for (i = length - 1; i > 0; i--)
    {
        swap(array, i, randomInt(0, i));
    }
}


/** Initializes a deck. */
static void initDeck(int* deck, size_t numCards)
{
    size_t i;
    for (i = 0; i < numCards; i++)
    {
        deck[i] = i;
    }
}


/** Prints a deck. */
static void printDeck(const int* deck, size_t numCards)
{
    size_t i;
    for (i = 0; i < numCards; i++)
    {
        fprintf(stdout, "%d ", deck[i]);
    }
    fputc('\n', stdout);
}


int main(int argc, char** argv)
{
    int* deck;
    size_t numCards = (argc == 2)
                      ? atoi(argv[1])
                      : stdDeckSize;

    if (   numCards > 0
        && (deck = calloc(numCards, sizeof *deck)) != NULL)
    {
        /* Seed the randomizer. */
        srand((unsigned int) time(NULL));

        /* Some common rand() implementations are very much non-random
         * in their initial results.  Sigh.
         */
        rand();
        rand();
        rand();
        rand();

        initDeck(deck, numCards);

        shuffle(deck, numCards, swapInts);

        printDeck(deck, numCards);

        free(deck);
    }

    return EXIT_SUCCESS;
}