/**************************************************************************
  GDB Test File 2 - contains a few errors
 ***************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TOKEN_LENGTH	         20			/* Assume maximum length of token. */
#define FALSE			 0
#define TRUE			 1

/************************** Typedefs and Symbolic Constants ***************/

typedef struct ListNodeType {
    char Token[TOKEN_LENGTH];				/* Pointer to text of token.       */
    int TimesFound;					/* Times that token has been found */
    struct ListNodeType *Next;				/* Next nodes in the list          */
} LIST_NODE;

/************************** Function Prototypes ***************************/

LIST_NODE *Alloc_ListNode( void );
int Find_Token( char *Token );
void SearchInsert( LIST_NODE **ListHead, char *Token );
void Print_List ( LIST_NODE *ListHead );
void Delete_List ( LIST_NODE **ListHead );

/**************************************************************************/

void main( void ) {
    LIST_NODE *ListHead;				/* Pointer to the root of tree */
    char Token[TOKEN_LENGTH];				/* Token read in               */
    int EndOfFileFlag;					/* Flag => have reached eof.   */
    
    ListHead = NULL;
    
    /* Read in tokens one by one. Break the loop only when have reached the
       end of the file. Pass the token to the procedure SearchInsert. */
    
    for( ; ; ) { 
	EndOfFileFlag = Find_Token( Token );
      if ( EndOfFileFlag == TRUE ) break;
	SearchInsert( &ListHead, Token );
    } /* for */
    printf("\nThe linked list contains:\n");
    Print_List( ListHead );
    Delete_List( &ListHead );
} /* main */

/**************************************************************************
  Alloc_ListNode() returns a pointer to a freshly allocated ListNode. 
  
  Input: none
  Output: Pointer to a new node for the list.
  Errors: no action
  *************************************************************************/

LIST_NODE *Alloc_ListNode() {
    return( ( LIST_NODE * ) malloc( (unsigned) sizeof(LIST_NODE) ) );
} /* Alloc_ListNode */

/**************************************************************************
  Find_Token finds the next white-space delimited token in a file
  and puts it into a buffer.  It is assumed tokens will be less than
  TOKEN_LENGTH.
  
  Input: Pointer to where the token is stored - **TokenBuffer
  Output: Token.
  Flag indicating whether a token has been found or not.
  Errors: If the end of the file has been reached, return to the calling
  procedure.
 **************************************************************************/

int Find_Token ( char *TokenBuffer) {
    int Symbol;						/* Symbol that was read from file. */
    int BufferLen, EndOfFileFlag;
    
    /* Skip leading whitespace by looping until either found the end of
       the file or reached a non-whitespace symbol. Read 1 character at a
       time.
     */
    
    EndOfFileFlag = FALSE;
    
    for( ; ; ) {
	Symbol = getchar();
      if( Symbol == EOF ) break;
      if( Symbol != ' ' && Symbol != '\n' && Symbol != '\t' ) break;
    } /* for */
    
    if( Symbol == EOF ) {
	EndOfFileFlag = TRUE;
    } else  {
	for ( BufferLen = 0 ; BufferLen < TOKEN_LENGTH - 2; BufferLen += 1 ) {
	    TokenBuffer[BufferLen] = Symbol;
	    Symbol = getchar();
	  if( Symbol == EOF || Symbol == ' ' || Symbol == '\n'
	       || Symbol == '\t' ) break;		/* Found end of token. */
	} /* for */
	TokenBuffer[BufferLen+1] = '\0';	        /* End string. */
    } /* if */
    return( EndOfFileFlag );
} /* Find_Token */

/**************************************************************************
  SearchInsert searches the list for the token. If the token is in the list,
  the repetition count of the token is incremented. Otherwise, the token is
  added to the list.
  
  Input:  Pointer to the start of the list - ListHead
  Pointer to the buffer which contains the token - Token
  Output: A list of tokens with their frequencies of occurrence
  Errors: If no space for new token, then print message and ignore token.
 **************************************************************************/

void SearchInsert ( LIST_NODE **ListHead, char *Token ) {
    LIST_NODE *new_node, *temp, *prev;
    int value;
    
    if (*ListHead = NULL) {
	*ListHead = Alloc_ListNode();
	if( *ListHead == NULL ) {			/* Ran out of space. */
	    fprintf(stderr, "ERROR: ran out of space\n");
	    exit(-3);
	} /* if */
	(*ListHead)->Next = NULL;
	(*ListHead)->TimesFound = 1;
	strncpy((*ListHead)->Token,Token,TOKEN_LENGTH-1);
    } else {
	prev = *ListHead;
	for ( temp = *ListHead; temp->Next != NULL; temp = temp->Next ) {
	    value = strcmp(temp->Token, Token);
	  if ( value >= 0 ) break;
	    prev = temp;	    
	} /* for */	  
	if (value == 0) {
	    temp->TimesFound += 1;
	} else {
	    new_node = Alloc_ListNode();
	    if ( new_node == NULL ) {			/* Ran out of space. */
		fprintf(stderr, "ERROR: ran out of space\n");
		exit(-3);
	    } /* if */
            strncpy(new_node->Token,Token,TOKEN_LENGTH-1);
	    new_node->TimesFound = 1;
	    if ( temp != NULL ) {
	        new_node->Next = prev->Next;		
		prev->Next = new_node;
	    } else {
		prev->Next = new_node;
	        new_node->Next = NULL;				
	    } /* if */
	} /* if */
    } /* if */
} /* SearchInsert */
    
/**************************************************************************
  Print_List prints the linked list with the token repetition counts.
  
  Input:  Pointer to the root of the tree - ListHead
  Output: The tokens and their frequencies of occurrence.  
 **************************************************************************/

void Print_List ( LIST_NODE *ListHead) {
    LIST_NODE *temp;
    
    for ( temp = ListHead; temp != NULL ; temp = temp->Next ) {
	printf("Token: %20s occurs %d time(s)\n",temp->Token,temp->TimesFound);
    } /* for */
} /* Print_List */

/**************************************************************************
  Delete_List deletes the binary search tree.
  
  Input:  Pointer to the root of the tree - ListHead
  Output: Resets ListHead to NULL at the end.
 **************************************************************************/

void Delete_List ( LIST_NODE **ListHead) {
    LIST_NODE *temp, *prev;
    
    prev = *ListHead;
    if ( *ListHead != NULL ) {
	for ( temp = (*ListHead)->Next ; temp != NULL ; temp = temp->Next ) {
	    prev = NULL;
	    free(prev);
	    prev = temp;
	} /* for */
    } else {
	free(*ListHead);
    } /* if */
} /* Delete_List */