/**
 *  Titus Winters 
 *  CS 14 - Fall 03 
 *  Lab 1 Sample Solution
 */
#include <iostream>

using namespace std;

class Node
{
public:
  int val;
  Node* next;
};

////////////////////////////////////////////////
// Predeclarations
void printList(Node* head);
unsigned int size(Node* head);
Node* insert(Node* head, int pos, int toInsert);
Node* removeVal(Node* head, int valToDelete);
Node* addToEnd(Node* head, int valToAdd);

int main()
{
  // "Allocate three nodes a, b, c on the heap using new"
  Node* a = new Node;
  Node* b = new Node;
  Node* c = new Node;

  // We use the -> operator instead of . because we have a pointer.
  a->val = 3;
  b->val = 8;

  // -> is the same as this.  -> is much cleaner.
  (*c).val = 10;

  // Make Node a point to b.  Note that B is a Node*, a->next is a Node*,
  // we don't need to dereference anything or take the address of anything.
  // (Just checking types will get you far in programming in C++)
  a->next = b;
  
  // These are actually redudant, the pointers default to NULL for objects
  // anyway.
  b->next = NULL;
  c->next = NULL;  

  cout << "A is ";
  printList(a);

  cout << "The size of a is " << size(a) << endl;

  cout << "Inserting 15 at the beginning of a" << endl;
  a = insert(a, 0, 15);
  printList(a);
  
  cout << "Inserting 20 in the middle of a" << endl;
  a = insert(a, 2, 20);
  printList(a);

  cout << "Inserting 30 at the end of a twice" << endl;
  a = addToEnd(a, 30);
  a = addToEnd(a, 30);
  printList(a);

  cout << "Inserting 30 at the head of a" << endl;
  a = insert(a, 0, 30);
  printList(a);

  cout << "Removing 30 from a" << endl;
  a = removeVal(a, 30);
  printList(a);
  
  
}

void printList(Node* head)
{
  // Doing this recursively, because I'm lazy.  The simple case: the list
  // is empty.
  if (head == NULL) return;

  // If the list wasn't empty, print out the first element.
  cout << head->val << endl;

  // Print out the rest of the list.  Since the rest of the list is
  // smaller than all of the list, this moves us closer to the base-case,
  // and thus the recursion will be successful.
  printList(head->next);
}

unsigned int size(Node* head)
{
  int counter = 0;

  // Not recursive this time, just to show how a simple loop works
  while (head != NULL)
    {
      // It is good practice to use pre-increment instead of post-increment
      // whenever possible.
      ++counter;
      
      // Advance to the next Node.  If this is the end of the list, the 
      // value will be NULL and the loop will terminate
      head = head->next;
    }

  // Return the number of nodes that we found
  return counter;
}

Node* insert(Node* head, int pos, int toInsert)
{
  // Base case #1: we want to insert at the head of the list
  if (pos == 0)
    {
      // Create a new node
      Node* newNode = new Node;
      newNode->val = toInsert;

      // Make it point to the old head of the list
      newNode->next = head;

      // Return it as the new head of the list
      return newNode;
    }

  // If the list is empty, just return the empty list (this means that
  // the insertion failed.  Later on we'll cover exceptions and this
  // would be a good place to throw an exception.)
  if (head == NULL) return head;

  // The only tricky part: insert the value somewhere in the rest of the list.
  head->next = insert(head->next, pos - 1, toInsert);
  
  return head;
}

Node* removeVal(Node* head, int valToDelete)
{
  // Base case 1: the list is empty, we are done
  if (head == NULL) return NULL;

  // If we need to remove the value, remove it
  if (head->val == valToDelete)
    {
      Node* temp = head->next;
      delete head;
      return removeVal(temp, valToDelete);
    }
  
  // Otherwise, remove the value from the rest of the list
  head->next = removeVal(head->next, valToDelete);
  
  return head;
}

// If we already have insert working, this is fairly simple. 
// Not the most efficient code that we could write (it makes 2 
// passes through the list), but still O(n).
Node* addToEnd(Node* head, int valToAdd)
{
  return insert(head, size(head), valToAdd);
}