#include "linklist.h"

//Implementation file for abstract data type LinkList.

LinkList::LinkList()
//Default constructor.
{
  Head = NULL;
  Prev = NULL;
  Cursor = NULL;
  Rear = NULL;
  Size = 0;
}

LinkList::~LinkList()
//Default destructor.
{
  ListElement* OldHead;

  //walk down list and return nodes to heap
  while(Head != NULL)
  {
    OldHead = Head;
    Head = Head->Successor;
    delete(OldHead);
  }
  Prev = NULL;
  Size = 0;
}

int LinkList::GetSize()
//Returns number of elements in current list.
{
  return(Size);
}

int LinkList::IsEmpty()
//Returns True is list is empty; otherwise returns False.
{
  return(Size == 0);
}

void LinkList::InitCursor()
//Sets Cursor to point to first list element.
//Pre : List is defined and non-empty.
//Post: Cursor set to first list element and Prev set to NULL,
//      since first list element has no predecessor.
{
  Cursor = Head;
  Prev = NULL;
}

int LinkList::AtEnd()
//Returns True if Cursor is NULL or is pointing to the last
//list element; otherwise returns False.
{
  int EndList;

  if(Cursor == NULL)        //empty list
    EndList = True;
  else if (Cursor->Successor == NULL)
    EndList = True;
  else
    EndList = False;

  return(EndList);
}

void LinkList::Advance()
//Advances Cursor to next list element.
//Pre : Object initialized.
//Post: Cursor set to next list element, Prev points to
//      former Cursor position.
{
  if(Cursor != NULL)
  {
    Prev = Cursor;                //save Cursor value
    Cursor = Cursor->Successor;   //advance Cursor position
  }
}

void LinkList::Retrieve(ListData &El, int &Success)
//Retrieves linked list element pointed to by Cursor.
//Pre : Linked list is initialized.
//Post: Returns through El the list element pointed to by
//      Cursor and sets Success to True or sets Success to
//      False if Cursor is NULL.
{
  if(Cursor == NULL)
    Success = False;
  else
  {
    El = Cursor->ListInfo;    //copy list element data to El
    Success = True;
  }
}

void LinkList::Traverse(FcnType Visit)
//Applies function Visit to each list element in sequence
//starting with the first.
//Pre : Linked list is initialized and function Visit is
//      declared in client program.
//Post: Visit has been applied to each list element.
{
  ListElement* Next;           //pointer to next list element

  Next = Head;                 //start with first element
  while(Next != NULL)
  {
    Visit(Next->ListInfo);     //apply Vist to lists element
    Next = Next->Successor;    //advance to next list element
  }
}

void LinkList::InsertAfter(ListData El)
//Inserts El as information portion of new list element which
//is the successor to the node pointed to by Cursor.
//Pre : List is initialized and El defined.
//Post: Advances Cursor to new list element and sets Prev to
//      former Cursor value.  If Cursor is NULL, El is inserted
//      as first list element, points Cursor to it, and sets
//      Prev to NULL. Increments Size.
{
  ListElement* RestOfList;        //sublist after insertion point

  if (Cursor == NULL)
    {
      Head = new ListElement;     //allocate first list element
      Cursor = Head;              //point Cursor to it
      RestOfList = Head;
    }
  else
    {
      //save position of new element successor
      RestOfList = Cursor->Successor;
      //link new list element to current element
      Cursor->Successor = new ListElement;
      Prev = Cursor;                      //save Cursor position
      Cursor = Cursor->Successor;         //point to new element
    }

  Cursor->ListInfo = El;           //copy El to new element
  Cursor->Successor = RestOfList;  //link it to rest of list
  Size++;

  if (AtEnd())        //update Rear if new element at end
    Rear = Cursor;
}

