using namespace std;

#include <cassert>

#include "list.h"

/**
 * Constructs an empty list.
 */

List::List()
{
  listData = NULL;
  currentPos = NULL;
  extraNode = new Node;
  numItems = 0;
}

/**
 * Constructs a copy of the given list.  The new list will contain all the
 * data from the original in the same order, and if there is a current
 * position in the original, the current position in the new list will
 * be the corresponding new element.
 */

List::List(const List& toCopy)
{
  Node *curr = toCopy.listData, *prev = NULL;
  currentPos = NULL;

  while (curr != NULL)
    {
      // make and set fields for new node
      Node* newNode = new Node;
      assert(newNode != NULL);
      newNode->info = curr->info;
      newNode->next = NULL;

      if (prev == NULL)
	listData = newNode; // adding first node
      else
	prev->next = newNode; // make node made last time point to newest one
      prev = newNode;

      // take care of currentPost
      if (curr == toCopy.currentPos)
	currentPos = newNode;

      curr = curr->next;
    }

  numItems = toCopy.numItems;
  extraNode = new Node;
}

/**
 * Destroys this list.
 */

List::~List()
{
  makeEmpty();
}

/**
 * pre: none
 * post: returns true iff the list is full.
 */

bool List::isFull() const
{
  return (extraNode == NULL);
}

/**
 * pre: none
 * post: returns the number of items on the list.
 */

int List::getLength() const
{
  return numItems;
}

/**
 * pre: none
 * post: if item with same key as i is on the list, then that item is
 * copied into i and found = true, otherwise i is unchanged and i = false
 */

void List::retrieveItem(ItemType& i, bool& found) const
{
  Node *curr = listData;

  // go until off end of list or found a >= key

  while (curr != NULL && curr->info.compareTo(i) < 0)
    curr = curr->next;

  // not found if off list or strictly >, found otherwise

  if (curr == NULL || curr->info.compareTo(i) > 0)
    found = false;
  else
    {
      found = true;
      i = curr->info;
    }
}

/**
 * pre: none
 * post: the list is empty
 */

void List::makeEmpty()
{
  Node *curr = listData;

  // delete all nodes

  while (curr != NULL)
    {
      Node *nextToDelete = curr->next;
      delete curr;
      curr = nextToDelete;
    }

  // reset data members

  numItems = 0;
  listData = NULL;
  currentPos = NULL;
  if (extraNode == NULL)
    extraNode = new Node;
}

/**
 * pre: no item with same key as toAdd is on the list and the list isn't full
 * post: item toAdd has been added to the list and items sorted by key
 */

void List::addItem(const ItemType& toAdd)
{
  assert(!isFull());

  // the nodes before and after where we're adding

  Node *afterAdded = listData;
  Node *beforeAdded = NULL;

  // find first item >= the item we're adding

  while (afterAdded != NULL && afterAdded->info.compareTo(toAdd) < 0)
    {
      beforeAdded = afterAdded;
      afterAdded = afterAdded->next;
    }

  // copy data into node we're adding

  extraNode->info = toAdd;
  extraNode->next = afterAdded;

  // link node into the list

  if (beforeAdded == NULL)
    listData = extraNode;
  else
    beforeAdded->next = extraNode;

  // get ourselves another extra node

  extraNode = new Node;

  // update item count

  numItems++;
}

/**
 * pre: an item with same key as toDelete is on the list
 * post: that item is no longer on the list and the current point is set to
 * the beginning of the list and items still sorted by key
 */

void List::deleteItem(const ItemType& toDelete)
{
  Node *match = listData;
  Node *beforeMatch = NULL;

  // find first item >= the item we're adding

  while (match != NULL && match->info.compareTo(toDelete) < 0)
    {
      beforeMatch = match;
      match = match->next;
    }

  assert(match != NULL && match->info.compareTo(toDelete) == 0);

  // unlink node

  if (beforeMatch == NULL)
    listData = match->next;
  else
    beforeMatch->next = match->next;

  // check if the node we just deleleted was the current node
  
  if (currentPos == match)
    currentPos = match->next;

  // get rid of deleted node

  if (extraNode == NULL)
    extraNode = match;
  else
    delete match;

  // decrement item count

  numItems--;
}

/**
 * pre: none
 * post: the current position in the list is the beginning of the list
 */

void List::resetCurrent()
{
  currentPos = listData;
}

/**
 * pre: there is a next item on the list
 * post: the current position is advanced one spot and the item moved over
 * is copied to nextItem
 */

void List::getNextItem(ItemType& nextItem)
{
  nextItem = currentPos->info;
  currentPos = currentPos->next;
}