Autocomplete Design Document v1.1

Program Description

Purpose

The tool autocomplete will help provide users with various autocompletions of words in different use cases:

(Batch mode)

1. In the case that a whole text file of prefixes is given, the tool will retrieve a specified number of possible completions, list the first N completions, and report the number of total completions for each prefix given.

(Interactive mode)

2. In the case that the user is typing interactively and there are more than one possible completions for the current prefix at the time "tab" is pressed, the tool will display up to 10 possible completions of the word. The tool will also allow the user to continue typing in autocomplete mode while updating the display of possible completions in real time.

3. In the case that the user is typing interactively and there is only one possible completion of a prefix, the tool will automatically complete a word entered by a user and allow the user to continue typing.

Modes

1. Interactive Mode

   Given a prefix typed by the user, the tool will automatically complete the word if the prefix only has one possible completion. If the user presses the Tab key, the tool will display a list of up to 10 possible completions of the prefix (if there are over ten possibilities, will indicate that there are too many options) from which the user can either select, or continue to type.

2. Batch Mode

   Given a file containing a list of prefixes, provides the total number of completions available for each prefix. If prompted, will also produce all the possible completions for each prefix, up to a configurable maximum.

General Method

• Requires that a collection of words (typically "all" the words in the English language) are pre-loaded into the Redis server.
• For testing purposes, the tool must also allow these words to be loaded from scratch when the tool starts running by parsing a dictionary.
• The collection of all words will be provided by a dictionary, stored as a trie in a redis server.

Interface

Interactive Mode

To enter interactive mode, simply run ./autocomplete with no arguments or files attached.

Functionality occuring passively as the user types in the shell:

• After any letter is typed or deleted, the current line in the shell will be pulled. Starting at the end of that line, ignoring special characters, the string after the most recent space character will be passed to get_valid_children and the resulting prefix struct will be stored.
• If the resulting prefix has only one valid child (including itself), the string mentioned above will be deleted from the end of the line and replaced by that valid child.

Active functionality, requiring specific user request:

• If a tab input is received, display (!!! How this display works is still being determined by the shell team !!!) the first 10 (by length, then alphabetization) children returned by get_valid_children above. If there were more than 10, also display a ... to indicate this. If there were none, display a message and allow the user to exit the 'selection' display with tab or esc.
• The user then either selects (!!! Again, how this is done is still being determined !!!) one of the displayed options, or exits the selection with tab or esc.

Both of the preceding functionalities continue until the user exits the shell.

Example Scenario: Jane Doe

• Jane Doe opens the tool by running ./autocomplete. Because she did not include any flags or files, the default mode is interactive mode. She starts typing "I like amphibi". When she hits the "o" key, the word she has been typing "amphibio" is automatically completed for her: "amphibious", and her sentence now looks like "I like amphibious".

• Jane continues to type the rest of her sentence: "I like amphibious cre", and realizes that she is not sure how to spell "creatures". She hits the Tab key. The screen displays the first ten possible completions, which includes the word "creature". She selects this word and continues to type.

• If she had misspelled creature and added two more letters, 't' and 'u', to her sentence: "I like amphibious cretu", the autocomplete would function like this if she presses the Tab key again: The screen displays "No possible completions. Keep typing or press CTRL+H for more options." If she presses CTRL+H, one of the options could be to add "cretu" to the dictionary, or to run spellcheck on "cretu". Jane doesn't do either, but rather gives up and closes the tool.

• Jane decides to reopen the tool by running ./autocomplete. She starts typing a sentence, "My favorite animal is the giraf", but stops typing because she forgets whether there are two or one f's in "giraffe". She hits the tab button. On the screen, she then sees a list of words: "giraffe, giraffes, giraffish" (each separated by a newline, specific formatting details to be determined later). Jane uses the arrow keys to select "giraffe", then hits enter. Her sentence is finished for her: "My favorite animal is the giraffe".

Batch Mode:

To enter batch mode:

• Run ./autocomplete with one (or optionally two) ints, and one (or optionally two) files.
• First flag indicates whether word options will additionally be displayed as opposed to just number of options. Mandatory, as the presence of this argument will also indicate that batch mode is desired.
• Second flag sets the number of words that will be displayed, assuming the flag above enables their display. Optional, as a default value is available.
• First file is the input file to be parsed by batch mode. Not an argument, piped in as usual via terminal. Mandatory.
• Second file is the output file to recieve the information returned. Likewise not an argument, but piped in as usual via terminal. Optional, as the output will default to stdout.

Formatting of Input and Output

• Input follows prefix\nprefix\nprefix style with a newline following each prefix. Non-letters will be ignored entirely, and not end the prefix.
• Output will be formatted as prefix: num_completions [completion1, completion2, ... completionN]\n
• (With the bracketed words' presence determined by the first flag above, and N by the second)

Example Scenario: John Doe

• John Doe is playing a word game against his friends. The players are given a list of prefixes and are awarded points for each complete word they can come up with. John decides to cheat. He types up the list on his computer, and saves it as "list.txt". He opens the autocomplete tool by running "./autocomplete -0 list.txt". The screen then displays his list back to him, but next to each prefix there is a number (total possible complete words) and up to ten words next to it.
• John wants to see more than ten words after each prefix, so he runs "./autocomplete -0 -20 list.txt". He then sees the same results, but now with up to 20 complete words after each prefix.
• John looks at his results and sees a lot of really rare words that not many people would recognize. He knows that if he submits all of them, he will probably be suspected of cheating. John, having cheated in this game before, has saved his own version of a dictionary which does not include a lot of exotic or overly advanced words. He wants to see what possible completions the prefixes have in this custom dictionary. He runs "./autocomplete -0 list.txt mydict.txt". On his screen, he now sees the possible completions for the list, but it only includes words that come from his own custom dictionary. John is happy with the results, so he writes them down and submits his answers. Nobody knows that he cheated, and John wins the game. He doesn't get anything in return though, just the knowledge that he cheated on a silly word game.

Implementation/Functions (Baseline)

Refer to the Trie Team's Design Document for the trie_t data structure and other baseline trie operations, as well as the API Team's Design Document for several more advanced functions such as get_valid_children etc.

Class: Dictionary (Defined elsewhere, noted here for reference)

Data Types:

• trie_t* dict

Functions:

• char** list_valid_children(char* pf, trie_t* dict, int tot_children)
  • lists all the children of a prefix, if they are complete words
• trie_t* define_new_word(char* pf, trie_t* dict)
  • adds a word to the dictionary

Class: Prefix_suggestions

Prefix_suggestions_t Data Structure:

• char* prefix
• char** possible_completions
• int* tot_completions

Functions:

• int prefix_exists?(char* pf, trie_t* dict)
  • checks if a given prefix exists in the dictionary trie

Mode: Shell

Local variables:

• prefix* current_entry

Functions: (draft)

• get_current_variable (not defined here but the primary function used)
• enter_selector

Mode: Batch

Functions:

• void init_parser()

• void parse_next_prefix()

  • Runs list_valid_children and put correct data in prefix_suggestions_t struct

• void print_tot_completions(int max_words_shown)