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
TEST(FastIntSetTests,Sanity)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