Cherno hash set assignment for video https://www.youtube.com/watch?v=kQsHF7C-FUY

instructions.md

Compile with:

clang++ -std=c++11 main.cpp -o assignment

Compile tests with:

clang++ -std=c++11 main.cpp -o assignment -DTESTS

Run with:

./assignment

Exmaple:

> clang++ main.cpp -o assignment
> ./assignment
Aapple Aorange Dapple Astrawberry

output:

orange strawberry

main.cpp

#include <iostream>
#include <iostream>
#include <array>
#include <string>
#include <vector>

// Default "hash" function
template <typename T>
struct DefaultHashFn {
    static int hash (const T& item) {
        return int(item.back()) - 'a';
    }
};

template <typename Key, int NumSlots = 26, int(*HashFn)(const Key&) = DefaultHashFn<Key>::hash>
class HashSet {
public:
    HashSet () : slots(), states{SlotState::NeverUsed} {}
    ~HashSet() {}

    const int NotFound = -1;

    // Find the slot containing the key
    int search (const Key& key) const {
        // taking modulus is redundant becuase HashFn already does it, but this way we can use any hash function even if its out of range
        const int hash = HashFn(key) % NumSlots;
        int search_hash = hash;
        do {
            if (states[search_hash] == SlotState::Occupied) {
                if (slots[search_hash] == key) {
                    return search_hash;
                }
            } else if (states[search_hash] == SlotState::NeverUsed) {
                return NotFound;
            }
            search_hash++;
        } while (search_hash != hash);
        return NotFound;
    }

    // Check if a key is contained in the set
    bool contains (const Key& key) const {
        return search(key) != NotFound;
    }

    // Insert a key into the set
    void insert (const Key& key) {
        if (! contains(key)) {
            const int hash = HashFn(key) % NumSlots;
            int insert_hash = hash;
            do {
                if (states[insert_hash] == SlotState::Occupied) {
                    insert_hash++;
                } else {
                    slots[insert_hash] = key;
                    states[insert_hash] = SlotState::Occupied;
                    break;
                }
            } while (insert_hash != hash);
        }
    }

    // Remove a key from the set
    void remove (const Key& key) {
        int slot = search(key);
        if (slot != NotFound) {
            states[slot] = SlotState::Tombstone;
        }
    }

    template <typename Fn>
    void dump (Fn fn) const {
        for (int idx = 0; idx < NumSlots; idx++) {
            if (states[idx] == SlotState::Occupied) {
                const Key& key = slots[idx]; // Make sure its a const reference when passed to Fn
                fn(key);
            }
        }
    }

private:
    enum class SlotState {
        NeverUsed,
        Tombstone,
        Occupied,
    };

    std::array<Key, NumSlots> slots;
    std::array<SlotState, NumSlots> states;
};

#ifdef TESTS
// Poor mans unit tests (normally I would use https://github.com/onqtam/doctest)
template <typename HS>
void test (const HS& hs, const std::string& key, bool expected) {
    bool found = hs.contains(key);
    std::cout << key << ": " << (found ? "found" : "not-found") << "\t" << (found == expected ? "✓" : "✗") << "\n";
    
}
void run_tests () {
    HashSet<std::string> set;

    // Test insertion and deletion
    test(set, "key", false);
    set.insert("key");
    test(set, "key", true);
    set.remove("key");
    test(set, "key", false);

    // Test hash collision
    set.insert("a_1");
    test(set, "a_1", true);
    test(set, "b_1", false);
    set.insert("b_1");
    test(set, "a_1", true);
    test(set, "b_1", true);
    set.remove("a_1");
    test(set, "a_1", false);
    test(set, "b_1", true);
    set.remove("b_1");
    test(set, "a_1", false);
    test(set, "b_1", false);
}
#endif

int main (int argc, char* argv[])
{
#ifdef TESTS
    run_tests();
#else

    HashSet<std::string> set;

    std::string input;
    std::getline(std::cin, input);
    auto it = input.begin();
    
    // Read up to 26 words from stdin
    for (int i=0; i<26; i++) {
        if (it == input.end()) {
            break;
        } else if (*it == ' ') {
            it++; // Skip the space between inputs
        }
        // Command is the first character
        char command = *it++;
        // Read until a space or end of input
        auto begin = it;
        while (it != input.end() && *it != ' ') {
            it++;
        }
        // Word is all read characters from command
        std::string word(begin, it);
        // Process command, A = add/insert, D = delete/remove
        if (command == 'A') {
            set.insert(word);
        } else if (command == 'D') {
            set.remove(word);
        }
    }

    // Output the contents of the set
    set.dump([](const std::string& key){
        std::cout << key << " ";
    });
    std::cout << "\n";


#endif
    return 0;
}