// Copyright 2025-present the zvec project
//
// Licensed 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 <algorithm>
#include <bitset>
#include <iostream>
#include <memory>
#include <set>
#include <vector>
#include <ailego/container/bitmap.h>
#include <ailego/utility/bitset_helper.h>
#include <gtest/gtest.h>
#include <zvec/ailego/utility/time_helper.h>

#if defined(__AVX2__)
#define INTRINSICS_SET "AVX2"
#elif defined(__AVX__)
#define INTRINSICS_SET "AVX"
#elif defined(__SSE4_2__)
#define INTRINSICS_SET "SSE4.2"
#elif defined(__SSE4_1__)
#define INTRINSICS_SET "SSE4.1"
#elif defined(__SSE2__)
#define INTRINSICS_SET "SSE2"
#else
#define INTRINSICS_SET "NONE"
#endif

using namespace zvec::ailego;

TEST(FixedBitset, General) {
  FixedBitset<0> bitset0;
  FixedBitset<32> bitset32;
  FixedBitset<64> bitset64;

  EXPECT_EQ(0u, bitset0.size());
  EXPECT_EQ(32u, bitset32.size());
  EXPECT_EQ(64u, bitset64.size());

  EXPECT_TRUE(bitset32.test_none());
  EXPECT_TRUE(bitset64.test_none());

  bitset32.set(30);
  bitset64.set(60);

  FixedBitset<32> bitset32_2(bitset32);
  FixedBitset<64> bitset64_2(bitset64);

  bitset32.set(28);
  bitset64.set(55);

  EXPECT_TRUE(bitset32_2.test_any());
  EXPECT_TRUE(bitset64_2.test_any());

  EXPECT_FALSE(bitset32_2.test_all());
  EXPECT_FALSE(bitset64_2.test_all());

  EXPECT_EQ(1u, bitset32_2.cardinality());
  EXPECT_EQ(1u, bitset64_2.cardinality());

  bitset32_2 = bitset32;
  bitset64_2 = bitset64;

  EXPECT_EQ(2u, bitset32_2.cardinality());
  EXPECT_EQ(2u, bitset64_2.cardinality());

  bitset32.reset(28);
  bitset64.reset(55);

  bitset32_2 = bitset32;
  bitset64_2 = bitset64;

  EXPECT_EQ(1u, bitset32_2.cardinality());
  EXPECT_EQ(1u, bitset64_2.cardinality());

  bitset32.flip(30);
  bitset64.flip(60);

  EXPECT_EQ(0u, bitset32.cardinality());
  EXPECT_EQ(0u, bitset64.cardinality());
}

TEST(FixedBitset, And) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  FixedBitset<3552> bitset1;
  FixedBitset<3552> bitset2;
  FixedBitset<3552> bitset3;
  std::bitset<3552> stl_bitset1;
  std::bitset<3552> stl_bitset2;
  std::bitset<3552> stl_bitset3;

  for (uint32_t i = 0; i < 623; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 623; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }

  bitset3 = bitset1;
  bitset3.bitwise_and(bitset2);
  stl_bitset3 = stl_bitset1 & stl_bitset2;

  for (uint32_t i = 0; i < bitset3.size(); ++i) {
    EXPECT_EQ(bitset3.test(i), stl_bitset3.test(i));
  }
  EXPECT_EQ(stl_bitset3.count(), bitset3.cardinality());

  FixedBitset<512>::Cast((uint32_t *)bitset3.data() + 1)
      ->bitwise_and(*(FixedBitset<512>::Cast((uint32_t *)bitset2.data() + 3)));
}

TEST(FixedBitset, Andnot) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  FixedBitset<2528> bitset1;
  FixedBitset<2528> bitset2;
  FixedBitset<2528> bitset3;
  std::bitset<2528> stl_bitset1;
  std::bitset<2528> stl_bitset2;
  std::bitset<2528> stl_bitset3;

  for (uint32_t i = 0; i < 623; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 623; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }

  bitset3 = bitset1;
  bitset3.bitwise_andnot(bitset2);
  stl_bitset3 = stl_bitset1 & (~stl_bitset2);

  for (uint32_t i = 0; i < bitset3.size(); ++i) {
    EXPECT_EQ(bitset3.test(i), stl_bitset3.test(i));
  }
  EXPECT_EQ(stl_bitset3.count(), bitset3.cardinality());

  FixedBitset<512>::Cast((uint32_t *)bitset3.data() + 1)
      ->bitwise_andnot(
          *(FixedBitset<512>::Cast((uint32_t *)bitset2.data() + 3)));
}

TEST(FixedBitset, Or) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  FixedBitset<2528> bitset1;
  FixedBitset<2528> bitset2;
  FixedBitset<2528> bitset3;
  std::bitset<2528> stl_bitset1;
  std::bitset<2528> stl_bitset2;
  std::bitset<2528> stl_bitset3;

  for (uint32_t i = 0; i < 623; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 623; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }

  bitset3 = bitset1;
  bitset3.bitwise_or(bitset2);
  stl_bitset3 = stl_bitset1 | stl_bitset2;

  for (uint32_t i = 0; i < bitset3.size(); ++i) {
    EXPECT_EQ(bitset3.test(i), stl_bitset3.test(i));
  }
  EXPECT_EQ(stl_bitset3.count(), bitset3.cardinality());

  FixedBitset<512>::Cast((uint32_t *)bitset3.data() + 1)
      ->bitwise_or(*(FixedBitset<512>::Cast((uint32_t *)bitset2.data() + 3)));
}

