// Lab Problem 5.1

// CS211 ADS2

// T Naughton, CS NUIM

#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

*/



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();



 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) {

    this->AddtoBack(tempint);

    // 'this' is a built-in pointer that refers to the IntList object

    // that called FillList(), i.e. 'list' declared in main()

    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 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.";



  list.DeleteList();

  list.PrintList();

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



  list.AddtoFront(77);

  list.AddtoFront(88);

  list.PrintList();

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



}