core/test/modules/ProbingHashMapTests.cpp

#include "../../src/ErrorSimulator.hpp"
#include "../Tests.hpp"
#include "core/data/ProbingHashMap.hpp"
#include "core/utils/Error.hpp"
#include "core/utils/HashCode.hpp"

template struct Core::ProbingHashMap<int, int>;
using IntMap = Core::ProbingHashMap<int, int>;

constexpr int INVALID = Core::emptyValue<int>();

static IntMap getTestIntMap() {
    IntMap map;
    map.add(1, 3).add(2, 4).add(3, 5).add(INVALID, 20);
    return map;
}

static void checkIntMap(IntMap& map) {
    int* a = map.search(1);
    int* b = map.search(2);
    int* c = map.search(3);
    int* d = map.search(INVALID);
    if(CORE_TEST_NOT_NULL(a) && CORE_TEST_NOT_NULL(b) &&
       CORE_TEST_NOT_NULL(c) && CORE_TEST_NOT_NULL(d)) {
        CORE_TEST_EQUAL(3, *a);
        CORE_TEST_EQUAL(4, *b);
        CORE_TEST_EQUAL(5, *c);
        CORE_TEST_EQUAL(20, *d);
    }
}

static void testAdd() {
    IntMap map;
    map.add(5, 4);
    int* value = map.search(5);
    CORE_TEST_NOT_NULL(value);
    if(value != nullptr) {
        CORE_TEST_EQUAL(4, *value);
    }
}

static void testMultipleAdd() {
    IntMap map = getTestIntMap();
    CORE_TEST_TRUE(map.contains(1));
    CORE_TEST_TRUE(map.contains(2));
    CORE_TEST_TRUE(map.contains(3));
    checkIntMap(map);
}

static void testSearch() {
    IntMap map;
    CORE_TEST_NULL(map.search(6));
    map.add(5, 4).add(10, 3).add(15, 2);
    CORE_TEST_NULL(map.search(6));
}

static void testAddReplace() {
    IntMap map;
    map.add(5, 4).add(5, 10);
    CORE_TEST_TRUE(map.contains(5));
    int* a = map.search(5);
    if(CORE_TEST_NOT_NULL(a)) {
        CORE_TEST_EQUAL(10, *a);
    }
}

static void testClear() {
    IntMap map;
    map.add(5, 4).add(4, 10);
    map.clear();
    CORE_TEST_FALSE(map.contains(5));
    CORE_TEST_FALSE(map.contains(4));
}

static void testOverflow(bool light) {
    int limit = light ? 10000 : 100000;
    IntMap map;
    map.add(INVALID, 42);
    for(int i = 0; i < limit; i++) {
        map.add(i, i);
    }
    for(int i = 0; i < limit; i++) {
        CORE_TEST_TRUE(map.contains(i));
    }
    CORE_TEST_TRUE(map.contains(INVALID));
}

static int aInstances = 0;

struct ProbingTest final {
    int a;
    int b;

    ProbingTest(int a_, int b_) : a(a_), b(b_) {
        aInstances++;
    }

    ProbingTest(const ProbingTest& o) : a(o.a), b(o.b) {
        aInstances++;
    }

    ProbingTest(ProbingTest&& o) : a(o.a), b(o.b) {
        aInstances++;
    }

    ~ProbingTest() {
        aInstances--;
    }

    ProbingTest& operator=(const ProbingTest& o) = default;
    ProbingTest& operator=(ProbingTest&& o) = default;

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

    template<typename String>
    check_return Core::Error toString(String& s) const {
        CORE_RETURN_ERROR(s.append("A("));
        CORE_RETURN_ERROR(s.append(a));
        CORE_RETURN_ERROR(s.append(", "));
        CORE_RETURN_ERROR(s.append(b));
        CORE_RETURN_ERROR(s.append(")"));
        return Core::ErrorCode::NONE;
    }
};

static void testEmplace() {
    {
        Core::ProbingHashMap<int, ProbingTest> map;

        ProbingTest* ar = nullptr;
        CORE_TEST_TRUE(map.tryEmplace(ar, 0, 3, 4));
        CORE_TEST_TRUE(map.tryEmplace(ar, 3, 4, 5));
        CORE_TEST_TRUE(map.tryEmplace(ar, 20, 5, 6));
        CORE_TEST_FALSE(map.tryEmplace(ar, 3, 6, 7));
        CORE_TEST_FALSE(map.tryEmplace(ar, 20, 7, 8));

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

        if(CORE_TEST_NOT_NULL(a) && CORE_TEST_NOT_NULL(b) &&
           CORE_TEST_NOT_NULL(c)) {
            CORE_TEST_EQUAL(ProbingTest(3, 4), *a);
            CORE_TEST_EQUAL(ProbingTest(4, 5), *b);
            CORE_TEST_EQUAL(ProbingTest(5, 6), *c);
        }
    }
    CORE_TEST_EQUAL(0, aInstances);
}

