openMSX
IterableBitSet_test.cc
Go to the documentation of this file.
1 #include "catch.hpp"
2 #include "IterableBitSet.hh"
3 #include "ranges.hh"
4 #include <iostream>
5 #include <vector>
6 
7 template<size_t N>
8 void expect(const IterableBitSet<N>& s, const std::vector<size_t>& expected)
9 {
10  auto it = expected.begin();
11  s.foreachSetBit([&](size_t i) {
12  REQUIRE(it != expected.end());
13  CHECK(*it++ == i);
14  });
15  CHECK(it == expected.end());
16 }
17 
18 template<size_t N>
19 void test(const IterableBitSet<N>& s, std::initializer_list<size_t> list)
20 {
21  REQUIRE((list.size() % 2) == 0);
22  std::vector<size_t> v;
23  auto f = list.begin();
24  auto l = list.end();
25  while (f != l) {
26  auto b = *f++;
27  auto e = *f++;
28  for (auto i = b; i != e; ++i) v.push_back(i);
29  }
30  ranges::sort(v);
31  v.erase(std::unique(v.begin(), v.end()), v.end());
32 
33  expect(s, v);
34 }
35 
36 template<size_t N>
37 void test(std::initializer_list<size_t> list)
38 {
41 
42  REQUIRE((list.size() % 2) == 0);
43  auto f = list.begin();
44  auto l = list.end();
45  while (f != l) {
46  auto b = *f++;
47  auto e = *f++;
48  REQUIRE(b <= e);
49  REQUIRE(e <= 256);
50  s1.setPosN(b, e - b);
51  s2.setRange(b, e);
52  }
53  test(s1, list);
54  test(s2, list);
55 }
56 
57 TEST_CASE("IterableBitSet")
58 {
59  SECTION("empty") {
60  SECTION("single word") {
62  CHECK(s.empty());
63  s.set(2);
64  CHECK(!s.empty());
65  }
66  SECTION("multiple words") {
68  CHECK(s.empty());
69  SECTION("1st") {
70  s.set(2);
71  CHECK(!s.empty());
72  }
73  SECTION("2nd") {
74  s.set(70);
75  CHECK(!s.empty());
76  }
77  }
78  }
79  SECTION("set single") {
80  SECTION("single word") {
82  expect(s, {});
83  s.set(11);
84  expect(s, {11});
85  s.set(17);
86  expect(s, {11, 17});
87  s.set(3);
88  expect(s, {3, 11, 17});
89  }
90  SECTION("multiple words") {
92  expect(s, {});
93  s.set(87);
94  expect(s, {87});
95  s.set(17);
96  expect(s, {17, 87});
97  s.set(110);
98  expect(s, {17, 87, 110});
99  }
100  }
101  SECTION("set range") {
102  SECTION("single word") {
103  test<32>({});
104 
105  test<32>({0, 0});
106  test<32>({0, 16});
107  test<32>({0, 31});
108  test<32>({0, 32});
109 
110  test<32>({10, 10});
111  test<32>({10, 16});
112  test<32>({10, 31});
113  test<32>({10, 32});
114 
115  test<32>({31, 31});
116  test<32>({31, 32});
117 
118  test<32>({32, 32});
119 
120  test<32>({10, 20, 25, 30});
121  }
122  SECTION("multiple words") {
123  test<256>({});
124 
125  test<256>({0, 0});
126  test<256>({0, 16});
127  test<256>({0, 63});
128  test<256>({0, 64});
129  test<256>({0, 65});
130  test<256>({0, 80});
131  test<256>({0, 127});
132  test<256>({0, 128});
133  test<256>({0, 143});
134  test<256>({0, 255});
135  test<256>({0, 256});
136 
137  test<256>({10, 10});
138  test<256>({10, 16});
139  test<256>({10, 63});
140  test<256>({10, 64});
141  test<256>({10, 65});
142  test<256>({10, 80});
143  test<256>({10, 127});
144  test<256>({10, 128});
145  test<256>({10, 143});
146  test<256>({10, 255});
147  test<256>({10, 256});
148 
149  test<256>({63, 63});
150  test<256>({63, 64});
151  test<256>({63, 65});
152  test<256>({63, 80});
153  test<256>({63, 127});
154  test<256>({63, 128});
155  test<256>({63, 143});
156  test<256>({63, 255});
157  test<256>({63, 256});
158 
159  test<256>({64, 64});
160  test<256>({64, 65});
161  test<256>({64, 80});
162  test<256>({64, 127});
163  test<256>({64, 128});
164  test<256>({64, 143});
165  test<256>({64, 255});
166  test<256>({64, 256});
167 
168  test<256>({10, 20, 40, 50});
169  test<256>({10, 20, 60, 70});
170  test<256>({10, 40, 20, 30});
171  test<256>({10, 40, 20, 50});
172  }
173  }
174 }
TEST_CASE("IterableBitSet")
void expect(const IterableBitSet< N > &s, const std::vector< size_t > &expected)
void test(const IterableBitSet< N > &s, std::initializer_list< size_t > list)
IterableBitSet.
bool empty() const
(Implicit) default constructor.
void setPosN(size_t pos, size_t n)
Starting from position 'pos', set the 'n' following bits to '1'.
void setRange(size_t begin, size_t end)
Set all bits in the half-open range [begin, end) to '1'.
void foreachSetBit(Operation op) const
Execute the given operation 'op' for all '1' bits.
void set(size_t pos)
Set the (single) bit at position 'pos' to '1'.
CHECK(m3==m3)
auto unique(ForwardRange &&range)
Definition: ranges.hh:167
void sort(RandomAccessRange &&range)
Definition: ranges.hh:34