/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "paimon/utils/roaring_bitmap64.h"

#include <climits>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <memory>
#include <utility>

#include "gtest/gtest.h"
#include "paimon/io/byte_array_input_stream.h"
#include "paimon/result.h"
#include "paimon/testing/utils/testharness.h"
#include "paimon/utils/range.h"

namespace paimon::test {
TEST(RoaringBitmap64Test, TestSimple) {
    RoaringBitmap64 roaring;
    ASSERT_TRUE(roaring.IsEmpty());
    roaring.Add(4147483647l);
    roaring.Add(614748364721l);
    ASSERT_TRUE(roaring.Contains(4147483647l));
    ASSERT_TRUE(roaring.Contains(614748364721l));
    ASSERT_FALSE(roaring.CheckedAdd(614748364721l));
    ASSERT_TRUE(roaring.CheckedAdd(8147483647210l));
    ASSERT_TRUE(roaring.Contains(614748364721l));
    ASSERT_FALSE(roaring.IsEmpty());
    ASSERT_EQ("{4147483647,614748364721,8147483647210}", roaring.ToString());
    ASSERT_EQ(3, roaring.Cardinality());
    roaring.AddRange(614748364720, 614748364725);
    ASSERT_EQ(
        "{4147483647,614748364720,614748364721,614748364722,614748364723,614748364724,"
        "8147483647210}",
        roaring.ToString());
    ASSERT_EQ(7, roaring.Cardinality());
    roaring.RemoveRange(614748364721l, 614748364723l);
    ASSERT_EQ("{4147483647,614748364720,614748364723,614748364724,8147483647210}",
              roaring.ToString());
    ASSERT_EQ(5, roaring.Cardinality());
}
TEST(RoaringBitmap64Test, TestCompatibleWithJava) {
    auto pool = GetDefaultPool();
    {
        RoaringBitmap64 roaring;
        for (int64_t i = 0; i < 100; i++) {
            roaring.Add(i + 100000000000l);
        }
        for (int64_t i = 0; i < 100; i++) {
            ASSERT_TRUE(roaring.Contains(i + 100000000000l));
        }
        auto bytes = roaring.Serialize(pool.get());
        std::vector<uint8_t> result(bytes->data(), bytes->data() + bytes->size());
        std::vector<uint8_t> expected = {1, 0, 0, 0,   0,  0,  0, 0, 23, 0, 0,   0,  59, 48,
                                         0, 0, 1, 118, 72, 99, 0, 1, 0,  0, 232, 99, 0};
        ASSERT_EQ(result, expected);

        RoaringBitmap64 de_roaring;
        ASSERT_OK(de_roaring.Deserialize(bytes->data(), bytes->size()));
        for (int64_t i = 0; i < 100; i++) {
            ASSERT_TRUE(de_roaring.Contains(i + 100000000000l));
        }
    }
    {
        RoaringBitmap64 roaring;
        for (int64_t i = RoaringBitmap64::MAX_VALUE - 1; i > RoaringBitmap64::MAX_VALUE - 101;
             i--) {
            roaring.Add(i);
        }
        for (int64_t i = RoaringBitmap64::MAX_VALUE - 1; i > RoaringBitmap64::MAX_VALUE - 101;
             i--) {
            ASSERT_TRUE(roaring.Contains(i));
        }
        auto bytes = roaring.Serialize(pool.get());
        std::vector<uint8_t> result(bytes->data(), bytes->data() + bytes->size());
        std::vector<uint8_t> expected = {1, 0, 0, 0,   0,   0,  0, 0, 255, 255, 255, 127, 59, 48,
                                         0, 0, 1, 255, 255, 99, 0, 1, 0,   155, 255, 99,  0};
        ASSERT_EQ(result, expected);

        RoaringBitmap64 de_roaring;
        ASSERT_OK(de_roaring.Deserialize(bytes->data(), bytes->size()));
        for (int64_t i = RoaringBitmap64::MAX_VALUE - 1; i > RoaringBitmap64::MAX_VALUE - 101;
             i--) {
            ASSERT_TRUE(de_roaring.Contains(i));
        }
    }
    {
        RoaringBitmap64 roaring;
        for (int64_t i = 5000; i < 10000; i += 17) {
            roaring.Add(i + 300000000000l);
        }
        for (int64_t i = 5000; i < 10000; i += 17) {
            ASSERT_TRUE(roaring.Contains(i + 300000000000l));
        }
        auto bytes = roaring.Serialize(pool.get());
        std::vector<uint8_t> result(bytes->data(), bytes->data() + bytes->size());
        std::vector<uint8_t> expected = {
            1,   0,   0,   0,   0,   0,   0,   0,   69,  0,   0,   0,   58,  48,  0,   0,   1,
            0,   0,   0,   100, 217, 38,  1,   16,  0,   0,   0,   136, 203, 153, 203, 170, 203,
            187, 203, 204, 203, 221, 203, 238, 203, 255, 203, 16,  204, 33,  204, 50,  204, 67,
            204, 84,  204, 101, 204, 118, 204, 135, 204, 152, 204, 169, 204, 186, 204, 203, 204,
            220, 204, 237, 204, 254, 204, 15,  205, 32,  205, 49,  205, 66,  205, 83,  205, 100,
            205, 117, 205, 134, 205, 151, 205, 168, 205, 185, 205, 202, 205, 219, 205, 236, 205,
            253, 205, 14,  206, 31,  206, 48,  206, 65,  206, 82,  206, 99,  206, 116, 206, 133,
            206, 150, 206, 167, 206, 184, 206, 201, 206, 218, 206, 235, 206, 252, 206, 13,  207,
            30,  207, 47,  207, 64,  207, 81,  207, 98,  207, 115, 207, 132, 207, 149, 207, 166,
            207, 183, 207, 200, 207, 217, 207, 234, 207, 251, 207, 12,  208, 29,  208, 46,  208,
            63,  208, 80,  208, 97,  208, 114, 208, 131, 208, 148, 208, 165, 208, 182, 208, 199,
            208, 216, 208, 233, 208, 250, 208, 11,  209, 28,  209, 45,  209, 62,  209, 79,  209,
            96,  209, 113, 209, 130, 209, 147, 209, 164, 209, 181, 209, 198, 209, 215, 209, 232,
            209, 249, 209, 10,  210, 27,  210, 44,  210, 61,  210, 78,  210, 95,  210, 112, 210,
            129, 210, 146, 210, 163, 210, 180, 210, 197, 210, 214, 210, 231, 210, 248, 210, 9,
            211, 26,  211, 43,  211, 60,  211, 77,  211, 94,  211, 111, 211, 128, 211, 145, 211,
            162, 211, 179, 211, 196, 211, 213, 211, 230, 211, 247, 211, 8,   212, 25,  212, 42,
            212, 59,  212, 76,  212, 93,  212, 110, 212, 127, 212, 144, 212, 161, 212, 178, 212,
            195, 212, 212, 212, 229, 212, 246, 212, 7,   213, 24,  213, 41,  213, 58,  213, 75,
            213, 92,  213, 109, 213, 126, 213, 143, 213, 160, 213, 177, 213, 194, 213, 211, 213,
            228, 213, 245, 213, 6,   214, 23,  214, 40,  214, 57,  214, 74,  214, 91,  214, 108,
            214, 125, 214, 142, 214, 159, 214, 176, 214, 193, 214, 210, 214, 227, 214, 244, 214,
            5,   215, 22,  215, 39,  215, 56,  215, 73,  215, 90,  215, 107, 215, 124, 215, 141,
            215, 158, 215, 175, 215, 192, 215, 209, 215, 226, 215, 243, 215, 4,   216, 21,  216,
            38,  216, 55,  216, 72,  216, 89,  216, 106, 216, 123, 216, 140, 216, 157, 216, 174,
            216, 191, 216, 208, 216, 225, 216, 242, 216, 3,   217, 20,  217, 37,  217, 54,  217,
            71,  217, 88,  217, 105, 217, 122, 217, 139, 217, 156, 217, 173, 217, 190, 217, 207,
            217, 224, 217, 241, 217, 2,   218, 19,  218, 36,  218, 53,  218, 70,  218, 87,  218,
            104, 218, 121, 218, 138, 218, 155, 218, 172, 218, 189, 218, 206, 218, 223, 218, 240,
            218, 1,   219, 18,  219, 35,  219, 52,  219, 69,  219, 86,  219, 103, 219, 120, 219,
            137, 219, 154, 219, 171, 219, 188, 219, 205, 219, 222, 219, 239, 219, 0,   220, 17,
            220, 34,  220, 51,  220, 68,  220, 85,  220, 102, 220, 119, 220, 136, 220, 153, 220,
            170, 220, 187, 220, 204, 220, 221, 220, 238, 220, 255, 220, 16,  221, 33,  221, 50,
            221, 67,  221, 84,  221, 101, 221, 118, 221, 135, 221, 152, 221, 169, 221, 186, 221,
            203, 221, 220, 221, 237, 221, 254, 221, 15,  222, 32,  222, 49,  222, 66,  222, 83,
            222, 100, 222, 117, 222, 134, 222, 151, 222, 168, 222, 185, 222, 202, 222, 219, 222,
            236, 222, 253, 222, 14,  223};
        ASSERT_EQ(result, expected);

        RoaringBitmap64 de_roaring;
        ASSERT_OK(de_roaring.Deserialize(bytes->data(), bytes->size()));
        for (int64_t i = 5000; i < 10000; i += 17) {
            ASSERT_TRUE(de_roaring.Contains(i + 300000000000l));
        }
    }
    // empty
    {
        RoaringBitmap64 roaring;
        auto bytes = roaring.Serialize(pool.get());
        std::vector<uint8_t> result(bytes->data(), bytes->data() + bytes->size());
        std::vector<uint8_t> expected = {0, 0, 0, 0, 0, 0, 0, 0};
        ASSERT_EQ(result, expected);
        RoaringBitmap64 de_roaring;
        ASSERT_OK(de_roaring.Deserialize(bytes->data(), bytes->size()));
        ASSERT_TRUE(de_roaring.IsEmpty());
        ASSERT_FALSE(de_roaring.Contains(58));
    }
}

TEST(RoaringBitmap64Test, TestDeserializeFailed) {
    RoaringBitmap64 roaring;
    std::vector<char> invalid_bytes = {0, 100};
    ASSERT_NOK_WITH_MSG(roaring.Deserialize(invalid_bytes.data(), invalid_bytes.size()),
                        "catch exception in Deserialize() of RoaringBitmap64");
}

TEST(RoaringBitmap64Test, TestAndOr) {
    RoaringBitmap64 roaring1 = RoaringBitmap64::From({100000000000l, 100000000000000l});
    RoaringBitmap64 roaring2 =
        RoaringBitmap64::From({200000000000l, 100000000000000l, 200000000000000l});

    auto and_roaring = RoaringBitmap64::And(roaring1, roaring2);
    ASSERT_EQ(and_roaring, RoaringBitmap64::From({100000000000000l}));

    auto or_roaring = RoaringBitmap64::Or(roaring1, roaring2);
    ASSERT_EQ(or_roaring, RoaringBitmap64::From(
                              {100000000000l, 200000000000l, 100000000000000l, 200000000000000l}));
}

TEST(RoaringBitmap64Test, TestAssignAndMove) {
    RoaringBitmap64 roaring1 = RoaringBitmap64::From({100000000000l, 200000000000000l});
    RoaringBitmap64 roaring2 = roaring1;
    ASSERT_EQ(roaring1, roaring2);
    ASSERT_FALSE(roaring1.IsEmpty());
    ASSERT_FALSE(roaring2.IsEmpty());

    RoaringBitmap64 roaring3 = std::move(roaring1);
    ASSERT_EQ(roaring3, roaring2);
    ASSERT_FALSE(roaring1.roaring_bitmap_);  // NOLINT(bugprone-use-after-move)

    roaring3.Add(20);
    ASSERT_FALSE(roaring3 == roaring2);

    roaring3 = roaring2;
    ASSERT_EQ(roaring3, roaring2);

    roaring2 = std::move(roaring3);
    ASSERT_FALSE(roaring3.roaring_bitmap_);  // NOLINT(bugprone-use-after-move)
    ASSERT_EQ("{100000000000,200000000000000}", roaring2.ToString());

    roaring3 = roaring2;
    ASSERT_EQ("{100000000000,200000000000000}", roaring3.ToString());

    roaring3 = std::move(roaring2);
    ASSERT_EQ("{100000000000,200000000000000}", roaring3.ToString());
    ASSERT_FALSE(roaring2.roaring_bitmap_);  // NOLINT(bugprone-use-after-move)
}

TEST(RoaringBitmap64Test, TestFastUnion) {
    RoaringBitmap64 roaring1 = RoaringBitmap64::From({100000000000l, 200000000000000l});
    RoaringBitmap64 roaring2 = RoaringBitmap64::From(
        {1l, 100000000000l, 150000000000l, 200000000000000l, 300000000000000l});
    RoaringBitmap64 roaring3 = RoaringBitmap64::From({2l, 200000000000000l, 800l});

    RoaringBitmap64 res = RoaringBitmap64::FastUnion({&roaring1, &roaring2, &roaring3});
    ASSERT_EQ(res, RoaringBitmap64::From({1l, 2l, 100000000000l, 150000000000l, 200000000000000l,
                                          300000000000000l, 800l}));

    std::vector<RoaringBitmap64> roarings = {roaring1, roaring2, roaring3};
    RoaringBitmap64 res2 = RoaringBitmap64::FastUnion(roarings);
    ASSERT_EQ(res2, RoaringBitmap64::From({1l, 2l, 100000000000l, 150000000000l, 200000000000000l,
                                           300000000000000l, 800l}));
}

TEST(RoaringBitmap64Test, TestFlip) {
    RoaringBitmap64 roaring =
        RoaringBitmap64::From({1000000000001l, 1000000000002l, 1000000000004l});
    roaring.Flip(1000000000000l, 1000000000005l);
    ASSERT_EQ(roaring, RoaringBitmap64::From({1000000000000l, 1000000000003l}));
}

TEST(RoaringBitmap64Test, TestAndNot) {
    RoaringBitmap64 roaring1 = RoaringBitmap64::From(
        {10000000000010l, 10000000000020l, 100000000000100l, 100000000000200l});
    RoaringBitmap64 roaring2 = RoaringBitmap64::From(
        {1000000000005l, 10000000000020l, 10000000000080l, 100000000000200l, 100000000000250l});

    auto andnot_roaring = RoaringBitmap64::AndNot(roaring1, roaring2);
    ASSERT_EQ(andnot_roaring, RoaringBitmap64::From({10000000000010l, 100000000000100l}));
}

TEST(RoaringBitmap64Test, TestIterator) {
    RoaringBitmap64 roaring = RoaringBitmap64::From({100000000000l, 200000000000l});
    auto iter = roaring.Begin();
    ASSERT_EQ(*iter, 100000000000l);
    auto iter2 = ++iter;
    ASSERT_EQ(*iter, 200000000000l);
    ASSERT_EQ(*iter2, 200000000000l);
    ++iter;
    ASSERT_EQ(iter, roaring.End());

    iter = roaring.EqualOrLarger(5);
    ASSERT_EQ(*iter, 100000000000l);
    iter = roaring.EqualOrLarger(100000000000l);
    ASSERT_EQ(*iter, 100000000000l);
    iter = roaring.EqualOrLarger(150000000000l);
    ASSERT_EQ(*iter, 200000000000l);
    iter = roaring.EqualOrLarger(200000000000l);
    ASSERT_EQ(*iter, 200000000000l);
    iter = roaring.EqualOrLarger(200000000001l);
    ASSERT_EQ(iter, roaring.End());
}

TEST(RoaringBitmap64Test, TestIteratorAssignAndMove) {
    RoaringBitmap64 roaring =
        RoaringBitmap64::From({10000000000010l, 100000000000100l, 100000000000200l});

    auto iter1 = roaring.EqualOrLarger(10000000000010l);
    auto iter2 = iter1;
    ASSERT_EQ(iter1, iter2);
    ASSERT_EQ(10000000000010l, *iter1);
    ASSERT_EQ(10000000000010l, *iter2);

    auto iter3 = std::move(iter1);
    ASSERT_EQ(iter2, iter3);
    ASSERT_FALSE(iter1.iterator_);  // NOLINT(bugprone-use-after-move)

    ++iter3;
    ASSERT_NE(iter3, iter2);
    ASSERT_EQ(100000000000100l, *iter3);

    iter3 = iter2;
    ASSERT_EQ(iter3, iter2);

    iter2 = std::move(iter3);
    ASSERT_FALSE(iter3.iterator_);  // NOLINT(bugprone-use-after-move)
    ASSERT_EQ(10000000000010l, *iter2);

    iter3 = iter2;
    ASSERT_EQ(iter2, iter3);
    ASSERT_EQ(10000000000010l, *iter2);
    ASSERT_EQ(10000000000010l, *iter3);

    iter3 = std::move(iter2);
    ASSERT_EQ(10000000000010l, *iter3);
    ASSERT_FALSE(iter2.iterator_);  // NOLINT(bugprone-use-after-move)
}

TEST(RoaringBitmap64Test, TestDeserializeFromInputStream) {
    RoaringBitmap64 roaring1 =
        RoaringBitmap64::From({10000000000010l, 10000000000020l, 100000000000100l});
    RoaringBitmap64 roaring2 = RoaringBitmap64::From(
        {10000000000010l, 10000000000050l, 100000000000150l, 100000000000200l});
    RoaringBitmap64 roaring3 =
        RoaringBitmap64::From({1000000000002l, 1000000000004l, 1000000000006l, 1000000000001000l});

    size_t len1 = roaring1.GetSizeInBytes();
    size_t len2 = roaring2.GetSizeInBytes();
    size_t len3 = roaring3.GetSizeInBytes();

    auto pool = GetDefaultPool();
    auto bytes1 = roaring1.Serialize(pool.get());
    ASSERT_EQ(bytes1->size(), len1);
    auto bytes2 = roaring2.Serialize(pool.get());
    ASSERT_EQ(bytes2->size(), len2);
    auto bytes3 = roaring3.Serialize(pool.get());
    ASSERT_EQ(bytes3->size(), len3);

    auto concat_bytes = std::make_shared<Bytes>(len1 + len2 + len3, pool.get());
    memcpy(concat_bytes->data(), bytes1->data(), len1);
    memcpy(concat_bytes->data() + len1, bytes2->data(), len2);
    memcpy(concat_bytes->data() + len1 + len2, bytes3->data(), len3);

    ByteArrayInputStream byte_array_input_stream(concat_bytes->data(), concat_bytes->size());
    RoaringBitmap64 de_roaring1;
    ASSERT_OK(de_roaring1.Deserialize(&byte_array_input_stream));
    ASSERT_EQ(de_roaring1, roaring1);
    ASSERT_EQ(byte_array_input_stream.GetPos().value(), len1);

    RoaringBitmap64 de_roaring2;
    ASSERT_OK(de_roaring2.Deserialize(&byte_array_input_stream));
    ASSERT_EQ(de_roaring2, roaring2);
    ASSERT_EQ(byte_array_input_stream.GetPos().value(), len1 + len2);

    RoaringBitmap64 de_roaring3;
    ASSERT_OK(de_roaring3.Deserialize(&byte_array_input_stream));
    ASSERT_EQ(de_roaring3, roaring3);
    ASSERT_EQ(byte_array_input_stream.GetPos().value(), len1 + len2 + len3);
}

TEST(RoaringBitmap64Test, TestHighCardinality) {
    std::srand(time(nullptr));
    auto pool = GetDefaultPool();
    RoaringBitmap64 roaring;
    for (int64_t i = 0; i < 10000; i++) {
        roaring.Add(static_cast<int64_t>(std::numeric_limits<int32_t>::max()) + std::rand());
    }
    auto bytes = roaring.Serialize(pool.get());
    RoaringBitmap64 de_roaring;
    ASSERT_OK(de_roaring.Deserialize(bytes->data(), bytes->size()));
    ASSERT_EQ(roaring, de_roaring);
}

TEST(RoaringBitmap64Test, TestInplaceAndOr) {
    RoaringBitmap64 roaring = RoaringBitmap64::From({0l, 1l, 100000000000100l});
    RoaringBitmap64 roaring1 = RoaringBitmap64::From({1l, 2l, 1000000000005l, 100000000000200l});
    roaring |= roaring1;
    ASSERT_EQ(roaring.ToString(), "{0,1,2,1000000000005,100000000000100,100000000000200}");
    RoaringBitmap64 roaring2 =
        RoaringBitmap64::From({1l, 2l, 3l, 1000000000005l, 100000000000100l, 100000000000500l});
    roaring &= roaring2;
    ASSERT_EQ(roaring.ToString(), "{1,2,1000000000005,100000000000100}");
    RoaringBitmap64 roaring3 = RoaringBitmap64::From({2l, 100000000000100l});
    roaring -= roaring3;
    ASSERT_EQ(roaring.ToString(), "{1,1000000000005}");
}

TEST(RoaringBitmap64Test, TestContainsAny) {
    RoaringBitmap64 roaring =
        RoaringBitmap64::From({10000000000010l, 10000000000011l, 10000000000100l});
    ASSERT_TRUE(roaring.ContainsAny(10000000000010l, 10000000000011l));
    ASSERT_TRUE(roaring.ContainsAny(10000000000010l, 10000000000020l));
    ASSERT_TRUE(roaring.ContainsAny(10000000000010l, 10000000000101l));
    ASSERT_TRUE(roaring.ContainsAny(10000000000020l, 10000000000200l));
    ASSERT_TRUE(roaring.ContainsAny(10000000000005l, 10000000000011l));
    ASSERT_FALSE(roaring.ContainsAny(10000000000005l, 10000000000010l));
    ASSERT_FALSE(roaring.ContainsAny(10000000000020l, 10000000000100l));
    ASSERT_FALSE(roaring.ContainsAny(10000000000020l, 10000000000030l));
    ASSERT_FALSE(roaring.ContainsAny(10000000000500l, 10000000000520l));
}

TEST(RoaringBitmap64Test, TestFromRoaringBitmap32) {
    {
        RoaringBitmap32 roaring32 = RoaringBitmap32::From({10, 20, 21});
        RoaringBitmap64 roaring64(roaring32);
        ASSERT_EQ(roaring64.ToString(), "{10,20,21}");
    }
    {
        RoaringBitmap32 roaring32 = RoaringBitmap32::From({10, 20, 21});
        RoaringBitmap64 roaring64;
        roaring64 = roaring32;
        ASSERT_EQ(roaring64.ToString(), "{10,20,21}");
    }
}

TEST(RoaringBitmap64Test, TestIteratorEqualOrLarger) {
    RoaringBitmap64 roaring = RoaringBitmap64::From({1l, 3l, 5l, 100l});
    auto iter = roaring.Begin();
    ASSERT_EQ(*iter, 1l);
    iter.EqualOrLarger(5l);
    ASSERT_EQ(*iter, 5l);
    iter.EqualOrLarger(10l);
    ASSERT_EQ(*iter, 100l);
    iter.EqualOrLarger(200l);
    ASSERT_EQ(iter, roaring.End());
}

// Helper function to convert a RoaringBitmap64 to a list of contiguous ranges.
static std::vector<Range> ToRangeList(const RoaringBitmap64& bitmap) {
    std::vector<Range> ranges;
    if (bitmap.IsEmpty()) {
        return ranges;
    }

    int64_t current_start = -1;
    int64_t current_end = -1;

    for (auto it = bitmap.Begin(); it != bitmap.End(); ++it) {
        int64_t value = *it;
        if (current_start == -1) {
            current_start = value;
            current_end = value;
        } else if (value == current_end + 1) {
            current_end = value;
        } else {
            ranges.emplace_back(current_start, current_end);
            current_start = value;
            current_end = value;
        }
    }

    if (current_start != -1) {
        ranges.emplace_back(current_start, current_end);
    }

    return ranges;
}

TEST(RoaringBitmap64Test, TestAddRangeBasic) {
    RoaringBitmap64 bitmap;
    bitmap.AddRange(5, 11);  // half-open interval [5, 11) == closed [5, 10]

    ASSERT_EQ(bitmap.Cardinality(), 6);
    ASSERT_FALSE(bitmap.Contains(4));
    ASSERT_TRUE(bitmap.Contains(5));
    ASSERT_TRUE(bitmap.Contains(7));
    ASSERT_TRUE(bitmap.Contains(10));
    ASSERT_FALSE(bitmap.Contains(11));
}

TEST(RoaringBitmap64Test, TestAddRangeSingleElement) {
    RoaringBitmap64 bitmap;
    bitmap.AddRange(100, 101);  // half-open interval [100, 101) == single element 100

    ASSERT_EQ(bitmap.Cardinality(), 1);
    ASSERT_FALSE(bitmap.Contains(99));
    ASSERT_TRUE(bitmap.Contains(100));
    ASSERT_FALSE(bitmap.Contains(101));
}

TEST(RoaringBitmap64Test, TestAddRangeMultipleNonOverlapping) {
    RoaringBitmap64 bitmap;
    bitmap.AddRange(0, 6);    // [0, 5]
    bitmap.AddRange(10, 16);  // [10, 15]
    bitmap.AddRange(20, 26);  // [20, 25]

    ASSERT_EQ(bitmap.Cardinality(), 18);

    ASSERT_FALSE(bitmap.Contains(6));
    ASSERT_FALSE(bitmap.Contains(9));
    ASSERT_FALSE(bitmap.Contains(16));
    ASSERT_FALSE(bitmap.Contains(19));

    ASSERT_TRUE(bitmap.Contains(0));
    ASSERT_TRUE(bitmap.Contains(5));
    ASSERT_TRUE(bitmap.Contains(10));
    ASSERT_TRUE(bitmap.Contains(15));
    ASSERT_TRUE(bitmap.Contains(20));
    ASSERT_TRUE(bitmap.Contains(25));

    std::vector<Range> ranges = ToRangeList(bitmap);
    ASSERT_EQ(ranges.size(), 3);
    ASSERT_EQ(ranges[0], Range(0, 5));
    ASSERT_EQ(ranges[1], Range(10, 15));
    ASSERT_EQ(ranges[2], Range(20, 25));
}

TEST(RoaringBitmap64Test, TestAddRangeLargeValues) {
    RoaringBitmap64 bitmap;
    int64_t start = static_cast<int64_t>(INT_MAX) + 100L;
    int64_t end = static_cast<int64_t>(INT_MAX) + 200L;
    bitmap.AddRange(start, end + 1);  // half-open interval [start, end+1) == closed [start, end]

    ASSERT_EQ(bitmap.Cardinality(), 101);
    ASSERT_FALSE(bitmap.Contains(start - 1));
    ASSERT_TRUE(bitmap.Contains(start));
    ASSERT_TRUE(bitmap.Contains(start + 50));
    ASSERT_TRUE(bitmap.Contains(end));
    ASSERT_FALSE(bitmap.Contains(end + 1));

    std::vector<int64_t> values;
    for (auto it = bitmap.Begin(); it != bitmap.End(); ++it) {
        values.push_back(*it);
    }
    ASSERT_EQ(values.size(), 101);
    ASSERT_EQ(values[0], start);
    ASSERT_EQ(values[100], end);
}

TEST(RoaringBitmap64Test, TestAddMany) {
    // empty input
    {
        RoaringBitmap64 bitmap;
        bitmap.AddMany(0, nullptr);
        ASSERT_TRUE(bitmap.IsEmpty());
    }
    // single element
    {
        RoaringBitmap64 bitmap;
        int64_t value = 999999999999ll;
        bitmap.AddMany(1, &value);
        ASSERT_EQ(bitmap.Cardinality(), 1);
        ASSERT_TRUE(bitmap.Contains(999999999999ll));
    }
    // single bucket (all values share the same high-32 bits)
    {
        RoaringBitmap64 bitmap;
        std::vector<int64_t> values = {100000000001ll, 100000000005ll, 100000000003ll,
                                       100000000002ll};
        bitmap.AddMany(values.size(), values.data());
        ASSERT_EQ(bitmap.Cardinality(), 4);
        ASSERT_TRUE(bitmap.Contains(100000000001ll));
        ASSERT_TRUE(bitmap.Contains(100000000002ll));
        ASSERT_TRUE(bitmap.Contains(100000000003ll));
        ASSERT_TRUE(bitmap.Contains(100000000005ll));
        ASSERT_FALSE(bitmap.Contains(100000000004ll));
    }
    // multiple buckets (values span different high-32 bit buckets)
    {
        RoaringBitmap64 bitmap;
        std::vector<int64_t> values = {1ll, 100000000000ll, 200000000000ll, 2ll, 100000000001ll};
        bitmap.AddMany(values.size(), values.data());
        ASSERT_EQ(bitmap.Cardinality(), 5);
        ASSERT_TRUE(bitmap.Contains(1ll));
        ASSERT_TRUE(bitmap.Contains(2ll));
        ASSERT_TRUE(bitmap.Contains(100000000000ll));
        ASSERT_TRUE(bitmap.Contains(100000000001ll));
        ASSERT_TRUE(bitmap.Contains(200000000000ll));
    }
    // duplicates
    {
        RoaringBitmap64 bitmap;
        std::vector<int64_t> values = {42ll, 42ll, 42ll, 100000000000ll, 100000000000ll};
        bitmap.AddMany(values.size(), values.data());
        ASSERT_EQ(bitmap.Cardinality(), 2);
        ASSERT_TRUE(bitmap.Contains(42ll));
        ASSERT_TRUE(bitmap.Contains(100000000000ll));
    }
    // unsorted input (reverse order)
    {
        std::vector<int64_t> values;
        for (int64_t i = 99; i >= 0; --i) {
            values.push_back(i + 100000000000ll);
        }
        RoaringBitmap64 bitmap;
        bitmap.AddMany(values.size(), values.data());
        ASSERT_EQ(bitmap.Cardinality(), 100);
        for (int64_t i = 0; i < 100; ++i) {
            ASSERT_TRUE(bitmap.Contains(i + 100000000000ll));
        }
    }
    // incremental insert (multiple AddMany calls accumulate)
    {
        RoaringBitmap64 bitmap;
        std::vector<int64_t> batch1 = {10ll, 20ll, 30ll};
        std::vector<int64_t> batch2 = {20ll, 40ll, 100000000000ll};
        bitmap.AddMany(batch1.size(), batch1.data());
        ASSERT_EQ(bitmap.Cardinality(), 3);
        bitmap.AddMany(batch2.size(), batch2.data());
        ASSERT_EQ(bitmap.Cardinality(), 5);
        ASSERT_TRUE(bitmap.Contains(10ll));
        ASSERT_TRUE(bitmap.Contains(20ll));
        ASSERT_TRUE(bitmap.Contains(30ll));
        ASSERT_TRUE(bitmap.Contains(40ll));
        ASSERT_TRUE(bitmap.Contains(100000000000ll));
    }
    // large values near MAX_VALUE
    {
        std::vector<int64_t> values;
        for (int64_t i = 0; i < 50; ++i) {
            values.push_back(RoaringBitmap64::MAX_VALUE - 1 - i);
        }
        RoaringBitmap64 bitmap;
        bitmap.AddMany(values.size(), values.data());
        ASSERT_EQ(bitmap.Cardinality(), 50);
        for (auto v : values) {
            ASSERT_TRUE(bitmap.Contains(v));
        }
    }
    // consistency with Add: AddMany must produce the same bitmap as repeated Add
    {
        std::vector<int64_t> values;
        for (int64_t i = 0; i < 100; ++i) {
            values.push_back(i + 100000000000ll);
        }
        for (int64_t i = 0; i < 50; ++i) {
            values.push_back(i + 200000000000ll);
        }
        RoaringBitmap64 bitmap_add;
        for (auto v : values) {
            bitmap_add.Add(v);
        }
        RoaringBitmap64 bitmap_add_many;
        bitmap_add_many.AddMany(values.size(), values.data());
        ASSERT_EQ(bitmap_add, bitmap_add_many);
    }
}

}  // namespace paimon::test