#include "stdstuff.h"
#include "Time.h"
#include "AllTime.h"

// Note that this sample solution uses linear rehashing and ensures that at least
// one element in the hash table is never used.

AllTimeList::AllTimeList (int capacity) {

  tableSize = 3 * capacity;
  table = new Node* [tableSize];
  count = 0;
  for (int i = 0; i < tableSize; i++) {
    table[i] = NULL;
  }
  fastest = slowest = NULL;
  walkInProgress = false;
}


AllTimeList::~AllTimeList () {

  for (int i = 0; i < tableSize; i++) {
    if (table[i] != NULL) delete table[i];
  }
  delete [] table;

}


static String2002 standardize (const String2002 &name) {

  int i;
  String2002 result;
  enum { justStarting, withinBlanks, withinWord } state = justStarting;

  for (i = 0; i < name.length(); i++) {
    if (name[i] == ' ') {
      // if we're justStarting, nothing has changed.
      // otherwise we've just begun to process embedded blanks.
      if (state != justStarting) state = withinBlanks;
    } else {
      if (state != withinWord) {
        // first letter of a word
        if (state == withinBlanks) result += ' ';
        result += (char) toupper(name[i]);
      } else {
        result += (char) tolower(name[i]);
      }
      state = withinWord;
    }
  }

  return result;

}


// returns a value between 0 and "tableSize - 1"
int AllTimeList::hash (const String2002 &name) const {

  int total = 0, i, multiplier;

  for (i = 0; i < name.length(); i++) {
    if ((i % 4) == 0) {
      multiplier = 1;
    }
    total += name[i] * multiplier;
    multiplier *= 128; // 2 ** 7
  }

  return total % tableSize;

}


void AllTimeList::addNodeToList (Node *node) {

  Node *p, *c;

  p = NULL; c = fastest;

  while (c != NULL && (c -> bestTime < node -> bestTime)) {
    p = c; c = c -> next;
  }

  node -> prior = p; node -> next = c;
  if (p == NULL) {
    fastest = node;
  } else {
    p -> next = node;
  }
  if (c == NULL) {
    slowest = node;
  } else {
    c -> prior = node;
  }

}


void AllTimeList::moveNodeIfNecessary (Node* node) {

  Node *p, *pp, *f;

  while ( node -> prior != NULL &&
          (node -> bestTime < node -> prior -> bestTime) ) {
    // move node one position up the list
    // p = prior node, pp = prior prior node, f = following node
    p = node -> prior; pp = p -> prior; f = node -> next;
    // update node's pointers
    node -> prior = pp; node -> next = p;
    // update prior node's pointers
    p -> prior = node; p -> next = f;
    // update prior prior node's pointers
    if (pp == NULL) {
      fastest = node;
    } else {
      pp -> next = node;
    }
    // update following node's pointers
    if (f == NULL) {
      slowest = p;
    } else {
      f -> prior = p;
    }
  }

}


void AllTimeList::add (const String2002 &name, const Time &bestTime) {

  String2002 standardizedName = standardize(name);
  int key = hash (standardizedName);

  for (;;) {

    if (table[key] == NULL) {
      if (count == tableSize - 1) {
        // no room left as we must keep one slot empty 
        // (Note that it would be even better (more efficient) to ensure that 
        // more than one spot is empty.  The code would also work if we allowed
        // the table to fill, but would be even less efficient.  Of course,
        // with hashing with buckets, this is not an issue.)
        throw overflow_error ("AllTimeList::add - table full");
      }
      table[key] = new Node (standardizedName, bestTime);
      addNodeToList (table[key]);
      count++;
      walkInProgress = false;
      return;
    }

    if (table[key] -> name == standardizedName) {
      throw invalid_argument ("AllTimeList::add - name exists");
    }

    key = (key + 1) % tableSize;

  }

}


void AllTimeList::reportTime (const String2002 &name, const Time &time) {

  String2002 standardizedName = standardize(name);
  int key = hash (standardizedName);

  for (;;) {

    if (table[key] == NULL) {
      throw overflow_error ("AllTimeList::reportTime - name does not exist");
    }

    if (table[key] -> name == standardizedName) {
      if (time < table[key] -> bestTime) {
        // we have a new best time
        table[key] -> bestTime = time;
        moveNodeIfNecessary (table[key]);
      }
      walkInProgress = false;
      return;
    }

    key = (key + 1) % tableSize;

  }

}


Time AllTimeList::lookupTime (const String2002 &name) const {

  String2002 standardizedName = standardize(name);
  int key = hash (standardizedName);

  for (;;) {

    if (table[key] == NULL) {
      throw overflow_error ("AllTimeList::lookupTime - name does not exist");
    }

    if (table[key] -> name == standardizedName) {
      return table[key] -> bestTime;
    }

    key = (key + 1) % tableSize;

  }

}


bool AllTimeList::startWalk (String2002 &name, Time &time) {

  if ((walkPosition = fastest) == NULL) return false;

  walkInProgress = true;
  name = walkPosition -> name;
  time = walkPosition -> bestTime;
  return true;

}


bool AllTimeList::continueWalk (String2002 &name, Time &time) {

  if (!walkInProgress) {
    throw range_error ("IntBag::continueWalk invalid call");
  }
  if ((walkPosition = walkPosition -> next) == NULL ) {
    walkInProgress = false; // we've come to the end of the road
    return false;
  }
  name = walkPosition -> name;
  time = walkPosition -> bestTime;
  return true;

}