core/tests/HashMapTests.cpp

#include "tests/HashMapTests.h"

#include "data/HashMap.h"
#include "test/Test.h"

using IntMap = Core::HashMap<int, int>;
using String = Core::ArrayString<128>;

template<typename T>
static String build(Core::Test& test, const T& t) {
    String s;
    test.checkFalse(s.append(t), "append works");
    return s;
}

static void testAdd(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(5, 4), "add works 1");
    int* value = map.search(5);
    test.checkTrue(value != nullptr, "contains added value");
    if(value != nullptr) {
        test.checkEqual(4, *value, "search finds added value");
    }
}

static void testMultipleAdd(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(5, 4), "add works 2");
    test.checkFalse(map.add(10, 3), "add works 3");
    test.checkFalse(map.add(15, 2), "add works 4");
    test.checkTrue(map.contains(5), "contains added value 1");
    test.checkTrue(map.contains(10), "contains added value 2");
    test.checkTrue(map.contains(15), "contains added value 3");
    int* a = map.search(5);
    int* b = map.search(10);
    int* c = map.search(15);
    test.checkTrue(a != nullptr, "contains added value 1");
    test.checkTrue(b != nullptr, "contains added value 2");
    test.checkTrue(c != nullptr, "contains added value 3");
    if(a != nullptr && b != nullptr && c != nullptr) {
        test.checkEqual(4, *a, "search finds added value 1");
        test.checkEqual(3, *b, "search finds added value 2");
        test.checkEqual(2, *c, "search finds added value 3");
    }
}

static void testSearch(Core::Test& test) {
    IntMap map;
    test.checkTrue(nullptr == map.search(6),
                   "search does not find missing key");
}

static void testAddReplace(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(5, 4), "add works 5");
    test.checkFalse(map.add(5, 10), "add works 6");
    test.checkTrue(map.contains(5), "contains replaced value");
    int* a = map.search(5);
    test.checkTrue(a != nullptr, "contains replaced value");
    if(a != nullptr) {
        test.checkEqual(10, *a, "search finds replaced value");
    }
}

static void testClear(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(5, 4), "add works 7");
    test.checkFalse(map.add(4, 10), "add works 8");
    map.clear();
    test.checkFalse(map.contains(5), "does not contain cleared values 1");
    test.checkFalse(map.contains(4), "does not contain cleared values 2");
}

static void testOverflow(Core::Test& test) {
    IntMap map;
    for(int i = 0; i < 1000000; i++) {
        test.checkFalse(map.add(i, i), "add works in overflow");
    }
    for(int i = 0; i < 1000000; i++) {
        test.checkTrue(map.contains(i), "still contains values after overflow");
    }
}

struct A {
    int a;
    int b;

    A(int a_, int b_) : a(a_), b(b_) {
    }

    // none of these should be needed for the hashmap
    A(const A&) = delete;
    A(A&&) = delete;
    A& operator=(const A&) = delete;
    A& operator=(A&&) = delete;

    bool operator==(const A& other) const {
        return a == other.a && b == other.b;
    }

    template<int N>
    check_return bool toString(Core::ArrayString<N>& s) const {
        return s.append("A(") || s.append(a) || s.append(", ") || s.append(b) ||
               s.append(")");
    }
};

static void testEmplace(Core::Test& test) {
    Core::HashMap<int, A> map;

    bool r1 = map.tryEmplace(0, 3, 4);
    bool r2 = map.tryEmplace(3, 4, 5);
    bool r3 = map.tryEmplace(20, 5, 6);
    bool r4 = map.tryEmplace(3, 6, 7);
    bool r5 = map.tryEmplace(20, 7, 8);

    A* a = map.search(0);
    A* b = map.search(3);
    A* c = map.search(20);

    test.checkTrue(a != nullptr, "contains emplaced value 1");
    test.checkTrue(b != nullptr, "contains emplaced value 2");
    test.checkTrue(c != nullptr, "contains emplaced value 3");

    if(a != nullptr && b != nullptr && c != nullptr) {
        test.checkEqual(A(3, 4), *a, "contains emplaced value 1");
        test.checkEqual(A(4, 5), *b, "contains emplaced value 2");
        test.checkEqual(A(5, 6), *c, "contains emplaced value 3");
    }

    test.checkFalse(r1, "emplacing returns correct value 1");
    test.checkFalse(r2, "emplacing returns correct value 2");
    test.checkFalse(r3, "emplacing returns correct value 3");
    test.checkTrue(r4, "emplacing returns correct value 4");
    test.checkTrue(r5, "emplacing returns correct value 5");
}

static void testToString1(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(1, 3), "add works to string 1");
    test.checkFalse(map.add(2, 4), "add works to string 2");
    test.checkFalse(map.add(3, 5), "add works to string 3");
    test.checkEqual(build(test, "[1 = 3, 2 = 4, 3 = 5]"), build(test, map),
                    "to string 1");
}

static void testToString2(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(1, 3), "add works to string 4");
    test.checkEqual(build(test, "[1 = 3]"), build(test, map), "to string 2");
}

static void testToString3(Core::Test& test) {
    IntMap map;
    test.checkEqual(build(test, "[]"), build(test, map), "to string 3");
}

static void testCopy(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(1, 3), "add works copy 1");
    test.checkFalse(map.add(2, 4), "add works copy 2");
    test.checkFalse(map.add(3, 5), "add works copy 3");
    IntMap copy;
    test.checkFalse(copy.copyFrom(map), "copy works");

    int* a[6] = {map.search(1),  map.search(2),  map.search(3),
                 copy.search(1), copy.search(2), copy.search(3)};
    for(int i = 0; i < 3; i++) {
        test.checkTrue(a[i] != nullptr && a[i + 3] != nullptr,
                       "copy has same values");
        if(a[i] != nullptr && a[i + 3] != nullptr) {
            test.checkEqual(*(a[i]), *(a[i + 3]), "copy has same values");
        }
    }
}

