xref: /llvm-project/llvm/unittests/ADT/CoalescingBitVectorTest.cpp (revision 2ecaf93525fe4b271117d3932118ecaccdacaa03)

//=== CoalescingBitVectorTest.cpp - CoalescingBitVector unit tests --------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "llvm/ADT/CoalescingBitVector.h"
#include "gtest/gtest.h"

using namespace llvm;

namespace {

using UBitVec = CoalescingBitVector<unsigned>;
using U64BitVec = CoalescingBitVector<uint64_t>;

bool elementsMatch(const UBitVec &BV, std::initializer_list<unsigned> List) {
  if (!std::equal(BV.begin(), BV.end(), List.begin(), List.end())) {
    UBitVec::Allocator Alloc;
    UBitVec Expected(Alloc);
    Expected.set(List);
    dbgs() << "elementsMatch:\n"
           << "     Expected: ";
    Expected.print(dbgs());
    dbgs() << "          Got: ";
    BV.print(dbgs());
    return false;
  }
  return true;
}

bool rangesMatch(iterator_range<UBitVec::const_iterator> R,
                 std::initializer_list<unsigned> List) {
  return std::equal(R.begin(), R.end(), List.begin(), List.end());
}

TEST(CoalescingBitVectorTest, Set) {
  UBitVec::Allocator Alloc;
  UBitVec BV1(Alloc);
  UBitVec BV2(Alloc);

  BV1.set(0);
  EXPECT_TRUE(BV1.test(0));
  EXPECT_FALSE(BV1.test(1));

  BV2.set(BV1);
  EXPECT_TRUE(BV2.test(0));
}

TEST(CoalescingBitVectorTest, Count) {
  UBitVec::Allocator Alloc;
  UBitVec BV(Alloc);
  EXPECT_EQ(BV.count(), 0u);
  BV.set(0);
  EXPECT_EQ(BV.count(), 1u);
  BV.set({11, 12, 13, 14, 15});
  EXPECT_EQ(BV.count(), 6u);
}

TEST(CoalescingBitVectorTest, ClearAndEmpty) {
  UBitVec::Allocator Alloc;
  UBitVec BV(Alloc);
  EXPECT_TRUE(BV.empty());
  BV.set(1);
  EXPECT_FALSE(BV.empty());
  BV.clear();
  EXPECT_TRUE(BV.empty());
}

TEST(CoalescingBitVector, Copy) {
  UBitVec::Allocator Alloc;
  UBitVec BV1(Alloc);
  BV1.set(0);
  UBitVec BV2 = BV1;
  EXPECT_TRUE(elementsMatch(BV1, {0}));
  EXPECT_TRUE(elementsMatch(BV2, {0}));
  BV2.set(5);
  BV2 = BV1;
  EXPECT_TRUE(elementsMatch(BV1, {0}));
  EXPECT_TRUE(elementsMatch(BV2, {0}));
}

TEST(CoalescingBitVectorTest, Iterators) {
  UBitVec::Allocator Alloc;
  UBitVec BV(Alloc);

  BV.set({0, 1, 2});

  auto It = BV.begin();
  EXPECT_TRUE(It == BV.begin());
  EXPECT_EQ(*It, 0u);
  ++It;
  EXPECT_EQ(*It, 1u);
  ++It;
  EXPECT_EQ(*It, 2u);
  ++It;
  EXPECT_TRUE(It == BV.end());
  EXPECT_TRUE(BV.end() == BV.end());

  It = BV.begin();
  EXPECT_TRUE(It == BV.begin());
  auto ItCopy = It++;
  EXPECT_TRUE(ItCopy == BV.begin());
  EXPECT_EQ(*ItCopy, 0u);
  EXPECT_EQ(*It, 1u);

  EXPECT_TRUE(elementsMatch(BV, {0, 1, 2}));

  BV.set({4, 5, 6});
  EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 4, 5, 6}));

  BV.set(3);
  EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 3, 4, 5, 6}));

  BV.set(10);
  EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 3, 4, 5, 6, 10}));

  // Should be able to reset unset bits.
  BV.reset(3);
  BV.reset(3);
  BV.reset(20000);
  BV.set({1000, 1001, 1002});
  EXPECT_TRUE(elementsMatch(BV, {0, 1, 2, 4, 5, 6, 10, 1000, 1001, 1002}));

  auto It1 = BV.begin();
  EXPECT_TRUE(It1 == BV.begin());
  EXPECT_TRUE(++It1 == ++BV.begin());
  EXPECT_TRUE(It1 != BV.begin());
  EXPECT_TRUE(It1 != BV.end());
}