TEST(FixedBitset, Xor) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  FixedBitset<2528> bitset1;
  FixedBitset<2528> bitset2;
  FixedBitset<2528> bitset3;
  std::bitset<2528> stl_bitset1;
  std::bitset<2528> stl_bitset2;
  std::bitset<2528> stl_bitset3;

  for (uint32_t i = 0; i < 623; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 623; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }

  bitset3 = bitset1;
  bitset3.bitwise_xor(bitset2);
  stl_bitset3 = stl_bitset1 ^ stl_bitset2;

  for (uint32_t i = 0; i < bitset3.size(); ++i) {
    EXPECT_EQ(bitset3.test(i), stl_bitset3.test(i));
  }
  EXPECT_EQ(stl_bitset3.count(), bitset3.cardinality());

  FixedBitset<512>::Cast((uint32_t *)bitset3.data() + 1)
      ->bitwise_xor(*(FixedBitset<512>::Cast((uint32_t *)bitset2.data() + 3)));
}

TEST(FixedBitset, Not) {
  FixedBitset<1504> bitset1;
  EXPECT_FALSE(bitset1.test_all());
  EXPECT_FALSE(bitset1.test_any());
  EXPECT_TRUE(bitset1.test_none());
  EXPECT_EQ(0u, bitset1.cardinality());

  for (uint32_t i = 0; i < bitset1.size(); ++i) {
    bitset1.set(i);
  }
  EXPECT_EQ(bitset1.size(), bitset1.cardinality());
  EXPECT_TRUE(bitset1.test_all());
  EXPECT_TRUE(bitset1.test_any());
  EXPECT_FALSE(bitset1.test_none());

  bitset1.bitwise_not();
  EXPECT_FALSE(bitset1.test_all());
  EXPECT_FALSE(bitset1.test_any());
  EXPECT_TRUE(bitset1.test_none());

  FixedBitset<512> bitset2;
  EXPECT_FALSE(bitset2.test_all());
  EXPECT_FALSE(bitset2.test_any());
  EXPECT_TRUE(bitset2.test_none());

  for (uint32_t i = 0; i < bitset2.size(); ++i) {
    bitset2.set(i);
  }
  EXPECT_TRUE(bitset2.test_all());
  EXPECT_TRUE(bitset2.test_any());
  EXPECT_FALSE(bitset2.test_none());

  bitset2.bitwise_not();
  EXPECT_FALSE(bitset2.test_all());
  EXPECT_FALSE(bitset2.test_any());
  EXPECT_TRUE(bitset2.test_none());

  FixedBitset<512 - 32>::Cast((uint32_t *)bitset2.data() + 1)->bitwise_not();
}

TEST(FixedBitset, TestAll) {
  FixedBitset<1504> bitset;
  EXPECT_FALSE(bitset.test_all());

  for (uint32_t i = 0; i < bitset.size(); ++i) {
    bitset.set(i);
  }
  EXPECT_TRUE(bitset.test_all());

  bitset.reset(999u);
  EXPECT_FALSE(bitset.test_all());
  EXPECT_FALSE(
      FixedBitset<1504 - 32>::Cast((uint32_t *)bitset.data() + 1)->test_all());
}

TEST(FixedBitset, TestAny) {
  FixedBitset<1504> bitset;
  EXPECT_FALSE(bitset.test_any());

  for (uint32_t i = 666; i < 888; ++i) {
    bitset.set(i);
  }
  EXPECT_TRUE(bitset.test_any());

  for (uint32_t i = 666; i < 777; ++i) {
    bitset.reset(i);
  }
  EXPECT_TRUE(bitset.test_any());
  EXPECT_TRUE(
      FixedBitset<1504 - 32>::Cast((uint32_t *)bitset.data() + 1)->test_any());
}

TEST(FixedBitset, TestNone) {
  FixedBitset<1504> bitset;
  EXPECT_TRUE(bitset.test_none());

  for (uint32_t i = 1000; i < 1111; ++i) {
    bitset.set(i);
  }
  EXPECT_FALSE(bitset.test_none());

  for (uint32_t i = 1000; i < 1110; ++i) {
    bitset.flip(i);
  }
  EXPECT_FALSE(bitset.test_none());
  EXPECT_FALSE(
      FixedBitset<1504 - 32>::Cast((uint32_t *)bitset.data() + 1)->test_none());
}

TEST(FixedBitset, Extract) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  FixedBitset<2528> bitset1;
  std::vector<size_t> vector1;

  for (uint32_t i = 0; i < 1111; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());

    bitset1.set(val1);
    vector1.push_back(val1);
  }

  std::sort(vector1.begin(), vector1.end());
  vector1.erase(std::unique(vector1.begin(), vector1.end()), vector1.end());

  std::vector<size_t> vector2;
  bitset1.extract(&vector2);

  EXPECT_EQ(vector1.size(), vector2.size());
  EXPECT_TRUE(std::equal(vector1.begin(), vector1.end(), vector2.begin()));
}

TEST(FixedBitset, BitwiseXorCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  FixedBitset<2528> bitset1;
  FixedBitset<2528> bitset2;
  std::bitset<2528> stl_bitset1;
  std::bitset<2528> stl_bitset2;

  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ(0u, FixedBitset<2528>::BitwiseXorCardinality(bitset1, bitset1));
  EXPECT_EQ(0u, FixedBitset<2528>::BitwiseXorCardinality(bitset2, bitset2));
  EXPECT_EQ((stl_bitset1 ^ stl_bitset2).count(),
            FixedBitset<2528>::BitwiseXorCardinality(bitset1, bitset2));

  EXPECT_EQ(FixedBitset<2528>::BitwiseAndnotCardinality(bitset1, bitset2) +
                FixedBitset<2528>::BitwiseAndnotCardinality(bitset2, bitset1),
            FixedBitset<2528>::BitwiseXorCardinality(bitset1, bitset2));
}

