list.c

linked list linked list tree struc

/*
 * Wei Cui
 * 981503
 * wec924 
 * Brian Gale
 * bmg002
 * 303473
 */
 
#include <stdio.h>
#include <list.h>


LIST listArray[LISTLEN];
NODE nodeArray[NODELEN];



LIST *ListCreate()
{
int listNo;
/*find next available list */
for (listNo=0; listNo<=LISTLEN; listNo++)
{
if ( !listArrayPtr[listNo] ) break;
}
    if (listNo >= LISTLEN )
    {
	printf("You have had %d lists, you can not creat any more!!\n", LISTLEN);
	return NULL;
    }
    else
    {
/*initialize it */
	    listArrayPtr[listNo] = &listArray[listNo];
	    listArrayPtr[listNo]->first_node = NULL;
	    listArrayPtr[listNo]->last_node = NULL;
	    listArrayPtr[listNo]->current_node = NULL;
    	    listArrayPtr[listNo]->counter = 0;
      	    listArrayPtr[listNo]->listindex = listNo;	
      	    return listArrayPtr[listNo];	
    }    
}


int __Add(LIST *mylist, void *nodeitem)
{
int nodeNo;
/*find next available node */
for (nodeNo=0; nodeNo<=NODELEN; nodeNo++)
{
if ( !nodeArrayPtr[nodeNo] )
{
break;
}
}
if ( nodeNo >= NODELEN )
{
return -1;
}
else
{
/*initialize it, and place it after the current node */
nodeArrayPtr[nodeNo] = &nodeArray[nodeNo];
nodeArrayPtr[nodeNo]->nodeindex = nodeNo;
nodeArrayPtr[nodeNo]->item = nodeitem;
nodeArrayPtr[nodeNo]->prev_node = mylist->current_node;
if ( mylist->current_node == NULL )                     /*the list is empty before insertion. */
/*Assume if any one of first, current or last node pointer is NULL, the list is empty */
{
nodeArrayPtr[nodeNo]->next_node = NULL;
mylist->current_node = nodeArrayPtr[nodeNo];
mylist->first_node = nodeArrayPtr[nodeNo];
mylist->last_node = nodeArrayPtr[nodeNo];
}
else
{
nodeArrayPtr[nodeNo]->next_node = mylist->current_node->next_node;
if ( mylist->current_node->next_node == NULL)
{
mylist->last_node = nodeArrayPtr[nodeNo];
}
else
{
mylist->current_node->next_node->prev_node = nodeArrayPtr[nodeNo];
}
mylist->current_node->next_node = nodeArrayPtr[nodeNo];
mylist->current_node = nodeArrayPtr[nodeNo];
}
mylist->counter++;
return 0;
}
}


int __Insert(LIST *mylist, void *nodeitem)
{
int nodeNo;
/*find next available node */
for (nodeNo=0; nodeNo<=NODELEN; nodeNo++)
{
if ( nodeArrayPtr[nodeNo] == NULL )
{
break;
}
}
if ( nodeNo > NODELEN )
{
return -1;
}
else
{
/*initialize it, and place it in front of the current node */
nodeArrayPtr[nodeNo] = &nodeArray[nodeNo];
nodeArrayPtr[nodeNo]->nodeindex = nodeNo;
nodeArrayPtr[nodeNo]->item = nodeitem;
nodeArrayPtr[nodeNo]->next_node = mylist->current_node;
if ( mylist->current_node == NULL )                   /*the list is empty before insertion. */
{
nodeArrayPtr[nodeNo]->prev_node = NULL;
mylist->current_node = nodeArrayPtr[nodeNo];
mylist->first_node = nodeArrayPtr[nodeNo];
mylist->last_node = nodeArrayPtr[nodeNo];
}
else
{
nodeArrayPtr[nodeNo]->prev_node = mylist->current_node->prev_node;
if ( mylist->current_node->prev_node == NULL)
{
mylist->first_node = nodeArrayPtr[nodeNo];
}
else
{
mylist->current_node->prev_node->next_node = nodeArrayPtr[nodeNo];
}
mylist->current_node->prev_node = nodeArrayPtr[nodeNo];
mylist->current_node = nodeArrayPtr[nodeNo];
}
mylist->counter++;
return 0;
}
}

int ListAdd(LIST *mylist, void *nodeitem)
{
return __Add(mylist, nodeitem);
}

int ListInsert(LIST *mylist, void *nodeitem)
{
return __Insert(mylist, nodeitem);
}

int ListAppend(LIST *mylist, void *nodeitem)
{
int callresult;
NODE *tempnode;
tempnode = mylist->current_node;
mylist->current_node = mylist->last_node;
callresult = __Add(mylist, nodeitem);
if ( callresult == -1 )
{
mylist->current_node = tempnode;       /*avoid side effect */
}
return callresult;
}


