/*

------------------------------------------------------------------------------

A license is hereby granted to reproduce this software source code and
to create executable versions from this source code for personal,
non-commercial use.  The copyright notice included with the software
must be maintained in all copies produced.

THIS PROGRAM IS PROVIDED "AS IS". THE AUTHOR PROVIDES NO WARRANTIES
WHATSOEVER, EXPRESSED OR IMPLIED, INCLUDING WARRANTIES OF
MERCHANTABILITY, TITLE, OR FITNESS FOR ANY PARTICULAR PURPOSE.  THE
AUTHOR DOES NOT WARRANT THAT USE OF THIS PROGRAM DOES NOT INFRINGE THE
INTELLECTUAL PROPERTY RIGHTS OF ANY THIRD PARTY IN ANY COUNTRY.

Copyright (c) 1995, John Conover, All Rights Reserved.

Comments and/or bug reports should be addressed to:

    john@johncon.com (John Conover)

------------------------------------------------------------------------------

qsortlist.c, quick sort a linked list

    a stable quick sort for linked lists

Tail recursion is used to limit recursion to ln (n) levels, which cuts
the number of recursive calls by a factor of 2. Sorting time will be
proportional to n ln (n).

Note: this algorithm uses double level indirection-modifications must
be made with meticulous care.

The algorithm is as follows (the pivot is the dividing line between
high and low sub lists in a sub list):

   append each item in the beginning of a sub list to the high or low
   sub list, (at the completion of this loop, the low sub list has
   already been linked into the calling context at the beginning of
   the sub list)

   the pivot element is appended after the low sub list, and the end
   of the high sublist is then linked into the calling context sub
   list

   the beginning of the high sub list is finally appended after the
   pivot

Note: although the re linking must be done in this order, the order of
sorting the sub lists is not critical.

Usage is to typedef LIST as the structure element to be sorted, and
the token "list" as a reference to a LIST type of element, for
example:

typedef struct my_struct
{
    .
    .
    .
    int count;
    struct my_struct *next;
} MYSTRUCT;

typedef MYSTRUCT LIST;

typedef LIST *list;

where the tokens "LIST" and "list" are used internal to qsortlist
module.

Additionally, the structure element must have an integer element,
"count," (in this example case, which is the sort key-but could
conceivably be any type, or token name,) and a reference element to
the next structure in the list, with a token name of "next," which is
used internal to the qsortlist module.

It is also necessary to include a comparison utility, either by
#define or function, that can compare the key elements in two list
elements. For example:

#define element_comp(x,y) (x)->count - (y)->count

The comparison utility must have the token name "element_comp," which
is used internal to the qsortlist module, and has the same return
value operations as strcmp(2), ie., if the first argument is lexically
larger, the return should be positive, and if it is smaller, it should
be negative, and if equal, zero is returned. Reverse the scenario for
a reverse sort on lexical order.

For a detailed description of quicksorting linked lists, see
"Quicksorting Linked Lists," Jeff Taylor, "C Gazette," Volume 5,
Number 6, October/November, 1991, ISSN 0897-4055, P.O. Box 70167,
Eugene, OR 97401-0110. Published by Oakley Publishing Company, 150
N. 4th Street, Springfield, OR 97477-5454.

The first argument references the first element in the linked list,
the second argument is null for linear linked lists, or references the
final element in a circularly linked list. The sort is stable, meaning
that elements with the same key value will remain in the same relative
order after the sorting process.

Returns nothing, but the linked list's next elements are rearranged
such that the list elements are in sorted order on the key.

To test this module, compile the module source with -DTEST_QSORTLIST

$Revision: 1.0 $
$Date: 1995/04/22 05:13:18 $
$Id: qsortlist.c,v 1.0 1995/04/22 05:13:18 john Exp $
$Log: qsortlist.c,v $
 * Revision 1.0  1995/04/22  05:13:18  john
 * Initial revision
 *

*/

