#include <stdio.h>   // don't use any headers except these
#include <time.h>    
#include <stdlib.h> 
#include <ctype.h> 
#include <string.h> 

#define MAXWORDS 150000
char *words[MAXWORDS];  // array to store words in
int no_of_words=0;      // number of words

// The following ugly stuff is to allow us to measure cpu time on NT/Win2k/XP.
// Win95/98 only lets us measure elapsed time so will not be as accurate
typedef struct { unsigned long l,h; } ti;
#ifdef __cplusplus
extern "C" {
#endif
void * _stdcall GetCurrentProcess(void);
unsigned long _stdcall GetVersion(void);
int _stdcall GetProcessTimes(void *, ti *,ti *, ti *, ti *);
void _stdcall Sleep(unsigned long);
#ifdef __cplusplus
}
#endif

int cputime(void) {
   ti ct,et,kt,ut;
   if(GetVersion()<0x80000000) {  // are we running on NT/2K/XP
      GetProcessTimes(GetCurrentProcess(),&ct,&et,&kt,&ut);
      return (ut.l)/10000;
   }
   else return clock(); // for Windows 95/98/ME
}

char *readword(FILE *f) {  // read a word from a file
   unsigned i=0;           // index of next char in word
   char word[256];         // temporary store for the word
   char *newword;          // pointer to be returned for word
   char c;                 // temporary store for a char in the word

   do {                    // skip over any leading non alphabetic chars
      c=fgetc(f);          // get a char from the file
   }while(!isalpha(c) && !feof(f));
   if(feof(f)) return NULL;   // if end of file without getting a word then return NULL
   do {                       // get the word
      word[i++]=tolower(c);   // convert to lower case
      c=fgetc(f);             // get the next char
   }while((isalpha(c) || c==0x27) && !feof(f)); // allow ' within a word e.g. don't
   if(word[i-1]==0x27) i--;   // remove trailing ' from a word
   word[i]=0;                 // NUL terminate the string

   newword=(char *)malloc(strlen(word)+1); //allocate space for the word
   strcpy(newword,word);      // copy the word into it
   return newword;
}


int main() {
   int i;
   unsigned starttime,endtime;
                                             // (do not change the next line or you will lose marks)           
   FILE *fin=fopen("sherlock.txt","r");      // open the input file 
   if(!fin) {puts("Could not open input file");return 0;}
         
   while((words[no_of_words]=readword(fin))!=0) // read all the words into an array
      no_of_words++;  
   printf("%d words found\n",no_of_words);   // how many words are there?

   puts("Sort started");
   starttime=cputime();    // remember what time the sort started
   sort(words);
   endtime=cputime();      // remember what time the sort finished
   puts("Sort finished");
   printf("Sort used %.2f seconds of cputime\n",
            ((float)(endtime-starttime))/1000);  // print out the time it took
   for (i=0;i<no_of_words-1;i++) {
     if(strcmp(words[i],words[i+1])>0)    // check that the list is sorted
       printf("Error: %s and %s are in the wrong order\n",words[i],words[i+1]);
   }
   return 1;
}