/* nag_chain_sort (m01cuc) Example Program.
 *
 * NAGPRODCODE Version.
 *
 * Copyright 2016 Numerical Algorithms Group.
 *
 * Mark 26, 2016.
 *
 *
 */

#include <nag.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);
#ifdef __cplusplus
}
#endif

int main(void)
{
  /* 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;

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

  /* 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) {
    printf("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)))
  {
    printf("Allocation failure\n");
    exit_status = -1;
    goto END;
  }

  /* Initialize the generator to a repeatable sequence */
  nag_rand_init_repeatable(genid, subid, seed, lseed, state, &lstate, &fail);
  if (fail.code != NE_NOERROR) {
    printf("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) {
      printf("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) {
      printf("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 */
  printf("nag_chain_sort (m01cuc) Example Program Results\n");
  printf("\nDATA\n\n");
  printf("Matrix Order:\n");
  printf("   Matrix Index      Linked List Index      Data\n");
  for (i = 0; i < n; ++i)
    printf("%10" NAG_UFMT "%20" NAG_IFMT "%20.6f\n", i, vec[i].index,
           vec[i].data);
  printf("Linked List Order:\n");
  printf("   Matrix Index      Linked List Index      Data\n");
  for (address = base; address != NULL; address = (*address).next)
    printf("%10" NAG_UFMT "%20" NAG_IFMT "%20.6f\n",
           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) {
    printf("Error from nag_chain_sort (m01cuc).\n%s\n", fail.message);
    exit_status = 1;
    goto END;
  }

  /* Output results */
  printf("\nRESULTS\n\n");

  /* The order in the input matrix is unchanged */
  printf("Matrix Order:\n");
  printf("   Matrix Index      Linked List Index      Data\n");
  for (i = 0; i < n; ++i)
    printf("%10" NAG_UFMT "%20" NAG_IFMT "%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 */
  printf("Linked List Order:\n");
  printf("   Matrix Index      Linked List Index      Data\n");
  for (address = base; address != NULL; address = (*address).next)
    printf("%10" NAG_UFMT "%20" NAG_IFMT "%20.6f\n",
           address - origbase, (*address).index, (*address).data);

END:
  NAG_FREE(vec);
  NAG_FREE(state);

  return exit_status;
}

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));
}