File: bitvector.cpp

package info (click to toggle)
iqtree 2.0.7%2Bdfsg-2
  • links: PTS, VCS
  • area: main
  • in suites: forky, sid
  • size: 14,700 kB
  • sloc: cpp: 142,571; ansic: 57,789; sh: 275; python: 242; makefile: 95
file content (118 lines) | stat: -rw-r--r-- 2,585 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <catch.hpp>

#include "../lib/ranked_bitvector.hpp"

namespace terraces {
namespace tests {

TEST_CASE("efficient bitvector", "[bitvector]") {
	// 0 1 2 3 4 5 6 7 8 9
	// 0 1 1 0 1 0 1 0 1 1
	// bitvector b(10);
	basic_ranked_bitvector<std::allocator<index>> b(10, {});
	b.set(1);
	b.set(2);
	b.set(4);
	b.set(6);
	b.set(8);
	b.set(9);
	b.invert();
	b.invert();
	b.update_ranks();
	CHECK(!b.get(0));
	CHECK(!b.get(3));
	CHECK(!b.get(5));
	CHECK(!b.get(7));
	b.flip(7);
	CHECK(b.get(7));
	b.flip(7);
	CHECK(!b.get(7));
	b.update_ranks();
	CHECK(b.get(1));
	CHECK(b.get(2));
	CHECK(b.get(4));
	CHECK(b.get(6));
	CHECK(b.get(8));
	CHECK(b.get(9));
	CHECK(b.rank(4) == 2);
	CHECK(b.rank(7) == 4);
	CHECK(b.rank(10) == 6);
	CHECK(b.first_set() == 1);
	CHECK(b.next_set(1) == 2);
	CHECK(b.next_set(2) == 4);
	CHECK(b.next_set(4) == 6);
	CHECK(b.next_set(6) == 8);
	CHECK(b.next_set(8) == 9);
	CHECK(b.next_set(9) == 10);
}

TEST_CASE("efficient bitvector large", "[bitvector]") {
	// bitvector b(519);
	basic_ranked_bitvector<std::allocator<index>> b(519, {});
	b.set(1);
	b.set(63);
	b.set(128);
	b.set(191);
	b.set(200);
	b.set(204);
	b.set(400);
	b.invert();
	b.invert();
	b.update_ranks();
	// bitvector b2(500);
	basic_ranked_bitvector<std::allocator<index>> b2(500, {});
	b2.set(128);
	// bitvector b3(1042);
	basic_ranked_bitvector<std::allocator<index>> b3(1042, {});
	CHECK(b.rank(10) == 1);
	CHECK(b.rank(63) == 1);
	CHECK(b.rank(64) == 2);
	CHECK(b.rank(128) == 2);
	CHECK(b.rank(129) == 3);
	CHECK(b.rank(191) == 3);
	CHECK(b.rank(192) == 4);
	CHECK(b.rank(200) == 4);
	CHECK(b.rank(201) == 5);
	CHECK(b.rank(204) == 5);
	CHECK(b.rank(205) == 6);
	CHECK(b.rank(255) == 6);
	CHECK(b.first_set() == 1);
	CHECK(b2.first_set() == 128);
	CHECK(b3.first_set() == 1042);
	CHECK(b.next_set(1) == 63);
	CHECK(b.next_set(63) == 128);
	CHECK(b.next_set(128) == 191);
	CHECK(b.next_set(191) == 200);
	CHECK(b.next_set(200) == 204);
	CHECK(b.next_set(204) == 400);
	CHECK(b.next_set(400) == 519);
	CHECK(b.select(0) == 1);
	CHECK(b.select(1) == 63);
	CHECK(b.select(2) == 128);
	CHECK(b.select(3) == 191);
	CHECK(b.select(4) == 200);
	CHECK(b.select(5) == 204);
	CHECK(b.select(6) == 400);
	b.blank();
	b.update_ranks();
	CHECK(b.count() == 0);
}

TEST_CASE("efficient bitvector xor", "[bitvector]") {
	// bitvector b(10);
	basic_ranked_bitvector<std::allocator<index>> b(10, {});
	b.set(1);
	b.set(2);
	b.set(4);
	b.set(6);
	b.set(8);
	b.set(9);
	b.bitwise_xor(b);
	b.invert();
	b.invert();
	b.update_ranks();
	CHECK(b.count() == 0);
}

} // namespace tests
} // namespace terraces