TEST(CoalescingBitVectorTest, Reset) {
  UBitVec::Allocator Alloc;
  UBitVec BV(Alloc);

  BV.set(0);
  EXPECT_TRUE(BV.test(0));
  BV.reset(0);
  EXPECT_FALSE(BV.test(0));

  BV.clear();
  BV.set({1, 2, 3});
  BV.reset(1);
  EXPECT_TRUE(elementsMatch(BV, {2, 3}));

  BV.clear();
  BV.set({1, 2, 3});
  BV.reset(2);
  EXPECT_TRUE(elementsMatch(BV, {1, 3}));

  BV.clear();
  BV.set({1, 2, 3});
  BV.reset(3);
  EXPECT_TRUE(elementsMatch(BV, {1, 2}));
}

TEST(CoalescingBitVectorTest, Comparison) {
  UBitVec::Allocator Alloc;
  UBitVec BV1(Alloc);
  UBitVec BV2(Alloc);

  // Single interval.
  BV1.set({1, 2, 3});
  BV2.set({1, 2, 3});
  EXPECT_EQ(BV1, BV2);
  EXPECT_FALSE(BV1 != BV2);

  // Different number of intervals.
  BV1.clear();
  BV2.clear();
  BV1.set({1, 2, 3});
  EXPECT_NE(BV1, BV2);

  // Multiple intervals.
  BV1.clear();
  BV2.clear();
  BV1.set({1, 2, 11, 12});
  BV2.set({1, 2, 11, 12});
  EXPECT_EQ(BV1, BV2);
  BV2.reset(1);
  EXPECT_NE(BV1, BV2);
  BV2.set(1);
  BV2.reset(11);
  EXPECT_NE(BV1, BV2);
}

// A simple implementation of set union, used to double-check the human
// "expected" answer.
void simpleUnion(UBitVec &Union, const UBitVec &LHS,
                    const UBitVec &RHS) {
  for (unsigned Bit : LHS)
    Union.test_and_set(Bit);
  for (unsigned Bit : RHS)
    Union.test_and_set(Bit);
}

