Finish the contain(key) and remove(key) in the ArrayDictionary class (50pt)

Use folder dictionary.

1. (20pt) Finish the contain() function in src/ArrayDictionary.h with unit tests

bool contain(KeyType &key) override {
    return false;
}

This function returns true if the dictionary contains an entry with the given key, and false otherwise. This given key is the key of the entry, not the hash key in the dictionary.

Finish the unit test for contain() in test/unit_test.cpp

TEST(dict, contain) {
    // homework
    ASSERT_TRUE(false); // placeholder
}

The following cases MUST be tested to receive any point.

Allow me repeat: If any of the following cases is missing, no point is given for this problem.

OK to split the above function with each set of tests:

set 1:

• empty dictionary<int, int>, contain returns false with key -1
• empty dictionary<int, int>, contain returns false with key 0
• empty dictionary<int, int>, contain returns false with key 1

set 2:

• dictionary<int, int>, capacity 1, init values {0:103}, key=2 returns false
• dictionary<int, int>, capacity 1, init values {0:103}, key=0 returns true

set 3:

• dictionary<int, int>, capacity 2, init values {0:103, 1:105}, key=0 returns true
• dictionary<int, int>, capacity 2, init values {0:103, 1:105}, key=1 returns true
• dictionary<int, int>, capacity 2, init values {0:103, 1:105}, key=2 returns false
• dictionary<int, int>, capacity 2, init values {0:103, 1:105}, key=3 returns false

set 4:

• dictionary<int, int>, capacity 3, init values {0:103, 1:105}, key=3 returns false
• dictionary<int, int>, capacity 3, init values {0:103, 1:105, 2:206}, key=1 returns true

set 5:

• dictionary<int, int>, capacity 3, init values {0:103, 1:105, 2:206, 4:407}, key=1 returns true
• dictionary<int, int>, capacity 3, init values {0:103, 1:105, 2:206, 4:407}, key=4 returns true
• dictionary<int, int>, capacity 3, init values {0:103, 1:105, 2:206, 4:407}, key=7 returns false
• dictionary<int, int>, capacity 3, init values {0:103, 1:105, 2:206, 4:407}, key=8 returns false

2. (20pt) Finish the remove(...) function in src/ArrayDictionary.h

bool remove(KeyType &key) override {
    // homework
    return false;
}

As the name indicates, remove(key) deletes ALL entries with the provided key. This include all entries in the chain whose keys match the given key but mapped to the same hash key.

Remove(key) returns true when any entry was removed, false if none.

3. (10pt) Finish the remove(key) function in src/ArrayDictionary.h with unit tests

Add unit tests to your remove(key) function. The following cases need to be tested:

• empty dictionary
• key exists in a dictionary that has no collision
• key does not exists in a dictionary that has no collision
• key exists in a dictionary that has collision, key is in the collision.
• key does not exists in a dictionary that has collision

You can have these in separate TEST() or if you choose to have one TEST(), please add comments indicating which case of these are being tested.

Same rule as problem 1. If any of these cases is missing, 0pt is given for task 3.