lists.h

bi directional anchored/headed lists libraray

/* 
@inv:	(list->head != NULL) ^ (list->head->prev == NULL) ^ (list->tail->next == NULL)
	(list->head == NULL) ^ (list->tail == NULL)
*/
typedef void * TPointer;     /* a type of general pointer           */

struct SLink {               /* a stracture of link                 */
	TPointer data;
	struct SLink *prev;
	struct SLink *next;
};

typedef struct SLink TLink;  /* a type of link                      */
typedef TLink * PLink;       /* a type of pointer to link           */

struct SList {
	PLink head;
	PLink tail;
};
typedef struct SList TList;  /* a type of list                      */

typedef TList *PList ;       /* a type of pointer to list           */

/* comperator is a pointer to a function that compare two data's and returns a int */
/* 	comperator > 0		data1 > data2                       */
/*	comperator < 0		data1 < data2                       */
/*	comperator = 0		data1 = data2                       */
typedef int TComperator(const TPointer data1, const TPointer data2);
typedef TComperator * PComperator;
typedef TPointer TFunction(TPointer data);
typedef TFunction * PFunction;

/* creates & returns an empty list */ 
PList CreateList();
PList CreateListFromArray(TPointer array[], unsigned int size);
void DestroyLink(PLink link);
/* destroy a list previoslly create with CreateList() */
void DestroyList(PList list);

/* adds data to  the list as a last element in it */
void AddLast(PList list, TPointer data);
/* adds data to  the list as a first element in it */
void AddFirst(PList list, TPointer data);

/* returns a pointer to the link at index 'index', indexes are numbered 0..size-1 */
/* if index==size then returns NULL */
PLink GetLinkByIndex(PList list, int index);
/* returns a pointer to the first link that link->data == data */
/* if there is no such link returns NULL */
PLink GetLinkByData(PList list, TPointer data, PComperator comperator);
/* sets the element in index 'index' to be with data 'data' & returns the previose data */ 
PLink SetData(PList list, int index, TPointer data); 
/* insert data in the place PREV to index, if index == size then insert data at the end of the list => tail.data == data*/
void Insert(PList list, int index, TPointer data);
/* delete the last element in 'list' */
void DelLast(PList list);
/* delete the first element in 'list' */
void DelFirst(PList list);
/* deletes the element in the index 'index', if index is out of bound the nothing is done */
void DeleteByIndex(PList list, int index);
/* deletes the first element that its data = 'data' */
void DeleteByData(PList list, TPointer data, PComperator comperator);

/* appends list2-begin to list1-end. */
/* DO NOT preform any copy => list2.head point to somewhere in the appended list */
PList Append(PList list1, PList list2);
/* returns a copy of list, but DONOT copy the actual data */
PList Copy(PList list);
/* returns a copy of list, and copy the actual data too => duplicate the list */
PList CopyWithData(PList list);
/* traverse over the list and do something to each link->data*/
void Map(PList list, PFunction f);