static void testMove(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(1, 3), "add works move 5");
    test.checkFalse(map.add(2, 4), "add works move 6");
    test.checkFalse(map.add(3, 5), "add works move 7");
    IntMap move(Core::move(map));

    int* a = move.search(1);
    int* b = move.search(2);
    int* c = move.search(3);

    test.checkTrue(a != nullptr, "move moves values 1");
    test.checkTrue(b != nullptr, "move moves values 2");
    test.checkTrue(c != nullptr, "move moves values 3");

    if(a != nullptr && b != nullptr && c != nullptr) {
        test.checkEqual(3, *a, "move moves values 1");
        test.checkEqual(4, *b, "move moves values 2");
        test.checkEqual(5, *c, "move moves values 3");
    }
}

static void testMoveAssignment(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(1, 3), "add works move assignment 1");
    test.checkFalse(map.add(2, 4), "add works move assignment 2");
    test.checkFalse(map.add(3, 5), "add works move assignment 3");

    IntMap move;
    move = Core::move(map);

    int* a = move.search(1);
    int* b = move.search(2);
    int* c = move.search(3);

    test.checkTrue(a != nullptr, "move moves values 1");
    test.checkTrue(b != nullptr, "move moves values 2");
    test.checkTrue(c != nullptr, "move moves values 3");

    if(a != nullptr && b != nullptr && c != nullptr) {
        test.checkEqual(3, *a, "move moves values 1");
        test.checkEqual(4, *b, "move moves values 2");
        test.checkEqual(5, *c, "move moves values 3");
    }
}

static void testRemove(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(1, 3), "add works remove 1");
    test.checkFalse(map.add(2, 4), "add works remove 2");
    test.checkFalse(map.add(3, 5), "add works remove 3");

    bool remove1 = map.remove(2);
    bool remove2 = map.remove(7);

    int* a = map.search(1);
    int* b = map.search(2);
    int* c = map.search(3);

    test.checkTrue(a != nullptr, "move moves values 1");
    test.checkTrue(b == nullptr, "move moves values 2");
    test.checkTrue(c != nullptr, "move moves values 3");

    test.checkTrue(remove1, "remove returns true");
    test.checkFalse(remove2, "remove returns false");

    if(a != nullptr && c != nullptr) {
        test.checkEqual(3, *a, "move moves values 1");
        test.checkEqual(5, *c, "move moves values 3");
    }
}

static void testEntryForEach(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(5, 4), "add works entry for each 1");
    test.checkFalse(map.add(10, 3), "add works entry for each 2");
    test.checkFalse(map.add(15, 2), "add works entry for each 3");

    int counter = 0;
    for(auto& entry : map.entries()) {
        counter += entry.getKey() + entry.value;
    }
    test.checkEqual(39, counter, "entry iterator");

    const IntMap& cmap = map;
    counter = 0;
    for(const auto& entry : cmap.entries()) {
        counter += entry.getKey() + entry.value;
    }
    test.checkEqual(39, counter, "const entry iterator");
}

static void testKeyForEach(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(5, 4), "add works key for each 1");
    test.checkFalse(map.add(10, 3), "add works key for each 2");
    test.checkFalse(map.add(15, 2), "add works key for each 3");

    int counter = 0;
    for(const int& key : map.keys()) {
        counter += key;
    }
    test.checkEqual(30, counter, "key iterator");

    const IntMap& cmap = map;
    counter = 0;
    for(const int& key : cmap.keys()) {
        counter += key;
    }
    test.checkEqual(30, counter, "const key iterator");
}

static void testValueForEach(Core::Test& test) {
    IntMap map;
    test.checkFalse(map.add(5, 4), "add works value for each 1");
    test.checkFalse(map.add(10, 3), "add works value for each 2");
    test.checkFalse(map.add(15, 2), "add works value for each 3");

    int counter = 0;
    for(int& value : map.values()) {
        counter += value;
    }
    test.checkEqual(9, counter, "value iterator");

    const IntMap& cmap = map;
    counter = 0;
    for(const int& value : cmap.values()) {
        counter += value;
    }
    test.checkEqual(9, counter, "const value iterator");
}

template<typename T>
static void testType(Core::Test& test) {
    Core::HashMap<T, int> m;
    test.checkFalse(m.add(T(), 3), "test type");
}

static void testTypes(Core::Test& test) {
    testType<char>(test);
    testType<signed char>(test);
    testType<signed short>(test);
    testType<signed int>(test);
    testType<signed long>(test);
    testType<signed long long>(test);
    testType<unsigned char>(test);
    testType<unsigned short>(test);
    testType<unsigned int>(test);
    testType<unsigned long>(test);
    testType<unsigned long long>(test);
}

void Core::HashMapTests::test() {
    Core::Test test("HashMap");
    testAdd(test);
    testMultipleAdd(test);
    testSearch(test);
    testAddReplace(test);
    testClear(test);
    testOverflow(test);
    testEmplace(test);
    testToString1(test);
    testToString2(test);
    testToString3(test);
    testCopy(test);
    testMove(test);
    testMoveAssignment(test);
    testRemove(test);
    testEntryForEach(test);
    testKeyForEach(test);
    testValueForEach(test);
    testTypes(test);
    test.finalize();
}