#include "stdstuff.h"
#include "IntSequence.h"


static const int INITIAL_CAPACITY = 4,
                 CAPACITY_STEP = 2;


void IntSequence::expandIfFull () {

  int *newData, i;

  if (count == capacity) {
    capacity += CAPACITY_STEP; // update capacity to its new value
    newData = new int [capacity]; // capacity has already been updated
    for (i = 0; i < count; i++) {
      newData[i] = data[i];
    }
    delete [] data;
    data = newData;

  }

}


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

  int i;

  for (i = 0; i < otherSequence.count; i++) {
    data[i] = otherSequence.data[i];
  }
  count = otherSequence.count;

  walkInProgress = false;

}


IntSequence::IntSequence () {

  data = new int [INITIAL_CAPACITY];
  capacity = INITIAL_CAPACITY;
  count = 0;

}


IntSequence::IntSequence (const IntSequence &otherSequence) {

  data = new int[otherSequence.capacity];
  capacity = otherSequence.capacity;

  copyFrom (otherSequence);

}


IntSequence::~IntSequence () {

  delete [] data;

}


void IntSequence::add (int value) {

  int i, j;

  for (i = 0; i < count; i++) {
    if (data[i] == value) return; // value already exists
    if (data[i] > value) {
      // make sure that we have room for the insertion
      expandIfFull();
      walkInProgress = false;
      // shuffle following values up one
      for (j = count; j > i; j--) {
        data[j] = data[j - 1];
      }
      data[i] = value;
      count++;
      return;
    }
  }

  // must be inserting at the end
  expandIfFull(); // make sure that we have room for the insertion
  data[count++] = value;
  walkInProgress = false;
  return;

}


bool IntSequence::remove (int value) {

  int i, j;

  for (i = 0; i < count; i++) {
    if (data[i] == value) {
      // we've found the data value.
      // shuffle all remaining values down one.
      for (j = i + 1; j < count; j++) {
        data[j - 1] = data[j];
      }
      count--;
      walkInProgress = false;
      return true;
    }
  }

  return false;

}


void IntSequence::removeAll () {

  count = 0; walkInProgress = false;

}


bool IntSequence::valueExists (int value) const {

  int i;

  for (i = 0; i < count; i++) {
    if (data[i] == value) return true;
    if (data[i] > value) return false;
  }

  return false;

}


int IntSequence::getValue (int i) const {

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

  return data[i];

}


bool IntSequence::startWalk (int &value) {

  if (count == 0) return false;

  walkInProgress = true; walkPosition = 0;
  value = data[walkPosition];
  return true;

}


bool IntSequence::continueWalk (int &value) {

  if (!walkInProgress) {
    throw range_error ("IntSequence::continueWalk invalid call");
  }
  if (++walkPosition == count) {
    walkInProgress = false; // we've come to the end of the road
    return false;
  }
  value = data[walkPosition];
  return true;

}


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

  int i;

  // 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.
  for (i = 0; i < count; i++) {
    if (data[i] != otherSequence.data[i]) return false;
  }
  return true;

}


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

  IntSequence result;
  int i, j;

  i = j = 0;

  while ((i < count) && (j < otherSequence.count)) {

    if (data[i] == otherSequence.data[j]) { // value is in both sequences
      result.expandIfFull(); // make sure that we have room
      result.data[result.count++] = data[i++];
      j++;
    } else if (data[i] < otherSequence.data[j]) {
      i++;
    } else {
      j++;
    }

  }

  return result;

}


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

  IntSequence result;
  int i, j;

  i = j = 0;

  while ((i < count) && (j < otherSequence.count)) {

    result.expandIfFull(); // make sure that we have room
    if (data[i] == otherSequence.data[j]) {
      result.data[result.count++] = data[i++];
      j++;
    } else if (data[i] < otherSequence.data[j]) {
      result.data[result.count++] = data[i++];
    } else {
      result.data[result.count++] = otherSequence.data[j++];
    }

  }

  while (i < count) {
    result.expandIfFull(); // make sure that we have room
    result.data[result.count++] = data[i++];
  }

  while (j < otherSequence.count) {
    result.expandIfFull(); // make sure that we have room
    result.data[result.count++] = otherSequence.data[j++];
  }

  return result;

}


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

  // check that the sequence being copied into is has enough capacity
  // and increase its capacity if it hasn't.
  if (capacity < otherSequence.count) {
    delete [] data;
    capacity = otherSequence.count;
    data = new int [capacity];
  }

  copyFrom (otherSequence);

  return *this;

}