core/test/modules/HashMapTests.cpp

#include "../Tests.hpp"
#include "core/ProbingHashMap.hpp"
#include "core/Random.hpp"
#include "core/Test.hpp"

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

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

// static void testHash() {
//     const char* s = "wusi";
//     TEST_TRUE(hashString(s) != 0);
// }

template<typename T>
static T getTestIntMap() {
    T map;
    map.add(1, 3).add(2, 4).add(3, 5).add(0, 20);
    return map;
}

template<typename T>
static void checkIntMap(T& map) {
    int* a = map.search(1);
    int* b = map.search(2);
    int* c = map.search(3);
    int* d = map.search(0);
    if(TEST_NOT_NULL(a) && TEST_NOT_NULL(b) && TEST_NOT_NULL(c) &&
       TEST_NOT_NULL(d)) {
        TEST(3, *a);
        TEST(4, *b);
        TEST(5, *c);
        TEST(20, *d);
    }
}

template<typename T>
static void testAdd() {
    T map;
    map.add(5, 4);
    int* value = map.search(5);
    if(TEST_NOT_NULL(value)) {
        TEST(4, *value);
    }
}

template<typename T>
static void testMultipleAdd() {
    T map = getTestIntMap<T>();
    TEST_TRUE(map.contains(0));
    TEST_TRUE(map.contains(1));
    TEST_TRUE(map.contains(2));
    TEST_TRUE(map.contains(3));
    checkIntMap(map);
}

template<typename T>
static void testSearch() {
    T map;
    TEST_NULL(map.search(6));
    map.add(5, 4).add(10, 3).add(15, 2);
    TEST_NULL(map.search(6));
}

template<typename T>
static void testAddReplace() {
    T map;
    map.add(5, 4).add(5, 10);
    TEST_TRUE(map.contains(5));
    int* a = map.search(5);
    if(TEST_NOT_NULL(a)) {
        TEST(10, *a);
    }
}

template<typename T>
static void testClear() {
    T map;
    map.clear();
    map.add(5, 4).add(4, 10);
    map.clear();
    TEST_FALSE(map.contains(5));
    TEST_FALSE(map.contains(4));
}

template<typename T>
static void testOverflow(bool light) {
    int limit = light ? 10'000 : 100'000;
    T map;
    for(int i = 0; i < limit; i++) {
        map.add(i, i);
    }
    for(int i = 0; i < limit; i++) {
        TEST_TRUE(map.contains(i));
    }
}

static int aInstances = 0;

struct HashMapTest {
    int a;
    int b;

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

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

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

    size_t toString(char* s, size_t n) const {
        size_t total = 0;
        addString("A(", s, n, total);
        addString(a, s, n, total);
        addString(", ", s, n, total);
        addString(b, s, n, total);
        addString(")", s, n, total);
        return total;
    }
};

struct ProbingTest final : public HashMapTest {
    ProbingTest(int a_, int b_) : HashMapTest(a_, b_) {
        aInstances++;
    }

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

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

    ~ProbingTest() {
        aInstances--;
    }

    ProbingTest& operator=(ProbingTest o) {
        a = o.a;
        b = o.b;
        return *this;
    }
};

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

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

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

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

template<typename T>
static void testToString() {
    if constexpr(Core::IsSame<T, int>) {
        TEST_STRING(
            "[1 = 3, 2 = 4, 3 = 5, 2147483647 = 20]", getTestIntMap<T>());
    } else {
        TEST_STRING("[0 = 20, 2 = 4, 1 = 3, 3 = 5]", getTestIntMap<T>());
    }
    TEST_STRING("[1 = 3]", T().add(1, 3));
    TEST_STRING("[]", T());
}

template<typename T>
static void testCopy() {
    T map = getTestIntMap<T>();
    T copy = map;
    T copyA;
    copyA = map;
    checkIntMap(map);
    checkIntMap(copy);
    checkIntMap(copyA);
    map.add(1, 20).add(2, 30).add(3, 40);
    checkIntMap(copy);
    checkIntMap(copyA);
}

template<typename T>
static void testMove() {
    T map = getTestIntMap<T>();
    T move(Core::move(map));
    checkIntMap(move);
}

template<typename T>
static void testMoveAssignment() {
    T map = getTestIntMap<T>();
    T move;
    move = Core::move(map);
    checkIntMap(move);
}

template<typename T>
static void testEntryForEach() {
    T map;
    map.add(0, 1).add(5, 4).add(10, 3).add(15, 2);

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

    const T& cmap = map;
    counter = 0;
    for(auto entry : cmap) {
        counter += entry.getKey() + entry.value;
    }
    TEST(40, counter);
}

