/******************************************************************************

    MODULE
	DLL.h

    DESCRIPTION
	Header File for ``Double Linked Lists''

    NOTES
	Okay - okay, such functions are also built
	into the Kickstart, but this is a more
	consistent interface, I hope ...

	We always have the concerned list as first argument
	(also, if knowledge of the list is ignored inside the
	function ...)

    HISTORY
	13-11-94 b_noll created

******************************************************************************/

#ifndef DLL_H
#define DLL_H 1

/**************************************
	    Includes
**************************************/

#ifndef   EXEC_TYPES_H
#include <exec/types.h>
#endif /* EXEC_TYPES_H */

/**************************************
	    Defines & Structures
**************************************/

struct DNode {
    struct DNode *Succ;
    struct DNode *Pred;
}; /* struct DNode */

struct DList {
    struct DNode *Head;
    struct DNode *Tail;
    struct DNode *TailPred;
}; /* struct DList */

/**************************************
	    Prototypes
**************************************/

/* ---- Movement */

extern struct DNode *DLL_GetHead (struct DList *l);
extern struct DNode *DLL_GetTail (struct DList *l);
extern struct DNode *DLL_GetSucc (struct DList *l, struct DNode *n);
extern struct DNode *DLL_GetPred (struct DList *l, struct DNode *n);

#define DLL_GetHead(l)                  ((APTR)     \
	(((struct DList *)(l))->Head->Succ ?        \
		((struct DList *)(l))->Head : NULL ))
#define DLL_GetTail(l)                  ((APTR)     \
	(((struct DList *)(l))->TailPred->Succ ?    \
		((struct DList *)(l))->TailPred : NULL ))
#define DLL_GetPred(l,n)                ((APTR)     \
	(((struct DNode *)(n))->Pred->Pred ?        \
		((struct DNode *)(n))->Pred : NULL ))
#define DLL_GetSucc(l,n)                ((APTR)     \
	(((struct DNode *)(n))->Succ->Succ ?        \
		((struct DNode *)(n))->Succ : NULL ))


/* ---- Construction and destruction */

extern void DLL_Init	   (struct DList *l);

extern void DLL_AddHead     (struct DList *l, struct DNode *n);
extern void DLL_AddTail     (struct DList *l, struct DNode *n);
extern void DLL_AddInfront  (struct DList *l, struct DNode *n, struct DNode *pos);
extern void DLL_AddBehind   (struct DList *l, struct DNode *n, struct DNode *pos);

extern void	     DLL_Remove     (struct DList *l, struct DNode *n);
extern struct DNode *DLL_RemHead    (struct DList *l);
extern struct DNode *DLL_RemTail    (struct DList *l);

/* ---- Searching and scanning	*/

extern void	     DLL_Scan (struct DList *l, void (*scan)(struct DNode *, void *, int), void *userdata);
extern struct DNode *DLL_Find (struct DList *l, int  (*find)(struct DNode *, void *, int), void *userdata);

/* ---- Indexing */

extern int	     DLL_Length    (struct DList *l);
extern struct DNode *DLL_NumToNode (struct DList *l, int num);
extern int	     DLL_NodeToNum (struct DList *l, struct DNode *n);

/* ---- BONUS: More complex structures */

extern void DLL_Sort		(struct DList *l, int (*comp)(struct DNode *, struct DNode *));
extern void DLL_Filter		(struct DList *l, struct DList *dest, int (*check)(struct DNode *, void *), void *ud);
extern void DLL_Join		(struct DList *dest, struct DList *add);
extern void DLL_AddSorted	(struct DList *l, struct DNode *n, int (*comp)(struct DNode *, struct DNode *, void *), void *ud);

#endif /* !DLL_H */

/******************************************************************************
*****  END DLL.h
******************************************************************************/