//=================================================== file = shuffle1.c =====
//=  Program to shuffle blocks of size M in a series of size N (M < N)      =
//=   - Implements an *external* shuffle                                    =
//===========================================================================
//=  Notes:                                                                 =
//=    1) Input from input file "in.dat" to stdin (see example below)       =
//=        * Comments are bounded by "&" characters at the beginning and    =
//=          end of the comment block                                       =
//=    2) Outputs int(N/M) blocks of size M each                            =
//=    3) Block size M is in #define section                                =
//=    4) Output is to stdout                                               =
//=    5) This program was created to aid in the evaluation of effects      =
//=       or SRD and LRD to queueing behavior.  Reference is,               =
//=         A. Erramilli, O. Narayan, W. Willinger, "Experimental Queueing  =
//=         Analysis with Long-Range Dependent Packet Traffic", IEEE/ACM    =
//=         Transactions on Networking, Vol 4, No. 2, April 1996.           =
//=-------------------------------------------------------------------------=
//= Example "in.dat" file:                                                  =
//=                                                                         =
//=    & Sample series of data which can be integers or reals.              =
//=      There are 10 values in this file. &                                =
//=     1                                                                   =
//=     2                                                                   =
//=     3                                                                   =
//=     4                                                                   =
//=     5                                                                   =
//=     6                                                                   =
//=     7                                                                   =
//=     8                                                                   =
//=     9                                                                   =
//=    10                                                                   =
//=-------------------------------------------------------------------------=
//= Example output (for above "in.dat" and M = 2):                          =
//=                                                                         =
//=   ---------------------------------------------- shuffle1.c -----       =
//=   7.000000                                                              =
//=   8.000000                                                              =
//=   9.000000                                                              =
//=   10.000000                                                             =
//=   1.000000                                                              =
//=   2.000000                                                              =
//=   3.000000                                                              =
//=   4.000000                                                              =
//=   5.000000                                                              =
//=   6.000000                                                              =
//=   & Output 5 blocks of M = 2 for 10 total values                        =
//=     ---------------------------------------------------------- &        =
//=-------------------------------------------------------------------------=
//=  Build: gcc shuffle1.c, bcc32 shuffle1.c, cl shuffle1.c                 =
//=-------------------------------------------------------------------------=
//=  Execute: shuffle1 < in.dat                                             =
//=-------------------------------------------------------------------------=
//=  Author: Kenneth J. Christensen                                         =
//=          University of South Florida                                    =
//=          WWW: http://www.csee.usf.edu/~christen                         =
//=          Email: christen@csee.usf.edu                                   =
//=-------------------------------------------------------------------------=
//=  History: KJC (01/19/99) - Genesis                                      =
//=           KJC (12/09/01) - Renamed as shuffle1.c and some clean-up      =
//===========================================================================

//----- Include files -------------------------------------------------------
#include <stdio.h>                 // Needed for printf() and feof()
#include <stdlib.h>                // Needed for exit() and atof()
#include <string.h>                // Needed for strcmp()

//----- Defines -------------------------------------------------------------
#define MAX_SIZE 1000000           // Maximum size of time series data array
#define M              2           // Block size for external shuffle

//----- Globals -------------------------------------------------------------
double     X[MAX_SIZE];            // Time series read from "in.dat"
int        N;                      // Number of values in "in.dat"

//----- Function prototypes -------------------------------------------------
void load_X_array(void);           // Load X array
int  shuffle_external(void);       // Shuffle the X array externally
int  rand_int(int max);            // Generate integer rv from 0 to max - 1

//===========================================================================
//=  Main program                                                           =
//===========================================================================
void main(void)
{
  int num_blocks;                  // Retuned value of number of blocks
  int i;                           // Loop counter

  // Load the series X
  printf("---------------------------------------------- shuffle1.c -----\n");
  load_X_array();

  // Do the shuffle
  num_blocks = shuffle_external();

  // Output the shuffled series
  for (i=0; i<(num_blocks * M); i++)
    printf("%f \n", X[i]);

  // Output closing message
  printf("&  Output %ld blocks of M = %ld for %ld total values \n",
    num_blocks, M, (num_blocks * M));
  printf("  ---------------------------------------------------------- & \n");
}

//===========================================================================
//=  Function to load X array from stdin and determine N                    =
//===========================================================================
void load_X_array(void)
{
  char      temp_string[1024];     // Temporary string variable

  // Read all values into X
  N = 0;
  while(1)
  {
    scanf("%s", temp_string);
    if (feof(stdin)) goto end;

    // This handles a comment bounded by "&" symbols
    while (strcmp(temp_string, "&") == 0)
    {
      do
      {
        scanf("%s", temp_string);
        if (feof(stdin)) goto end;
      } while (strcmp(temp_string, "&") != 0);
      scanf("%s", temp_string);
      if (feof(stdin)) goto end;
    }

    // Enter value in array and increment array index
    X[N] = atof(temp_string);
    N++;

    // Check if MAX_SIZE data values exceeded
    if (N >= MAX_SIZE)
    {
      printf("*** ERROR - greater than %ld data values \n", MAX_SIZE);
      exit(1);
    }
  }

  // End-of-file escape
  end:

  return;
}

//===========================================================================
//=  Function to shuffle series X in blocks of size M values                =
//===========================================================================
int shuffle_external(void)
{
  int    i, j, k;                 // Loop counters
  int    num_blocks;              // Number of blocks in X[]
  int    to_block;                // Random "to block" to move curent block to
  double temp[M];                 // Temporary block

  // Determine number of blocks (note to integer division)
  num_blocks = N / M;

  // Dp the shuffle
  for (i=0; i<num_blocks; i++)
  {
    // Determine random "to block"
    to_block = rand_int(num_blocks);

    // Copy "to block" to temp[]
    j = 0; k = to_block*M;
    do
    {
      temp[j++] = X[k++];
    }
    while (k < (to_block+1)*M);

    // Copy current block to "to_block"
    j = i*M; k = to_block*M;
    do
    {
      X[k++] = X[j++];
    }
    while (j < (i+1)*M);

    // Copy temp[] to current block
    j = 0; k = i*M;
    do
    {
      X[k++] = temp[j++];
    }
    while (j < M);
  }

  return(num_blocks);
}

//===========================================================================
//=  Function to generate uniformly distributed integer random variable     =
//=    - Input:  Maximum value (max)                                        =
//=    - Output: Value between 0 and (max - 1)                              =
//===========================================================================
int rand_int(int max)
{
  double z;                       // Uniform random number (0 < z < 1)
  int    rand_value;              // Computed exponential value to be returned

  // Pull a uniform random number (0 <= z <= 1)
  do
  {
    z = ((double) rand() / RAND_MAX);
  } while ((z == 0) || (z == 1.0));

  // Compute integer random variable between 0 and x
  rand_value = (int) (z * max);

  return(rand_value);
}