/*----------------------------------------------------------------------
  File    : listops.c
  Contents: some special list operations
  Author  : Christian Borgelt
  History : 2000.11.02 file created from file lists.h
----------------------------------------------------------------------*/
#include <stdio.h>
#include "listops.h"

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/

void* l_sort (void *list, LCMPFN cmpfn, void *data)
{                               /* --- sort a list with mergesort */
  LE *src, *dst;                /* list of source/destination lists */
  LE **end;                     /* end of list of destination lists */
  LE *in1, *in2;                /* input lists for merging */
  LE **out;                     /* output list for merging */

  if (!list) return list;       /* check for an empty list */
  for (src = list; src->succ; ) {
    dst = src; src = src->succ; /* traverse the list and split it */
    dst->succ = NULL;           /* into a list (abused pred ptr.) of */ 
  }                             /* single element lists (succ ptr.) */
  while (src->pred) {           /* while more than one source list */
    end = &dst;                 /* start list of destination lists */
    do {                        /* merge pairs of source lists */
      out = end;                /* start output list (merged input) */
      in1 = src;                /* remove two (one) source list(s) */
      in2 = src->pred;          /* and use them as input for merging */
      if (!in2) {               /* if there is only one source list */
        *end = in1; end = &in1->pred;
        break;                  /* append it to the list of */
      }                         /* output list and abort the loop */
      src = in2->pred;          /* remove lists from list of sources */
      while (1) {               /* source lists merge loop */
        if (cmpfn(in1, in2, data) < 0) {
                                /* if first list's element is smaller */
          *out = in1;           /* move element to output list, */
          out  = &(in1->succ);  /* advance output pointer and */ 
          in1  = in1->succ;     /* remove element from input list */
          if (!in1) break; }    /* if the list gets empty, abort loop */
        else {                  /* if second list's element is smaller */
          *out = in2;           /* move element to output list, */
          out  = &(in2->succ);  /* advance output pointer and */
          in2  = in2->succ;     /* remove element from input list */
          if (!in2) break;      /* if the list gets empty, abort loop */
        }                       /* (merge input lists into one) */
      }
      if (in1) *out = in1;      /* append remaining elements */
      else     *out = in2;      /* to the output list */
      end = &(*end)->pred;      /* advance destination list pointer */
    } while (src);              /* while there is another source list */
    *end = NULL;                /* terminate destination list */
    src  = dst;                 /* transfer destination list */
  }                             /* to source list and start over */
  for (src->pred = NULL; src->succ; src = src->succ)
    src->succ->pred = src;      /* set predecessor pointers */
  return dst;                   /* return a pointer to the first */
}  /* l_sort() */               /* element of the sorted list */

/*--------------------------------------------------------------------*/

void* l_reverse (void *list)
{                               /* --- reverse a list */
  LE *le = NULL;                /* to traverse the list elements */

  while (list) {                /* while the list is not empty */
    le       = list;            /* get the next list element */
    list     = le->succ;        /* exchange the successor */
    le->succ = le->pred;        /* and the predecessor */
    le->pred = list;            /* of the list element */
  }
  return le;                    /* return a pointer to */
}  /* l_reverse() */            /* the new first element */