Project Week 3: Auto Complete
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.
You must implement a
ListMap<K, V> class that implements the
interface. The class must have one attribute
private final List<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.
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
Map with one entry with a key of 't' and a value of a node representing
a trie containing "rie".
must have one private attribute:
private final Node root that is
the root of the tree. The static inner class,
Node contains a
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:
allNonPrefixMatches(String substring)to the interface. This method returns all strings that contain the substring passed as an argument.
This laboratory assignment, developed by Dr. Chris Taylor.