CS Project 2 Solved

   Goal:
To gain a better understanding of search algorithms and symbol tables by
implementing an autocompletion engine.


   Background:
In order to make typing on a mobile device quick and easy, an autocomplete
feature is commonly implemented to try to guess what word a user wishes to type
before they are finished. Such a feature requires extensive use of search
algorithms. Here, you will be building the backend of an autocomplete engine
(i.e., you won't gathering any user input).


   Specifications:
* The default class is `./app/src/main/java/cs1501_p2/App.java`. The provided
  `App.java` simply provides the autocomplete engine with a few characters and
  prints out the predictions generated. In order to get this running, you will
  first need download a copy of the English dictionary that you will use for
  this project from
  [here](http://people.cs.pitt.edu/~nlf4/cs1501/handouts/dictionary.txt) and
  place it in your `./app/src/main/resources/` folder. Placing it here will
  make it available to your programs via the relative path
  `build/resources/main/dictionary.txt` when you run `./gradlew run`.
    * **Do not** add this file to your git repository, however! (i.e.,
        **do not** run `git add dictionary.txt`).
    * Note that Gradle will automatically copy this file to
        `./app/build/resources/main/` when you run `./gradlew run` (hence
        why the path to read this file is
        `"build/resources/main/dictionary.txt"` in `App.java`.  A similar thing
        is done for `./gradlew test`, moving from
        `./app/src/test/resources/dictionary.java` to
        `./app/build/resources/test/`.
    * Also note that the provided testing dictionary is much smaller than this
        one.

* In order to get your project to actually compile and run, however, you will
  need to implement 3 classes:
      * `DLB` in `./app/src/main/java/cs1501_p2/DLB.java` which implements
      `Dict`
    * `UserHistory` in `./app/src/main/java/cs1501_p2/UserHistory.java` which
      also implements `Dict`
    * `AutoCompleter` in `./app/src/main/java/cs1501_p2/AutoCompleter.java`
      which implements `AutoComplete_Inter`.

* For `DLB`, you must implement a De La Briandais (DLB) trie data structure (as 
  described in lecture) to use in your project. This class will be used to
  store the dictionary of English words.`DLB` must be all your own code (e.g.,
  you cannot use the Java LinkedList, you must implement your own linked-list).
  You must use the `DLBNode` defined in
  `./app/src/main/java/cs1501_p2/DLBNode.java` to construct the DLB. You cannot
  modify `DLBNode.java`. You must implement all of the methods of `Dict` as
  defined in `Dict.java`, specifically:

    * `public void add(String key);`
    * `public boolean contains(String key);`
    * `public boolean containsPrefix(String pre);`
    * `public int searchByChar(char next);`
    * `public void resetByChar();`
    * `public ArrayList<String> suggest();`
    * `public ArrayList<String> traverse();`
    * `public int count();`

  For descriptions of what these methods should do, refer to the JavaDoc
  comments in `Dict.java`. `DLB` must return the results of `suggest()` in
  ascending order by their character value ("ASCIIbetical" order).

  This class must be all your own code. You cannot use any code from the
  textbook authors or the JCL in constructing the DLB. The only exception is
  tha tyou can use an ArrayList to construct the return values for `suggest()`
  and `traverse()`.

* `UserHistory` will be used to keep track of what words the user has actually
  selected, and how many times that word has been selected. For `UserHistory`,
  you are free to use whatever approach you choose to implement `Dict`. You are
  free to use any JCL classes or code provided by the textbook authors to
  implement `UserHistory`. Your implementation of `UserHistory` *must* have the
  same **worst-case** asymptotic runtime for all operations as the DLB (as
  described in lecture). Further, as an additional requirement, `UserHistory`'s
  implementation of `suggest()` must produce up to 5 words that the user has most
  frequently selected based off of the given prefix (in order). E.g., if the user
  has selected "free" 5 times in the past, "frequent" 3 times, and "frustration"
  1 time in the past, after entering 'f', then 'r', `suggest()` should return
  an ArrayList containing "free", "frequent", then "frustration".

* `AutoCompleter` will bring all of this together to form the API of your
  autocomplete engine. First, you will need to have a constructor that accepts
  2 String filenames. The first is the name of a file containing the English
  dictionary, the second the name of a file containing saved user history 
  information. You should also implement an overloaded constructor that
  supports only the first argument (the English language dictionary). Both of
  these constructors should create `DLB` and `UserHistory` objects as
  attributes of `AutoCompleter` (in the case of the latter constructor, the
  `UserHistory` object will be empty).

  There are 3 methods defined in `AutoComplete_Inter`. For `finishWord()`, be
  sure to reset the state of any searches and update the user history
  attribute to reflect the word selected. Note that it may not be based on the
  current search! E.g., you should support the calls:

      * `.nextChar('a')`
      * `.nextChar('b')`
      * `.nextChar('c')`
    * `.finishWord("word")`

  For `saveUserHistory()`, you are free to adopt whatever approach you want
  for saving the state of the `UserHistory` object to a file. The save file
  does not need to be a text file or human-readable. Saving and loading the
  user history should have a O(n) runtime (where n is the number of distinct
  words in the `UserHistory` object). **Do not** add any user history save
  state files to your repository!


    Example `App.java` run

An example run of the default `App.java` would proceed as follows:

```
Entered: t
Predictions:
        1: t
        2: ta
        3: tab
        4: tab's
        5: tabbed

Entered: h
Predictions:
        1: thalami
        2: thalamus
        3: thalamus's
        4: thalidomide
        5: thalidomide's

Entered: e
Predictions:
        1: the
        2: theater
        3: theater's
        4: theatergoer
        5: theatergoer's

Entered: r
Predictions:
        1: therapeutic
        2: therapeutically
        3: therapeutics
        4: therapeutics's
        5: therapies

Entered: e
Predictions:
        1: there
        2: there's
        3: thereabout
        4: thereabouts
        5: thereafter

Selected: thereabout

Entered: t
Predictions:
        1: thereabout
        2: t
        3: ta
        4: tab
        5: tab's

Entered: h
Predictions:
        1: thereabout
        2: thalami
        3: thalamus
        4: thalamus's
        5: thalidomide

Entered: e
Predictions:
        1: thereabout
        2: the
        3: theater
        4: theater's
        5: theatergoer

Entered: r
Predictions:
        1: thereabout
        2: therapeutic
        3: therapeutically
        4: therapeutics
        5: therapeutics's

Entered: e
Predictions:
        1: thereabout
        2: there
        3: there's
        4: thereabouts
        5: thereafter
```


   Submission Guidelines:
* **DO NOT** add the `./app/build/` diectory to your repository.
    * Leave the `./app/build.gradle` file there, however

* Be sure to remember to push the latest copy of your code back to your GitHub
    repository before submitting. To submit, log into GradeScope from Canvas and
    have GradeScope pull your repository from GitHub.


   Additional Notes:
* Note that if your user history predictions contain a word that is also
  contained in the dictionary predictions, this word should not be presented
  as a suggestion to the user twice in the same prompt (e.g., the final list
  of predictions in the example above).

* Your program should run in a case-sensitive manner in order to allow for
  easier prediction of proper nouns and acronyms.

* Don't forget to make all of your source files a part of the package 
  `cs1501_p2`!

* The default file to run is `App.java`, you can execute this by running
  `./gradlew run` on Linux or macOS.

* There a number of tests for your classes in
  `./app/src/test/java/cs1501_p2/AllTest.java`. Running `./gradlew test` on
  Linux or macOS will run these tests.

* As always, note that we will be grading your project using different tests
  than those that appear in `./app/src/test`. You are encouraged to write your
  own tests to help ensure that your project is working as specified.


   Grading Rubric:
| Feature | Points
| ------- | ------:
| `DLB` implemented as specified | 35
| `UserHistory` implemented as specified | 35
| `AutoCompleter` implemented as specified | 25
| Proper assignment submission | 5