TEST(FixedBitset, BitwiseOrCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  FixedBitset<2528> bitset1;
  FixedBitset<2528> bitset2;
  std::bitset<2528> stl_bitset1;
  std::bitset<2528> stl_bitset2;

  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ((stl_bitset1 | stl_bitset2).count(),
            FixedBitset<2528>::BitwiseOrCardinality(bitset1, bitset2));
}

TEST(FixedBitset, BitwiseAndCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  FixedBitset<2528> bitset1;
  FixedBitset<2528> bitset2;
  std::bitset<2528> stl_bitset1;
  std::bitset<2528> stl_bitset2;

  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ((stl_bitset1 & stl_bitset2).count(),
            FixedBitset<2528>::BitwiseAndCardinality(bitset1, bitset2));
}

TEST(FixedBitset, BitwiseAndnotCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  FixedBitset<2528> bitset1;
  FixedBitset<2528> bitset2;
  std::bitset<2528> stl_bitset1;
  std::bitset<2528> stl_bitset2;

  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ((stl_bitset1 & ~stl_bitset2).count(),
            FixedBitset<2528>::BitwiseAndnotCardinality(bitset1, bitset2));

  EXPECT_EQ((stl_bitset2 & ~stl_bitset1).count(),
            FixedBitset<2528>::BitwiseAndnotCardinality(bitset2, bitset1));
}

TEST(FixedBitset, Benchmark) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  const uint32_t dimension = 2048u;
  const uint32_t test_count = 100000u;

  std::vector<FixedBitset<dimension>> bucket1_vec;
  std::vector<FixedBitset<dimension>> bucket2_vec;

  std::unique_ptr<FixedBitset<dimension>> bucket1(new FixedBitset<dimension>);
  std::unique_ptr<FixedBitset<dimension>> bucket2(new FixedBitset<dimension>);

  for (uint32_t i = 0; i < 2000; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bucket1->size());
    uint32_t val2 = (uint32_t)(rand() % bucket2->size());

    bucket1->set(val1);
    bucket2->set(val2);
  }
  for (uint32_t i = 0; i < 1000; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bucket1->size());
    uint32_t val2 = (uint32_t)(rand() % bucket2->size());

    bucket1->flip(val1);
    bucket2->flip(val2);
  }
  for (uint32_t i = 0; i < 500; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bucket1->size());
    uint32_t val2 = (uint32_t)(rand() % bucket2->size());

    bucket1->reset(val1);
    bucket2->reset(val2);
  }

  bucket1_vec.reserve(test_count);
  bucket2_vec.reserve(test_count);
  for (uint32_t j = 0; j < test_count; ++j) {
    bucket1_vec.push_back(*bucket1);
    bucket2_vec.push_back(*bucket2);
  }

  {
    uint64_t t1 = Monotime::MicroSeconds();
    uint64_t sum = 0;
    for (uint32_t i = 0; i < test_count; ++i) {
      sum += FixedBitset<dimension>::BitwiseAndCardinality(bucket1_vec[i],
                                                           bucket2_vec[i]);
    }
    std::cout << INTRINSICS_SET
              << " BitwiseAndCardinality: " << Monotime::MicroSeconds() - t1
              << " us, sum: " << sum << std::endl;
  }

  {
    uint64_t t1 = Monotime::MicroSeconds();
    uint64_t sum = 0;
    for (uint32_t i = 0; i < test_count; ++i) {
      sum += FixedBitset<dimension>::BitwiseAndnotCardinality(bucket1_vec[i],
                                                              bucket2_vec[i]);
    }
    std::cout << INTRINSICS_SET
              << " BitwiseAndnotCardinality: " << Monotime::MicroSeconds() - t1
              << " us, sum: " << sum << std::endl;
  }

  {
    uint64_t t1 = Monotime::MicroSeconds();
    uint64_t sum = 0;
    for (uint32_t i = 0; i < test_count; ++i) {
      sum += FixedBitset<dimension>::BitwiseXorCardinality(bucket1_vec[i],
                                                           bucket2_vec[i]);
    }
    std::cout << INTRINSICS_SET
              << " BitwiseXorCardinality: " << Monotime::MicroSeconds() - t1
              << " us, sum: " << sum << std::endl;
  }

  {
    uint64_t t1 = Monotime::MicroSeconds();
    uint64_t sum = 0;
    for (uint32_t i = 0; i < test_count; ++i) {
      sum += FixedBitset<dimension>::BitwiseOrCardinality(bucket1_vec[i],
                                                          bucket2_vec[i]);
    }
    std::cout << INTRINSICS_SET
              << " BitwiseOrCardinality: " << Monotime::MicroSeconds() - t1
              << " us, sum: " << sum << std::endl;
  }

  {
    std::unique_ptr<FixedBitset<dimension>> bucket3(new FixedBitset<dimension>);
    *bucket3 = bucket1_vec[0];

    uint64_t t1 = Monotime::MicroSeconds();
    for (uint32_t i = 0; i < test_count; ++i) {
      bucket3->bitwise_and(bucket2_vec[i]);
    }
    std::cout << INTRINSICS_SET << " And: " << Monotime::MicroSeconds() - t1
              << " us" << std::endl;
  }

  {
    std::unique_ptr<FixedBitset<dimension>> bucket3(new FixedBitset<dimension>);
    *bucket3 = bucket1_vec[0];

    uint64_t t1 = Monotime::MicroSeconds();
    for (uint32_t i = 0; i < test_count; ++i) {
      bucket3->bitwise_andnot(bucket2_vec[i]);
    }
    std::cout << INTRINSICS_SET << " Andnot: " << Monotime::MicroSeconds() - t1
              << " us" << std::endl;
  }

  {
    std::unique_ptr<FixedBitset<dimension>> bucket3(new FixedBitset<dimension>);
    *bucket3 = bucket1_vec[0];

    uint64_t t1 = Monotime::MicroSeconds();
    for (uint32_t i = 0; i < test_count; ++i) {
      bucket3->bitwise_or(bucket2_vec[i]);
    }
    std::cout << INTRINSICS_SET << " Or: " << Monotime::MicroSeconds() - t1
              << " us" << std::endl;
  }

  {
    std::unique_ptr<FixedBitset<dimension>> bucket3(new FixedBitset<dimension>);
    *bucket3 = bucket1_vec[0];

    uint64_t t1 = Monotime::MicroSeconds();
    for (uint32_t i = 0; i < test_count; ++i) {
      bucket3->bitwise_xor(bucket2_vec[i]);
    }
    std::cout << INTRINSICS_SET << " Xor: " << Monotime::MicroSeconds() - t1
              << " us" << std::endl;
  }
}