TEST(CoalescingBitVectorTest, Union) {
  UBitVec::Allocator Alloc;

  // Check that after doing LHS |= RHS, LHS == Expected.
  auto unionIs = [&](std::initializer_list<unsigned> LHS,
                     std::initializer_list<unsigned> RHS,
                     std::initializer_list<unsigned> Expected) {
    UBitVec BV1(Alloc);
    BV1.set(LHS);
    UBitVec BV2(Alloc);
    BV2.set(RHS);
    UBitVec DoubleCheckedExpected(Alloc);
    simpleUnion(DoubleCheckedExpected, BV1, BV2);
    ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
    BV1 |= BV2;
    ASSERT_TRUE(elementsMatch(BV1, Expected));
  };

  // Check that "LHS |= RHS" and "RHS |= LHS" both produce the expected result.
  auto testUnionSymmetrically = [&](std::initializer_list<unsigned> LHS,
                     std::initializer_list<unsigned> RHS,
                     std::initializer_list<unsigned> Expected) {
    unionIs(LHS, RHS, Expected);
    unionIs(RHS, LHS, Expected);
  };

  // Empty LHS.
  testUnionSymmetrically({}, {1, 2, 3}, {1, 2, 3});

  // Empty RHS.
  testUnionSymmetrically({1, 2, 3}, {}, {1, 2, 3});

  // Full overlap.
  testUnionSymmetrically({1}, {1}, {1});
  testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 11, 12}, {1, 2, 11, 12});

  // Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
  // it. Repeat this swapping LHS and RHS.
  testUnionSymmetrically({2, 3, 4}, {1, 2, 3}, {1, 2, 3, 4});
  testUnionSymmetrically({2, 3, 4}, {2, 3, 4}, {2, 3, 4});
  testUnionSymmetrically({2, 3, 4}, {3, 4, 5}, {2, 3, 4, 5});
  testUnionSymmetrically({1, 2, 3}, {2, 3, 4}, {1, 2, 3, 4});
  testUnionSymmetrically({3, 4, 5}, {2, 3, 4}, {2, 3, 4, 5});

  // Multiple overlaps, but at least one of the overlaps forces us to split an
  // interval (and possibly both do). For ease of understanding, fix LHS to be
  // {1, 2, 11, 12}, but vary RHS.
  testUnionSymmetrically({1, 2, 11, 12}, {1}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {2}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {11}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {12}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {1, 11}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {1, 12}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {2, 11}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {2, 12}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {1, 11, 12}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {2, 11, 12}, {1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {0, 11, 12}, {0, 1, 2, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {3, 11, 12}, {1, 2, 3, 11, 12});
  testUnionSymmetrically({1, 2, 11, 12}, {1, 11, 13}, {1, 2, 11, 12, 13});
  testUnionSymmetrically({1, 2, 11, 12}, {1, 10, 11}, {1, 2, 10, 11, 12});

  // Partial overlap, but the existing interval covers future overlaps.
  testUnionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
                         {1, 2, 3, 4, 5, 6, 7, 8});
  testUnionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 7, 8, 9},
                         {1, 2, 3, 4, 5, 6, 7, 8, 9});

  // More partial overlaps.
  testUnionSymmetrically({1, 2, 3, 4, 5}, {0, 1, 2, 4, 5, 6},
                         {0, 1, 2, 3, 4, 5, 6});
  testUnionSymmetrically({2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4});
  testUnionSymmetrically({3, 4}, {1, 2, 3, 4}, {1, 2, 3, 4});
  testUnionSymmetrically({1, 2}, {1, 2, 3, 4}, {1, 2, 3, 4});
  testUnionSymmetrically({0, 1}, {1, 2, 3, 4}, {0, 1, 2, 3, 4});

  // Merge non-overlapping.
  testUnionSymmetrically({0, 1}, {2, 3}, {0, 1, 2, 3});
  testUnionSymmetrically({0, 3}, {1, 2}, {0, 1, 2, 3});
}

// A simple implementation of set intersection, used to double-check the
// human "expected" answer.
void simpleIntersection(UBitVec &Intersection, const UBitVec &LHS,
                        const UBitVec &RHS) {
  for (unsigned Bit : LHS)
    if (RHS.test(Bit))
      Intersection.set(Bit);
}

