/*
 *				f x a d d o . c
 */

/*)LIBRARY
*/

#ifdef	DOCUMENTATION

title	fxaddo	Add Ordered To a Flex
index		Add ordered to a flex
index		Locate last element added ordered to a flex

synopsis

	 #ifdef	vms
	 #include "c:flex.h"
	 #else
	 #include <flex.h>
	 #endif

	 FLEX *fxaddo(fx,itm,ord)
	 FLEX *fx;
	 char *itm;
	 int (*ord)();

	 extern unsigned fxladd;

description

	fxaddo is similar to fxadd except that it ensures that the items in
	the flex are in increasing order, where "in order" is defined by a
	passed function, ord.  ord must return values akin to strcmp:
	ord(a,b) is -1 if a<b, 0 if a=b, and 1 if a>b.  Elements that compare
	equal will be stored in the order they are passed.

	The global fxladd gets the item number at which itm was added.

	WARNING:  fxaddo() uses straight insertion to maintain the ordering.
	This is an O(n**2) algorithm and will become very slow when the flex
	gets large.  If you need to build a large, sorted flex, it is probably
	best to fill it first and then use something like qqsort() to sort it
	when you are done.  (Another approach, more in keeping with the
	philosophy of fxaddo(), would be to define, say, fxaddh(), which keeps
	the flex ordered as a heap, and then scan through it as a heap.  I
	leave this to someone else.) 

	Note:  If for some reason you don't want to include equal elements,
	you can safely issue an error message in ord() and use, for example,
	setjmp() and longjmp() to abort the insertion.  This process will
	leave the flex unchanged.  Alternatively, set a flag and use fxladd to
	eject the item later.

bugs

author

	Jerry Leichter
#endif

/*
 * )EDITLEVEL=16
 * Edit history
 * 0.0  5-May-81 JSL	Invention
 * 1.0  6-May-81 JSL	Completely re-done using fxinject(); added fxladd.
 * 1.1  7-May-81 JSL	Define fxinject() locally as flex.h no longer does.
 * 1.2 20-May-81 JSL	Documentation now standard and up-to-date.
 * 1.3 14-Jul-81 JSL	flex.h again defines fxinject().
 */

#ifdef	vms
#include "c:flex.h"
#else
#include <flex.h>
#endif
#define NULL 0

unsigned fxladd;		/* Where this routine stored an item */

FLEX *
fxaddo(fx,itm,ord)
FLEX *fx;
char *itm;
int (*ord)();
{	register char *p,*data;
	register unsigned isz;

	if (fx == NULL || fx->fxdata == NULL)
		return(NULL);

	isz = fx->fxisz;
	data = fx->fxdata;
	p = data + isz*(fx->fxused - 1);
	while (p >= data && (*ord)(p,itm) > 0)
		p -= isz;

	return(fxinject(fx,itm,(fxladd = (p-data+isz)/isz)));
}