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

    MODULE
	SLL.c

    DESCRIPTION
	Type SLL - Single Linked List

	This module is used to simplify work with some Intuition
	structures like Windows, Menus, MenuItems, Gadgets ...

    HISTORY
	30-10-94 b_noll created
	14-11-94 b_noll cleaned up using SList/SNode
	$Log: SLL.c $

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

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

#ifndef   SLL_H
#include <SLL.h>
#endif /* SLL_H */

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

#define Prototype extern
#undef	SLL_GetHead
#undef	SLL_GetTail
#undef	SLL_GetSucc
#undef	SLL_GetPred
#undef	SLL_Init

/**************************************
	     Implementation
**************************************/

Prototype void SLL_Init (struct SList *l);
void SLL_Init (struct SList *l) {
    l->Head = NULL;
} /* SLL_Init */
#define SLL_Init(l) (l)->Head=NULL

Prototype struct SNode *SLL_GetHead (struct SList *l);
struct SNode *SLL_GetHead (struct SList *l) {
    return l->Head;
} /* SLL_GetHead */
#define SLL_GetHead(l) ((l)->Head)

Prototype struct SNode *SLL_GetSucc (struct SList *l, struct SNode *n);
struct SNode *SLL_GetSucc (struct SList *l, struct SNode *n) {
    return n->Succ;
} /* SLL_GetSucc */
#define SLL_GetSucc(l,n) ((n)->Succ)

Prototype struct SNode *SLL_GetPred (struct SList *l, struct SNode *n);
struct SNode *SLL_GetPred (struct SList *l, struct SNode *n) {
    struct SNode *m, *p;
    if (!(p = SLL_GetHead(l)) || (p == n))
	return NULL;
    while ((m = SLL_GetSucc(l,p)) && (m != n))
	p = m;
    return (m == n)? p: NULL;
} /* SLL_GetPred */

Prototype struct SNode *SLL_GetTail (struct SList *l);
struct SNode *SLL_GetTail (struct SList *l) {
    return SLL_GetPred(l,NULL);
} /* SLL_GetTail */
#define SLL_GetTail(l) SLL_GetPred(l,NULL)

Prototype struct SNode * SLL_NumToNode (struct SList *l, int i);
struct SNode * SLL_NumToNode (struct SList *l, int i) {
    struct SNode *n;
    for (n = SLL_GetHead(l); n && i--; n = SLL_GetSucc(l,n));
    return n;
} /* SLL_NumToNode */

Prototype int SLL_NodeToNum (struct SList *l, struct SNode *n);
int SLL_NodeToNum (struct SList *l, struct SNode *n) {
    struct SNode *m;
    int 	  i;
    for (i = 0, m = SLL_GetHead(l); m && (m != n); ++i, m = SLL_GetSucc(l,m));
    return (m == n)? i: NULL;
} /* SLL_NodeToNum */

Prototype int SLL_Length (struct SList *l);
int SLL_Length (struct SList *l) {
    return SLL_NodeToNum(l, NULL);
} /* SLL_Length */

Prototype struct SNode *SLL_RemHead (struct SList *l);
struct SNode *SLL_RemHead (struct SList *l) {
    struct SNode *n;
    if ((n = SLL_GetHead(l))) {
	SLL_Remove(l,n);
    } /* if */
    return n;
} /* SLL_RemHead */

Prototype struct SNode *SLL_RemTail (struct SList *l);
struct SNode *SLL_RemTail (struct SList *l) {
    struct SNode *n;
    if ((n = SLL_GetTail(l))) {
	SLL_Remove(l,n);
    } /* if */
    return n;
} /* SLL_RemTail */

/* ---- SLL Internal - append an entry to another */

static void _SLL__AddAfter (struct SNode *new, struct SNode *pos) {
    new->Succ = pos->Succ;
    pos->Succ = new;
} /* SLL_AddAfter */

/* ---- Append an entry at the end of a SLL */

Prototype void SLL_AddTail (struct SList *l, struct SNode *n);
void SLL_AddTail (struct SList *l, struct SNode *n) {
    struct SNode *p;
    if ((p = SLL_GetTail(l)))
	_SLL__AddAfter(  n,p);
    else
	SLL_AddHead(l,n);
} /* SLL_AddTail */

