/*
** sptree.h:  The following type declarations provide the binary tree
**  representation of event-sets or priority queues needed by splay trees
**
**  assumes that data and datb will be provided by the application
**  to hold all application specific information
**
**  assumes that key will be provided by the application, comparable
**  with the compare function applied to the addresses of two keys.
*/

# ifndef SPTREE_H
# define SPTREE_H

# ifndef NULL
# define NULL	0
# endif

# define STRCMP( a, b ) ( (Sct = *(a) - *(b)) ? Sct : strcmp( (a), (b) ) )

typedef struct _spblk SPBLK;

typedef struct _spblk
{
    SPBLK	* leftlink;
    SPBLK	* rightlink;
    SPBLK	* uplink;

    char	* key;		/* formerly time/timetyp */
    char	* data;		/* formerly aux/auxtype */
    char	* datb;
};

typedef struct
{
    SPBLK	* root;		/* root node */

    /* Statistics, not strictly necessary, but handy for tuning  */

    int		lookups;	/* number of splookup()s */
    int		lkpcmps;	/* number of lookup comparisons */
    
    int		enqs;		/* number of spenq()s */
    int		enqcmps;	/* compares in spenq */
    
    int		splays;
    int		splayloops;

} SPTREE;


/* sptree.c */
extern SPTREE * spinit();	/* init tree */
extern int spempty();		/* is tree empty? */
extern SPBLK * spenq();		/* insert item into the tree */
extern SPBLK * spdeq();		/* return and remove lowest item in subtree */
extern SPBLK * spenqprior();	/* insert before items with same key */
extern void splay();		/* reorganize tree */

/* spaux.c */
extern SPBLK * sphead();	/* return first node in tree */
extern void spdelete();		/* delete node from tree */
extern SPBLK * spnext();	/* return next node in tree */
extern SPBLK * spprev();	/* return previous node in tree */
extern SPBLK * spenqbefore();	/* enqueue before existing node */
extern SPBLK * spenqafter();	/* enqueue after existing node */

/* spdaveb.c */
extern SPBLK * splookup();	/* find key in a tree */
extern SPBLK * spinstall();	/* enter an item, allocating or replacing */
extern SPBLK * sptail();	/* find end of a tree */
extern void spscan();		/* scan forward through tree */
extern void sprscan();		/* reverse scan through tree */
extern SPBLK * spfnext();	/* fast non-splaying next */
extern SPBLK * spfprev();	/* fast non-splaying prev */

# endif