/* nag_chain_sort (m01cuc) Example Program.
 *
 * Copyright 1996 Numerical Algorithms Group.
 *
 * Mark 4, 1996.
 * Mark 5 revised, 1998.
 * Mark 7 revised, 2001.
 *
 * Mark 8 revised, 2004
 *
 */

#include <nag.h>
#include <nagx04.h>
#include <stdio.h>
#include <nag_stdlib.h>
#include <nag_stddef.h>
#include <nagg05.h>
#include <nagm01.h>

struct recd
{
  double      data;
  struct recd *next;
  Integer     index;
};

#ifdef __cplusplus
extern "C"
{
#endif
static Integer NAG_CALL compare(const Nag_Pointer a, const Nag_Pointer b)
{
  double x = ((struct recd *) a)->data;
  double y = ((struct recd *) b)->data;
  return(x < y?-1:(x == y?0:1));
}
#ifdef __cplusplus
}
#endif

int main(int argc, char *argv[])
{
  FILE        *fpout;
  /* Integer scalar and array declarations */
  Integer     exit_status = 0;
  Integer     lstate;
  Integer     *state = 0, draw[1];

  /* Double scalars */
  double      p[1];

  /* NAG structures and types */
  NagError    fail;
  ptrdiff_t   ptroffset;
  size_t      i, j, l[20];
  struct recd *address, *base, *origbase, *vec = 0;

  /* Set the number of data fields */
  size_t      n = 10;

  /* Choose the base generator */
  Nag_BaseRNG genid = Nag_Basic;
  Integer     subid = 0;

  /* Set the seed */
  Integer     seed[] = { 1762543 };
  Integer     lseed = 1;

  /* Initialise the error structure */
  INIT_FAIL(fail);

  /* Check for command-line IO options */
  fpout = nag_example_file_io(argc, argv, "-results", NULL);

  /* Get the length of the state array */
  lstate = -1;
  nag_rand_init_repeatable(genid, subid, seed, lseed, state, &lstate, &fail);
  if (fail.code != NE_NOERROR)
    {
      fprintf(fpout, "Error from nag_rand_init_repeatable (g05kfc).\n%s\n",
              fail.message);
      exit_status = 1;
      goto END;
    }

  /* Allocate arrays */
  if (!(vec = NAG_ALLOC(20, struct recd)) ||
      !(state = NAG_ALLOC(lstate, Integer)))
    {
      fprintf(fpout, "Allocation failure\n");
      exit_status = -1;
      goto END;
    }

  /* Initialise the generator to a repeatable sequence */
  nag_rand_init_repeatable(genid, subid, seed, lseed, state, &lstate, &fail);
  if (fail.code != NE_NOERROR)
    {
      fprintf(fpout, "Error from nag_rand_init_repeatable (g05kfc).\n%s\n",
              fail.message);
      exit_status = 1;
      goto END;
    }

  ptroffset = (ptrdiff_t)(((char *) &(vec->next)) - ((char *) vec));

  /* Set data field to random number between 0 and 5 */
  for (i = 0; i < n; ++i)
    {
      /* Generate a random integer from a uniform distribution */
      nag_rand_discrete_uniform(1, (Integer) 0, (Integer) 5, state, draw,
                                &fail);
      if (fail.code != NE_NOERROR)
        {
          fprintf(fpout,
                  "Error from nag_rand_discrete_uniform (g05tlc).\n%s\n",
                  fail.message);
          exit_status = 1;
          goto END;
        }
      vec[i].data = (double) draw[0];
    }

  /* Randomly set index fields from 0 to 9 */
  for (i = 0; i < n; ++i)
    {
      /* Generate a random value from a uniform distribution */
      nag_rand_basic(1, state, p, &fail);
      if (fail.code != NE_NOERROR)
        {
          fprintf(fpout, "Error from nag_rand_basic (g05sac).\n%s\n",
                  fail.message);
          exit_status = 1;
          goto END;
        }
      j = (int)((i+1)*p[0]);

      /* j is less than or equal to i */
      (vec[i]).index = (vec[j]).index;
      (vec[j]).index = i;
    }

  /* Set next pointers to make linked list in index field order */
  for (i = 0; i < n; ++i)
    l[(vec[i]).index] = i;
  for (i = 0; i < n-1; ++i)
    vec[l[i]].next = &vec[l[i+1]];
  vec[l[n-1]].next = NULL;

  /* Get pointers to the start of the linked list (base) and the start
     of the array (origbase) */
  origbase = &vec[0];
  base = &vec[l[0]];

  /* Print Input Data */
  fprintf(fpout, "nag_chain_sort (m01cuc) Example Program Results\n");
  fprintf(fpout, "\nDATA\n\n");
  fprintf(fpout, "Matrix Order:\n");
  fprintf(fpout, "   Matrix Index      Linked List Index      Data\n");
  for (i = 0; i < n; ++i)
    fprintf(fpout, "%10" NAG_UFMT "%20ld%20.6f\n", i, vec[i].index,
            vec[i].data);
  fprintf(fpout, "Linked List Order:\n");
  fprintf(fpout, "   Matrix Index      Linked List Index      Data\n");
  for (address = base; address != NULL; address = (*address).next)
    fprintf(fpout, "%10" NAG_UFMT "%20ld%20.6f\n",
            (ptrdiff_t)(address-origbase), (*address).index, (*address).data);

  /* Sort the linked list on the data field */
  /* nag_chain_sort (m01cuc).
   * Chain sort of linked list
   */
  nag_chain_sort((Pointer *) &base, ptroffset, compare, Nag_Ascending, &fail);
  if (fail.code != NE_NOERROR)
    {
      fprintf(fpout, "Error from nag_chain_sort (m01cuc).\n%s\n", fail.message);
      exit_status = 1;
      goto END;
    }

  /* Output results */
  fprintf(fpout, "\nRESULTS\n\n");

  /* The order in the input matrix is unchanged */
  fprintf(fpout, "Matrix Order:\n");
  fprintf(fpout, "   Matrix Index      Linked List Index      Data\n");
  for (i = 0; i < n; ++i)
    fprintf(fpout, "%10" NAG_UFMT "%20ld%20.6f\n", i, vec[i].index,
            vec[i].data);

  /* But the linked list pointers have been changed to reflect
     the ascending sort on the data field */
  fprintf(fpout, "Linked List Order:\n");
  fprintf(fpout, "   Matrix Index      Linked List Index      Data\n");
  for (address = base; address != NULL; address = (*address).next)
    fprintf(fpout, "%10" NAG_UFMT "%20ld%20.6f\n",
            (ptrdiff_t)(address-origbase), (*address).index, (*address).data);

 END:
  if (fpout != stdout) fclose(fpout);
  if (vec) NAG_FREE(vec);
  if (state) NAG_FREE(state);

  return exit_status;
}