/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

#ifndef LIST_H__
#define LIST_H__ 1

/*--------------------*/

#include <string.h>

typedef char * Element;

#define eqElement(x,y) (strcmp((x),(y)) == 0)
#define geElement(x,y) (strcmp((x),(y)) >= 0)

/*--------------------*/

typedef struct Node *List;

struct Node
{
  List    next;		/* alignment within structs */
  Element info;		/* next is 1. field (!?) */
};


/*--------------------*/

#if MACROS

#define mkEmptyList() ((List)0)
#define isEmptyList(l) ((l) == (List)0)
#define head(l) ((l)->info)
#define tail(l) ((l)->next)

#else

extern List mkEmptyList(void);
extern int isEmptyList(List l);
extern Element head(List l);
extern List tail(List l);

#endif

/*--------------------*/

extern List cons(Element e, List l);

extern unsigned int length(List l);

extern Element at(List l,
                  unsigned int i);

extern int isInList(Element e, List l);

extern List insertElem(Element e,
                       List l);

extern List removeHead(List l);

extern List removeElem(Element e,
                       List l);

extern List removeAllElems(Element e,
                           List l);

extern List concat(List l1, List l2);

extern List append(List l, Element e);

extern List splitAt(List l,
		    unsigned int i,
		    List * rest);

extern List removeAt(List l,
		     unsigned int i);

extern List insertAt(List l,
		     unsigned int i,
		     Element e);

extern List Union(List l1, List l2);

/*--------------------*/

/* consistency check for sorted lists */

#if ! SORTED && DUPLICATES

#define invList(l) 1

#else

extern int invList(List l);

#endif

/*--------------------*/

/* space performance measurements */

extern unsigned spaceUsed(List l);

extern unsigned spaceNecc(List l);

extern double spaceOverhead(List l);

/*--------------------*/

#endif