/**
 * blortsort.cpp
 * 30apr07/sklar
 *
 * this program demonstrates the blort sort algorithm.
 *
 */

#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;


// declare constants
const int NUM_DICE = 5;

// declare global variable
int dice[NUM_DICE];

// declare function prototypes
void initDice();
void printDice( int d[], int n );
void swapDice( int a, int b );
bool isSorted();
void permuteDice();
void blortSort();



/**
 * initDice()
 *
 * this function initializes the values in the array of dice to
 * integers between 1 and 6
 *
 */
void initDice() {
  for ( int i=0; i<NUM_DICE; i++ ) {
    dice[i] = ( rand() % 6 ) + 1;
  }
} // end of initDice()


/**
 * printDice()
 *
 * this function prints the values in the array of dice
 *
 */
void printDice( int d[], int n ) {
  int i;
  for ( i=0; i<n-1; i++ ) {
    cout << d[i] << " ";
  }
  cout << d[i] << endl;
} // end of printDice()



/**
 * swapDice()
 *
 * this function swaps two values in the array of dice
 *
 */
void swapDice( int a, int b ) {
  int tmp;
  tmp = dice[a];
  dice[a] = dice[b];
  dice[b] = tmp;
  return;
} // end of swapDice()



/**
 * isSorted()
 *
 * this function returns "true" if the dice are in sorted order;
 * and "false" if they are not
 *
 */
bool isSorted() {
  int i = 0;
  bool anyErrors = false;
  while (( ! anyErrors ) && ( i < NUM_DICE-1 )) {
    if ( dice[i] > dice[i+1] ) {
      anyErrors = true;
    }
    else {
      i++;
    }
  } // end while
  return( ! anyErrors );
} // end of isSorted()



/**
 * permuteDice()
 *
 * this function "permutes" (mixes up) all the values in the dice array
 *
 */
void permuteDice() {
  int i, r;
  for ( i=0; i<NUM_DICE; i++ ) {
    r = rand() % NUM_DICE;
    swapDice( i, r );
  } // end for
} // end of permuteDice()



/**
 * blortSort()
 *
 * this function performs "blort" sort, the "fun but stupid sort"
 *
 * the algorithm is to first check if the array is sorted; if not,
 * then randomly permute all the entries in the array and check again;
 * and so on, until the array is sorted
 *
 * note that this could take a very long (even infinite!) amount of
 * time...
 *
 */
void blortSort() {
  int num_passes = 0;
  while ( ! isSorted()) {
    permuteDice();
    num_passes++;
    cout << "after pass #" << num_passes << ": ";
    printDice( dice, NUM_DICE );
  } // end of while
  cout << "TOTAL number of passes = " << num_passes << endl;
} // end of blortSort()



/**
 * main()
 *
 */
int main() {

  // initialize random number seed
  srand( time( NULL ));

  // initialize the array of dice
  initDice();

  // print the array before sorting it
  cout << "before sorting:";
  printDice( dice, NUM_DICE );

  // perform blort sort
  blortSort();

  // print the array after sorting it
  cout << "after sorting:";
  printDice( dice, NUM_DICE );

} // end of main()