/*************
 *
 * listWords.c
 *
 * September 2002 assignment in Algorithms class
 *
 *   -- original assignment -- 
 *   Write a C program which reads some number N of words from the
 *   dictionary file /usr/share/lib/dict/words on akbar. and stores them as
 *   a list. Let the characters 0..9a..zA..Z have the values 0-9, 10-36,
 *   37-63. Write an algorithm to search your list for the largest
 *   word. How long does this take to run as a function of N, the number of
 *   words in your table? ("gprof" may be the tool to help you see how long
 *   it takes to run.)
 *
 * BUT the above has some fencepost errors, like a..z is 26 chars but
 * 10..36 is 27 numbers.  So let's decide to have string values
 * (0..9,a..z,A..Z) =>  (0..9, 10..35, 37..62) and 
 * (since the problem didn't say) have other characters assigned to zero.
 *
 * Jim Mahoney (mahoney@marlboro.edu)
 *
 *  version 1.0, Sep 24 3am  
 *  Doesn't do timing on N yet, but otherwise fits the bill.
 * 
 ******************************************************/

#include <stdio.h>
#include <string.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;


int getStringValue(char* aString);

List makeEmptyList();
ListElement makeElement(char* inputData);
void printListElement(ListElement theList);
void printList(List theList);
void appendElementToList(List theList, ListElement newElement);
void appendStringToList(List theList, char* theString);

List readWordsIntoList(int howManyWords);
void findMaxValue(List theList);

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 printListElement(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
      printListElement(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();
  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");

  printList(theList);
}

// -----------------------------------------------------------
// 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);
}

//  Printing out some values, I see that the ascii values 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
//  Ignore 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);
}

// -----------------------------------------------------------
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);
}

// -----------------------------------------------------------
// Once this (and the other pieces) 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++;
  }

}


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

int main(){

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

  //findMaxValue(readWordsIntoList(50000));

}