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

# include "sort_rc.h"

/******************************************************************************/

void i4vec_print ( int n, int a[], char *title )

/******************************************************************************/
/*
  Purpose:

    I4VEC_PRINT prints an I4VEC.

  Discussion:

    An I4VEC is a vector of I4's.

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    14 November 2003

  Author:

    John Burkardt

  Parameters:

    Input, int N, the number of components of the vector.

    Input, int A[N], the vector to be printed.

    Input, char *TITLE, a title.
*/
{
  int i;

  fprintf ( stdout, "\n" );
  fprintf ( stdout, "%s\n", title );
  fprintf ( stdout, "\n" );

  for ( i = 0; i < n; i++ )
  {
    fprintf ( stdout, "  %6d: %8d\n", i, a[i] );
  }
  return;
}
/******************************************************************************/

int *i4vec_uniform_ab_new ( int n, int a, int b, int *seed )

/******************************************************************************/
/*
  Purpose:

    I4VEC_UNIFORM_AB_NEW returns a scaled pseudorandom I4VEC.

  Discussion:

    The pseudorandom numbers should be uniformly distributed
    between A and B.

  Licensing:

    This code is distributed under the MIT license. 

  Modified:

    13 January 2014

  Author:

    John Burkardt

  Reference:

    Paul Bratley, Bennett Fox, Linus Schrage,
    A Guide to Simulation,
    Second Edition,
    Springer, 1987,
    ISBN: 0387964673,
    LC: QA76.9.C65.B73.

    Bennett Fox,
    Algorithm 647:
    Implementation and Relative Efficiency of Quasirandom
    Sequence Generators,
    ACM Transactions on Mathematical Software,
    Volume 12, Number 4, December 1986, pages 362-376.

    Pierre L'Ecuyer,
    Random Number Generation,
    in Handbook of Simulation,
    edited by Jerry Banks,
    Wiley, 1998,
    ISBN: 0471134031,
    LC: T57.62.H37.

    Peter Lewis, Allen Goodman, James Miller,
    A Pseudo-Random Number Generator for the System/360,
    IBM Systems Journal,
    Volume 8, Number 2, 1969, pages 136-143.

  Parameters:

    Input, integer N, the dimension of the vector.

    Input, int A, B, the limits of the interval.

    Input/output, int *SEED, the "seed" value, which should NOT be 0.
    On output, SEED has been updated.

    Output, int I4VEC_UNIFORM_AB_NEW[N], a vector of random values 
    between A and B.
*/
{
  int c;
  int i;
  const int i4_huge = 2147483647;
  int k;
  float r;
  int value;
  int *x;

  if ( *seed == 0 )
  {
    fprintf ( stderr, "\n" );
    fprintf ( stderr, "I4VEC_UNIFORM_AB_NEW - Fatal error!\n" );
    fprintf ( stderr, "  Input value of SEED = 0.\n" );
    exit ( 1 );
  }
/*
  Guaranteee A <= B.
*/
  if ( b < a )
  {
    c = a;
    a = b;
    b = c;
  }

  x = ( int * ) malloc ( n * sizeof ( int ) );

  for ( i = 0; i < n; i++ )
  {
    k = *seed / 127773;

    *seed = 16807 * ( *seed - k * 127773 ) - k * 2836;

    if ( *seed < 0 )
    {
      *seed = *seed + i4_huge;
    }

    r = ( float ) ( *seed ) * 4.656612875E-10;
/*
  Scale R to lie between A-0.5 and B+0.5.
*/
    r = ( 1.0 - r ) * ( ( float ) a - 0.5 ) 
      +         r   * ( ( float ) b + 0.5 );
/*
  Use rounding to convert R to an integer between A and B.
*/
    value = round ( r );
/*
  Guarantee A <= VALUE <= B.
*/
    if ( value < a )
    {
      value = a;
    }
    if ( b < value )
    {
      value = b;
    }

    x[i] = value;
  }

  return x;
}
/******************************************************************************/

void sort_rc ( int n, int *indx, int *i, int *j, int isgn )

