//=================================================== file = disc_sim.c =====
//=  Simulation of node discovery in a passive network                      =
//===========================================================================
//=  Notes:                                                                 =
//=    1) This simulation models a room full of people (nodes) where each   =
//=       node shouts-out its name after a delay based on a roll of a       =
//=       die.  Each node has a die.  A delay is the number of seconds of   =
//=       the rolled die value.  If a success (no collision) occurs, the    =
//=       number of nodes left is decremented.  On both collision and       =
//=       success, all nodes left re-roll their die for the next "play"     =
//=    2) Must manually set NUM_ITER, M, and N in the #defines.             =
//=-------------------------------------------------------------------------=
//=  Example execution: (NUM_ITER = 100, M = 6, and N = 10)                 =
//=                                                                         =
//=    *** BEGIN SIMULATION ***                                             =
//=    -------------------------------------------------------------        =
//=    --     *** Results from node discovery simulation ***      --        =
//=    -------------------------------------------------------------        =
//=    - Number of iterations    = 100                                      =
//=    - Number of sides on die  = 6                                        =
//=    - Number of nodes         = 10                                       =
//=    -------------------------------------------------------------        =
//=    - Maximum elasped time    = 73 seconds                               =
//=    - Mean elasped time       = 30.470000 seconds                        =
//=    -------------------------------------------------------------        =
//=    *** END SIMULATION ***                                               =
//=-------------------------------------------------------------------------=
//=  Build: bcc32 discsim1.c                                                =
//=-------------------------------------------------------------------------=
//=  Execute: discsim1                                                      =
//=-------------------------------------------------------------------------=
//=  Author: Kenneth J. Christensen                                         =
//=          University of South Florida                                    =
//=          WWW: http://www.csee.usf.edu/~christen                         =
//=          Email: christen@csee.usf.edu                                   =
//=-------------------------------------------------------------------------=
//=  History: KJC (01/02/02) - Genesis                                      =
//===========================================================================

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

//----- Defines -------------------------------------------------------------
#define    NUM_ITER   100000        // Number iterations
#define           M        6        // Number of sides on the "die"
#define           N       10        // Number of nodes to be discovered

//----- Function prototypes -------------------------------------------------
int  comp(const void *p, const void *q);    // Compare p and q for qsort()

//===========================================================================
//=  Main program                                                           =
//===========================================================================
void main(void)
{
  int      num_nodes;               // Number of nodes left
  int      wait[N];                 // Array of "die rolls" (between 1 and M)
  int      time;                    // Simulated time variable
  int      max_time;                // Maximum elapsed time
  int      ave_time;                // Average (mean) elapsed time
  int      iter;                    // Iteration loop counter
  int      i;                       // Generic loop counter

  // Output banner
  printf("*** BEGIN SIMULATION *** \n");

  // Initialize
  max_time = ave_time = 0;

  // Do for NUM_ITER iterations
  for (iter=0; iter<NUM_ITER; iter++)
  {
    // Initialize
    time = 0;
    num_nodes = N;

    // Simulate for all nodes to be discovered
    do
    {
      // Roll a die for each node left
      for (i=0; i<num_nodes; i++)
        wait[i] = (rand() % M) + 1;

      // Sort the wait array
      qsort(wait, num_nodes, sizeof(int), comp);

      // Increment the simulated time to the first success or collision
      time = time + wait[0];

      // If it is success decrement the number of nodes left
      if (wait[0] < wait[1])
        num_nodes--;

    } while (num_nodes > 0);

    // Update ave_time and max_time variables
    ave_time = ave_time + time;
    if (time > max_time) max_time = time;
  }

  // Output results
  printf("------------------------------------------------------------- \n");
  printf("--     *** Results from node discovery simulation ***      -- \n");
  printf("------------------------------------------------------------- \n");
  printf("- Number of iterations    = %d \n", NUM_ITER);
  printf("- Number of sides on die  = %d \n", M);
  printf("- Number of nodes         = %d \n", N);
  printf("------------------------------------------------------------- \n");
  printf("- Maximum elasped time    = %d seconds \n", max_time);
  printf("- Mean elasped time       = %f seconds \n",
    (double) ave_time / NUM_ITER);
  printf("------------------------------------------------------------- \n");
  printf("*** END SIMULATION *** \n");
}

//===========================================================================
//=  Function to compare two arguments in an array of int                   =
//=   - Needed by qsort()                                                   =
//===========================================================================
int  comp(const void *p, const void *q)
{
  int *ptr1 = (int *)(p);
  int *ptr2 = (int *)(q);

  if (*ptr1 < *ptr2)
    return -1;
  else if (*ptr1 == *ptr2)
    return 0;
  else
    return 1;
}