Create a map that shall map a student's first and last name to an id. In other words we are mapping a String to an integer. Names shall consist of: - A single array of characters - A combination of rst and last name separated by a space. - The first letter of each name shall be capitalized, the rest is in lower case.

In between each first and last name shall be a space. Every student's name shall map to a single 32-bit integer. All IDs will be strictly above 0.

Keep in mind your program will be graded for both accuracy and performance. For performance, the two operations that will be analyzed: - get(const char *key, int &ret) which retrieves an ID from the given string. - howMany(const char *prex) which returns the number of names that begin with prex.

So far we have learned arrays, pointers, and linked lists. That should be enough to design your data structure. No hashmaps for this problem {they will not solve the prefix problem efficiently. You will be judged on memory footprint as well as performance! To be clear, a HashMap/HashTable implementation will be issued a 0.

Here are some functions that MUST BE INCLUDED:

#ifndef MAP_H #define MAP_H

class Map{ public: Map();

/* Adds (inserts) val with the associated key. * Returns if successful or not. (It is not successful if we are out of * memory, or if the key already exists.) */ bool add(const char *key, int val);

/* Searches for the key. If found it sets ret to the correct val and * returns true. Otherwise, this function returns false. */ bool get(const char *key, int &ret);

/* Returns the size (memory consumed) by this data structure. */ int size(); /* Removes the current value from the Map AND frees up any memory that * it can. * Returns true if there was something to remove, false otherwise. */ bool remove(const char *key);

/ * Returns the number of names with a given prefix. * Ex: If we have {Alex, Alexander, Jennifer, Ronald, Alexis, Jake} then * howMany ("Al") == 3 (THIS COULD BE ANY PREFIX SIZE) */ int howMany(const char *prefix);

/* Frees all memory */ ~Map();

private: char *mStudentKey; int mIDVal;

};

#endif