About the System: Way is a GPS navigation system that provides real-time directions. The first thing that a user of Way must do is enter her/his destination address. This is not difficult on some platforms (e.g., those that have keyboards) but can be quite awkward on a wireless telephone which only has a numeric keypad.

Some applications that run on wireless telephones require multiple key presses for some letters. That is, the '2' key is pressed once for an 'A', twice for a 'B', and three times for a 'C'; the '3' key is pressed once for a 'D', twice for an 'E', and three times for an 'F'; etc... This would be both a tedious and time-consuming way to enter street names.

StreetSmarts is designed to make it easier to enter street names on a numeric keypad. It uses the correspondence that is printed on the keypad directly. That is, the '2' key represents the three letters 'A', 'B' and 'C', the '3' key represents the three letters 'D', 'E' and 'F', etc... This greatly reduces the number of required key presses. The only drawback of this approach is that the data entered by the user is ambiguous.

Hence, the system will first ask the user to enter the first n letters in the name of the street. It will then present (on the LCD display) a list of all of the streets that start with those n letters.

Summary: You must develop a "search engine" that finds all of the street names that begin with the first n letters that the user enters.

Approach: One way to proceed is to create a sorted list of all of the street names and then use a binary search to find the first street in the array that begins with those letters. In general, this is a reasonable approach. However, it will not work for StreetSmarts because each key corresponds to three or four letters, not one. So, if the user enters 2-2-3 this could correspond to the letters: AAD, AAE, AAF, ABD, ABE, etc... Hence, many searches would have to be conducted.

Your implementation must, instead, be based on hashing. Your hash function must be based on the telephone keypad correspondence illustrated below:

Description: This is the main module. It must make use of one command line argument that will contain the number of characters that will be used to hash each street name.

Requirements: After processing the command line argument, this module must:

1. Construct an empty StreetSmartsTable object.
2. Read the list of street names from the file streetnames.txt and put them in the StreetSmartsTable.
3. Repeatedly prompt the user to enter the first n characters of a street name as they would on the telephone keypad (i.e., as numeric digits) and display all appropriate street names (i.e., all street names with that hash value). For example (under Unix or OS X):

   $ StreetSmartsDriver 5
   
   Enter the first 5 characters: 64559
   Milkweed
   Milky
   Milky Way
   Millway
   Millwheel
   Millwood
   Millwood Pond
   Millwood Pond Drice
   Millwoods
   Millwright
   
   Enter the first 5 characters: 223
   Abe
   Ace
   Bad
   
   Enter the first 5 characters: ^D
   

   (Note: Each street name should be entered on a single line. The loop should terminate when the user enters an "End of File" character.)

4. Delete all objects it created before terminating.

Description: The StreetSmartsTable class is, essentially, a hashmap that uses chaining to resolve collisions.

Methods: It must have the following public methods:

/**
 * Explicit Value Constructor
 *
 * @param digits  The number of digits to use in the key
 */
StreetSmartsTable(int digits)



/**
 * Destructor
 */
~StreetSmartsTable(void)



/**
 * Returns the first Node in the chain that has the
 * given key
 *
 * @param key   The key (i.e., the digits entered at the keypad)
 */
Node *get(int key)




/**
 * Put a street name in the table
 *
 * @param name  The name of the street
 */
void put(char *name)


  

It may have other public and private methods as well.

Hash Function: The characters '0', '1', '2', ... must be converted to a 0, 1, 2, ...

The characters 'A', 'B' and 'C' must be converted to a 2, 'D', 'E', and 'F' must be converted to a 3, etc... (Note: You must ignore the case of the letter. So, 'a', 'b' and 'c' must also be converted to a 2.)

Spaces must be converted to a 1 and all other characters must be converted to a 0.

Each digit in the string must represent a digit in a base-10 number. That is, the value of the right-most character must be multiplied by 10⁰, the value of the second right-most character (if there is one) must be multiplied by 10¹, etc...

For example:

String	Hash
Bad	223
One	663
At	28
I	4

Note: Be careful if you use the pow() function as it returns a floating point number and if you cast the result to an int you may not always get what you want.

A Node Class: Obviously, you will need a Node class of some kind for your "chain". You may implement this class as you see fit.

A Chain Class: You may or may not decide that you need a class for the "chain"

Other Classes: You may create other classes you deem appropriate/necessary.