/* 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 <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(void)
{
  Integer draw, exit_status=0, igen=0, iseed[]={0, 0, 0, 0};
  NagError fail;
  ptrdiff_t ptroffset;
  size_t i, j, l[20], n;
  struct recd *address, *base, *origbase, *vec=0;

  INIT_FAIL(fail);

  if (!(vec = NAG_ALLOC(20, struct recd)))
    {
      Vprintf("Allocation failure\n");
      exit_status = -1;
      goto END;
    }
  ptroffset = (ptrdiff_t) (((char *) &(vec->next)) - ((char *) vec));
  /* nag_rngs_init_repeatable (g05kbc).
   * Initialize seeds of a given generator for random number
   * generating functions (that pass seeds explicitly) to give
   * a repeatable sequence
   */
  nag_rngs_init_repeatable(&igen, iseed);
  n = 10;
  /* Set data field to random number between 0 and 5 */
  for (i=0; i<n; ++i)
    {
      /* nag_rngs_discrete_uniform (g05mac).
       * Generates a vector of random integers from a uniform
       * distribution, seeds and generator number passed
       * explicitly
       */
      nag_rngs_discrete_uniform((Integer)0,(Integer)5, 1, &draw, igen, iseed,
                                &fail);
      if (fail.code != NE_NOERROR)
        {
          Vprintf("Error from nag_rngs_discrete_uniform (g05mac).\n%s\n",
                  fail.message);
          exit_status = 1;
          goto END;
        }
      vec[i].data = (double)draw;
    }
  /* Randomly set index fields from 0 to 9*/
  for (i=0; i<n; ++i)
    {
      /* nag_rngs_basic (g05kac).
       * Pseudo-random real numbers, uniform distribution over
       * (0,1), seeds and generator number passed explicitly
       */
      j = (int)((i+1)*nag_rngs_basic(igen, iseed));
      /* 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;
  base = origbase = &vec[l[0]];
  for (i=0; i<n-1; ++i)
    vec[l[i]].next = &vec[l[i+1]];
  vec[l[n-1]].next = NULL;
  /* Print Input Data */
  Vprintf("nag_chain_sort (m01cuc) Example Program Results\n");
  Vprintf("\nDATA\n\n");
  Vprintf("Matrix Order:\n");
  Vprintf("   Matrix Index      Linked List Index      Data\n");
  for (i=0; i<n; ++i)
    Vprintf("%10u%20ld%20.6f\n",i,vec[i].index,vec[i].data);
  Vprintf("Linked List Order:\n");
  Vprintf("   Matrix Index      Linked List Index      Data\n");
  address = base;
  while (address != NULL)
    {
      Vprintf("%10u%20ld%20.6f\n", (ptrdiff_t)(address-base),
              (*address).index, (*address).data);
      address = (*address).next;
    }
  /* 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)
    {
      Vprintf("Error from nag_chain_sort (m01cuc).\n%s\n", fail.message);
      exit_status = 1;
      goto END;
    }
  /* Output results */
  Vprintf("\nRESULTS\n\n");
  /* The order in the input matrix is unchanged */
  Vprintf("Matrix Order:\n");
  Vprintf("   Matrix Index      Linked List Index      Data\n");
  for (i=0; i<n; ++i)
    Vprintf("%10u%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 */
  Vprintf("Linked List Order:\n");
  Vprintf("   Matrix Index      Linked List Index      Data\n");
  address = base;
  while (address != NULL)
    {
      Vprintf("%10u%20ld%20.6f\n",
              (ptrdiff_t)(address-origbase), (*address).index, (*address).data);
      address = (*address).next;
    }
 END:
  if (vec) NAG_FREE(vec);
  return exit_status;
}