TEST(CoalescingBitVectorTest, Intersection) {
  UBitVec::Allocator Alloc;

  // Check that after doing LHS &= RHS, LHS == Expected.
  auto intersectionIs = [&](std::initializer_list<unsigned> LHS,
                            std::initializer_list<unsigned> RHS,
                            std::initializer_list<unsigned> Expected) {
    UBitVec BV1(Alloc);
    BV1.set(LHS);
    UBitVec BV2(Alloc);
    BV2.set(RHS);
    UBitVec DoubleCheckedExpected(Alloc);
    simpleIntersection(DoubleCheckedExpected, BV1, BV2);
    ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
    BV1 &= BV2;
    ASSERT_TRUE(elementsMatch(BV1, Expected));
  };

  // Check that "LHS &= RHS" and "RHS &= LHS" both produce the expected result.
  auto testIntersectionSymmetrically = [&](std::initializer_list<unsigned> LHS,
                     std::initializer_list<unsigned> RHS,
                     std::initializer_list<unsigned> Expected) {
    intersectionIs(LHS, RHS, Expected);
    intersectionIs(RHS, LHS, Expected);
  };

  // Empty case, one-element case.
  testIntersectionSymmetrically({}, {}, {});
  testIntersectionSymmetrically({1}, {1}, {1});
  testIntersectionSymmetrically({1}, {2}, {});

  // Exact overlaps cases: single overlap and multiple overlaps.
  testIntersectionSymmetrically({1, 2}, {1, 2}, {1, 2});
  testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 11, 12}, {1, 2, 11, 12});

  // Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
  // it.
  testIntersectionSymmetrically({2, 3, 4}, {1, 2, 3}, {2, 3});
  testIntersectionSymmetrically({2, 3, 4}, {2, 3, 4}, {2, 3, 4});
  testIntersectionSymmetrically({2, 3, 4}, {3, 4, 5}, {3, 4});

  // No overlap, but we have multiple intervals.
  testIntersectionSymmetrically({1, 2, 11, 12}, {3, 4, 13, 14}, {});

  // Multiple overlaps, but at least one of the overlaps forces us to split an
  // interval (and possibly both do). For ease of understanding, fix LHS to be
  // {1, 2, 11, 12}, but vary RHS.
  testIntersectionSymmetrically({1, 2, 11, 12}, {1}, {1});
  testIntersectionSymmetrically({1, 2, 11, 12}, {2}, {2});
  testIntersectionSymmetrically({1, 2, 11, 12}, {11}, {11});
  testIntersectionSymmetrically({1, 2, 11, 12}, {12}, {12});
  testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11}, {1, 11});
  testIntersectionSymmetrically({1, 2, 11, 12}, {1, 12}, {1, 12});
  testIntersectionSymmetrically({1, 2, 11, 12}, {2, 11}, {2, 11});
  testIntersectionSymmetrically({1, 2, 11, 12}, {2, 12}, {2, 12});
  testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 11}, {1, 2, 11});
  testIntersectionSymmetrically({1, 2, 11, 12}, {1, 2, 12}, {1, 2, 12});
  testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11, 12}, {1, 11, 12});
  testIntersectionSymmetrically({1, 2, 11, 12}, {2, 11, 12}, {2, 11, 12});
  testIntersectionSymmetrically({1, 2, 11, 12}, {0, 11, 12}, {11, 12});
  testIntersectionSymmetrically({1, 2, 11, 12}, {3, 11, 12}, {11, 12});
  testIntersectionSymmetrically({1, 2, 11, 12}, {1, 11, 13}, {1, 11});
  testIntersectionSymmetrically({1, 2, 11, 12}, {1, 10, 11}, {1, 11});

  // Partial overlap, but the existing interval covers future overlaps.
  testIntersectionSymmetrically({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
                                {2, 3, 4, 6, 7});
}

// A simple implementation of set intersection-with-complement, used to
// double-check the human "expected" answer.
void simpleIntersectionWithComplement(UBitVec &Intersection, const UBitVec &LHS,
                                      const UBitVec &RHS) {
  for (unsigned Bit : LHS)
    if (!RHS.test(Bit))
      Intersection.set(Bit);
}