template<typename T>
static void testKeyForEach() {
    T map;
    map.add(5, 4).add(10, 3).add(15, 2);

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

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

template<typename T>
static void testValueForEach() {
    T map;
    map.add(5, 4).add(10, 3).add(15, 2);

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

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

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

template<typename T>
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>();
}

template<typename T>
static void testInvalid() {
    T map;
    int* v;
    TEST_TRUE(map.tryEmplace(v, 0, 2));
    if(TEST_NOT_NULL(v)) {
        TEST(2, *v);
    }
    TEST_FALSE(map.tryEmplace(v, 0, 6));
    if(TEST_NOT_NULL(v)) {
        TEST(2, *v);
    }
    TEST(3, map.put(0, 3));
    v = map.search(0);
    if(TEST_NOT_NULL(v)) {
        TEST(3, *v);
    }
    map.clear();
    TEST_NULL(map.search(0));
}

template<typename T>
static void testInvalidPut() {
    T map;
    TEST_STRING("[]", map);
    TEST(3, map.put(0, 3));
    TEST_STRING("[0 = 3]", map);
    int* v = map.search(0);
    if(TEST_NOT_NULL(v)) {
        TEST(3, *v);
    }
    map.clear();
    TEST_FALSE(map.contains(0));
    TEST_STRING("[]", map);
}

template<typename T>
static void testAddCollisions() {
    T map;
    for(int i = 0; i < 16; i++) {
        map.add(i * 64, i);
    }
}

template<typename T>
static void testRemove() {
    T map;
    map.add(1, 3).add(2, 4).add(3, 5);

    TEST_TRUE(map.remove(2));
    TEST_FALSE(map.remove(7));

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

    TEST_NULL(b);
    if(TEST_NOT_NULL(a) && TEST_NOT_NULL(c)) {
        TEST(3, *a);
        TEST(5, *c);
    }
}

template<typename T>
static void testRemoveLong() {
    T map;
    Core::Random r(5);
    constexpr size_t LIMIT = 75;
    Core::Array<i32, LIMIT> a;
    for(int i = 0; i < 10'000; i++) {
        i32 r1 = r.nextI32(0, LIMIT);
        if(r.nextBool()) {
            i32 r2 = r.nextI32(0, LIMIT);
            map.add(r1, 2);
            map.add(r2, 2);
            a[static_cast<size_t>(r1)] = 1;
            a[static_cast<size_t>(r2)] = 1;
        } else {
            map.remove(r1);
            a[static_cast<size_t>(r1)] = 0;
        }

        Core::Array<i32, LIMIT> copy = a;
        for(int key : map.getKeys()) {
            TEST_TRUE(copy[static_cast<size_t>(key)]);
            copy[static_cast<size_t>(key)] = 0;
        }
        for(int key : copy) {
            TEST(0, key);
        }
    }
}

template<typename T>
static void testMap(bool light) {
    testAdd<T>();
    testMultipleAdd<T>();
    testSearch<T>();
    testAddReplace<T>();
    testClear<T>();
    testOverflow<T>(light);
    testToString<T>();
    testCopy<T>();
    testMove<T>();
    testMoveAssignment<T>();
    testEntryForEach<T>();
    testKeyForEach<T>();
    testValueForEach<T>();
    testTypes<T>();
    testInvalid<T>();
    testInvalidPut<T>();
    testAddCollisions<T>();
    testRemove<T>();
    testRemoveLong<T>();
}

// static void testEmplace() {
//     Core::ProbingHashMap<int, HashMapTest> map;
//
//     HashMapTest* ar = nullptr;
//     TEST_TRUE(map.tryEmplace(ar, 0, 3, 4));
//     TEST_TRUE(map.tryEmplace(ar, 3, 4, 5));
//     TEST_TRUE(map.tryEmplace(ar, 20, 5, 6));
//     TEST_FALSE(map.tryEmplace(ar, 3, 6, 7));
//     TEST_FALSE(map.tryEmplace(ar, 20, 7, 8));
//
//     HashMapTest* a = map.search(0);
//     HashMapTest* b = map.search(3);
//     HashMapTest* c = map.search(20);
//
//     if(TEST_NOT_NULL(a) && TEST_NOT_NULL(b) && TEST_NOT_NULL(c)) {
//         TEST(HashMapTest(3, 4), *a);
//         TEST(HashMapTest(4, 5), *b);
//         TEST(HashMapTest(5, 6), *c);
//     }
// }

void testHashMap(bool light) {
    // testHash();
    testMap<ProbingIntMap>(light);
    // testMap<IntMap>(light);
    // testEmplace();
    testEmplaceProbing();
}