allword4.cc From Astrachan pp 395-398
-------------------------------------
#include <iostream.h>
#include <fstream.h>
#include <stdlib.h>                // for exit
#include "CPstring.h"
#include "vector.h"
#include "ctimer.h"                // for CTimer
#include "strutils.h"              // for StripPunc
#include "prompt.h"

// author: Owen Astrachan
//
// lists all words in an input file, with word counts
// uses class WordList to encapsulate behavior
//
// 5-15-95


struct WordStat
{
    string info;                 // the string
    int count;                   // # of times string occurs
};


class WordList
{
  public:
    WordList(int size);             // constructor,  specify size of list
    void Update(string word);       // update occurrences of word
    int GetUnique();                // return # of unique words in list
    int GetTotal();                 // return # of total words in list
    void Print(ostream & output);   // print all words in list
  private:

    int myCount;                    // # of entries stored in myList
    int mySize;                     // capacity of myList
    int myTotal;                    // # of words (non-unique)
    Vector<WordStat> myList;        // storage for word statistics
    
    int Search(const string & key); // returns index in myList of key
};

WordList::WordList(int size)
   : myCount(0),
     mySize(size),
     myTotal(0),
     myList(size)
{
    // all work done in initializer list
}

int WordList::Search(const string & key)
// postcondition: returns index at which key occurs in myList
//                returns -1 if key does not occur     
{
    int low = 0;
    int high = myCount-1;
    int mid;                          // middle of current range
    while (low <= high)
    {
        mid = (low + high)/2;
        if (myList[mid].info == key)       // found key, exit
        {
            return mid;
        }
        else if (myList[mid].info < key)   // key in upper half
        {
            low = mid + 1;
        }
        else                          // key in lower half
        {
            high = mid - 1;
        }
    }
    return -1;
}

void WordList::Update(string word)
// postcondition: updates occurrence of word
//                adds word to list if not already present
//                increments count of total # of words     
{
    int loc = Search(word);

    myTotal++;
    
    if (loc == -1)                 // not already in list
    {
        if (myCount >= mySize)
        {
            mySize *= 2;
            myList.SetSize(mySize);
        }
        loc = myCount - 1;         // shift structs right
        while (0 <= loc && word < myList[loc].info)
        {
            myList[loc+1] = myList[loc];
            loc--;
        }
        myList[loc+1].info = word;
        myList[loc+1].count = 1;
        myCount++;
    }
    else
    {
        myList[loc].count++;
    }
}

void WordList::Print(ostream & output)
// postcondition: all elements of myList printed
{
    int k;
    for(k=0; k < myCount; k++)
    {
        output << myList[k].count << "\t" << myList[k].info << endl;
    }
    output << endl << "# of words = " << myCount << endl;
}

int WordList::GetUnique()
// postcondition: returns # unique words in list     
{
    return myCount;
}

int WordList::GetTotal()
// postcondition: returns total # of words in list
//                same as # of times Update called     
{
    return myTotal;
}

int main()
{
    string word;                       // word read from file
    string filename = PromptString("enter name of file: ");
    ifstream input;
    WordList wlist(1000);
    CTimer timer;
    
    input.open(filename);
    if (input.fail())
    {
        cout << "could not open file " << filename << endl;
        exit(0);
    }
    
    while (input >> word)              // reading word succeeded
    {
	word = word.Downcase();
	StripPunc(word);
        timer.Start();
        wlist.Update(word);
        timer.Stop();
    }
    wlist.Print(cout);

    cout << "total words (non-unique): " << wlist.GetTotal() << endl;
    cout << "total time for update = " << timer.CumulativeTime() << endl;    
    return 0;
}