Introduction

Google is still hiring! Last time you implement a deque resume container to help Google HR deal with the large amount of resumes, but HR complains that they are tired of searching resumes one by one. They want to have a more convenient container to help them. So this time you are going to use BST to implement a more efficient BSTMap container for them.

In this lab, you are going to implement a Map container based on the BST implementation that you have learned in the lecture. For details of BST, please refer to the lecture notes. The BSTMap you are going to implement is actually a BST in which each node has a key and a value. Keys are sortable data, and values are data tagged with their keys.

Following external links for similar data structures may be useful to you:

• C++ Reference: C++ Map ;
• Wikipedia: Associative array;

Overview

The descriptions of classes and members in classes are as follows:

• Structure Pair: Data stored in a MapItem.
  • K key:
  Key of MapItem
  • V value:
  Value of MapItem

• Structure MapItem : Structure defined in Class BSTMap.
  • Pair data:
  Data in MapItem.
  • BSTMap left:
  Left sub-tree.
  • BSTMap right:
  Right sub-tree.
  • MapItem(const MapItem&):
  Copy constructor of MapItem. Notice that (BSTMap) sub-tree's copy constructor will be invoked.
  • ~MapItem():
  Destructor of MapItem. Notice that (BSTMap) sub-tree's destructor will be invoked.
  • MapItem(const K& k, const V& v):
  Constructor.

• class BSTMap:
  • MapItem* root:
  Pointer to the root of BST.
  • BSTMap() :
  Constructor.
  • ~BSTMap() :
  Destructor: delete root; all sub-trees will be deleted recursively.
  • BSTMap(const BSTMap& bst):
  Copy constructor; all sub-trees will be copied recursively.
  • const Pair& find_min():
  Return the data pair whose key is minimum in BSTMap.
  • const Pair find_max():
  Return the data pair whose key is maximal in BSTMap.
  • is_empty():
  Return true if BSTMap is empty.
  • contains(const K& key):
  Return true if the given key is in the BSTMap.
  • void remove(const K& key);:
  Delete item corresponding to the given key.
  • void insert(const K& key, const V& value):
  Insert an item into BSTMap.
  • V& operator[] (const K& key) (TODO):
  Indexing operator. Return a reference to the value corresponding to the given key in the BSTMap. If the provided key does not exist, print an error message "Key is not in BSTMap" to std::cerr, then terminate the program by exit(-1). In practice, one should check if the key is contained in the BSTMap before calling this indexing operator.
  • V operator[](const K& key) const (TODO)::
  const version of the indexing operator. Semantics is identical to the non-const version, the only difference is this method returns a value, not a reference.
  • BSTMap& operator=(const BSTMap& bst) (TODO):
  Assignment constructor, similar to copy constructor. Before assignment, you need to first check whether this != &bst, if the two pointers are equal then you need to do nothing. You also need to clear the original Map before assignment, we will check memory leak in this lab.
  • int size() (TODO):
  Return the number of Items in the BSTMap.
  • operator<< (TODO):
  Print the information of the BSTMap to the stream. You should use In-Order Traversal to traverse the BST and print them in the format "{key1:value1} , {key2:value2}..." (Please refer to the example outputs). You can assume operator<< is alreay overloaded for all types of keys and values.
  • void clear() (TODO):
  Delete all the things in BSTMap recursively.

[Hint]: While doing your own implementation, you can reuse some of the provided functions to ease your work. The implementation uses recursion a lot. You can read and learn from the provided functions.

Lab tasks

1. Finish the TODOs in bstmap-todo.tpp.
2. Compile the project. Notice we add sanitizer in Makefile, if your computer does not support you can delete -fsanitize=address flag to suppress error like cannot find -lasan.
3. Run lab8, check with the expected output below:
4. LA5 is not graded in this lab, all other sessions will be graded.

Create resume container for position: C++ developer.

Applicants of C++ developer:
{Amelia:CUHK} , {David:HKU} , {James:HKUST} , {Yang:HKUST}

Merge with C developers applications.
Applicants of C & C++ developer:
{Amelia:CUHK} , {David:HKU} , {James:HKUST} , {Oliver:PolyU} , {Tony:HKUST} , {Wang:CUHK} , {Yang:HKUST}
We have 7 candidates.

Some candidates fail in the interview
The remaining C & C++ developer candidates:
{Amelia:CUHK} , {James:HKUST} , {Oliver:PolyU} , {Tony:HKUST} , {Yang:HKUST}
We have 5 candidates.

Create a backup of applications.
Backup applications:
{Amelia:CUHK} , {James:HKUST} , {Oliver:PolyU} , {Tony:HKUST} , {Yang:HKUST}

HR wants to search candidates' information
Oliver is graduated from PolyU
Yang is graduated from HKUST
Amelia is graduated from CUHK

Oh! HR accidentaly delete all the application forms
We have 0 candidates.

Don't worry, we have a backup. Let's see whether the information is correct.
Amelia is still a candidate? [Yes]
James is still a candidate? [Yes]
Wang is still a candidate? [No]
Tony is still a candidate? [Yes]
David is still a candidate? [No] 

Submission Deadline and Guidelines:

The due date and time will be 10-min after your lab session. You are supposed to upload the following files in an archive to ZINC:

- bstmap-todo.tpp

You can submit your codes multiple times by the deadline. Only the last submission will be graded.