#ifndef MPLIB1_LMSORT
#define MPLIB1_LMSORT
/*
*  Header file for lmsort

*  Optimal list-merge sorting algorithm with exponential merge schedule.
*
*  From: Software Development International, Winter 1991.
*  
*  This implementation by Jeremy Harris jgh@imptld.com
*
*  Adapted into toolkit by Martin Poole mpoole@cix.compulink.co.uk
*  
**
** WARNING !!  WARNING !! WARNING !! WARNING !! WARNING !! WARNING !!
**
** Any changes to be made to this file should first be checked with
** mplib1 source control for library integrity.
**
** mplib1 source control can be reached at  mplib1@quatermass.co.uk
** 
* $Source$
* $Author$
* $Date$
* $Revision$
*
* $Log$
*
*******************************************************************************
*/

#ident "$Header$"

#ifdef CXREF
#include <sys/types.h>
#endif

/* ------------------------------------------------------------------
    defines
   ------------------------------------------------------------------ */

/* ------------------------------------------------------------------
    structures
   ------------------------------------------------------------------ */

struct lmsortp
{
    struct lmsortp *	next;
    void *		dp;
};


typedef int lmsortp_t (const void *, const void *);


/* ------------------------------------------------------------------
    function definitions
   ------------------------------------------------------------------ */

extern struct lmsortp *
lmsort( struct lmsortp * start, lmsortp_t compar );

extern struct lmsortp *
lmsort_init( void* base, size_t nel, size_t width, struct lmsortp *dp );

extern void
lmsort_end( struct lmsortp *dp );


/*****  How to use these routines. *****

    Consider how an array of elements would typically be sorted using qsort()


	struct some_struct them[ARRAY_SIZE];
	int t;

	qsort(  &them[0],
		ARRAY_SIZE,
		sizeof(struct some_struct),
		some_struct_comparison_function );

	for ( t=0; t<ARRAY_SIZE; t++ )
	    some_struct_print_function( &some_struct[t] );
    

    qsort works by shuffling the values around as determined by the
    comparison function.  This has the disadvantage of transferring a lot
    of data, which is probably an unnecessary and large overhead if the
    only use for the data is to print some part of it.

    The lmsort routines behave differently because they do not shuffle
    the data itself, only a linked list of pointers to the data.
    To sort the above array using lmsort you need two extra variables, and
    a pair of extra calls.

	struct some_struct them[ARRAY_SIZE];
	struct lmsortp *lp1, *lp2;

	lp1 = lmsort_init(  &them[0],
			    ARRAY_SIZE,
			    sizeof(struct some_struct),
			    NULL );
	lp2 = lmsort( lp1, some_struct_comparison_function );

	while (lp2)
	{
	    some_struct_print_function( lp2->dp );
	    lp2 = lp2->next;
	};

	lmsort_end( lp1 );

    The three functions perform the following actions.
	lmsort_init - This routine allocates an array of lmsortp structures
	    and initialises the data pointers and link chain.
	lmsort - This routine performs the sort, and returns a pointer to
	    the first lmsortp structure. Note that the value returned is not
	    necessarily the same as the supplied parameter.
	lmsort_end - This routine simply frees up the array allocated by the
	    call to lmsort_init.

    It is not a requirement to use the _init and _end functions. If your
    data structure has a sub-structure that is a struct lmsortp then all that
    is required is that the ->next list is initialised ( with a NULL pointer
    on the last item), and that the data pointers are set.

*/

#endif
/* -- End of File -- */