TEST(CoalescingBitVectorTest, IntersectWithComplement) {
  UBitVec::Allocator Alloc;

  // Check that after doing LHS.intersectWithComplement(RHS), LHS == Expected.
  auto intersectionWithComplementIs =
      [&](std::initializer_list<unsigned> LHS,
          std::initializer_list<unsigned> RHS,
          std::initializer_list<unsigned> Expected) {
        UBitVec BV1(Alloc);
        BV1.set(LHS);
        UBitVec BV2(Alloc);
        BV2.set(RHS);
        UBitVec DoubleCheckedExpected(Alloc);
        simpleIntersectionWithComplement(DoubleCheckedExpected, BV1, BV2);
        ASSERT_TRUE(elementsMatch(DoubleCheckedExpected, Expected));
        BV1.intersectWithComplement(BV2);
        ASSERT_TRUE(elementsMatch(BV1, Expected));
      };

  // Empty case, one-element case.
  intersectionWithComplementIs({}, {}, {});
  intersectionWithComplementIs({1}, {1}, {});
  intersectionWithComplementIs({1}, {2}, {1});

  // Exact overlaps cases: single overlap and multiple overlaps.
  intersectionWithComplementIs({1, 2}, {1, 2}, {});
  intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 11, 12}, {});

  // Sliding window: fix {2, 3, 4} as the LHS, and slide a window before/after
  // it. Repeat this swapping LHS and RHS.
  intersectionWithComplementIs({2, 3, 4}, {1, 2, 3}, {4});
  intersectionWithComplementIs({2, 3, 4}, {2, 3, 4}, {});
  intersectionWithComplementIs({2, 3, 4}, {3, 4, 5}, {2});
  intersectionWithComplementIs({1, 2, 3}, {2, 3, 4}, {1});
  intersectionWithComplementIs({3, 4, 5}, {2, 3, 4}, {5});

  // No overlap, but we have multiple intervals.
  intersectionWithComplementIs({1, 2, 11, 12}, {3, 4, 13, 14}, {1, 2, 11, 12});

  // Multiple overlaps. For ease of understanding, fix LHS to be
  // {1, 2, 11, 12}, but vary RHS.
  intersectionWithComplementIs({1, 2, 11, 12}, {1}, {2, 11, 12});
  intersectionWithComplementIs({1, 2, 11, 12}, {2}, {1, 11, 12});
  intersectionWithComplementIs({1, 2, 11, 12}, {11}, {1, 2, 12});
  intersectionWithComplementIs({1, 2, 11, 12}, {12}, {1, 2, 11});
  intersectionWithComplementIs({1, 2, 11, 12}, {1, 11}, {2, 12});
  intersectionWithComplementIs({1, 2, 11, 12}, {1, 12}, {2, 11});
  intersectionWithComplementIs({1, 2, 11, 12}, {2, 11}, {1, 12});
  intersectionWithComplementIs({1, 2, 11, 12}, {2, 12}, {1, 11});
  intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 11}, {12});
  intersectionWithComplementIs({1, 2, 11, 12}, {1, 2, 12}, {11});
  intersectionWithComplementIs({1, 2, 11, 12}, {1, 11, 12}, {2});
  intersectionWithComplementIs({1, 2, 11, 12}, {2, 11, 12}, {1});
  intersectionWithComplementIs({1, 2, 11, 12}, {0, 11, 12}, {1, 2});
  intersectionWithComplementIs({1, 2, 11, 12}, {3, 11, 12}, {1, 2});
  intersectionWithComplementIs({1, 2, 11, 12}, {1, 11, 13}, {2, 12});
  intersectionWithComplementIs({1, 2, 11, 12}, {1, 10, 11}, {2, 12});

  // Partial overlap, but the existing interval covers future overlaps.
  intersectionWithComplementIs({1, 2, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 6, 7},
                               {1, 5, 8});
}

TEST(CoalescingBitVectorTest, FindLowerBound) {
  U64BitVec::Allocator Alloc;
  U64BitVec BV(Alloc);
  uint64_t BigNum1 = uint64_t(1) << 32;
  uint64_t BigNum2 = (uint64_t(1) << 33) + 1;
  EXPECT_TRUE(BV.find(BigNum1) == BV.end());
  BV.set(BigNum1);
  auto Find1 = BV.find(BigNum1);
  EXPECT_EQ(*Find1, BigNum1);
  BV.set(BigNum2);
  auto Find2 = BV.find(BigNum1);
  EXPECT_EQ(*Find2, BigNum1);
  auto Find3 = BV.find(BigNum2);
  EXPECT_EQ(*Find3, BigNum2);
  BV.reset(BigNum1);
  auto Find4 = BV.find(BigNum1);
  EXPECT_EQ(*Find4, BigNum2);

  BV.clear();
  BV.set({1, 2, 3});
  EXPECT_EQ(*BV.find(2), 2u);
  EXPECT_EQ(*BV.find(3), 3u);
}

