Lab 9: Trie-d and true Java
Goals: Work with two implementations of dictionaries
Introduction: String Dictionaries
A dictionary is a data structure that allows us to associate keys with values. (For example, in English, a dictionary associates words with definitions. For another, a phone book associates names with phone numbers.) In general, we probably want an interface IDict<K, V>, parameterized by the types of the keys and values.
Dictionaries are often most useful when they are mutable, so that you can add and remove items from the dictionary. So we’ll need the ability to lookup items and set and/or add new items. Since looking up items may not work if the key is not present, we also need the ability to determine if a key is present.
In this assignment, you’re going to build one specialized implementation of a specific kind of dictionary, where the keys are ints, and the values are Strings: an IStringDict as follows. (I.e., you are not building completely general-purpose dictionaries.)
interface IStringDict { // Returns true if the given key exists in this dictionary boolean hasKey(int key); // Returns the string associated with the given key, if present in this // dictionary, or throws an error if not found String lookup(int key); // Returns a new IStringDict which consists of all the mappings of this // current IStringDict, and with the given key mapped to the given string IStringDict set(int key, String value); }
9.1 Try and Trie Again: A New Kind of Dictionary
Before smartphones had virtual keyboards and Blackberries had physical keyboards, sending text messages required typing words by using only the number keys, with a system known as T-9. Typing a 2 meant either A, B, or C; typing a 3 meant either D, E or F; and so on. Every number represented one of three letter choices, except for 7 which stood for P, Q, R or S, and 9 which meant W, X, Y or Z. So to type "HELLO", you would type 43556, and to type "GOOD" you would type 4663. But how did the phone know which letter the 4 means?
9.1.1 Basic functionality
You task in this problem is to design the data structures that make this work. You need to represent a dictionary (in the English sense) of words, organized by the digits that “spell them out”. Here, the keys, literally, are the digits 2 through 9, but what should the values be?
Suppose the user of your data structure has entered 435 so far. We would like to have a value that represents “all words that at least start with 435”, which includes "HELLO" but also "HELP", "HELM" and "IDLE", among others.
interface IT9DictData { // Returns the complete word, if any, that has been spelled so far String completeWord(); // Returns a new IT9DictData which contains all the same content as this // IT9DictData, and creates a new IT9DictData with the given word and inserts it // at the given digit in this IT9DictData IT9DictData insertWord(int digit, String value); } class WordT9Dict implements IT9DictData { String completeWord; ArrayList<IT9DictData> digitData; // Constructs a new dictionary containing the given word and nothing else WordT9Dict(String word) { ... } } class EmptyT9Dict implements IT9DictData { ... }
In the WordT9Dict class, it will be convenient for the
ArrayList to have ten elements, but where you choose to
ignore the first two, so that when a user types the digit 2,
you’ll look at the value of digitData.get(2) —
To actually use this dictionary, we need one more class that implements the IStringDict interface. Here is your starting point:
class T9Dict implements IStringDict { // The actual contents of the dictionary. Your IStringDict methods should // use this field somehow IT9DictData contents; // You may use the following helper methods to convert a number into an ArrayList ArrayList<Integer> toList(int num) { ArrayList<Integer> ret = new ArrayList<>(); int curNum = num; while (curNum != 0) { int ones = curNum % 10; // Computes curNum modulo 10, i.e. the units digit ret.add(0, ones); // Puts that digit at the *front* of the list curNum = curNum / 10; // Does integer division, which truncates } return ret; } // ... Fill in the rest here ... // lookup, hasKey, and set should take a number and use this.toList() to convert // it to a list of digits, then traverse this.contents using that result. // For now, set() can throw an error if the digit sequence is already // present in the dictionary. }
This T9Dict is a wrapper around IT9DictData, WordT9Dict and EmptyT9Dict —
You should also build an example T-9 dictionary such that the following tests pass:
class ExampleT9Dict { IStringDict theDict; void initTheDict() { this.theDict = ...; } void testDict(Tester t) { this.initTheDict(); t.checkExpect(this.theDict.lookup(43556), "HELLO"); t.checkExpect(this.theDict.lookup(4653), "HOLE"); t.checkExpect(this.theDict.lookup(2276), "BARN"); } }
9.1.2 “Textonyms”
If you try spelling "HOME" and "GOOD", you’ll notice that they both are spelled with the number 4663 (as are "GONE", "HOOD", and other words), so called “textonyms” (words that are T-9-spelled the same, but mean different things). What to do? T-9 texting used the '*' key to distinguish these words, so that "HOME" might be spelled 4663, but "GOOD" is spelled 4663*, while "GONE" is spelled 4663**. We’ll use the digit 0 instead of the '*' key, to keep our dictionary keys numeric.
Extend your data structure to support the 0 digit (you should now use index 0 of your digitData list), and extend hasKey and lookup to support these textonyms. Test your enhancements well. (Hint: you’ll need to manually construct a dictionary containing textonyms, since you can’t yet insert them into an existing dictionary...)
Finally, your initial implementation of set assumed that you would never insert multiple textonyms into your dictionary, but that isn’t a realistic assumption. Extend your implementation of set to handle this case. You should ensure that when you add a textonym to your dictionary, you maintain the textonyms in alphabetical order. That is, the following tests should pass:
class ExampleT9Dict { void testAlphabetizedDict(Tester t) { IStringDict mtDict = new T9Dict(); IStringDict addedHome = mtDict.set(4663, "HOME"); IStringDict addedGood = addedHome.set(4663, "GOOD"); IStringDict addedGone = addedGood.set(4663, "GONE"); t.checkExpect(addedGone.lookup(4663), "GONE"); t.checkExpect(addedGone.lookup(46630), "GOOD"); t.checkExpect(addedGone.lookup(466300), "HOME"); } }
Discussion
This data structure, where the keys are broken up into smaller pieces and then used to guide paths through a tree, is known as a trie (rhymes with “try”, not “tree”). Tries are clearly somewhat specialized in purpose, since not every key type can be split up in such a way, but when they’re applicable, they’re surprisingly efficient. Several well-known object-oriented programming languages actually use tries as their representation for objects! We’ll come back to how languages represent objects near the end of the semester.