Function TestRandomized

src/minisketch/src/test.cpp:126–223

Test properties of sketches with random elements put in. */

/** Test properties of sketches with random elements put in. */
void TestRandomized(uint32_t bits, size_t max_capacity, size_t iter) {
    std::random_device rnd;
    std::uniform_int_distribution<uint64_t> capacity_dist(0, std::min<uint64_t>(std::numeric_limits<uint64_t>::max() >> (64 - bits), max_capacity));
    std::uniform_int_distribution<uint64_t> element_dist(1, std::numeric_limits<uint64_t>::max() >> (64 - bits));
    std::uniform_int_distribution<uint64_t> rand64(0, std::numeric_limits<uint64_t>::max());
    std::uniform_int_distribution<int64_t> size_offset_dist(-3, 3);

    std::vector<uint64_t> decode_0;
    std::vector<uint64_t> decode_other;
    std::vector<uint64_t> decode_temp;
    std::vector<uint64_t> elements;

    for (size_t i = 0; i < iter; ++i) {
        // Determine capacity, and construct Minisketch objects for all implementations.
        uint64_t capacity = capacity_dist(rnd);
        auto sketches = CreateSketches(bits, capacity);
        // Sanity checks
        if (sketches.empty()) return;
        for (size_t impl = 0; impl < sketches.size(); ++impl) {
            CHECK(sketches[impl].GetBits() == bits);
            CHECK(sketches[impl].GetCapacity() == capacity);
            CHECK(sketches[impl].GetSerializedSize() == sketches[0].GetSerializedSize());
        }
        // Determine the number of elements, and create a vector to store them in.
        size_t element_count = std::max<int64_t>(0, std::max<int64_t>(0, capacity + size_offset_dist(rnd)));
        elements.resize(element_count);
        // Add the elements to all sketches
        for (size_t j = 0; j < element_count; ++j) {
            uint64_t elem = element_dist(rnd);
            CHECK(elem != 0);
            elements[j] = elem;
            for (auto& sketch : sketches) sketch.Add(elem);
        }
        // Remove pairs of duplicates in elements, as they cancel out.
        std::sort(elements.begin(), elements.end());
        size_t real_element_count = element_count;
        for (size_t pos = 0; pos + 1 < elements.size(); ++pos) {
            if (elements[pos] == elements[pos + 1]) {
                real_element_count -= 2;
                // Set both elements to 0; afterwards we will move these to the end.
                elements[pos] = 0;
                elements[pos + 1] = 0;
                ++pos;
            }
        }
        if (real_element_count < element_count) {
            // Move all introduced zeroes (masking duplicates) to the end.
            std::sort(elements.begin(), elements.end(), [](uint64_t a, uint64_t b) { return a != b && (b == 0 || (a != 0 && a < b)); });
            CHECK(elements[real_element_count] == 0);
            elements.resize(real_element_count);
        }
        // Create and compare serializations
        auto serialized_0 = sketches[0].Serialize();
        for (size_t impl = 1; impl < sketches.size(); ++impl) {
            auto serialized_other = sketches[impl].Serialize();
            CHECK(serialized_other == serialized_0);
        }
        // Deserialize and reserialize them