TEST(CoalescingBitVectorTest, AdvanceToLowerBound) {
  U64BitVec::Allocator Alloc;
  U64BitVec BV(Alloc);
  uint64_t BigNum1 = uint64_t(1) << 32;
  uint64_t BigNum2 = (uint64_t(1) << 33) + 1;

  auto advFromBegin = [&](uint64_t To) -> U64BitVec::const_iterator {
    auto It = BV.begin();
    It.advanceToLowerBound(To);
    return It;
  };

  EXPECT_TRUE(advFromBegin(BigNum1) == BV.end());
  BV.set(BigNum1);
  auto Find1 = advFromBegin(BigNum1);
  EXPECT_EQ(*Find1, BigNum1);
  BV.set(BigNum2);
  auto Find2 = advFromBegin(BigNum1);
  EXPECT_EQ(*Find2, BigNum1);
  auto Find3 = advFromBegin(BigNum2);
  EXPECT_EQ(*Find3, BigNum2);
  BV.reset(BigNum1);
  auto Find4 = advFromBegin(BigNum1);
  EXPECT_EQ(*Find4, BigNum2);

  BV.clear();
  BV.set({1, 2, 3});
  EXPECT_EQ(*advFromBegin(2), 2u);
  EXPECT_EQ(*advFromBegin(3), 3u);
  auto It = BV.begin();
  It.advanceToLowerBound(0);
  EXPECT_EQ(*It, 1u);
  It.advanceToLowerBound(100);
  EXPECT_TRUE(It == BV.end());
  It.advanceToLowerBound(100);
  EXPECT_TRUE(It == BV.end());
}

TEST(CoalescingBitVectorTest, HalfOpenRange) {
  UBitVec::Allocator Alloc;

  {
    UBitVec BV(Alloc);
    BV.set({1, 2, 3});

    EXPECT_EQ(*BV.find(0), 1U); // find(Start) > Start
    EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 5), {1, 2, 3}));
    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 4), {1, 2, 3}));
    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 3), {1, 2}));
    EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 3), {2}));
    EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 4), {2, 3}));
    EXPECT_TRUE(rangesMatch(BV.half_open_range(4, 5), {}));
  }

  {
    UBitVec BV(Alloc);
    BV.set({1, 2, 11, 12});

    EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 15), {1, 2, 11, 12}));
    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 13), {1, 2, 11, 12}));
    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 12), {1, 2, 11}));

    EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 5), {1, 2}));
    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 5), {1, 2}));
    EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 5), {2}));
    EXPECT_TRUE(rangesMatch(BV.half_open_range(1, 2), {1}));
    EXPECT_TRUE(rangesMatch(BV.half_open_range(13, 14), {}));

    EXPECT_TRUE(rangesMatch(BV.half_open_range(2, 10), {2}));
  }

  {
    UBitVec BV(Alloc);
    BV.set({1});

    EXPECT_EQ(*BV.find(0), 1U); // find(Start) == End
    EXPECT_TRUE(rangesMatch(BV.half_open_range(0, 1), {}));
  }

  {
    UBitVec BV(Alloc);
    BV.set({5});

    EXPECT_EQ(*BV.find(3), 5U); // find(Start) > End
    EXPECT_TRUE(rangesMatch(BV.half_open_range(3, 4), {}));
  }
}

TEST(CoalescingBitVectorTest, Print) {
  std::string S;
  {
    raw_string_ostream OS(S);
    UBitVec::Allocator Alloc;
    UBitVec BV(Alloc);
    BV.set({1});
    BV.print(OS);

    BV.clear();
    BV.set({1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20});
    BV.print(OS);
  }
  EXPECT_EQ(S, "{[1]}"
               "{[1][11, 20]}");
}

} // namespace