int ListPrepend(LIST *mylist, void *nodeitem)
{
int callresult;
NODE *tempnode;
tempnode = mylist->current_node;
mylist->current_node = mylist->first_node;
callresult = __Insert(mylist, nodeitem);
if ( callresult == -1 )
{
mylist->current_node = tempnode;       /*avoid side effect */
}
return callresult;
}


void ListConcat(LIST *list1, LIST *list2)
{
int listNo;
if ( list1->last_node == NULL )
{
list1->last_node = list2->last_node;
list1->first_node = list2->first_node;
list1->current_node = list2->first_node;
}
else
{
if ( list2->first_node != NULL )
{
list1->last_node->next_node = list2->first_node;
list2->first_node->prev_node = list1->last_node;
list1->last_node = list2->last_node;
}
}
list1->counter += list2->counter;
listNo = list2->listindex;
listArrayPtr[listNo] = NULL;
list2->first_node = NULL;
list2->last_node = NULL;
list2->current_node = NULL;
list2->counter = 0;                        /*list2 left empty */
}

void *__Curr(LIST *mylist)
{
if (mylist->current_node == NULL )
{ 
return NULL;
}
else
{
return mylist->current_node->item;
} 
}


void *ListCurr(LIST *mylist)
{
return __Curr(mylist);
}

int ListCount(LIST *mylist)
{
return mylist->counter;
}


void *ListFirst(LIST *mylist)
{
mylist->current_node = mylist->first_node;
return __Curr(mylist);
}


void *ListLast(LIST *mylist)
{
mylist->current_node = mylist->last_node;
return __Curr(mylist);
}


void *ListNext(LIST *mylist)
{
if ( mylist->current_node == mylist->last_node )
{
return NULL;
}
else
{
mylist->current_node = mylist->current_node->next_node;
return __Curr(mylist);
}
}


void *ListPrev(LIST *mylist)
{
if ( mylist->current_node == mylist->first_node )
{
return NULL;
}
else
{
mylist->current_node = mylist->current_node->prev_node;
return __Curr(mylist);
}
}


void *ListSearch(LIST *mylist, int Comparator(void *, void *), void *comparison)
{
int callresult;
if ( mylist->current_node == NULL )                      /*the list is empty. */
{
return NULL;
}
else
{
callresult = (*Comparator)(mylist->current_node->item, comparison);                 /*routine pointer call */

while ( !callresult && mylist->current_node->next_node )
{
mylist->current_node = mylist->current_node->next_node;
callresult = (*Comparator)(mylist->current_node->item, comparison);                 /*routine pointer call */   

}
if ( callresult == 1 )
{
return mylist->current_node->item;
}
else
{
return NULL;
}
}
}

void *__Remove(LIST *mylist)
{
void *temp;
int nodeNo;
if ( mylist->counter == 0 )                  /* mylist is empty. */
{
return NULL;
}
else
{
nodeNo = mylist->current_node->nodeindex;
nodeArrayPtr[nodeNo] = NULL;
temp = mylist->current_node->item;
if ( mylist->counter == 1 )                  /* mylist ihas only one node, end up empty. */
{
	mylist->first_node = NULL;
	mylist->current_node = NULL;
	mylist->last_node = NULL;
}
else
{
	if ( mylist->current_node == mylist->last_node )                  /* mylist has more than one node */
	{
		mylist->current_node->prev_node->next_node = NULL;
		mylist->last_node = mylist->current_node->prev_node;
		mylist->current_node = mylist->current_node->prev_node;
	}
	else
	{
		if ( mylist->current_node == mylist->first_node )
		{
			mylist->current_node->next_node->prev_node = NULL;
			mylist->first_node = mylist->current_node->next_node;
			mylist->current_node = mylist->current_node->next_node;
		}
		else
		{
			mylist->current_node->prev_node->next_node = mylist->current_node->next_node;
			mylist->current_node->next_node->prev_node = mylist->current_node->prev_node;
			mylist->current_node = mylist->current_node->next_node;
		}
	}
}
mylist->counter--;
return temp;
}
}

void *ListRemove(LIST *mylist)
{
return __Remove(mylist);
}

void ListFree(LIST *mylist, void itemFree(void *))
{
int nodeNo, listNo;
void *tempItem;
mylist->current_node = mylist->first_node;
while ( mylist->current_node != NULL )
{
tempItem = mylist->current_node->item;
(*itemFree)(tempItem);                     /* call the pointer routine to deal with each item. */
nodeNo = mylist->current_node->nodeindex;
nodeArrayPtr[nodeNo] = NULL;
mylist->current_node = mylist->current_node->next_node;
}
mylist->first_node = NULL;
mylist->last_node = NULL;
mylist->counter = 0;                       /* mylist left empty */
listNo = mylist->listindex;
listArrayPtr[listNo] = NULL;               /* but the space is available to be reused */
}


void *ListTrim(LIST *mylist)
{
mylist->current_node = mylist->last_node;
return __Remove(mylist);
}