clang++ -std=c++11 main.cpp -o assignment
clang++ -std=c++11 main.cpp -o assignment -DTESTS
./assignment
> clang++ main.cpp -o assignment
> ./assignment
Aapple Aorange Dapple Astrawberry
output:
orange strawberry
#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; | |
} |