#include "stdstuff.h"
#include "List.h"

// private copy method used by copy constructor and operator=
// creates a duplicate of the given linked list
void List::copy (const List &otherList) {
  Node *c, *tail, *n;

  // so far the list we're creating does not have a last node
  tail = head = NULL;

  // for all nodes in the other stack's list
  for (c = otherList.head; c != NULL; c = c -> next) {
    // create a copy of the node
    n = new Node(c -> data, NULL);
    // make the last node in the list being created point to it
    if (tail == NULL) { // no last node yet
      head = n; // new node goes at the start of the list
    } else {
      tail -> next = n;
    }
    // our new node is now the last node
    tail = n;
  }
}

// private deleteAll method used by destructor and operator=
// deletes nodes, one at a time
void List::deleteAll () {

 Node *t;
  while (head != NULL) {
     t = head; 
     head = head -> next; 
     delete t;
  }

}


// copy constructor just copies list
List::List (const List &otherList) {

  copy(otherList);

}


// the destructor deletes all nodes
List::~List () {

  deleteAll();

}


// prints the list to cout one node at a time, starting with the head
void List::outputList () const {
  
  Node *c = head;
  int i = 0;

  cout << "The list contains:" << endl;

  while (c != NULL) {
    cout << "  " << c -> data;
    if (++i == 10) {
      cout << endl; i = 0;
    }
    c = c -> next;
  }
  if (i != 0) cout << endl;

}


// inserts a node into the list at the head of the list
void List::insert (int data) {

  head = new Node (data, head);

}

// assigns one linked list to another
List& List::operator= (const List &otherList) {

  deleteAll ();  // nix the linked list for the object being assigned to
  copy (otherList);  // copy the other list
  return *this;  // as always for operator=, so a=b=c works

}

// Method countLessThan(n) returns the number of values in the given list that are less than n.  
// Note that "less than" refers to the contents (value) of the node *not* its position in the list.   
// If there are no values greater than n, this method returns 0.
// This method does *not* change the list.
int List::countLessThan(int n) const {
   return subCountLessThan(n,head);
}

// recursive sub-method to count the number of values less than n
int List::subCountLessThan(int n, Node* subHead) const {

   if (subHead==NULL) return 0; // empty list has no values < n

   // if this value is less than n, count it, plus of the number of values less than n in the rest of the list
   if (subHead->data < n) return 1 + subCountLessThan(n,subHead->next);

   // otherwise return the number of values less than n in the rest of the list
   return subCountLessThan(n,subHead->next);
}


// Method hasValueGreaterEqual(m) returns true if the list contains a value greater than or equal to m, false otherwise.  
// Note that "greater than or equal to" refers to the contents (value) of the node *not* its position in the list.  
// If there are no values in the list, this method returns false.
// This method does *not* change the list.
bool List::hasValueGreaterEqual(int m) const {
   return subHasValueGreaterEqual(m,head);
}

// recursive sub-method to see if the list contains a value greater than or equal to m.  
bool List::subHasValueGreaterEqual(int m, Node* subHead) const {

   if (subHead==NULL) return false; // empty list has no values greater than or equal to m

   if (subHead->data >= m) return true; // found a value >= m

   // otherwise list has a value great than or equal to m if the rest of the list has a value greater than or equal to m
   return subHasValueGreaterEqual(m,subHead->next);
}


// Method hasOneThirdValuePrior() returns true if the list contains a node directly preceded by a node containing
// one third of the value of the first node, and false otherwise.
// If there are no values in the list, this method returns false.
// This method does *not* change the list.
bool List::hasOneThirdValuePrior() const {
   return subHasOneThirdValuePrior(head);
}

// recursive sub-method to see if the list contains a node directly preceded by a node containing
// one third the value of the first node.
bool List::subHasOneThirdValuePrior(Node* subHead) const {

   // empty list or list with one value has no node preceded by 1/3 its value
   if (subHead==NULL || subHead->next==NULL) return false; 

   // if second value is three times the first one, return true
   if (subHead->data*3 == subHead->next->data) return true;

   // otherwise list has a node preceded by 1/3 its value only if that occurs in the rest of the list
   return subHasOneThirdValuePrior(subHead->next);
}