TEST(Bitset, General) {
  Bitset bitset32(31);
  Bitset bitset64(61);

  EXPECT_EQ(32u, bitset32.size());
  EXPECT_EQ(64u, bitset64.size());

  EXPECT_TRUE(bitset32.test_none());
  EXPECT_TRUE(bitset64.test_none());

  bitset32.set(30);
  bitset64.set(60);

  Bitset bitset32_2(bitset32);
  Bitset bitset64_2(bitset64);

  bitset32.set(28);
  bitset64.set(55);

  EXPECT_TRUE(bitset32_2.test_any());
  EXPECT_TRUE(bitset64_2.test_any());

  EXPECT_FALSE(bitset32_2.test_all());
  EXPECT_FALSE(bitset64_2.test_all());

  EXPECT_EQ(1u, bitset32_2.cardinality());
  EXPECT_EQ(1u, bitset64_2.cardinality());

  bitset32_2 = bitset32;
  bitset64_2 = bitset64;

  EXPECT_EQ(2u, bitset32_2.cardinality());
  EXPECT_EQ(2u, bitset64_2.cardinality());

  bitset32.reset(28);
  bitset64.reset(55);

  bitset32_2 = bitset32;
  bitset64_2 = bitset64;

  EXPECT_EQ(1u, bitset32_2.cardinality());
  EXPECT_EQ(1u, bitset64_2.cardinality());

  bitset32.flip(30);
  bitset64.flip(60);

  EXPECT_EQ(0u, bitset32.cardinality());
  EXPECT_EQ(0u, bitset64.cardinality());
}