/******************************************************************************/
/*
  Purpose:

    SORT_RC externally sorts a list of items into ascending order.

  Discussion:

    The actual list of data is not passed to the routine.  Hence this
    routine may be used to sort integers, reals, numbers, names,
    dates, shoe sizes, and so on.  After each call, the routine asks
    the user to compare or interchange two items, until a special
    return value signals that the sorting is completed.

    Note that this function uses internal persistent memory during the sort.

  Example:

    n = 100;
    indx = 0;

    for ( ; ; )
    {
      sort_rc ( n, &indx, &i, &j, isgn );

      if ( indx < 0 )
      {
        isgn = 1;
        if ( a[i-1] <= a[j-1] )
        {
          isgn = -1;
        }
      }
      else if ( 0 < indx )
      {
        k      = a[i-1];
        a[i-1] = a[j-1];
        a[j-1] = k;
      }
      else
      {
        break;
      }
    }

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    09 March 2015

  Author:

    Original FORTRAN77 version by Albert Nijenhuis, Herbert Wilf.
    C version by John Burkardt.

  Reference:

    Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms,
    Academic Press, 1978, second edition,
    ISBN 0-12-519260-6.

  Parameters:

    Input, int N, the length of the input list.

    Input/output, int *INDX.
    The user must set INDX to 0 before the first call.
    On return,
      if INDX is greater than 0, the user must interchange
      items I and J and recall the routine.
      If INDX is less than 0, the user is to compare items I
      and J and return in ISGN a negative value if I is to
      precede J, and a positive value otherwise.
      If INDX is 0, the sorting is done.

    Output, int *I, *J.  On return with INDX positive,
    elements I and J of the user's list should be
    interchanged.  On return with INDX negative, elements I
    and J are to be compared by the user.

    Input, int ISGN. On return with INDX negative, the
    user should compare elements I and J of the list.  If
    item I is to precede item J, set ISGN negative,
    otherwise set ISGN positive.
*/
{
  static int i_save = 0;
  static int j_save = 0;
  static int k_save = 0;
  static int l_save = 0;
  static int n_save = 0;
/*
  INDX = 0: This is the first call.
*/
  if ( *indx == 0 )
  {

    i_save = 0;
    j_save = 0;
    k_save = n / 2;
    l_save = n / 2;
    n_save = n;
  }
/*
  INDX < 0: The user is returning the results of a comparison.
*/
  else if ( *indx < 0 )
  {
    if ( *indx == -2 )
    {
      if ( isgn < 0 )
      {
        i_save = i_save + 1;
      }
      j_save = l_save;
      l_save = i_save;
      *indx = -1;
      *i = i_save;
      *j = j_save;
      return;
    }

    if ( 0 < isgn )
    {
      *indx = 2;
      *i = i_save;
      *j = j_save;
      return;
    }

    if ( k_save <= 1 )
    {
      if ( n_save == 1 )
      {
        i_save = 0;
        j_save = 0;
        *indx = 0;
      }
      else
      {
        i_save = n_save;
        j_save = 1;
        n_save = n_save - 1;
        *indx = 1;
      }
      *i = i_save;
      *j = j_save;
      return;
    }
    k_save = k_save - 1;
    l_save = k_save;
  }
/*
  0 < INDX: the user was asked to make an interchange.
*/
  else if ( *indx == 1 )
  {
    l_save = k_save;
  }

  for ( ; ; )
  {

    i_save = 2 * l_save;

    if ( i_save == n_save )
    {
      j_save = l_save;
      l_save = i_save;
      *indx = -1;
      *i = i_save;
      *j = j_save;
      return;
    }
    else if ( i_save <= n_save )
    {
      j_save = i_save + 1;
      *indx = -2;
      *i = i_save;
      *j = j_save;
      return;
    }

    if ( k_save <= 1 )
    {
      break;
    }

    k_save = k_save - 1;
    l_save = k_save;
  }

  if ( n_save == 1 )
  {
    i_save = 0;
    j_save = 0;
    *indx = 0;
    *i = i_save;
    *j = j_save;
  }
  else
  {
    i_save = n_save;
    j_save = 1;
    n_save = n_save - 1;
    *indx = 1;
    *i = i_save;
    *j = j_save;
  }

  return;
}
/******************************************************************************/

void sort_safe_rc ( int n, int *indx, int *i, int *j, int isgn, int *i_save,
  int *j_save, int *k_save, int *l_save, int *n_save )

