// Lab Sheet 8 Example A (Some recursive methods)

// CS211 ADS2

// T Naughton, CS NUIM

#include<iostream>



/* This program contains recursive methods in a class to manage a

** linked list of integers

*/



class ListElement {

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

 public:

  int data;

  ListElement * next;

};



class IntList {



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



 public:

  IntList(); // constructor

  ~IntList(); // destructor

  ListElement * GetHead();

  void SetHead(ListElement * ptr);



  // methods that act on IntList (wrapper methods that take

  // care of special cases or extra tasks before calling the

  // private recursive methods that do the real work)

  void AddtoBack(int newdata);

  void PrintList();

  void DeleteList();

  bool Contains(int value);



 private:

  // recursive implementations of the tasks

  void AddtoBackRec(ListElement * current, int newdata);

  void PrintListRec(ListElement * current);

  void DeleteListRec(ListElement * current);

  bool ContainsRec(ListElement * current, int value);

};



IntList::IntList() {

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

               // with NULL)

}



IntList::~IntList() {

  DeleteList();

}



ListElement * IntList::GetHead(){

  return head;

}



void IntList::SetHead(ListElement * ptr){

  head = ptr;

}



void IntList::AddtoBack(int newdata){

  // Wrapper method for adding a node at the end of the list.

  // Takes account of the special case where head==NULL before

  // calling the recursive method

  ListElement * temp;



  if (GetHead() == NULL) {

    temp = new ListElement;

    temp->data = newdata;

    temp->next = NULL;

    SetHead(temp);



  } else {

    AddtoBackRec(GetHead(), newdata);

  }

}



void IntList::AddtoBackRec(ListElement * current, int newdata){

  // Recursive method to add a node at the end of the list.

  // A wrapper method ensures that current is not NULL

  ListElement * temp;



  if (current->next == NULL) {

    temp = new ListElement;

    temp->data = newdata;

    temp->next = NULL;

    current->next = temp;



  } else {

    AddtoBackRec(current->next, newdata);

  }

}



void IntList::PrintList(){

  // Wrapper method to print out a list

  cout << endl << "List contents:";

  PrintListRec(GetHead());

}



void IntList::PrintListRec(ListElement * current){

  // Recursive method to print out a list

  if (current != NULL) {

    cout << current->data << ' ';

    PrintListRec(current->next);

  }

}



void IntList::DeleteList(){

  // Wrapper method to delete a list.

  // Although all memory (including that at the head of the list) will

  // be deallocated correctly, we should also point the head pointer

  // away from this memory location. This means we can safely add new

  // nodes after deleting the list

  DeleteListRec(GetHead());

  SetHead(NULL);

}



void IntList::DeleteListRec(ListElement * current){

  // Recursive method to delete a list. Deletes nodes from the tail

  // to the head

  if (current != NULL) {

    DeleteListRec(current->next);

    delete current;

  }

}



bool IntList::Contains(int value){

  // Wrapper method to check for an int in the list. Does nothing

  // extra, but means the user does not have to explicitly pass the

  // head of the list when calling this method

  return ContainsRec(GetHead(), value);

}



bool IntList::ContainsRec(ListElement * current, int value){

  // Recursive method to check if a value is in a list

  if (current == NULL) {

    return false;

  } else if (current->data == value) {

    return true;

  } else {

    return ContainsRec(current->next, value);

  }

}



void main(void){



  IntList list;



  cout << endl << endl << "Here we go:";



  list.AddtoBack(4);

  list.AddtoBack(5);

  list.AddtoBack(2);



  list.PrintList();



  cout << endl << "5 is ";

  if (!list.Contains(5)) {

    cout << "not ";

  }

  cout << "in the list.";



  cout << endl << "9 is ";

  if (!list.Contains(9)) {

    cout << "not ";

  }

  cout << "in the list.";



  list.DeleteList();



  list.PrintList();



  list.AddtoBack(8);

  list.AddtoBack(9);



  list.PrintList();

}