COSC-052 Project 4

COSC-052: Computer Science II

Project 4
Spring 2013

Due: Tue, Apr 16 @ 5 PM
10 points

A map, associative array, dictionary, or associative list is an abstract data type for storing key-value pairs. A key is a unique identifier for a value, which could be a simple or complex type. In Project 1, the id was a key for events. In Project 2, the id was a key for bikes. With a map, keys and their values are stored as two separate objects. Maps let us store and retrieve objects based on their keys.

Key-value pairs are a powerful way to represent information. As one example, notice that an athlete's number is a unique key with his or her name being a value. In this example, the key is an integer and the value is a string. As another example, a pope's name is a unique key with his personal name being a value. In this case, both the key and value are strings. In a dictionary, the word is the key, whereas the word's definition is its value. Both are strings.

There are many information formats and data structures based on the notion of key-value pairs. Javascript Object Notion (JSON) is based on key-value pairs. In the C++ Standard Library, there is the map class. In boost, there is the Property Map Library. In the Java Collections Framework, there are several types of maps derived from AbstractMap. The NoSQL movement includes stores and databases based on key-value pairs. redis is a prime example.

In this project, we will implement the Map class using a doubly-linked list as the underlying data structure. (Technically, this is an association list, but that name is too long.) Programmers using the Map class must be able to specify any type for the key and value, so the Map class must be a template class with two template variables. Naturally, there are methods for adding and removing key-value pairs, for changing and retrieving a key's value, and for performing other functions, such as copying a map, clearing a map, getting the size of a map, and determining whether the map is empty.

For the design for this project, I drew inspiration from Java's TreeMap. Notice that methods that dynamically allocates memory throw bad_alloc, methods that return or remove objects throw NoSuchObject when the container is empty or the key or value is not present in the container.

Consider the following code fragment that stores the names of recent popes and their personal names:

Map<string,string> popes;
popes.put( "Paul VI", "Giovanni Battista Enrico Antonio Maria Montini" );
popes.put( "John Paul I", "Albino Luciani" );
popes.put( "John Paul II", "Karol Jozef Wojtyla" );
popes.put( "Benedict XVI", "Joseph Alois Ratzinger" );
popes.put( "Francis", "Jorge Mario Bergoglio, S.J." );
cout << popes << endl;
cout << popes.get( "Francis" ) << endl;

The output of this code fragment is:

[<Francis: Jorge Mario Bergoglio, S.J.>, <Benedict XVI: Joseph Alois Ratzinger>, <John Paul II: Karol Jozef Wojtyla>, <John Paul I: Albino Luciani>, <Paul VI: Giovanni Battista Enrico Antonio Maria Montini>] Jorge Mario Bergoglio, S.J.

Consider the following fragment that stores information about some of the delivery bikes from Project 2:

Map<string,string> b1, b2, b3;
b1.put( "name", "Trek Transport+" );
b1.put( "gears", "8" );
b1.put( "capacity", "80" );
b2.put( "name", "Johnny Loco Cargo Cruiser" );
b2.put( "gears", "8" );
b2.put( "capacity", "75" );
b3.put( "name", "Kona Minute" );
b3.put( "gears", "8" );
b3.put( "capacity", "70" );
cout << b1.get( "name" ) << endl;
cout << b1 << endl;

The output of this code fragment is:

Trek Transport+
[<capacity:80>,<gears:8>,<name:Trek Transport+>]

Finally, we can create a map of maps. Consider the following example that stores the three previous maps of bike information in a map with the bike ID as the key:

Map< string,Map<string,string> > bikes;
bikes.put( "D01", b1 );
bikes.put( "D02", b2 );
bikes.put( "D03", b3 );
cout << bikes.get( "D01" ).get( "name" ) << endl;
cout << bikes << endl;

The output of this fragment is:

Trek Transport+ [<D03: [<capacity: 70>, <gears: 8>, <name: Kona Minute>]>, <D02: [<capacity: 75>, <gears: 8>, <name: Johnny Loco Cargo Cruiser>]>, <D01: [<capacity: 80>, <gears: 8>, <name: Trek Transport+>]>]

For this project, we will also implement an iterator. Iterators let programmers iterate over the elements in a collection. We will implement a bidirectional iterator, which provides forward and backward iteration through a collection. Conceptually, an iterator is positioned before the first element, after the last element, or between two elements. Methods retrieve the next or previous element and indicate whether such elements exist. I based the design of MapIterator<string,string> on Java's ListIterator.

Put simply, an iterator is an encapsulation of a pointer. As you know, a pointer must point to a node, it cannot point between nodes, and so we must use Boolean flags to indicate when the iterator has iterated over the first and last nodes. For example, the pointer of an iterator points to the last node of the doubly-linked list of the map both before and after the iterator iterates over that element. Therefore, to distinguish between these two states, a Boolean variable indicates when the iterator is at the end of the map. We will discuss the details of iterators in lecture.

The following code fragment illustrates how to iterate over the map of popes.

MapIterator<string,string> mi = popes.getIterator();
while ( mi.hasNext() ) {
  cout << mi.next() << endl;
} // while

The output is:

Jorge Mario Bergoglio, S.J.
Joseph Alois Ratzinger
Karol Jozef Wojtyla
Albino Luciani
Giovanni Battista Enrico Antonio Maria Montini

To grade your project, I'll drop a main function into your directory and compile. main will test all aspects of all of your class. As a consequence, it is imperative that you test all of your methods thoroughly, preferably as you're developing them. It is imperative that you follow my design.

Getting Started

Overloading the stream insertion operator for a template class requires some forward declarations and some funky, unintuitive syntax. I put a zip file on cs-class that contains all of the .h files you need for the project. To copy the zip file to your current directory, type:

cs-class% cp ~maloofm/cosc052/p4.zip ./

To unzip the file, type:

cs-class% unzip p4.zip

This will create a new directory named "p4m", which you can rename. I used this name so it wouldn't overwrite anything in case you have a directory named p4.

Instructions for Electronic Submission

At the top of the file main.cc (or the file containing the main function), place the following header comment, with the appropriate substitutions:

/*
 * COSC-052 Project 4
 * Name: <your name>
 * ID: <GoCard ID>
 * E-mail: <e-mail address>
 * Instructor: Maloof
 *
 * In accordance with the class policies and Georgetown's Honor Code,
 * I certify that, with the exceptions of the class resources and those
 * items noted below, I have neither given nor received any assistance
 * on this project.
 */

You'll be submitting p4 exactly like you submitted p3. If you need to include a message about your submission, then place the message in a file named README. Place the README file in the project's directory.