// ---------------------------------------------------------------------------
// SimpleLinkedList.h
//
// A generic linked list class.  (There is already a list class in the 
// Standard C++ Library; this class is just an illustration of how such a
// class is written from scratch!)
// ---------------------------------------------------------------------------

#ifndef _SIMPLE_LINKED_LIST_H
#define _SIMPLE_LINKED_LIST_H

#include <stdexcept>
using namespace std;

// A list object is represented as a doubly-linked ring of nodes.  One
// header (or "dummy") node always exists, so that insertion and removal
// can be implemented consistently whether or not it is taking place
// at the middle or the ends.

template<class T>
class List {

// A private local class for the nodes that are linked together.
private:
  class Node {
  public:
    Node* previous;
    T data;
    Node* next;
    Node(Node* previous, T data, Node* next): 
      previous(previous), data(data), next(next) {
    }
  };

// The list itself is just a pointer to the dummy header node.
private:
  Node* header;
  int size;

// Constructors and Destructors
public:

  // Constructs a new EMPTY list.  The empty list is represented as one
  // containing only the header.
  List(): header(new Node(0, T(), 0)), size(0) {
    header->previous = header;
    header->next = header;
  }

  // The copy constructor!
  List(const List& other): header(new Node(0, T(), 0)), size(other.size) {
    header->previous = header;
    header->next = header;
    for (Node* n = other.header->next; n != other.header; n = n->next) {
      Node* newNode = new Node(header->previous, n->data, header);
      newNode->previous->next = newNode;
      newNode->next->previous = newNode;
    }
  }
  
  // Deletes all the nodes.  TODO: THIS IS AN INEFFICIENT so it should be
  // rewritten.
  ~List() {
    destroy();
    delete header;
  }

// Behavior
public:

  // Returns the number of items in the list.
  int getSize() {
    return size;
  }

  // Returns whether the list is empty.
  bool isEmpty() {
    return size == 0;
  }

  // Adds an item so that it has position index.  The index positions start
  // at zero.  If the index argument is not in the range 0..size then an
  // out_of_range is thrown.
  void add(int index, T item) {
    addBefore(item, (index == size ? header : nodeAt(index)));
  }

  // Removes the item at position index.  Throws an out_of_range if the
  // index is not in the range 0..size-1.
  void remove(int index) {
    remove(nodeAt(index));
  }

  // Returns the index of the first occurence of the given item, or -1
  // if not found.
  int indexOf(T item) {
    int index = 0;
    for (Node* n = header->next; n != header; n = n->next) {
      if (n->data == item) {
        return index;
      }
      index++;
    }
    return -1;
  }
  
  // Retrieve the item at the given index.
  T get(int index) {
    return nodeAt(index)->data;
  }
  
  // Update the item at the given index.
  void set(int index, T item) {
    nodeAt(index)->data = item;
  }
  
  // Assignment Operator
  List& operator=(const List& other) {
    if (&other == this) {
      return *this;
    }
    destroy();
    size = other.size;
    for (Node* n = other.header->next; n != other.header; n = n->next) {
      Node* newNode = new Node(header->previous, n->data, header);
      newNode->previous->next = newNode;
      newNode->next->previous = newNode;
    }
    return *this;
  }
  
  // Returns whether this list has the same size, and values in the
  // same positions, as another.
  bool operator==(const List& other) {
    if (size != other.size) {
      return false;
    }
    Node* n1 = header->next;
    Node* n2 = other.header->next;
    while (n1 != header && n2 != other.header) {
      if (n1->data != n2->data) {
        return false;
      }
      n1 = n1->next;
      n2 = n2->next;
    }
    return true;
  }
  
// Helpers
private:

  // Deletes all the nodes in this list except the header.
  void destroy() {
    while (!isEmpty()) {
      remove(0);
    }
  }
  
  // Return a pointer to the node at the given index position.
  Node* nodeAt(int index) {
    if (index < 0 || index > size) {
      throw out_of_range("Invalid list position");
    }
    Node* n = header;
    for (int i = 0; i <= index; i++) {
      n = n->next;
    }
    return n;
  }
  
  // Add a new node containing the given value before the node
  // pointed to by n.
  void addBefore(T item, Node* n) {
    Node* newNode = new Node(n->previous, item, n);
    newNode->previous->next = newNode;
    newNode->next->previous = newNode;
    size++;
  }
  
  // Remove the node pointed to by n.
  void remove(Node* n) {
    if (n == 0 || n == header) {
      throw runtime_error("The list class is screwed up");
    }
    n->previous->next = n->next;
    n->next->previous = n->previous;
    size--;
  }
  
};

#endif

// ---------------------------------------------------------------------------
// testlinkedlist.cpp                                                                 
//                                                                           
// A test script for the SimpleLinkedList class.
// ---------------------------------------------------------------------------

#include <iostream>
#include <strstream>
#include <cassert>
#include <cmath>
#include <stdexcept>
using namespace std;

#include "SimpleLinkedList.h"

// This helper allows much more concise assertion expressions.
// Check them out in the body of main() below.  NOTE: I'm using
// a strstream (which takes in a char*) rather than a sstream
// (which takes in a string) because when I wrote this my C++
// compiler (gcc 2.95.2) didn't have an sstream class!

List<int> stringToIntList(const char* s) {
  List<int> result;
  istrstream stream(s);
  while (true) {
    int i;
    stream >> i;
    if (!stream) break;
    result.add(result.getSize(), i);
  }
  return result;
}

// Well, this isn't too complete.  Add more tests for extra credit.

int main(int argc, char** argv) {
  List<int> list;

  // Some tests of add, indexOf, isEmpty, getSize and ==
  assert(list.isEmpty() && list.getSize() == 0);
  list.add(0, 5);
  list.add(1, 6);
  list.add(2, 7);
  list.add(1, 4);
  assert(!list.isEmpty() && list.getSize() == 4);
  assert(list.indexOf(7) == 3);
  assert(list == stringToIntList("5 4 6 7 "));

  // Test that copy constructor produces equal lists and
  // does not share values.
  
  List<int> otherList(list);
  assert(list == otherList);
  otherList.set(1, 10);
  assert(list == stringToIntList("5 4 6 7 "));
  assert(otherList == stringToIntList("5 10 6 7 "));
  assert(! (list == otherList));
  
  // Test assignment.  Make sure assignment to self doesn't
  // crash, and that after assignment the lists are ==.
  
  otherList = otherList;
  list = list;
  list = otherList;
  assert(list == otherList);
  assert(list.get(1) == 10);
  
  // Test out_of_range errors are properly thrown.
  
  bool errorHappened = false;
  try {
    list.add(-4, 3);
  } 
  catch (out_of_range e) {
    errorHappened = true;
  }
  assert(errorHappened);

  // ------------------------------------------------------------------
  // TODO More tests here.  Extra credit for you if you do them for me.
  // You have to test EVERYTHING.
  // ------------------------------------------------------------------

  cout << "All tests have passed\n";
  return 0;
}