lists.c

bi directional anchored/headed lists libraray

#include <stdlib.h>
#include "Lists.h"

PList CreateList() {
	PList pl = (PList) malloc(sizeof(PList));
	pl->head = NULL;
	pl->tail = NULL;
	return pl;
}

void DestroyLink(PLink link) {
	free(link);
}

void DestroyList(PList list) {
	PLink link = list->head;
	PLink temp;
	while (link!=NULL) {
		temp = link;
		link = link->next;
		DestroyLink(temp);
	}
	free(list);
}

void AddLast(PList list, TPointer data) {
	PLink link = (PLink) malloc(sizeof(TLink));
	link->data = data;
	
	link->prev = list->tail;
	if (list->tail == NULL)  /* first link in the list -> update head */
		list->head = link;
	else
		list->tail->next = link;
	
	list->tail = link;
	list->tail->next = NULL;
}

void AddFirst(PList list, TPointer data) {
	PLink link = (PLink) malloc(sizeof(TLink));
	link->data = data;
	
	link->next = list->head;
	if (list->head == NULL)   /* first link in the list -> update tail */
		list->tail = link;
	else 
		list->head->prev = link;
	
	list->head = link;
	list->head->prev = NULL;
}

PList CreateListFromArray(TPointer array[], unsigned int size) {
	unsigned int i;
	PList list = CreateList();
	for (i=0; i<size; i++) {
		AddLast(list, array[i]);
	}
	return list;
}

/* 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) {
	PLink link;
	int i;
	
	for (i = 0, link = list->head; i<index && link->next != NULL; i++, link = link->next) {
	}
	if (i == index) return link; else return link->next;
}

/* 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) {
	PLink link;
	
	for (link = list->head; (comperator(data, link->data)!=0) && (link->next!=NULL); link = link->next) {
	}
	if (comperator(data, link->data)==0) return link; else return link->next;	
}

/* sets the element in index 'index' to be with data 'data' & returns the previose data */ 
PLink SetData(PList list, int index, TPointer data) {
	PLink  link = GetLinkByIndex(list, index);
	TPointer prev_data = link->data;
	
	link->data = data;
	return prev_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) {
	PLink next = GetLinkByIndex(list, index);
	PLink prev;
	PLink link = (PLink) malloc(sizeof(TLink));
	
	if (next == NULL) prev = list->tail; else prev = next->prev;
	
	link->data = data;
	link->next = next;
	link->prev = prev;
	
	if (next == NULL) /*next==tail*/
		list->tail = link;
	else
		next->prev = link;
	if (prev == NULL)  /*prev==head*/
		list->head = link;
	else
		prev->next = link;
}

/* delete the last element in 'list' */
void DelLast(PList list) {
	PLink link;
	if (list->tail == NULL) return;
	
	link = list->tail;
	list->tail = list->tail->prev;
	if (link->prev == NULL)
		list->head = NULL;
	else
		list->tail->next = NULL;
	DestroyLink(link);
}

/* delete the first element in 'list' */
void DelFirst(PList list) {
	PLink link;
	if (list->head == NULL) return;
	
	link = list->head;
	list->head = list->head->next;
	if (link->next == NULL)
		list->tail = NULL;
	else
		list->head->prev = NULL;
	DestroyLink(link);
}

/* deletes the element in the index 'index', if index is out of bound the nothing is done */
void DeleteByIndex(PList list, int index) {
	PLink link = GetLinkByIndex(list, index);
	PLink prev, next;
	
	if (link == NULL) return;
		
	prev = link->prev;
	next = link->next;
	
	/* prev == NULL => link == head */
	if (prev == NULL) list->head = next; else prev->next = next;
	/* next == NULL => link == tail */
	if (next == NULL) list->tail = prev; else next->prev = prev;
	
	free(link);
}

/* deletes the first element that its data = 'data' */
void DeleteByData(PList list, TPointer data, PComperator comperator) {
	PLink link = GetLinkByData(list, data, comperator);
	PLink prev, next;
	
	if (link == NULL) return;
		
	prev = link->prev;
	next = link->next;
	
	/* prev == NULL => link == head */
	if (prev == NULL) list->head = next; else prev->next = next;
	/* next == NULL => link == tail */
	if (next == NULL) list->tail = prev; else next->prev = prev;
	
	free(link);	
}

/* 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) {
	list1->tail->next = list2->head;
	list2->head->prev = list1->tail;
	
	list1->tail = list2->tail;
	return list1;
}

/* returns a copy of list, but DONOT copy the actual data */
PList Copy(PList list) {
	PList result = NULL;
	PLink link;
	
	if (list == NULL) return result;
	
	result = CreateList();
	for (link=list->head; link!=NULL; link=link->next) {
		AddLast(result, link->data);
	}
	return result;
}

/* returns a copy of list, and copy the actual data too => duplicate the list */
PList CopyWithData(PList list) {
	PList result = NULL;
	PLink link;
	TPointer p;
	
	if (list == NULL) return result;
	
	result = CreateList();
	for (link=list->head; link!=NULL; link=link->next) {
		p = malloc(sizeof(*(link->data)));
		*((char *)p) = *((char *)(link->data)); /*using casting to char*/
		
		AddLast(result, p);
	}
	return result;
}

/* traverse over the list and do something to each link->data*/
void Map(PList list, PFunction f) {
	PLink link;
	
	for (link = list->head; link!=NULL; link = link->next) {
		link->data = f(link->data);
	}
}