static void testToString() {
    CORE_TEST_STRING("[2 = 4, 1 = 3, 3 = 5, 2147483647 = 20]", getTestIntMap());
    CORE_TEST_STRING("[1 = 3]", IntMap().add(1, 3));
    CORE_TEST_STRING("[]", IntMap());
}

static void testCopy() {
    IntMap map = getTestIntMap();
    IntMap copy = map;
    IntMap copyA;
    copyA = map;
    checkIntMap(map);
    checkIntMap(copy);
    checkIntMap(copyA);
}

static void testMove() {
    IntMap map = getTestIntMap();
    IntMap move(Core::move(map));
    checkIntMap(move);
}

static void testMoveAssignment() {
    IntMap map = getTestIntMap();
    IntMap move;
    move = Core::move(map);
    checkIntMap(move);
}

static void testEntryForEach() {
    IntMap map;
    map.add(5, 4).add(10, 3).add(15, 2);

    int counter = 0;
    for(auto entry : map) {
        counter += entry.getKey() + entry.value;
    }
    CORE_TEST_EQUAL(39, counter);

    const IntMap& cmap = map;
    counter = 0;
    for(auto entry : cmap) {
        counter += entry.getKey() + entry.value;
    }
    CORE_TEST_EQUAL(39, counter);
}

static void testKeyForEach() {
    IntMap map;
    map.add(5, 4).add(10, 3).add(15, 2);

    int counter = 0;
    for(const int& key : map.getKeys()) {
        counter += key;
    }
    CORE_TEST_EQUAL(30, counter);

    const IntMap& cmap = map;
    counter = 0;
    for(const int& key : cmap.getKeys()) {
        counter += key;
    }
    CORE_TEST_EQUAL(30, counter);
}

static void testValueForEach() {
    IntMap map;
    map.add(5, 4).add(10, 3).add(15, 2);

    int counter = 0;
    for(int& value : map.getValues()) {
        counter += value;
    }
    CORE_TEST_EQUAL(9, counter);

    const IntMap& cmap = map;
    counter = 0;
    for(const int& value : cmap.getValues()) {
        counter += value;
    }
    CORE_TEST_EQUAL(9, counter);
}

template<typename T>
static void testType() {
    Core::ProbingHashMap<T, int> m;
    m.add(T(), 3);
}

static void testTypes() {
    testType<char>();
    testType<signed char>();
    testType<signed short>();
    testType<signed int>();
    testType<signed long>();
    testType<signed long long>();
    testType<unsigned char>();
    testType<unsigned short>();
    testType<unsigned int>();
    testType<unsigned long>();
    testType<unsigned long long>();
}

static void testInvalid() {
    IntMap map;
    int* v;
    CORE_TEST_TRUE(map.tryEmplace(v, INVALID, 2));
    if(CORE_TEST_NOT_NULL(v)) {
        CORE_TEST_EQUAL(2, *v);
    }
    CORE_TEST_FALSE(map.tryEmplace(v, INVALID, 6));
    if(CORE_TEST_NOT_NULL(v)) {
        CORE_TEST_EQUAL(2, *v);
    }
    CORE_TEST_EQUAL(3, map.put(INVALID, 3));
    v = map.search(INVALID);
    if(CORE_TEST_NOT_NULL(v)) {
        CORE_TEST_EQUAL(3, *v);
    }
    map.clear();
    CORE_TEST_NULL(map.search(INVALID));
}

static void testInvalidPut() {
    IntMap map;
    CORE_TEST_EQUAL(3, map.put(INVALID, 3));
    int* v = map.search(INVALID);
    if(CORE_TEST_NOT_NULL(v)) {
        CORE_TEST_EQUAL(3, *v);
    }
}

static void testAddCollisions() {
    IntMap map;
    for(int i = 0; i < 8; i++) {
        map.add(i * 16, i);
    }
}

void Core::testProbingHashMap(bool light) {
    testAdd();
    testMultipleAdd();
    testSearch();
    testAddReplace();
    testClear();
    testOverflow(light);
    testEmplace();
    testToString();
    testCopy();
    testMove();
    testMoveAssignment();
    testEntryForEach();
    testKeyForEach();
    testValueForEach();
    testTypes();
    testInvalid();
    testInvalidPut();
    testAddCollisions();
}