#include "a:list.h"


 //initilizes a list with header node
void CreateList(List *list)
{   *list=(ListNode *)malloc(sizeof(ListNode)); //creates the header node

    if (*list != NULL)
        (*list)->next=NULL;
}

//destroys all the nodes in a list, including the header node
void ClearList(List *list)
{  ListNode *p;
   while ( *list != NULL)
   {  p=*list;
      *list = (*list)->next;
      free(p);
   }
}
      
//retuen true if the list is empty -- contains only the header node
BOOLEAN EmptyList(List *list)
{ if ((*list)->next == NULL)
       return TRUE;
   else
       return FALSE;
}

//retuens true if the list is full -- there is no memory on the heap
BOOLEAN FullList(void)
{ ListNode *p;
   if ((p = malloc(sizeof(ListNode))) == NULL)
       return (TRUE);
   else 
   {  free(p);
      return (FALSE);
   }
}

//returns current as pointer to the node with key as target if found, else return NULL
void FindNode(List *list,KeyType target,NodePointer *previous, NodePointer *current)
{  *previous=*list;
   *current=(*list)->next;

   while((*current!=NULL)&&(*current)->entry.key<target)
   { *previous= *current; 
     *current=(*current)->next;
   }


   if ((*current!=NULL)&&(*current)->entry.key!=target)
       *current=NULL;
}

//deletes a node with the target key if found
void Delete(KeyType target, List *list)
{   ListNode *current, *previous;
    
    FindNode(list, target, &previous, &current);

   if (!current == NULL)  //the item is found
   {   previous->next = current->next;
        free(current);
   }
}

//inserts a new node with item as newitem at the correct position
void Insert(ItemType newitem, List *list)
{   ListNode *newnode, *previous, *ignore;
    
   newnode=(ListNode *)malloc(sizeof(ListNode));


   if (!newnode == NULL)
   {    newnode->entry=newitem;

        //link the new node to the list
        FindNode(list, newitem.key,&previous,&ignore);
        newnode->next = previous->next;
        previous->next = newnode;
   }
}

//visits each node in the list and process it -- except the header node
void Traverse(List *list)
 {
    ListNode *p=(*list)->next;
    while (p != NULL)
    { printf("%d ",p->entry.key);  //This depends on the application.  
      p=p->next;
    }
 }


 //returns pointer to the node whose key is same as target if found, NULL otherwise
NodePointer SearchList(List *list,KeyType target)
{   ListNode *current, *previous;
    
    FindNode(list, target, &previous, &current);

    return current;
}