/******************************************************************************/
/*
  Purpose:

    SORT_SAFE_RC externally ascending sorts a list of items.

  Discussion:

    This is a version of SORT_RC which does not rely on
    storing certain work variables internally to the function.  This makes
    the function somewhat more awkward to call, but easier to program
    in a variety of languages, and safe to use in a parallel programming
    environment, or in cases where the sorting of several vectors is to
    be carried out at more or less the same time.

    The actual list of data is not passed to the routine.  Hence this
    routine may be used to sort integers, reals, numbers, names,
    dates, shoe sizes, and so on.  After each call, the routine asks
    the user to compare or interchange two items, until a special
    return value signals that the sorting is completed.

  Example:

    n = 100;
    indx = 0;

    for ( ; ; )
    {
      sort_rc ( n, &indx, &i, &j, isgn, &i_save, &j_save, &k_save, 
        &l_save, &n_save );

      if ( indx < 0 )
      {
        isgn = 1;
        if ( a[i-1] <= a[j-1] )
        {
          isgn = -1;
        }
      }
      else if ( 0 < indx )
      {
        k      = a[i-1];
        a[i-1] = a[j-1];
        a[j-1] = k;
      }
      else
      {
        break;
      }
    }

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    09 March 2015

  Author:

    Original FORTRAN77 version by Albert Nijenhuis, Herbert Wilf.
    C version by John Burkardt.

  Reference:

    Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms,
    Academic Press, 1978, second edition,
    ISBN 0-12-519260-6.

  Parameters:

    Input, int N, the length of the input list.

    Input/output, int *INDX.
    The user must set INDX to 0 before the first call.
    On return,
      if INDX is greater than 0, the user must interchange
      items I and J and recall the routine.
      If INDX is less than 0, the user is to compare items I
      and J and return in ISGN a negative value if I is to
      precede J, and a positive value otherwise.
      If INDX is 0, the sorting is done.

    Output, int *I, *J.  On return with INDX positive,
    elements I and J of the user's list should be
    interchanged.  On return with INDX negative, elements I
    and J are to be compared by the user.

    Input, int ISGN. On return with INDX negative, the
    user should compare elements I and J of the list.  If
    item I is to precede item J, set ISGN negative,
    otherwise set ISGN positive.

    Input/output, int *I_SAVE, *J_SAVE, *K_SAVE, *L_SAVE,
    *N_SAVE, workspace needed by the routine.  Before calling the function,
    the user should declare variables to hold these values, but should
    not change them, and need not ever examine them.
*/
{
/*
  INDX = 0: This is the first call.
*/
  if ( *indx == 0 )
  {
    *i_save = 0;
    *j_save = 0;
    *k_save = n / 2;
    *l_save = n / 2;
    *n_save = n;
  }
/*
  INDX < 0: The user is returning the results of a comparison.
*/
  else if ( *indx < 0 )
  {
    if ( *indx == -2 )
    {
      if ( isgn < 0 )
      {
        *i_save = *i_save + 1;
      }
      *j_save = *l_save;
      *l_save = *i_save;
      *indx = -1;
      *i = *i_save;
      *j = *j_save;
      return;
    }

    if ( 0 < isgn )
    {
      *indx = 2;
      *i = *i_save;
      *j = *j_save;
      return;
    }

    if ( *k_save <= 1 )
    {
      if ( *n_save == 1 )
      {
        *i_save = 0;
        *j_save = 0;
        *indx = 0;
      }
      else
      {
        *i_save = *n_save;
        *j_save = 1;
        *n_save = *n_save - 1;
        *indx = 1;
      }
      *i = *i_save;
      *j = *j_save;
      return;
    }
    *k_save = *k_save - 1;
    *l_save = *k_save;
  }
/*
  0 < INDX: the user was asked to make an interchange.
*/
  else if ( *indx == 1 )
  {
    *l_save = *k_save;
  }

  for ( ; ; )
  {
    *i_save = 2 * ( *l_save );

    if ( *i_save == *n_save )
    {
      *j_save = *l_save;
      *l_save = *i_save;
      *indx = -1;
      *i = *i_save;
      *j = *j_save;
      return;
    }
    else if ( *i_save <= *n_save )
    {
      *j_save = *i_save + 1;
      *indx = -2;
      *i = *i_save;
      *j = *j_save;
      return;
    }

    if ( *k_save <= 1 )
    {
      break;
    }

    *k_save = *k_save - 1;
    *l_save = *k_save;
  }

  if ( *n_save == 1 )
  {
    *i_save = 0;
    *j_save = 0;
    *indx = 0;
    *i = *i_save;
    *j = *j_save;
  }
  else
  {
    *i_save = *n_save;
    *j_save = 1;
    *n_save = *n_save - 1;
    *indx = 1;
    *i = *i_save;
    *j = *j_save;
  }

  return;
}
/******************************************************************************/

void timestamp ( )

/******************************************************************************/
/*
  Purpose:

    TIMESTAMP prints the current YMDHMS date as a time stamp.

  Example:

    31 May 2001 09:45:54 AM

  Licensing:

    This code is distributed under the MIT license.

  Modified:

    24 September 2003

  Author:

    John Burkardt

  Parameters:

    None
*/
{
# define TIME_SIZE 40

  static char time_buffer[TIME_SIZE];
  const struct tm *tm;
  time_t now;

  now = time ( NULL );
  tm = localtime ( &now );

  strftime ( time_buffer, TIME_SIZE, "%d %B %Y %I:%M:%S %p", tm );

  fprintf ( stdout, "%s\n", time_buffer );

  return;
# undef TIME_SIZE
}