TEST(Bitset, BitwiseXorCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitset bitset1;
  Bitset bitset2;
  bitset1.resize(500000);
  bitset2.resize(630000);
  std::bitset<638888> stl_bitset1;
  std::bitset<638888> stl_bitset2;

  for (uint32_t i = 0; i < 800; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    ;
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ((stl_bitset1 ^ stl_bitset2).count(),
            Bitset::BitwiseXorCardinality(bitset1, bitset2));

  EXPECT_EQ(Bitset::BitwiseAndnotCardinality(bitset1, bitset2) +
                Bitset::BitwiseAndnotCardinality(bitset2, bitset1),
            Bitset::BitwiseXorCardinality(bitset1, bitset2));
  EXPECT_EQ(Bitset::BitwiseXorCardinality(bitset1, bitset2),
            Bitset::BitwiseXorCardinality(bitset2, bitset1));
}

TEST(Bitset, BitwiseOrCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitset bitset1;
  Bitset bitset2;
  bitset1.resize(599999);
  bitset2.resize(500000);

  std::bitset<638888> stl_bitset1;
  std::bitset<638888> stl_bitset2;

  for (uint32_t i = 0; i < 800; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ((stl_bitset1 | stl_bitset2).count(),
            Bitset::BitwiseOrCardinality(bitset1, bitset2));
  EXPECT_EQ(Bitset::BitwiseOrCardinality(bitset1, bitset2),
            Bitset::BitwiseOrCardinality(bitset2, bitset1));
}

TEST(Bitset, BitwiseAndCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitset bitset1;
  Bitset bitset2;
  bitset1.resize(500001);
  bitset2.resize(599999);

  std::bitset<638888> stl_bitset1;
  std::bitset<638888> stl_bitset2;

  for (uint32_t i = 0; i < 800; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ((stl_bitset1 & stl_bitset2).count(),
            Bitset::BitwiseAndCardinality(bitset1, bitset2));
  EXPECT_EQ(Bitset::BitwiseAndCardinality(bitset1, bitset2),
            Bitset::BitwiseAndCardinality(bitset2, bitset1));
}

TEST(Bitset, BitwiseAndnotCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitset bitset1;
  Bitset bitset2;
  bitset1.resize(599997);
  bitset2.resize(500002);

  std::bitset<638888> stl_bitset1;
  std::bitset<638888> stl_bitset2;

  for (uint32_t i = 0; i < 800; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.set(val1);
    stl_bitset1.set(val1);

    bitset2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = (uint32_t)(rand() % bitset1.size());
    uint32_t val2 = (uint32_t)(rand() % bitset2.size());

    bitset1.flip(val1);
    stl_bitset1.flip(val1);

    bitset2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ((stl_bitset1 & ~stl_bitset2).count(),
            Bitset::BitwiseAndnotCardinality(bitset1, bitset2));

  EXPECT_EQ((stl_bitset2 & ~stl_bitset1).count(),
            Bitset::BitwiseAndnotCardinality(bitset2, bitset1));
}

TEST(Bitmap, General) {
  const uint32_t data1[] = {0,     1,      2,      4,      7,    9,
                            31,    65,     77,     100,    1000, 1999,
                            19999, 100000, 188888, 2999999};
  const uint32_t data2[] = {8,     12,    13,    24,     7777,      9999,
                            66666, 88888, 99999, 100002, 0x7fffffff};
  Bitmap bitmap1;

  EXPECT_EQ(0u, bitmap1.cardinality());
  for (size_t i = 0; i < sizeof(data1) / sizeof(data1[0]); ++i) {
    bitmap1.set(data1[i]);
  }

  // Test `Set`
  Bitmap bitmap2(bitmap1);

  EXPECT_NE(0u, bitmap2.cardinality());
  EXPECT_EQ(sizeof(data1) / sizeof(data1[0]), bitmap2.cardinality());
  for (size_t i = 0; i < sizeof(data1) / sizeof(data1[0]); ++i) {
    EXPECT_TRUE(bitmap2.test(data1[i]));
  }

  // Test `Reset`
  for (size_t i = 0; i < sizeof(data2) / sizeof(data2[0]); ++i) {
    bitmap1.reset(data2[i]);
  }
  for (size_t i = 0; i < sizeof(data2) / sizeof(data2[0]); ++i) {
    EXPECT_FALSE(bitmap1.test(data2[i]));
  }

  EXPECT_EQ(sizeof(data1) / sizeof(data1[0]), bitmap1.cardinality());
  for (size_t i = 0; i < sizeof(data1) / sizeof(data1[0]); ++i) {
    bitmap1.reset(data1[i]);
  }
  EXPECT_EQ(0u, bitmap1.cardinality());

  // Test `Flip`
  for (size_t i = 0; i < sizeof(data1) / sizeof(data1[0]); ++i) {
    bitmap1.flip(data1[i]);
  }
  for (size_t i = 0; i < sizeof(data2) / sizeof(data2[0]); ++i) {
    bitmap1.flip(data2[i]);
  }
  EXPECT_EQ(sizeof(data1) / sizeof(data1[0]) + sizeof(data2) / sizeof(data2[0]),
            bitmap1.cardinality());

  bitmap2 = bitmap1;
  for (size_t i = 0; i < sizeof(data1) / sizeof(data1[0]); ++i) {
    EXPECT_TRUE(bitmap2.test(data1[i]));
  }
  for (size_t i = 0; i < sizeof(data2) / sizeof(data2[0]); ++i) {
    EXPECT_TRUE(bitmap2.test(data2[i]));
  }

  // Test `ShrinkToFit`
  bitmap1.shrink_to_fit();
  for (size_t i = 0; i < sizeof(data1) / sizeof(data1[0]); ++i) {
    EXPECT_TRUE(bitmap1.test(data1[i]));
  }
  for (size_t i = 0; i < sizeof(data2) / sizeof(data2[0]); ++i) {
    EXPECT_TRUE(bitmap1.test(data2[i]));
  }

  // Test `Clear`
  EXPECT_NE(0u, bitmap1.cardinality());
  bitmap2 = bitmap1;
  bitmap1.clear();
  EXPECT_EQ(0u, bitmap1.cardinality());
  for (size_t i = 0; i < sizeof(data1) / sizeof(data1[0]); ++i) {
    EXPECT_FALSE(bitmap1.test(data1[i]));
  }
  for (size_t i = 0; i < sizeof(data2) / sizeof(data2[0]); ++i) {
    EXPECT_FALSE(bitmap1.test(data2[i]));
  }
  for (size_t i = 0; i < sizeof(data1) / sizeof(data1[0]); ++i) {
    EXPECT_TRUE(bitmap2.test(data1[i]));
  }
  for (size_t i = 0; i < sizeof(data2) / sizeof(data2[0]); ++i) {
    EXPECT_TRUE(bitmap2.test(data2[i]));
  }
}

TEST(Bitmap, ShrinkToFit) {
  Bitmap bitmap1;
  bitmap1.shrink_to_fit();

  EXPECT_EQ(0u, bitmap1.bucket_size());
  bitmap1.set(2);
  EXPECT_EQ(1u, bitmap1.bucket_size());
  bitmap1.reset(2);
  EXPECT_EQ(1u, bitmap1.bucket_size());
  bitmap1.shrink_to_fit();
  EXPECT_EQ(0u, bitmap1.bucket_size());

  bitmap1.set(100);
  bitmap1.set(100000);
  bitmap1.set(1000000);
  EXPECT_EQ((1000000u + 0xffff) / 0x10000, bitmap1.bucket_size());

  bitmap1.reset(100);
  bitmap1.reset(1000000);
  EXPECT_EQ((1000000u + 0xffff) / 0x10000, bitmap1.bucket_size());
  bitmap1.shrink_to_fit();
  EXPECT_EQ((100000u + 0xffff) / 0x10000, bitmap1.bucket_size());
}

TEST(Bitmap, And) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitmap bitmap1, bitmap2;
  std::set<size_t> set1, set2, set3;
  std::vector<size_t> vec1, vec3;

  for (uint32_t i = 0; i < 25000; ++i) {
    uint32_t val1 = rand() % 1000000;
    bitmap1.set(val1);
    set1.insert(val1);
  }

  for (uint32_t i = 0; i < 45000; ++i) {
    uint32_t val2 = rand() % 1000000;
    bitmap2.set(val2);
    set2.insert(val2);
  }
  std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(),
                        std::inserter(set3, set3.begin()));
  bitmap1.bitwise_and(bitmap2);
  bitmap1.extract(&vec1);
  ASSERT_EQ(bitmap1.cardinality(), vec1.size());
  ASSERT_EQ(set3.size(), vec1.size());

  vec3.reserve(set3.size());
  std::copy(set3.begin(), set3.end(), std::back_inserter(vec3));
  EXPECT_TRUE(std::equal(vec1.begin(), vec1.end(), vec3.begin()));
}

TEST(Bitmap, Andnot) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitmap bitmap1, bitmap2;
  std::set<size_t> set1, set2, set3;
  std::vector<size_t> vec1, vec3;

  for (uint32_t i = 0; i < 20000; ++i) {
    uint32_t val1 = rand() % 1000000;
    bitmap1.set(val1);
    set1.insert(val1);
  }

  for (uint32_t i = 0; i < 20000; ++i) {
    uint32_t val2 = rand() % 1000000;
    bitmap2.set(val2);
    set2.insert(val2);
  }
  std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(),
                      std::inserter(set3, set3.begin()));
  bitmap1.bitwise_andnot(bitmap2);
  bitmap1.extract(&vec1);
  ASSERT_EQ(bitmap1.cardinality(), vec1.size());
  ASSERT_EQ(set3.size(), vec1.size());

  vec3.reserve(set3.size());
  std::copy(set3.begin(), set3.end(), std::back_inserter(vec3));
  EXPECT_TRUE(std::equal(vec1.begin(), vec1.end(), vec3.begin()));
}