void LinkList::Insert(ListData El)
//Inserts El as information portion of new list element which
//is pointed to by Cursor.
//Pre : List is initialized and El defined.
//Post: Element formerly pointed to by Cursor is successor to
//      new list element, Cursor pointes to new element. If Head
//      is NULL or Head == Cursor; El is inserted as first list
//      element, sets Cursor to point to it. Increments Size.
{
  if (Cursor == Head)
    {                               //insert new head
     Head = new ListElement;        //connect new element to Head
     Head->Successor = Cursor;      //connect it to rest of list
     Cursor = Head;                 //reset Cursor
    }
  else
    {
      //insert between Prev and Cursor
      //allocate new node and connect to predecessor
      Prev->Successor = new ListElement;
      //link new element to rest of list
      Prev->Successor->Successor = Cursor;
      //reset Cursor
      Cursor = Prev->Successor;
    }

  Cursor->ListInfo = El;
  Size++;

  if (AtEnd())           //update Rear if new node at end
    Rear = Cursor;
}

void LinkList::InsertAtEnd(ListData El)
//Inserts El as information portion of new list element which
//is pointed to by Rear.
//Pre : List is initialized and El is defined.
//Post: Advances Cursor to new list element and sets Prev to
//      former Rear value. If Rear is NULL, El is inserted
//      as the only list element and points Head, Cursor, and
//      Rear to it, sets Prev to NULL. Increments Size.
{
  if (Head == NULL)               //test for empty list
    {
     Head = new ListElement;      //connect new element to Head
     Head->Successor = NULL;
     Cursor = Head;               //reset Cursor
    }
  else
    {
      //insert after last node
      Prev = Rear;
      //allocate new node and connect to predecessor
      Rear->Successor = new ListElement;
      //mark last element as end of list
      Rear->Successor->Successor = NULL;
      //reset Cursor
      Cursor = Prev->Successor;
    }

  Cursor->ListInfo = El;
  Size++;
  Rear = Cursor;          //set Rear to point to new last node
}

void LinkList::DoSearch(ListData El,
			ListElement *ListHead,
			int &Success)
//Helper function, called by Search to perform actual search.
//Pre : List initialized, El defined, ListHead points to same
//      node as Cursor.
//Post: Returns True if element at head of sublist pointed to by
//      ListHead matches El, points Cursor to it, sets Prev to
//      its predecessor. Returns False is search fails or list
//      is empty.
{
  if (ListHead == NULL)
    //empty sublist
    Success = False;
  else if (ListHead->ListInfo.IsEqual(El))
    //element in node pointed to by ListHead
    Success = True;
  else if (ListHead->Successor == NULL)
    //one element sublist - no further match possible
    Success = False;
  else
    {
     //search remainder of list
     Advance();
     DoSearch(El, Cursor, Success);
    }
}

void LinkList::Search(ListData El, int &Success)
//Searches list for element matching El using ListData.IsEqual.
//Pre : List initialized and El defined.
//Post: If found, Success is set to True, Cursor points to
//      matching list element, Prev points to predecessor;
//      otherwise Sucess is set to False.
{
  //start search at list head
  InitCursor();
  DoSearch(El, Cursor, Success);
}


void LinkList::DeleteNode()
//Deletes the list element pointed to by Cursor.
//Pre : List object initialized.
//Post: Resets Cursor to point to deleted element's successor
//      and returns its storage space to the heap. If list is
//      empty, no element is deleted.
{
  ListElement *ToBeDeleted;    //item to be deleted

  if (Size != 0)               //non-empty list
    {
     if (Cursor == Head)       //first element
       {
	 //save position of node to delete
	 ToBeDeleted = Head;
	 //advance Cursor to next position
	 Cursor = Cursor->Successor;
	 //make Head point to new first node
	 Head = Cursor;
       }
     else
       {
	 //connect predecessor to rest of list
	 Prev->Successor = Cursor->Successor;
	 //save position of Node to delete
	 ToBeDeleted = Cursor;
	 //advance Cursor to next list element
	 Cursor = Cursor->Successor;
       }

      delete(ToBeDeleted);        //dispose deleted node
      Size--;

      if (Cursor == NULL)  //update Rear is last node deleted
	Rear = Prev;
    }
}