SparseSetTest.cpp

//===------ ADT/SparseSetTest.cpp - SparseSet unit tests -  -----*- C++ -*-===//
//
// 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/SparseSet.h"
#include "gtest/gtest.h"

using namespace llvm;

namespace {

typedef SparseSet<unsigned> USet;

// Empty set tests.
TEST(SparseSetTest, EmptySet) {
  USet Set;
  EXPECT_TRUE(Set.empty());
  EXPECT_TRUE(Set.begin() == Set.end());
  EXPECT_EQ(0u, Set.size());

  Set.setUniverse(10);

  // Lookups on empty set.
  EXPECT_TRUE(Set.find(0) == Set.end());
  EXPECT_TRUE(Set.find(9) == Set.end());

  // Same thing on a const reference.
  const USet &CSet = Set;
  EXPECT_TRUE(CSet.empty());
  EXPECT_TRUE(CSet.begin() == CSet.end());
  EXPECT_EQ(0u, CSet.size());
  EXPECT_TRUE(CSet.find(0) == CSet.end());
  USet::const_iterator I = CSet.find(5);
  EXPECT_TRUE(I == CSet.end());
}

// Single entry set tests.
TEST(SparseSetTest, SingleEntrySet) {
  USet Set;
  Set.setUniverse(10);
  std::pair<USet::iterator, bool> IP = Set.insert(5);
  EXPECT_TRUE(IP.second);
  EXPECT_TRUE(IP.first == Set.begin());

  EXPECT_FALSE(Set.empty());
  EXPECT_FALSE(Set.begin() == Set.end());
  EXPECT_TRUE(Set.begin() + 1 == Set.end());
  EXPECT_EQ(1u, Set.size());

  EXPECT_TRUE(Set.find(0) == Set.end());
  EXPECT_TRUE(Set.find(9) == Set.end());

  EXPECT_FALSE(Set.count(0));
  EXPECT_TRUE(Set.count(5));

  // Redundant insert.
  IP = Set.insert(5);
  EXPECT_FALSE(IP.second);
  EXPECT_TRUE(IP.first == Set.begin());

  // Erase non-existent element.
  EXPECT_FALSE(Set.erase(1));
  EXPECT_EQ(1u, Set.size());
  EXPECT_EQ(5u, *Set.begin());

  // Erase iterator.
  USet::iterator I = Set.find(5);
  EXPECT_TRUE(I == Set.begin());
  I = Set.erase(I);
  EXPECT_TRUE(I == Set.end());
  EXPECT_TRUE(Set.empty());
}

// Multiple entry set tests.
TEST(SparseSetTest, MultipleEntrySet) {
  USet Set;
  Set.setUniverse(10);

  Set.insert(5);
  Set.insert(3);
  Set.insert(2);
  Set.insert(1);
  Set.insert(4);
  EXPECT_EQ(5u, Set.size());

  // Without deletions, iteration order == insertion order.
  USet::const_iterator I = Set.begin();
  EXPECT_EQ(5u, *I);
  ++I;
  EXPECT_EQ(3u, *I);
  ++I;
  EXPECT_EQ(2u, *I);
  ++I;
  EXPECT_EQ(1u, *I);
  ++I;
  EXPECT_EQ(4u, *I);
  ++I;
  EXPECT_TRUE(I == Set.end());

  // Redundant insert.
  std::pair<USet::iterator, bool> IP = Set.insert(3);
  EXPECT_FALSE(IP.second);
  EXPECT_TRUE(IP.first == Set.begin() + 1);

  // Erase last element by key.
  EXPECT_TRUE(Set.erase(4));
  EXPECT_EQ(4u, Set.size());
  EXPECT_FALSE(Set.count(4));
  EXPECT_FALSE(Set.erase(4));
  EXPECT_EQ(4u, Set.size());
  EXPECT_FALSE(Set.count(4));

  // Erase first element by key.
  EXPECT_TRUE(Set.count(5));
  EXPECT_TRUE(Set.find(5) == Set.begin());
  EXPECT_TRUE(Set.erase(5));
  EXPECT_EQ(3u, Set.size());
  EXPECT_FALSE(Set.count(5));
  EXPECT_FALSE(Set.erase(5));
  EXPECT_EQ(3u, Set.size());
  EXPECT_FALSE(Set.count(5));

  Set.insert(6);
  Set.insert(7);
  EXPECT_EQ(5u, Set.size());

  // Erase last element by iterator.
  I = Set.erase(Set.end() - 1);
  EXPECT_TRUE(I == Set.end());
  EXPECT_EQ(4u, Set.size());

  // Erase second element by iterator.
  I = Set.erase(Set.begin() + 1);
  EXPECT_TRUE(I == Set.begin() + 1);

  // Clear and resize the universe.
  Set.clear();
  EXPECT_FALSE(Set.count(5));
  Set.setUniverse(1000);

  // Add more than 256 elements.
  for (unsigned i = 100; i != 800; ++i)
    Set.insert(i);

  for (unsigned i = 0; i != 10; ++i)
    Set.erase(i);

  for (unsigned i = 100; i != 800; ++i)
    EXPECT_TRUE(Set.count(i));

  EXPECT_FALSE(Set.count(99));
  EXPECT_FALSE(Set.count(800));
  EXPECT_EQ(700u, Set.size());
}

struct Alt {
  unsigned Value;
  explicit Alt(unsigned x) : Value(x) {}
  unsigned getSparseSetIndex() const { return Value - 1000; }
};

TEST(SparseSetTest, AltStructSet) {
  typedef SparseSet<Alt> ASet;
  ASet Set;
  Set.setUniverse(10);
  Set.insert(Alt(1005));

  ASet::iterator I = Set.find(5);
  ASSERT_TRUE(I == Set.begin());
  EXPECT_EQ(1005u, I->Value);

  Set.insert(Alt(1006));
  Set.insert(Alt(1006));
  I = Set.erase(Set.begin());
  ASSERT_TRUE(I == Set.begin());
  EXPECT_EQ(1006u, I->Value);

  EXPECT_FALSE(Set.erase(5));
  EXPECT_TRUE(Set.erase(6));
}

TEST(SparseSetTest, PopBack) {
  USet Set;
  const unsigned UpperBound = 300;
  Set.setUniverse(UpperBound);
  for (unsigned i = 0; i < UpperBound; ++i)
    Set.insert(i);

  // Make sure pop back returns the values in the reverse order we
  // inserted them.
  unsigned Expected = UpperBound;
  while (!Set.empty())
    ASSERT_TRUE(--Expected == Set.pop_back_val());

  // Insert again the same elements in the sparse set and make sure
  // each insertion actually inserts the elements. I.e., check
  // that the underlying data structure are properly cleared.
  for (unsigned i = 0; i < UpperBound; ++i)
    ASSERT_TRUE(Set.insert(i).second);
}
} // namespace