TEST(Bitmap, Or) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitmap bitmap1, bitmap2;
  std::set<size_t> set1, set2, set3;
  std::vector<size_t> vec1, vec3;

  for (uint32_t i = 0; i < 3000; ++i) {
    uint32_t val1 = rand() % 2000000;
    bitmap1.set(val1);
    set1.insert(val1);
  }

  for (uint32_t i = 0; i < 2000; ++i) {
    uint32_t val2 = rand() % 2000000;
    bitmap2.set(val2);
    set2.insert(val2);
  }
  std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(),
                 std::inserter(set3, set3.begin()));
  bitmap1.bitwise_or(bitmap2);
  bitmap1.extract(&vec1);
  ASSERT_EQ(bitmap1.cardinality(), vec1.size());
  ASSERT_EQ(set3.size(), vec1.size());

  vec3.reserve(set3.size());
  std::copy(set3.begin(), set3.end(), std::back_inserter(vec3));
  EXPECT_TRUE(std::equal(vec1.begin(), vec1.end(), vec3.begin()));
}

TEST(Bitmap, Xor) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitmap bitmap1, bitmap2;
  std::set<size_t> set1, set2, set3;
  std::vector<size_t> vec1, vec3;

  for (uint32_t i = 0; i < 3000; ++i) {
    uint32_t val1 = rand() % 2000000;
    bitmap1.set(val1);
    set1.insert(val1);
  }

  for (uint32_t i = 0; i < 2000; ++i) {
    uint32_t val2 = rand() % 2000000;
    bitmap2.set(val2);
    set2.insert(val2);
  }
  std::set_symmetric_difference(set1.begin(), set1.end(), set2.begin(),
                                set2.end(), std::inserter(set3, set3.begin()));
  bitmap1.bitwise_xor(bitmap2);
  bitmap1.extract(&vec1);
  ASSERT_EQ(bitmap1.cardinality(), vec1.size());
  ASSERT_EQ(set3.size(), vec1.size());

  vec3.reserve(set3.size());
  std::copy(set3.begin(), set3.end(), std::back_inserter(vec3));
  EXPECT_TRUE(std::equal(vec1.begin(), vec1.end(), vec3.begin()));
}

TEST(Bitmap, Not) {
  Bitmap bitmap1, bitmap2, bitmap3;
  std::set<size_t> set1, set2, set3;
  std::vector<size_t> vec1;

  for (uint32_t i = 0; i < 20000; ++i) {
    uint32_t val1 = rand() % 1000000;
    bitmap1.set(val1);
    set1.insert(val1);
  }

  for (uint32_t i = 0; i < 20000; ++i) {
    uint32_t val2 = rand() % 1000000;
    bitmap2.set(val2);
    set2.insert(val2);
  }

  bitmap2.bitwise_not();
  bitmap2.bitwise_not();

  {
    set3.clear();
    vec1.clear();
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(),
                          std::inserter(set3, set3.begin()));

    bitmap3 = bitmap1;
    bitmap3.bitwise_and(bitmap2);
    bitmap3.extract(&vec1);
    ASSERT_EQ(bitmap3.cardinality(), vec1.size());
    ASSERT_EQ(set3.size(), vec1.size());

    std::vector<size_t> vec3(set3.begin(), set3.end());
    EXPECT_TRUE(std::equal(vec1.begin(), vec1.end(), vec3.begin()));
  }

  {
    set3.clear();
    vec1.clear();
    std::set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(),
                        std::inserter(set3, set3.begin()));

    bitmap3 = bitmap1;
    bitmap3.bitwise_andnot(bitmap2);
    bitmap3.extract(&vec1);
    ASSERT_EQ(bitmap3.cardinality(), vec1.size());
    ASSERT_EQ(set3.size(), vec1.size());

    std::vector<size_t> vec3(set3.begin(), set3.end());
    EXPECT_TRUE(std::equal(vec1.begin(), vec1.end(), vec3.begin()));
  }

  {
    set3.clear();
    vec1.clear();
    std::set_union(set1.begin(), set1.end(), set2.begin(), set2.end(),
                   std::inserter(set3, set3.begin()));

    bitmap3 = bitmap1;
    bitmap3.bitwise_or(bitmap2);
    bitmap3.extract(&vec1);
    ASSERT_EQ(bitmap3.cardinality(), vec1.size());
    ASSERT_EQ(set3.size(), vec1.size());

    std::vector<size_t> vec3(set3.begin(), set3.end());
    EXPECT_TRUE(std::equal(vec1.begin(), vec1.end(), vec3.begin()));
  }

  {
    set3.clear();
    vec1.clear();
    std::set_symmetric_difference(set1.begin(), set1.end(), set2.begin(),
                                  set2.end(),
                                  std::inserter(set3, set3.begin()));

    bitmap3 = bitmap1;
    bitmap3.bitwise_xor(bitmap2);
    bitmap3.extract(&vec1);
    ASSERT_EQ(bitmap3.cardinality(), vec1.size());
    ASSERT_EQ(set3.size(), vec1.size());

    std::vector<size_t> vec3(set3.begin(), set3.end());
    EXPECT_TRUE(std::equal(vec1.begin(), vec1.end(), vec3.begin()));
  }
}

