Lab 8: Auto Complete

Overview

This week you will implement a custom Trie data structure and use it to implement the AutoCompleter interface. The trie data structure is a tree where each node can have an arbitrary number of children.

Assignment

Details

ListMap class

You must implement a ListMap<K, V> class that implements the Map<K, V> interface. The class must have one attribute private final List<Map.Entry<K, V>> entries that is assigned via a one-argument constructor. Note: the constructor should remove any entries in the list passed to the constructor.

Trie Implementation

Implement the AutoCompleter interface using a trie data structure. A trie stores each string as a chain of characters. For example, if the trie contains one string: "trie". Here the root node would be contain a Map with one entry with a key of 't' and a value of a node representing a trie containing "rie". Your class must have one private attribute: private final Node root that is the root of the tree. The static inner class, Node contains a Map<Character, Node> that keeps track of the node's children and a boolean that indicates whether or not the node terminates a entry stored in the trie. strings in the collection passed to the constructor.

Just For Fun

Ambitious students may wish to:

• Add allNonPrefixMatches(String substring) to the interface. This method returns all strings that contain the substring passed as an argument.

Acknowledgment

This laboratory assignment, developed by Dr. Chris Taylor.