// Lab Problem 6.1 (repeat of Problem 5.2)

// CS211 ADS2

// T Naughton, CS NUIM

// Last updated 31 Mar 2000

#include<iostream>



/*

** This program maintains a linked list of integers. Functionality

** includes:

** -prompting the user for a list of numbers

** -adding a node at the beginning of the list

** -adding a node at the end of the list

** -printing the contents of the list

** -checking if a given integer is in the list

** -deleting the entire list

** -counting the number of elements in the list

**

** These are the new ones:

** -delete a given integer from the list

** -print out the list in reverse order

*/



class ListElement {

  // A very simple class describing each node of the list

 public:

  int element;

  ListElement * next;

};



class IntList {



 public:

  IntList(); // constructor

  ~IntList(); // destructor



  // methods that act on IntList

  void FillList();

  void AddtoFront(int newdata);

  void AddtoBack(int newdata);

  void PrintList();

  bool Contains(int element);

  void DeleteList();

  int Count();

  void RemoveElement(int element);

  void PrintListReverseRec(ListElement * current);

  ListElement * GetHeadPtr();



 private:

  ListElement * head; // a pointer to the head of the list



};



IntList::IntList(){

  head = NULL; // Initialise the list (mark the end of the list

               // with NULL).

}



IntList::~IntList(){

  DeleteList(); // Clean up when finished with the variable

}



void IntList::FillList(){

  // This method reads positive integers, one per line, from the

  // keyboard. The user indicates that they are finished

  // by entering any negative integer (the negative integer itself is

  // not stored).

  int tempint; // temporary storage for ints from user



  cout << endl << endl << "Please enter positive integers (one ";

  cout << "per line). Terminate with any negative integer:" << endl;



  cin >> tempint;

  while (tempint >= 0) {

    AddtoBack(tempint);

    cin >> tempint;

  }

}



void IntList::AddtoFront(int newdata){

  // This method creates a new node with the data that is passed to

  // it, adding the node to the front of the list.

  ListElement * temp;      // Create a pointer to a new node

  temp = new ListElement;  // Allocate memory for the node

  temp->element = newdata; // Put the data in the node



  // Put this node at the top of the list by (a) pointing it at the

  // head of the list and (b) repointing the head of the list at this

  // node.

  // Can you see that the first time we add a node to the list

  // (i.e. when head==NULL) that we end up marking the end of the

  // list with a NULL?

  temp->next = head;

  head = temp;

}



void IntList::AddtoBack(int newdata){

  // This method creates a new node with the data that is passed to

  // it, adding the node to the end of the list.

  ListElement * current;   // node pointer to find end of list

  ListElement * temp;      // pointer for the new node



  temp = new ListElement;  // allocate memory for the new node

  temp->element = newdata; // put data in

  temp->next = NULL;

  // This node will be placed at the end of the list, so set its

  // next pointer to NULL.



  // If the list is empty we do not want to try to traverse the

  // list (because checking current->next when current is NULL

  // will cause a runtime error).

  if (head == NULL) {



    head = temp; // set head to point to the new node



  } else {

    // Otherwise we want current to point to the last node in

    // the list.

    current = head;

    while (current->next != NULL) {

      current = current->next;

    }

    // current now points to the last node in the list

    current->next = temp;

  }

}



void IntList::PrintList(){

  // This method prints out the list. It does so by printing out the

  // contents of the head of the list and then each subsequent element

  // in turn. It repeats this until the end of the

  // list (a NULL) is found. The function returns a pointer to the

  // head of the list. Note: this function will work if an empty

  // list is passed to it.

  ListElement * current;



  cout << endl << "List: ";

  current = head; // set current to point to the head of the list

  while (current != NULL) {

    cout << current->element << ' ';

    current = current->next;

  }

}



bool IntList::Contains(int element){

  // Return true if element is in the list, false if not.

  ListElement * current;

  bool found;



  current = head;

  found = false;

  while ((current != NULL) && !found) {

    if (current->element == element) {

      found = true;

    }

    current = current->next;

  }

  return found;

}



void IntList::DeleteList(){

  // Delete the entire list

  ListElement * temp; // pointer to element to be deleted



  while (head != NULL) {

    temp = head;

    head = head->next;

    delete temp;

  }

  // head will have been set to NULL when loop terminates.

}