TEST(Bitmap, TestAll) {
  Bitmap bitmap;
  EXPECT_FALSE(bitmap.test_all());

  for (uint32_t i = 0; i < Bitmap::Bucket::MAX_SIZE * 2; ++i) {
    bitmap.set(i);
  }
  EXPECT_TRUE(bitmap.test_all());

  bitmap.reset(Bitmap::Bucket::MAX_SIZE + 2);
  EXPECT_FALSE(bitmap.test_all());
}

TEST(Bitmap, TestAny) {
  Bitmap bitmap;
  EXPECT_FALSE(bitmap.test_any());

  for (uint32_t i = 69000; i < 70000; ++i) {
    bitmap.set(i);
  }
  EXPECT_TRUE(bitmap.test_any());

  for (uint32_t i = 69888; i < 70111; ++i) {
    bitmap.reset(i);
  }
  EXPECT_TRUE(bitmap.test_any());
}

TEST(Bitmap, TestNone) {
  Bitmap bitmap;
  EXPECT_TRUE(bitmap.test_none());

  for (uint32_t i = 65000; i < 70000; ++i) {
    bitmap.set(i);
  }
  EXPECT_FALSE(bitmap.test_none());

  for (uint32_t i = 65555; i < 70022; ++i) {
    bitmap.flip(i);
  }
  EXPECT_FALSE(bitmap.test_none());
}

TEST(Bitmap, Extract) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitmap bitmap1;
  std::vector<size_t> vector1;

  for (uint32_t i = 0; i < 1111; ++i) {
    uint32_t val1 = rand();

    bitmap1.set(val1);
    vector1.push_back(val1);
  }

  std::sort(vector1.begin(), vector1.end());
  vector1.erase(std::unique(vector1.begin(), vector1.end()), vector1.end());

  std::vector<size_t> vector2;
  bitmap1.extract(&vector2);

  EXPECT_EQ(vector1.size(), vector2.size());
  EXPECT_TRUE(std::equal(vector1.begin(), vector1.end(), vector2.begin()));
}