#include "rel.h"

#ifndef LINT /* include rcsid only if not running lint */

static char rcsid[] = "$Id: qsortlist.c,v 1.0 1995/04/22 05:13:18 john Exp $"; /* module version */
static char rcsid_h[] = QSORTLIST_H_ID; /* module include version */

#endif

#ifdef __STDC__

void qsortlist (list *top, list bottom)

#else

void qsortlist (top, bottom)
    list *top;
    list bottom;

#endif

{
    int n; /* sub list's length, greater than 0 means high sub list is larger, less than 0 means lower sub list is larger */

    list *high, /* reference to top of sub list */
         high_list, /* reference to top of list */
         *low, /* reference to bottom of sub list */
         pivot, /* reference to pivot element for list sub division */
         previous; /* reference to previous element to pivot element */

    while (*top != bottom) /* starting at the top of the list, when the end of the list is reached, this recursion is finished */
    {
        previous = pivot = *top; /* save the top of the list */
        low = top; /* save the reference to the top of the list */
        high = &high_list; /* reference the high list */
        n = 0; /* sub list has no length */

        while ((previous = previous->next) != bottom) /* scan the list to find the partition-this is the pivot value */
        {

            if (element_comp (previous, pivot) <= 0) /* compare this element's value with the value in the pivot */
            {
                *low = previous; /* if it less than or equal, the low value references this element */
                low = &previous->next; /* and the low value references the next element in the list */
                n--; /* decrement the sub list's length */
            }

            else
            {
                *high = previous; /* if it is higher, the high value references this element */
                high = &previous->next; /* and the high value references the next element in the list */
                n++; /* increment the sub list's length */
            }

        }

        *low = pivot; /* reassemble with pivot between parts, reference the pivot element */
        *high = bottom; /* reference the end of the list */
        pivot->next = high_list; /* the pivot element's list references the top of the list */

        if (n > 0) /* sort sublists-always sort the larger sub list: is the high part is larger? */
        {
            qsortlist (top, pivot); /* yes, recurse on lower part */
            top = &pivot->next; /* and the top of the list references the element past the pivot element */
        }

        else
        {
            qsortlist (&pivot->next, bottom); /* no, recurse on high part */
            bottom = pivot; /* and the end of the list references the pivot */
        }

    }

}

#ifdef TEST_QSORTLIST

/*

simple exerciser for testing qsortlist (); sort the numbers listed on
the command line, and print the sorted numbers to stdout; ignore the:

declared global, could be static
    qsortlist           qsortlist.c(xxx)

from lint

*/

#ifdef __STDC__

int main (int argc, char *argv[])

#else

int main (argc, argv)
    int argc;
    char *argv[];

#endif

{
    list mylist, /* the list to be sorted */
         ref; /* temporary reference to list element */

    if (argc < 2) /* enough arguments? */
    {
        (void) printf ("usage: arg arg arg ...\n"); /* no, print the usage */
        exit (1); /* and exit */
    }

    mylist = (list) 0; /* null the list reference */

    for (argc--; argc > 0; argc--) /* for each argument on the command line */
    {

        if ((ref = (LIST *) malloc (sizeof (LIST))) == (LIST *) 0) /* allocate a list element */
        {
            (void) fprintf (stderr, "error allocating memory\n"); /* couldn't allocate the list element, print the error */
            exit (1); /* and exit */
        }

        ref->count = atoi (argv[argc]); /* store the key element value */
        ref->next = mylist; /* add the element to the list */
        mylist = ref; /* new list head */
    }

    qsortlist (&mylist, (list) 0); /* sort the list */

    for (ref = mylist; ref; ref = ref->next) /* for each element on the list */
    {
        (void) printf ("%d\n", ref->count); /* print the element's key value */
    }

    exit (0); /* success */

#ifdef LINT /* include only if running lint */

    return (0); /* for LINT formality */

#endif

}

#endif