/* ---- Add a new entry at the head of a SLL */

Prototype void SLL_AddHead (struct SList *l, struct SNode *n);
void SLL_AddHead (struct SList *l, struct SNode *n) {
    _SLL__AddAfter(  n,(struct SNode *)l);
} /* SLL_AddHead */

/* ---- Add a new entry into a SLL in front of a given entry */


Prototype void SLL_AddInfront (struct SList *l, struct SNode *n, struct SNode *pos);
void SLL_AddInfront (struct SList *l, struct SNode *n, struct SNode *pos) {
    struct SNode *p;
    if ((p = SLL_GetPred(l,pos)))
	_SLL__AddAfter(  n,p);
    else
	SLL_AddHead(l,n);
} /* SLL_AddInfront */

/* ---- Add a new entry into a SLL behind a given entry */

Prototype void SLL_AddBehind (struct SList *l, struct SNode *n, struct SNode *pos);
void SLL_AddBehind (struct SList *l, struct SNode *n, struct SNode *pos) {
    _SLL__AddAfter(  n,pos);
} /* SLL_AddBehind */

/* ---- Find an entry in a SLL */

Prototype struct SNode *SLL_Find (struct SList *l, int (*find)(void *, APTR, int), APTR userdata);
struct SNode *SLL_Find (struct SList *l, int (*find)(void *, APTR, int), APTR userdata) {
    struct SNode *n;
    int 	  i = 0;
    for  (n = SLL_GetHead(l); n; n = SLL_GetSucc(l,n))
	if (!(*find) (n, userdata, i++))
	    return n;
    return NULL;
} /* SLL_Find */

/* ---- Step through all entries of a SLL (may be used to delete) */

Prototype void SLL_Scan (struct SList *l, void (*scan) (void *, APTR, int), APTR userdata);
void SLL_Scan (struct SList *l, void (*scan) (void *, APTR, int), APTR userdata) {
    struct SNode *n, *nn;
    int 	  i = 0;
    for (nn = SLL_GetHead(l); (n = nn); nn = SLL_GetSucc(l,nn))
	(*scan) (n, userdata, i++);
} /* SLL_Scan */

/* ---- Remove an entry from a SLL */

BOOL SLL_Remove (struct SList *l, struct SNode *n) {
    struct SNode *m, *p;
    for (p = (void *)l; m = SLL_GetSucc(l,p); p = m)
	if (m == n) {
	    p->Succ = n->Succ;
	    n->Succ = NULL;
	    return TRUE;
	} /* if */
    return FALSE;
} /* SLL_Remove */





/* cleaned up up to here ... at 14-11-94 */



#if 0

/* ---- Create a node, if it does not yet exist in a SLL */

Prototype void *SLL_Find_or_Append (void *sll, int (*find)(void*, ULONG), void *(Create)(ULONG), ULONG userdata);
void *SLL_Find_or_Append (SLL *sll, int (*find)(void*, ULONG), void *(Create)(ULONG), ULONG userdata) {
    void *inter;
    inter = SLL_Find (sll, find, userdata);
    if (!inter) {
	inter = (*Create) (userdata);
	if (inter)
	    SLL_AddTail (sll, inter);
    } /* if */
    return inter;
} /* SLL_Find_or_Append */

/* ---- Delete an entry in a SLL */

Prototype void SLL_Delete (void *sll, void *remove, void (*delete)(void *, ULONG), ULONG userdata);
void SLL_Delete (SLL *sll, void *remove, void (*delete)(void *, ULONG), ULONG userdata) {
    SLL_Remove (sll, remove);
    (*delete) (remove, userdata);
} /* SLL_Delete */

Prototype BOOL SLL_Find_and_Delete (void *sll, int (*find)(void *, ULONG), void (*delete)(void *, ULONG), ULONG userdata);
BOOL SLL_Find_and_Delete (SLL *sll, int (*find)(void *, ULONG), void (*delete)(void *, ULONG), ULONG userdata) {
    void *inter;
    if ((inter = SLL_Find (sll, find, userdata)) {
	SLL_Remove (sll, inter);
	(*delete) (inter, userdata);
	return TRUE;
    } /* if */
    return FALSE;
} /* SLL_Find_and_Delete */

#endif

/******************************************************************************
*****  END SLL.c
******************************************************************************/