TEST(Bitmap, BitwiseXorCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitmap bitmap1;
  Bitmap bitmap2;
  std::bitset<500000> stl_bitset1;
  std::bitset<500000> stl_bitset2;

  for (uint32_t i = 0; i < 800; ++i) {
    uint32_t val1 = rand() % 500000;
    uint32_t val2 = rand() % 500000;

    bitmap1.set(val1);
    stl_bitset1.set(val1);

    bitmap2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = rand() % 500000;
    uint32_t val2 = rand() % 500000;

    bitmap1.flip(val1);
    stl_bitset1.flip(val1);

    bitmap2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ((stl_bitset1 ^ stl_bitset2).count(),
            Bitmap::BitwiseXorCardinality(bitmap1, bitmap2));

  EXPECT_EQ(Bitmap::BitwiseAndnotCardinality(bitmap1, bitmap2) +
                Bitmap::BitwiseAndnotCardinality(bitmap2, bitmap1),
            Bitmap::BitwiseXorCardinality(bitmap1, bitmap2));
  EXPECT_EQ(Bitmap::BitwiseXorCardinality(bitmap2, bitmap1),
            Bitmap::BitwiseXorCardinality(bitmap1, bitmap2));
}

TEST(Bitmap, BitwiseOrCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitmap bitmap1;
  Bitmap bitmap2;
  std::bitset<500000> stl_bitset1;
  std::bitset<500000> stl_bitset2;

  for (uint32_t i = 0; i < 800; ++i) {
    uint32_t val1 = rand() % 500000;
    uint32_t val2 = rand() % 500000;

    bitmap1.set(val1);
    stl_bitset1.set(val1);

    bitmap2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = rand() % 500000;
    uint32_t val2 = rand() % 500000;

    bitmap1.flip(val1);
    stl_bitset1.flip(val1);

    bitmap2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ((stl_bitset1 | stl_bitset2).count(),
            Bitmap::BitwiseOrCardinality(bitmap1, bitmap2));
  EXPECT_EQ(Bitmap::BitwiseOrCardinality(bitmap2, bitmap1),
            Bitmap::BitwiseOrCardinality(bitmap1, bitmap2));
}

TEST(Bitmap, BitwiseAndCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitmap bitmap1;
  Bitmap bitmap2;
  std::bitset<500000> stl_bitset1;
  std::bitset<500000> stl_bitset2;

  for (uint32_t i = 0; i < 800; ++i) {
    uint32_t val1 = rand() % 500000;
    uint32_t val2 = rand() % 500000;

    bitmap1.set(val1);
    stl_bitset1.set(val1);

    bitmap2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = rand() % 500000;
    uint32_t val2 = rand() % 500000;

    bitmap1.flip(val1);
    stl_bitset1.flip(val1);

    bitmap2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ((stl_bitset1 & stl_bitset2).count(),
            Bitmap::BitwiseAndCardinality(bitmap1, bitmap2));
  EXPECT_EQ(Bitmap::BitwiseAndCardinality(bitmap2, bitmap1),
            Bitmap::BitwiseAndCardinality(bitmap1, bitmap2));
}

TEST(Bitmap, BitwiseAndnotCardinality) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitmap bitmap1;
  Bitmap bitmap2;
  std::bitset<500000> stl_bitset1;
  std::bitset<500000> stl_bitset2;

  for (uint32_t i = 0; i < 800; ++i) {
    uint32_t val1 = rand() % 500000;
    uint32_t val2 = rand() % 500000;

    bitmap1.set(val1);
    stl_bitset1.set(val1);

    bitmap2.set(val2);
    stl_bitset2.set(val2);
  }
  for (uint32_t i = 0; i < 600; ++i) {
    uint32_t val1 = rand() % 500000;
    uint32_t val2 = rand() % 500000;

    bitmap1.flip(val1);
    stl_bitset1.flip(val1);

    bitmap2.flip(val2);
    stl_bitset2.flip(val2);
  }
  EXPECT_EQ((stl_bitset1 & ~stl_bitset2).count(),
            Bitmap::BitwiseAndnotCardinality(bitmap1, bitmap2));

  EXPECT_EQ((stl_bitset2 & ~stl_bitset1).count(),
            Bitmap::BitwiseAndnotCardinality(bitmap2, bitmap1));
}

TEST(Bitmap, Benchmark) {
  srand((uint32_t)time(nullptr));
  srand((uint32_t)rand());

  Bitmap bitmap1, bitmap2;

  for (uint32_t i = 0; i < 2000; ++i) {
    uint32_t val1 = rand() % 200000000u;
    uint32_t val2 = rand() % 200000000u;

    bitmap1.set(val1);
    bitmap2.set(val2);
  }
  for (uint32_t i = 0; i < 1000; ++i) {
    uint32_t val1 = rand() % 200000000u;
    uint32_t val2 = rand() % 200000000u;

    bitmap1.flip(val1);
    bitmap2.flip(val2);
  }
  for (uint32_t i = 0; i < 500; ++i) {
    uint32_t val1 = rand() % 200000000u;
    uint32_t val2 = rand() % 200000000u;

    bitmap1.reset(val1);
    bitmap2.reset(val2);
  }

  {
    uint64_t t1 = Monotime::MicroSeconds();
    uint64_t sum = 0;
    for (uint32_t i = 0; i < 3; ++i) {
      sum += Bitmap::BitwiseAndCardinality(bitmap1, bitmap2);
    }
    std::cout << INTRINSICS_SET
              << " BitwiseAndCardinality: " << Monotime::MicroSeconds() - t1
              << " us, sum: " << sum << std::endl;
  }

  {
    uint64_t t1 = Monotime::MicroSeconds();
    uint64_t sum = 0;
    for (uint32_t i = 0; i < 3; ++i) {
      sum += Bitmap::BitwiseAndnotCardinality(bitmap1, bitmap2);
    }
    std::cout << INTRINSICS_SET
              << " BitwiseAndnotCardinality: " << Monotime::MicroSeconds() - t1
              << " us, sum: " << sum << std::endl;
  }

  {
    uint64_t t1 = Monotime::MicroSeconds();
    uint64_t sum = 0;
    for (uint32_t i = 0; i < 3; ++i) {
      sum += Bitmap::BitwiseXorCardinality(bitmap1, bitmap2);
    }
    std::cout << INTRINSICS_SET
              << " BitwiseXorCardinality: " << Monotime::MicroSeconds() - t1
              << " us, sum: " << sum << std::endl;
  }

  {
    uint64_t t1 = Monotime::MicroSeconds();
    uint64_t sum = 0;
    for (uint32_t i = 0; i < 3; ++i) {
      sum += Bitmap::BitwiseOrCardinality(bitmap1, bitmap2);
    }
    std::cout << INTRINSICS_SET
              << " BitwiseOrCardinality: " << Monotime::MicroSeconds() - t1
              << " us, sum: " << sum << std::endl;
  }

  {
    Bitmap bitmap3;
    bitmap3 = bitmap1;

    uint64_t t1 = Monotime::MicroSeconds();
    for (uint32_t i = 0; i < 3; ++i) {
      bitmap1.bitwise_and(bitmap2);
    }
    std::cout << INTRINSICS_SET << " And: " << Monotime::MicroSeconds() - t1
              << " us" << std::endl;
  }

  {
    Bitmap bitmap3;
    bitmap3 = bitmap1;

    uint64_t t1 = Monotime::MicroSeconds();
    for (uint32_t i = 0; i < 3; ++i) {
      bitmap1.bitwise_andnot(bitmap2);
    }
    std::cout << INTRINSICS_SET << " Andnot: " << Monotime::MicroSeconds() - t1
              << " us" << std::endl;
  }

  {
    Bitmap bitmap3;
    bitmap3 = bitmap1;

    uint64_t t1 = Monotime::MicroSeconds();
    for (uint32_t i = 0; i < 3; ++i) {
      bitmap1.bitwise_or(bitmap2);
    }
    std::cout << INTRINSICS_SET << " Or: " << Monotime::MicroSeconds() - t1
              << " us" << std::endl;
  }

  {
    Bitmap bitmap3;
    bitmap3 = bitmap1;

    uint64_t t1 = Monotime::MicroSeconds();
    for (uint32_t i = 0; i < 3; ++i) {
      bitmap1.bitwise_xor(bitmap2);
    }
    std::cout << INTRINSICS_SET << " Xor: " << Monotime::MicroSeconds() - t1
              << " us" << std::endl;
  }
}