int IntList::Count(){

  // Count the number of nodes in the list

  ListElement * current;

  int total;



  total = 0;

  current = head;

  while (current != NULL) {

    total++;

    current = current->next;

  }

  return total;

}



void IntList::RemoveElement(int element){

  // Remove any elements in list that have the key 'element'.

  // This means that after deleting an element the program must

  // search the remainder of the list for more elements with the

  // same key.

  // There are four cases to take account of here:

  // i) The list is empty

  // ii) The element is at the head of the list

  // iii) The element is in the middle of the list

  // iv) The element is at the end of the list

  // In our method, we have three algorithms, one for the first

  // case, one for the second case, and one to take care of the

  // last two cases.

  ListElement * current; // used to traverse the list

  ListElement * temp; // used to mark a node for deletion

  bool keepgoing;



  current = head;

  if (current == NULL) {

    // do nothing



  } else {

    // delete all contiguous occurances of element at the

    // beginning of the list

    keepgoing = (current->element == element);

    while (keepgoing) {

      // delete head of the list

      head = current->next;

      delete current;

      current = head;

      // if not NULL compare current->element again

      if (current != NULL) {

        keepgoing = (current->element == element);

      } else {

        keepgoing = false;

      }

    }

  }

  if (current != NULL) { // make sure not at end of list



    // at this point we are guaranteed that current is not NULL

    // and does not point to an element we would want to delete

    while (current->next != NULL) {

      if (current->next->element == element) {

        // delete current->next node

        temp = current->next;

        current->next = current->next->next;

        delete temp;



      } else {

        // Because removing a node implicitly advances current->next

        // we will only advance if we do not remove a node

        current = current->next;



        // Putting this in an 'else' serves two purposes. Firstly,

        // if we advance after removing an element we will skip

        // our test of the next element, thereby failing to remove

        // multiples next to each other. Secondly, if we have just

        // deleted the last element of the list then advancing

        // current will cause a runtime error when we check the

        // condition of the while loop above.

      }

    }

  }

}



void IntList::PrintListReverseRec(ListElement * current){

  // This method prints out the list in reverse order. It does so by

  // employing a nice effect in recursion. We recursively seek the

  // end of the list and on the way out of the multiple recursive

  // calls we print the list elements. As always, we want our function

  // to work if an empty list is passed to it.

  if (current != NULL) {

    PrintListReverseRec(current->next);

    cout << current->element << ' ';

  } else {

    cout << endl << "List in reverse: ";

  }

}



ListElement * IntList::GetHeadPtr(){

  // Return a pointer to the head of the list (which is private)

  return head;

}



void main(void){



  /*

  ** Call the methods here to test them.

  */



  IntList list;

  int tempint;



  list.FillList();

  list.PrintList();



  tempint = 1;

  cout << endl << "Adding " << tempint << " at front...";

  list.AddtoFront(tempint);

  list.PrintList();



  tempint = 99;

  cout << endl << "Adding " << tempint << " at back...";

  list.AddtoBack(tempint);

  list.PrintList();



  tempint = 5;

  cout << endl << tempint << " is ";

  if (!list.Contains(tempint)) {

    cout << "not ";

  }

  cout << "in the list.";



  tempint = 24;

  cout << endl << tempint << " is ";

  if (!list.Contains(tempint)) {

    cout << "not ";

  }

  cout << "in the list.";



  cout << endl << "There are " << list.Count() << " elements.";



  list.AddtoFront(77);

  list.AddtoFront(88);

  list.PrintList();

  cout << endl << "There are " << list.Count() << " elements.";



  list.PrintListReverseRec(list.GetHeadPtr());



  cout << "Removing 88...";

  list.RemoveElement(88);

  list.PrintList();



  cout << "Removing 5...";

  list.RemoveElement(5);

  list.PrintList();



  cout << "Removing 99...";

  list.RemoveElement(99);

  list.PrintList();



  cout << "Deleting entire list...";

  list.DeleteList();

  list.PrintList();

  cout << endl << "There are " << list.Count() << " elements.";



  cout << "Attempting to delete '4'...";

  list.RemoveElement(4);

  cout << endl << "There are " << list.Count() << " elements.";



  cout << "Adding 7...";

  list.AddtoBack(7);

  list.PrintList();

  cout << endl << "There are " << list.Count() << " elements.";



}