lab 6: 15-113 Fall 2000

Lab 6: Implementing a Map with a BST

Due Date: Mon 11 Dec, 23:59. Note the change from the usual Tuesday!

Background

Lab 6 will provide you an opportunity to work with binary search trees (BSTs). You are to implement a map (a container that allows associations between keys and values) via a binary search tree. Similar to Lab 3, you may want to implement the destructor/copy constructor/assignment operator after you've gotten everything else working. Our associations are between andrew-ids (strings) and student information (name and year). An interesting feature of maps is the overloading of the [ ] operator (called the indexing operator) to allow easy access to the value mapped to a key. The textbook discusses maps on pages 251-252. The Set mastery problems can be effectively modeled on this assignment.

What You'll Need

Download the lab6.zip file from the 15-113 course web site. Save the zip file to your temp directory and unzip the files. You should see the following files:

lab6.mcp
map.cpp
map.h
map-test.cpp
rand-stu.txt - the full 542 student file
small-stu.txt - a small file to test things initially
student.h - a slightly different version than the one used for lab 4 (i.e., it doesn't store the andrew id internally anymore)

Assignment

The operations you are to implement are the following:

operator[ ] - takes a key and returns a reference to the value associated with the key in the map (if it is in the map); creates a default value associated with the key otherwise.
Remove - removes the key and associated value from the map (prints a message if the key is not found).
InDomain - returns true if key is in set of currently mapped keys; false otherwise
PrintDomain - prints currently mapped keys in alphabetical order
operator<< - displays the map (key->association) in level order, one entry per line

The current driver exercises some functionality. Make sure that you write code that exercises all the commands present in the assignment.

Sample Output

The output of operator<< on the initial tree created from small-stu.txt:


ubardak -> ULAS BARDAK 4
chiang -> MENG-YANG CHIANG 4
ymb -> YEVGENY BOKK 4
balaji -> BALAJI SARPESHKAR 2
minsun -> MINSUN JEONG 1
alwong -> ANGELINE WONG 2
flo -> FRANCIS LO 1
rlie -> RIDY LIE 1
dwexler -> DJANGO WEXLER 2
fning -> FRANCES NING 3
nbr -> NITHIN REDDY 2
sss -> SEEMA SHAH 3
danielf -> DANIEL FERNANDEZ 1
jsaks -> JEVAN SAKS 2
clt -> CHRISTOPHER TUTTLE 2
ddf -> DMITRY FRUMKIN 3
ggp -> GEOFFREY PLITT 2
kgm -> KEVIN MILANS 3

Handing in your Solution

Your solution should be in the form of a .zip file. When we grade your solution we will unzip the folder and execute the project.

Your Solution zip file must contain (only) the following files

lab6.mcp
map.cpp
map.h

Note that there's no need to submit your map-test.cpp. I have my own test driver to run against your code...

Use the Intro Programming dropoff form to submit your zip file.