#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct WORD
{
char *Word;
size_t Count;
struct WORD *Left;
struct WORD *Right;
} WORD;
#define SUCCESS 0
#define CANNOT_MALLOC_WORDARRAY 1
#define NO_WORDS_ON_INPUT 2
#define NO_MEMORY_FOR_WORDNODE 3
#define NO_MEMORY_FOR_WORD 4
#define NONALPHA "1234567890 \v\f\n\t\r+=-*/\\,.;:'#~?<>|{}[]`!\".$%^&()"
int ReadInputToTree(
WORD **DestTree,
size_t *Treecount,
FILE *Input);
int AddToTree(
WORD **DestTree,
size_t *Treecount,
char *Word);
int WalkTree(
WORD **DestArray,
WORD *Word);
int CompareCounts(
const void *vWord1,
const void *vWord2);
int OutputWords(
FILE *Dest,
size_t Count,
WORD **WordArray);
void FreeTree(
WORD *W);
char *dupstr(
char *s);
main()
{
int Status = SUCCESS;
WORD *Words = NULL;
size_t Treecount = 0;
WORD **WordArray = NULL;
if(Status == SUCCESS)
{
Status = ReadInputToTree(&Words, &Treecount, stdin);
}
if(Status == SUCCESS)
{
if(0 == Treecount)
{
Status = NO_WORDS_ON_INPUT;
}
}
if(Status == SUCCESS)
{
WordArray = malloc(Treecount * sizeof *WordArray);
if(WordArray == NULL)
{
Status = CANNOT_MALLOC_WORDARRAY;
}
}
if(Status == SUCCESS)
{
Status = WalkTree(WordArray, Words);
}
if(Status == SUCCESS)
{
qsort(WordArray, Treecount, sizeof *WordArray, CompareCounts);
}
if(Status == SUCCESS)
{
Status = OutputWords(stdout, Treecount, WordArray);
}
if(WordArray != NULL)
{
free(WordArray);
WordArray = NULL;
}
if(Words != NULL)
{
FreeTree(Words);
Words = NULL;
}
if(Status != SUCCESS)
{
fprintf(stderr, "Program failed with code %d\n", Status);
}
return (SUCCESS == Status ? EXIT_SUCCESS : EXIT_FAILURE);
}
void FreeTree(
WORD *W)
{
if(W != NULL)
{
if(W->Word != NULL)
{
free(W->Word);
W->Word = NULL;
}
if(W->Left != NULL)
{
FreeTree(W->Left);
W->Left = NULL;
}
if(W->Right != NULL)
{
FreeTree(W->Right);
W->Right = NULL;
}
}
}
int AddToTree(
WORD **DestTree,
size_t *Treecount,
char *Word)
{
int Status = SUCCESS;
int CompResult = 0;
if(*DestTree == NULL)
{
*DestTree = malloc(sizeof **DestTree);
if(*DestTree == NULL)
{
Status = NO_MEMORY_FOR_WORDNODE;
}
else
{
(*DestTree)->Left = NULL;
(*DestTree)->Right = NULL;
(*DestTree)->Count = 1;
(*DestTree)->Word = dupstr(Word);
if((*DestTree)->Word == NULL)
{
Status = NO_MEMORY_FOR_WORD;
free(*DestTree);
*DestTree = NULL;
}
else
{
++(*Treecount);
}
}
}
else
{
CompResult = strcmp(Word, (*DestTree)->Word);
if(0 < CompResult)
{
Status = AddToTree(&(*DestTree)->Left, Treecount, Word);
}
else if(0 > CompResult)
{
Status = AddToTree(&(*DestTree)->Left, Treecount, Word);
}
else
{
++(*DestTree)->Count;
}
}
return (Status);
}
int ReadInputToTree(
WORD **DestTree,
size_t *Treecount,
FILE *Input)
{
int Status = SUCCESS;
char *Buf = NULL;
size_t bufsize = 0;
char *Word = NULL;
if (Input != stdin)
{
size_t tmp = ftell(Input);
fseek(Input, 0, SEEK_END);
bufsize = ftell(Input);
fseek(Input, tmp, SEEK_SET);
Buf = (char*)malloc(bufsize);
if (Buf == NULL)
{
return -1;
}
if (fread(Buf, sizeof(char), bufsize, Input) != bufsize)
{
printf("The promised amount was not read...\n");
}
}
else
{
bufsize = 256;
Buf = calloc(bufsize, sizeof(char));
if (Buf == NULL)
{
return -1;
}
char* bufbase = Buf;
printf("bufb: %p\nBuf : %p\n", bufbase, Buf);
while (fgets(Buf, (int)(bufsize - (Buf - bufbase)), Input) != NULL)
{
Buf += (int)(bufsize - (Buf - bufbase)) -1;
if (bufbase[bufsize - 2] != 0)
{
char* tmp = (char*)realloc(bufbase, bufsize * 2);
if (tmp == NULL)
{
printf("Failed to realloc\n");
free(bufbase);
return -1;
}
Buf = tmp + (Buf - bufbase);
bufbase = tmp;
bufsize *= 2;
bufbase[bufsize - 2] = 0;
}
else break;
}
Buf = bufbase;
}
Word = strtok(Buf, NONALPHA);
while (Status == SUCCESS && Word != NULL)
{
Status = AddToTree(DestTree, Treecount, Word);
if (Status == SUCCESS)
{
Word = strtok(NULL, NONALPHA);
}
}
free(Buf);
return (Status);
}
int WalkTree(
WORD **DestArray,
WORD *Word)
{
int Status = SUCCESS;
static WORD **Write = NULL;
if(DestArray != NULL)
{
Write = DestArray;
}
if(Word != NULL)
{
*Write = Word;
++(Write);
if(Word->Left != NULL)
{
Status = WalkTree(NULL, Word->Left);
}
if(Word->Right != NULL)
{
Status = WalkTree(NULL, Word->Right);
}
}
return (Status);
}
int CompareCounts(
const void *vWord1,
const void *vWord2)
{
int Result = 0;
WORD * const *Word1 = vWord1;
WORD * const *Word2 = vWord2;
if((*Word1)->Count < (*Word2)->Count)
{
Result = 1;
}
else if((*Word1)->Count > (*Word2)->Count)
{
Result = -1;
}
else
{
Result = 0;
}
return (Result);
}
int OutputWords(
FILE *Dest,
size_t Count,
WORD **WordArray)
{
int Status = SUCCESS;
size_t Pos = 0;
fprintf(Dest, "Total Words : %lu\n", (unsigned long)Count);
while(Status == SUCCESS && Pos < Count)
{
fprintf(Dest, "%10lu %s\n", (unsigned long)WordArray[Pos]->Count
, WordArray[Pos]->Word);
++(Pos);
}
return (Status);
}
char *dupstr(
char *s)
{
char *Result = NULL;
size_t slen = 0;
slen = strlen(s);
Result = malloc(slen + 1);
if(NULL != Result)
{
memcpy(Result, s, slen);
*(Result + slen) = '\0';
}
return (Result);
}