1 //===-- flang/unittests/Common/FastIntSetTest.cpp ---------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "gtest/gtest.h" 10 #include "flang/Common/fast-int-set.h" 11 #include <optional> 12 13 TEST(FastIntSetTests, Sanity) { 14 static constexpr int N{100}; 15 Fortran::common::FastIntSet<N> set; 16 17 ASSERT_FALSE(set.IsValidValue(-1)); 18 ASSERT_TRUE(set.IsValidValue(0)); 19 ASSERT_TRUE(set.IsValidValue(N - 1)); 20 ASSERT_FALSE(set.IsValidValue(N)); 21 ASSERT_TRUE(set.IsEmpty()); 22 ASSERT_EQ(set.size(), 0); 23 ASSERT_FALSE(set.Contains(0)); 24 ASSERT_FALSE(set.Contains(N - 1)); 25 26 ASSERT_TRUE(set.Add(0)); 27 ASSERT_FALSE(set.IsEmpty()); 28 ASSERT_EQ(set.size(), 1); 29 ASSERT_TRUE(set.Contains(0)); 30 31 ASSERT_TRUE(set.Add(0)); // duplicate 32 ASSERT_EQ(set.size(), 1); 33 ASSERT_TRUE(set.Contains(0)); 34 35 ASSERT_TRUE(set.Remove(0)); 36 ASSERT_TRUE(set.IsEmpty()); 37 ASSERT_EQ(set.size(), 0); 38 ASSERT_FALSE(set.Contains(0)); 39 40 ASSERT_FALSE(set.Add(N)); 41 ASSERT_TRUE(set.IsEmpty()); 42 ASSERT_EQ(set.size(), 0); 43 ASSERT_FALSE(set.Contains(N)); 44 45 ASSERT_TRUE(set.Add(N - 1)); 46 ASSERT_FALSE(set.IsEmpty()); 47 ASSERT_EQ(set.size(), 1); 48 ASSERT_TRUE(set.Contains(N - 1)); 49 50 std::optional<int> x; 51 x = set.PopValue(); 52 ASSERT_TRUE(x.has_value()); 53 ASSERT_EQ(*x, N - 1); 54 ASSERT_TRUE(set.IsEmpty()); 55 ASSERT_EQ(set.size(), 0); 56 57 x = set.PopValue(); 58 ASSERT_FALSE(x.has_value()); 59 60 for (int j{0}; j < N; ++j) { 61 ASSERT_TRUE(set.Add(j)) << j; 62 } 63 ASSERT_FALSE(set.IsEmpty()); 64 ASSERT_EQ(set.size(), N); 65 for (int j{0}; j < N; ++j) { 66 ASSERT_TRUE(set.Contains(j)) << j; 67 } 68 69 for (int j{0}; j < N; ++j) { 70 ASSERT_TRUE(set.Remove(j)) << j; 71 ASSERT_EQ(set.size(), N - j - 1) << j; 72 ASSERT_FALSE(set.Contains(j)) << j; 73 } 74 75 ASSERT_TRUE(set.IsEmpty()); 76 ASSERT_EQ(set.size(), 0); 77 78 for (int j{N - 1}; j >= 0; --j) { 79 ASSERT_TRUE(set.Add(j)) << j; 80 } 81 for (int j{0}; j < N; j++) { 82 x = set.PopValue(); 83 ASSERT_TRUE(x.has_value()); 84 ASSERT_EQ(*x, j) << j; 85 } 86 ASSERT_TRUE(set.IsEmpty()); 87 ASSERT_EQ(set.size(), 0); 88 89 for (int j{0}; j < N; j++) { 90 ASSERT_TRUE(set.Add(j)) << j; 91 } 92 ASSERT_FALSE(set.IsEmpty()); 93 ASSERT_EQ(set.size(), N); 94 for (int j{0}; j < N; j += 2) { 95 ASSERT_TRUE(set.Remove(j)) << j; 96 } 97 ASSERT_FALSE(set.IsEmpty()); 98 ASSERT_EQ(set.size(), N / 2); 99 for (int j{0}; j < N; j++) { 100 ASSERT_EQ(set.Contains(j), (j & 1) == 1); 101 } 102 103 set.Clear(); 104 ASSERT_TRUE(set.IsEmpty()); 105 } 106