/*************
 *
 * This is the listWords.c code that I 
 * started typing into during class on oct 9, when we
 * were starting to think about working with arrays rather than lists.
 * 
 ******************************************************/

#include <stdio.h>
#include <string.h>
#include <sys/time.h>

// ===== defines, typedefs and subroutine declarations  ================
// ===== (Might put into a .h file later.) =============================

// maximum number of characters in one word.
#define MaxChars 128

// A doubly linked list element to hold a string and its value.
typedef struct ListElementStruct_ {
  struct ListElementStruct_*	next;
  struct ListElementStruct_*	prev;
  char*				data;
  int				value;
} ListElementStruct, *ListElement;

typedef struct ListStruct_ {
  ListElement			first, last;
  int				nElements;
} ListStruct, *List;

/// &&&&&&& playing around in oct 9 class ---- untested &&&&&&&&&&&&&&&&

typedef struct ArrayElementStruct_ {
  char*          data;
  int            value;
} ArrayElementStruct, *ArrayElement;

typedef struct ArrayStruct_ {
  int                         nElements;
  ArrayElement                which[];
} ArrayStruct, *Array;

Array makeArray(int n) {
  int i;
  Array theArray = (Array)malloc(sizeof(ArrayStruct));
  theArray->nElements = n;
  theArray->which = (ArrayElement*)malloc( n*sizeof(ArrayElement));
  for (i=0;i<n;i++){
    theArray->which[i] = (ArrayElement)malloc(sizeof(ArrayElementStruct));
    theArray->which[i]->value=0;
    theArray->which[i]->data=NULL;
  }
}

// &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&

int getStringValue(char* aString);

List makeEmptyList();
ListElement makeElement(char* inputData);
void printElement(ListElement theList);
void printList(List theList);
void appendElementToList(List theList, ListElement newElement);
void appendStringToList(List theList, char* theString);
ListElement nthElement(List theList, int n);

List readWordsIntoList(int howManyWords);
void findMaxValue(List theList);  // of whole list
ListElement findMaxOfNWords(ListElement element, int nWords);
double timeIt(int nWords, List theList);
void timeMany(int nPoints);

void testList();
void testGetStringValue();
void trialReadWords();


// ==== subroutine implementations ==============================

// -----------------------------------------------------------
// Create and return a new empty list.
List makeEmptyList() {
  List newList = (List)malloc(sizeof(ListStruct));
  newList->nElements = 0;
  newList->first = NULL;
  newList->last = NULL;
  return(newList);
}

// -----------------------------------------------------------
// Create and return a new list element given an input string.
// Also, calculate and store the value of the string.
ListElement makeElement(char* inputData){
  ListElement newElement = (ListElement)malloc(sizeof(ListElementStruct));
  newElement->next  = NULL;
  newElement->prev  = NULL;
  newElement->data  = (char*)malloc(strlen(inputData));
  newElement->value = getStringValue(inputData);
  strcpy(newElement->data, inputData);
  return(newElement);
}

// -----------------------------------------------------------
void printElement(ListElement theList){
  printf("self=%p, next=%p, prev=%p. Data is '%s, value=%i\n", 
	 theList, theList->next, theList->prev,
	 theList->data, theList->value);
}

// -----------------------------------------------------------
void printList(List theList){
  ListElement el;
  int i;
  if (theList->nElements == 0){
    printf("   This list is empty.\n");
  }
  else {
    printf("   This list has %i element(s): \n", theList->nElements);
    i=0;
    el = theList->first;
    while (el != NULL && i<100) {  // don't show more than 100 elements
      printf("   %i : ",i);
      printElement(el);
      el = el->next;
      i++;
    }
  }
}

// -----------------------------------------------------------
void appendElementToList(List theList, ListElement newElement){
  theList->nElements++;
  if (theList->last == NULL){
    theList->first = newElement;
    theList->last = newElement;
  }
  else {
    theList->last->next = newElement;
    newElement->prev = theList->last;
    theList->last = newElement;
  }
}

// -----------------------------------------------------------
void appendStringToList(List theList, char* theString){
  ListElement theElement = makeElement(theString);
  appendElementToList(theList, theElement);
}

// -----------------------------------------------------------
void testList(){
  List theList = makeEmptyList();
  ListElement anElement;

  printf(" ------------------- test list operations ------------ \n");

  printf("  adding 'Hello'\n");
  appendStringToList(theList, "Hello");
  printList(theList);

  printf("  adding 'Goodbye'\n");
  appendStringToList(theList, "Goodbye");

  printf("  adding 'Put123Back'\n");
  appendStringToList(theList, "Put123Back");

  printf("  adding 'Yet another'\n");
  appendStringToList(theList, "Yet another");

  printList(theList);

  anElement = nthElement(theList,2);
  printf("  Element 2 is: \n    ");
  printElement(anElement);

}

// -----------------------------------------------------------
// return the "value" of a string from the assignment definition.
int getStringValue(char* theString){
  int totalValue = 0;
  int characterValue=0;
  int asInt=1;
  int i=0;
  while (asInt != 0 && i<MaxChars) {
    asInt = (int)theString[i];
    if (48 <= asInt && asInt <= 57) {
      characterValue = asInt - 48;
    }
    else if (65 <= asInt && asInt <= 90 ) {
      characterValue = asInt - 55;
    }
    else if (97 <= asInt && asInt <= 122 ) {
      characterValue = asInt - 60;
    }
    else {
      characterValue = 0;
    }
//  printf("   in getStringValue: char %i is '%c', asInt is %i, value is %i\n",
//	   i, theString[i], asInt, characterValue);
    i++;
    totalValue += characterValue;
  }
  return(totalValue);
}

