►Fundamentals II (Honors)
Introduction to Class-based Program Design
▼Assignments
►7 2/  28:   Trie-d and true Java
On this page:
7.1 Setting up Eclipse
7.2 Warmup:   Simple data and method definitions
7.3 Reprise:   String Dictionaries
7.4 Try and Trie Again:   A New Kind of Dictionary
7.4.1 Extra:   “Textonyms”
7.4.2 Extra:   Adding words with textonyms, and maintaining order
5.92
    ← prev  up  next → 

7 2/28: Trie-d and true Java

Due: 2/28 at 11:59pm.

Language: Java

7.1 Setting up Eclipse
7.2 Warmup: Simple data and method definitions
7.3 Reprise: String Dictionaries

Think back to the 1/27: Dictionaries lab, where we defined [Dict V] as an interface for looking up values (of any type V) based on numeric keys. In this assignment, you’re going to translate that dictionary to Java — though we’ll specialize our code to when V is String. As a reminder, here’s the interface definition, written in Java:

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);

}

Note that we have removed the assumption for lookup that the key is in the dictionary. It turns out that, unlike in class/0, Java forces us to implement lookup for all classes that implement the Dict interface.

Since you can’t leave the method unimplemented, you can just define the method to return an error when there is no key. In Java, you can return an error with a statement like this:

throw new RuntimeException("Your error message here");

Exercise 1. Design one or more classes to implement the IStringDict interface in Java, using the “list-of-pairs” design from lab 1/27: Dictionaries. (Make sure to translate the data definition to the Java syntax first, and substituting IStringDict for [ListDict V] everywhere.)

You may find the compareTo method on Strings useful for this exercise. The compareTo method takes a stringActually, compareTo takes any object that implements the Comparable interface; most built-in Java objects, including Strings, implement this interface. and returns an int. This number is negative, zero, and postive respectively when the given string is less than, equal to, or greater than this.

7.4 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.

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”. In the Dicts above, the key was a single, arbitrary number, and the values were arbitrary strings. 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.

Our data structure, then, should be a dictionary of nested dictionaries. Specifically, we want something like the following:

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;

  IT9DictData         digit2, digit3;

  IT9DictData digit4, digit5, digit6;

  IT9DictData digit7, digit8, digit9;

 

  // Constructs a new dictionary containing the given word and nothing else

  WordT9Dict(String word) { ... }

}

class EmptyT9Dict implements IT9DictData { ... }

To actually use this dictionary, we need one more class that implements the IStringDict interface:

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 a

  // ILoNum (though you'll have to design classes that implement ILoNum!)

  ILoNum toList(int num) {

    return this.toListHelp(num, new MtLoNum());

  }

  ILoNum toListHelp(int num, ILoNum leadingDigits) {

    if (num == 0) {

      return leadingDigits; // We're done

    } else {

      int ones = num % 10; // Computes num modulo 10, i.e. the units digit

      int rest = num / 10; // Does integer division, which truncates

      return this.toListHelp(rest, new ConsLoNum(ones, leadingDigits));

    }

  }

 

  // ...  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.

}

You should also build an example T-9 dictionary such that the following tests pass:

class ExampleT9Dict {

   IStringDict theDict = ...;

   boolean testDict(Tester T) {

     return t.checkExpect(this.theDict.lookup(43556), "HELLO") &&

            t.checkExpect(this.theDict.lookup(4653),  "HOLE") &&

            t.checkExpect(this.theDict.lookup(2276),  "BARN");

   }

}

7.4.1 Extra: “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 and textonyms.

7.4.2 Extra: Adding words with textonyms, and maintaining order

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, following tests should pass:

class ExampleT9Dict {

   boolean testDict(Tester T) {

     IStringDict mtDict = new T9Dict();

     IStringDict addedHome = mtDict.set(4663, "HOME");

     IStringDict addedGood = addedHome.set(4663, "GOOD");

     IStringDict addedGone = addedGood.set(4663, "GONE");

 

     return t.checkExpect(addedGood.lookup(4663),  "GOOD") &&

            t.checkExpect(addedGood.lookup(46630), "HOME") &&

            t.checkExpect(addedGone.lookup(46630),  "GONE") &&

            t.checkExpect(addedGone.lookup(466300), "GOOD");

   }

}

    ← prev  up  next →