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

#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)
{
  struct recd vec[20];
  struct recd *base, *origbase, *address;
  size_t i, j, l[20], n;
  ptrdiff_t ptroffset;
  static NagError fail;

  ptroffset = (ptrdiff_t) (((char *) &(vec->next)) - ((char *) vec));
  g05cbc((Integer)0);
  n = 10;
  /* Set data field to random number between 0 and 5 */
  for (i=0; i<n; ++i)
    vec[i].data = (double) g05dyc((Integer)0,(Integer)5);
  /* Randomly set index fields from 0 to 9*/
  for (i=0; i<n; ++i)
    {
      j = (int)((i+1)*g05cac());
      /* 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("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("%10ld%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("%10ld%20ld%20.6f\n", (ptrdiff_t)(address-base),
              (*address).index, (*address).data);
      address = (*address).next;
    }
  /* Sort the linked list on the data field */
  fail.print= TRUE;
  m01cuc((Pointer *)&base, ptroffset, compare, Nag_Ascending, &fail);
  if (fail.code != NE_NOERROR)
    return EXIT_FAILURE;
  /* 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("%10ld%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("%10ld%20ld%20.6f\n", (ptrdiff_t)(address-origbase), (*address).index,
              (*address).data);
      address = (*address).next;
    }
  return EXIT_SUCCESS;
}