#include "stdstuff.h"

#include "IntSequence.h"


void IntSequence::copyFrom (const IntSequence &otherSequence){

  DNode *c; // used to walk through list for other sequence

  // make sure that the object is properly initialized.
  head = tail = NULL;
  count = 0;

  for (c = otherSequence.head; c != NULL; c = c -> next) {
    addAtEnd (c -> data);
  }

  walkInProgress = false;

}


void IntSequence::deleteList () {

  DNode *c;

  while (head != NULL) {
    c = head;
    head = head -> next;
    delete c;
  }

  tail = NULL;
  count = 0;
  walkInProgress = false;

}


void IntSequence::addAtEnd (int value) {

  DNode *n;

  n = new DNode (value, NULL);
  if (tail == NULL) {
    head = n;
  } else {
    tail -> next = n;
  }
  tail = n;

  count++;

}


IntSequence::IntSequence () {

  head = tail = NULL;
  count = 0;

  walkInProgress = false;

}


IntSequence::IntSequence (const IntSequence &otherSequence) {

  copyFrom (otherSequence);

}


IntSequence::~IntSequence () {

  deleteList ();

}


void IntSequence::add (int value) {

  DNode *p, *c, *n;

  p = NULL; c = head;
  while ((c != NULL) && (c -> data <= value)) {
    if (c -> data == value) return; // value already exists
    p = c; c = c -> next;
  }

  n = new DNode (value, c);
  if (p == NULL) {
    head = n;
  } else {
    p -> next = n;
  }
  if (c == NULL) tail = n; // new last node

  count++;
  walkInProgress = false;

}


bool IntSequence::remove (int value) {

  DNode *p, *c;

  p = NULL; c = head;
  // we stop looking when "c" becomes NULL or we come across a value
  // that is greater than or equal to the value we're looking for
  while ((c != NULL) && (c -> data < value)) {
    p = c; c = c -> next;
  }

  // if we stopped because "c" is null or we've hit a value that is bigger
  // than the value we're looking for, then the value doesn't exist.
  if ((c == NULL) || (c -> data > value)) return false; // value does not exist

  if (p == NULL) {
    head = c -> next;
  } else {
    p -> next = c -> next;
  }
  if (c -> next == NULL) tail = p; // deleted node was last node in list
  delete c;

  count--;
  walkInProgress = false;
  return true;

}


void IntSequence::removeAll () {

  // "deleteList" zeroes count and makes "walkInProgress" false
  deleteList ();

}


bool IntSequence::valueExists (int value) const {

  DNode *c;

  for (c = head; c != NULL; c = c -> next) {
    if (c -> data == value) return true;
    if (c -> data > value) return false;
  }

  return false;

}


int IntSequence::getValue (int i) const {

  DNode *c;

  if ((i < 0) || (i >= count)) {
    throw out_of_range ("IntSequence::getValue - index out of range");
  }

  c = head;
  // take the required number of steps.
  // note that, if "i" is zero, we won't take any steps at all.
  while (i != 0) {
    c = c -> next; i--;
  }

  return c -> data;

}


bool IntSequence::startWalk (int &value) {

  if (count == 0) return false;

  walkInProgress = true; walkPointer = head;
  value = walkPointer -> data;
  return true;

}


bool IntSequence::continueWalk (int &value) {

  if (!walkInProgress) {
    throw range_error ("IntSequence::continueWalk invalid call");
  }

  // advance one step
  walkPointer = walkPointer -> next;

  if (walkPointer == NULL) {
    walkInProgress = false; // we've come to the end of the road
    return false;
  }

  value = walkPointer -> data;
  return true;

}


bool IntSequence::operator== (const IntSequence &otherSequence) const {

  DNode *c1, *c2;

  // if the sequences have different sizes, they aren't equal
  if (count != otherSequence.count) return false;

  // the sequences have the same size.  check the values.
  c1 = head; c2 = otherSequence.head;
  while (c1 != NULL) { // both pointers become NULL at the same time
    if (c1 -> data != c2 -> data) return false;
    c1 = c1 -> next; c2 = c2 -> next;
  }
  return true;

}


IntSequence IntSequence::intersect (const IntSequence &otherSequence) const {

  IntSequence result;
  DNode *c1, *c2;

  c1 = head; c2 = otherSequence.head;
  while ((c1 != NULL) && (c2 != NULL)) {

    if (c1 -> data == c2 -> data) { // value in in both sequences
      result.addAtEnd (c1 -> data);
      c1 = c1 -> next; c2 = c2 -> next;
    } else if (c1 -> data < c2 -> data) {
      c1 = c1 -> next;
    } else {
      c2 = c2 -> next;
    }

  }

  return result;

}


IntSequence IntSequence::unionWith (const IntSequence &otherSequence) const {

  IntSequence result;
  DNode *c1, *c2;

  c1 = head; c2 = otherSequence.head;
  while ((c1 != NULL) && (c2 != NULL)) {

    if (c1 -> data == c2 -> data) {
      result.addAtEnd (c1 -> data);
      c1 = c1 -> next; c2 = c2 -> next;
    } else if (c1 -> data < c2 -> data) {
      result.addAtEnd (c1 -> data);
      c1 = c1 -> next;
    } else {
      result.addAtEnd (c2 -> data);
      c2 = c2 -> next;
    }

  }

  while (c1 != NULL) {
    result.addAtEnd (c1 -> data);
    c1 = c1 -> next;
  }

  while (c2 != NULL) {
    result.addAtEnd (c2 -> data);
    c2 = c2 -> next;
  }

  return result;

}


IntSequence& IntSequence::operator= (const IntSequence &otherSequence) {

  // delete existing list
  deleteList ();

  // make a copy of the list in the other sequence
  copyFrom (otherSequence);

  return *this;

}