//  By printing out some values (uncomment printf in getStringValue() , 
//  I see that the ascii values I care about are are:
//   "0" => 48, "9" => 57  , so subtract 48 from these to get 0..9
//   "A" => 65, "Z" => 90  , so subtract 55 from these to get 10..35
//   "a" => 97, "z" => 122 , so subtract 60 from these to get 37..62
//  I'll ignore the other characters.
void testGetStringValue(){
  char* sampleString = "09.AZ.az.";
  int value;
  printf(" ---------- test getStringValue ---------- \n");
  printf("  sampleString is '%s'\n", sampleString);
  printf("  length is %i\n", strlen(sampleString));
  value = getStringValue(sampleString);
  printf("  total value this word is %i\n", value);
}


// -----------------------------------------------------------
List readWordsIntoList(int howManyWords){
  char* fileName = "/usr/share/lib/dict/words"; // 25143 words, one per line.
  char oneWord[MaxChars];
  int n=0;
  int s;
  FILE* filePtr = fopen(fileName,"r");		// "r" is "read only" mode
  List theList = makeEmptyList();

  printf("# Reading %i words from '%s'.\n", howManyWords, fileName);
  if (filePtr==NULL){ 
    fprintf(stderr, "Error opening file '%s'\n");
    exit(1);					// Non-zero signals an error.
  }
  while (n<howManyWords) {
    fscanf(filePtr, "%s", oneWord);
    if (feof(filePtr)) {			// end of file test.
      return(theList);
    }
    appendStringToList(theList, oneWord);
    n++;
  }
  return(theList);
}

// -----------------------------------------------------------
// Return the element with the highest value starting at given element,
// after looking at nWords elements.
ListElement findMaxOfNWords(ListElement element, int nWords){
  ListElement bestSoFar = element;
  int i;
  for (i=1;i<nWords;i++){  // start at 1 since we have 0 already in hand.
    if (element == NULL) {
      printf(" OOPS: hit end of list in findMaxOfNWords\n");
      return(NULL);  // error return
    }
    element = element->next;			// walk down the list
    if (element->value > bestSoFar->value){
      bestSoFar = element;
    }
  }
  return(bestSoFar);
}

// -----------------------------------------------------------
void findMaxValue(List theList){
  ListElement el = theList->first;
  ListElement bestSoFar;
  if (el==NULL) {
    printf(" Oops: can't do findMaxValue on an empty list.\n");
    return;
  }
  printf(" Looking for largest value in %i element list...\n",
	 theList->nElements);
  bestSoFar = el;
  while (el->next != NULL){
    el = el->next;				// walk down the list
    if (el->value > bestSoFar->value){
      bestSoFar = el;
    }
  }
  printf(" Done.   *** Biggest is %i on word '%s'. ***\n\n", 
	 bestSoFar->value, bestSoFar->data);
}

// -----------------------------------------------------------
// Return the N'th element of the given list, 0<=N<=(size-1)
// For N>=size, return NULL.
ListElement nthElement(List theList, int n){
  ListElement el = theList->first;
  int i;
  if (n >= theList->nElements){
    return(NULL);
  }
  for (i=0;i<n;i++){
    el = el->next;
  }
  return(el);
}

// -----------------------------------------------------------
// Once this piece (and the others) worked, 
// I cut'n'paste the useful bits into readWordsIntoList.
void trialReadWords(){
  char* fileName = "/usr/share/lib/dict/words"; // 25143 words, one per line.
  char oneWord[MaxChars];
  int howManyWords = 20;			// Just as a warm up.
  int n=0;
  int s;
  FILE* filePtr = fopen(fileName,"r");		// "r" is "read only" mode

  printf(" ---------- test read words ---------- \n");

  if (filePtr==NULL){ 
    fprintf(stderr, "Error opening file '%s'\n");
    exit(1);					// Non-zero signals an error.
  }
  while (n<howManyWords) {
    fscanf(filePtr, "%s", oneWord);		
    s = strlen((const char*)oneWord);		// without cast gives warning
    printf(" %6i: '%s', length=%i, value=%i \n",
	   n,oneWord,s, getStringValue(oneWord));
    n++;
  }

}

// -----------------------------------------------------------
// Return the time (in seconds) it takes find the max value of nWords words.
double timeIt(int nWords, List theList){
  hrtime_t start,end;
  const int repititions = 20;
  int i;
  ListElement maxFound;
  start=gethrtime();
  for (i=0;i<repititions;i++){
    maxFound = findMaxOfNWords(theList->first, nWords);
  }
  end=gethrtime();
  return 1.0e-9*(end-start)/repititions;
  
}

// -----------------------------------------------------------
// Find how long it takes for various values n of nWords,
// using nPoints values of n.  Print out a list of the results.
// Put "#" at the start of the non-numeric lines so that gnuplot
// will ignore them.  (Same in printf() in readWordsIntoList().)
void timeMany(int nPoints){
  List theList = readWordsIntoList(50000);  // read the whole file.
  double sec;
  int dN, n;
  const int MaxNWords = 25143;  // number of words in the file.
  dN = MaxNWords/nPoints;
  printf("# Time (in sec) to find max of n words,\n");
  printf("# using %i values for n:\n", nPoints);
  for (n=dN;n<MaxNWords;n+=dN){
    sec = timeIt(n, theList);
    printf(" %10i   %-20g \n", n, sec);
  }
}


// ==== Fire it up. =================================================

int main(){

  /** Testing **/
  //testGetStringValue();
  //testList();
  //trialReadWords();

  /** Version 1: find max of entire file **/
  //findMaxValue(readWordsIntoList(50000));

  /** Version 1.1: timing of various values for nWords. **/
  timeMany(100);

}