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
|