Some software packages provide a facility to predict the word you are
typing, based on previous input and the initial characters that you type.
For example, Netscape predicts the URL you are typing, and some word
processors will predict the next word you are typing into your text.
WordFinisher is a program that does this, in a simple way.
At any stage the user may press the tab key, and
WordFinisher will present the word that that starts with
the characters already typed in the current word, that has been used the
most.
Pressing tab again presents the next most used word, etc,
for a maximum of 10 words.
If the presented word is the one required, a space or return indicates
acceptance, and the user continues typing the next word.
Input is terminated by inputing a period alone on a line.
WordFinisher can take a single argument, which is the name
of a file from which previous usage history is loaded into the system, and
to which the usage history is saved when terminating.
A first implementation of WordFinisher (source code and
executable) is available in the Indy lab in
~geoff/MTH517/WordFinisher.
The implementation consists of these files:
WordFinisher.cpp
- The driver program, that deals with screen handling.
boolean.h
- A simple Booean type definition.
simplestring.h
- A simple string type definition.
linkedlistclass.h
- The header file of the linked list class.
linkedlistclass.cpp
- The implementation of the linked list class.
wordusage.h
- The header file of the word usage class.
wordusage.cpp
- The implementation of the word usage class.
WordFinisher and
understand how it works, before you can do this assignment.
WordFinisher, in terms of
the number of words stored and their average length.
RecordUse and
GetPossibleWords.
Work out the asymptotic time requirements for these two functions,
in terms of the number of words stored.
RecordUse
and GetPossibleWords (in terms of the number of words
stored).
Better asymptotic time requirements are more important than better
asymptotic space requirements.
saw 1 some 1 soon 1 that 2 thing 3 this 2
wordusage.h
and wordusage.cpp at least, and may choose to use more
files (as the initial version does).
MTH517/WordFinisher off your home directory on the
Indy lab machines, by 6:15pm on 28th March.
You must submit a document (word processed or equivalent - hand written
documents are for the computer illiterate), containing:
(a) the space and time analyses for the initial program;
(b) a short description of the new data structure;
(c) the picture of the data structure for the usage history given above;
(d) the space and time analyses for the new program;
to the instructor or the teaching assistant, by 6:15pm on 28th March.
Your work will be assessed on: