Created
June 30, 2019 08:53
-
-
Save cocomoff/efd9cdf157340162ac60e71685369164 to your computer and use it in GitHub Desktop.
bit vector example
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
g++ -std=c++14 -o main main.cpp -I/home/cocomoff/sdsl-lite/build/include -L/home/cocomoff/sdsl-lite/build/lib -lsdsl -ldivsufsort -ldivsufsort64 | |
*/ | |
#include <bits/stdc++.h> | |
#include <sdsl/int_vector.hpp> | |
#include <sdsl/bit_vectors.hpp> | |
#include <sdsl/rank_support.hpp> | |
#include <sdsl/util.hpp> | |
using namespace std; | |
using namespace sdsl; | |
typedef bit_vector::size_type size_type; | |
int main() { | |
const int N = 10; | |
size_type n = N; | |
bit_vector bv(n, 0); | |
rank_support_v<1> rs(&bv); | |
// U = {0, 1, ..., 9} | |
// V = {0, 2, 3, 5, 9} | |
bv[0] = bv[2] = bv[3] = bv[5] = bv[0] = 1; | |
cout << bv << endl; | |
// access(B, x) | |
for (int i = 0; i < N; i++) { | |
cout << "Element " << i << " is in U? = " << boolalpha << bv[i] << endl; | |
} | |
// (i+1)-th smaller element in V | |
for (int i = 0; i < N; i++) { | |
cout << i << "-th smaller element in U = " << rs(i) << endl; | |
} | |
// 1-support | |
size_t zeros = rank_support_v<0>(&bv)(bv.size()); | |
bit_vector::select_0_type b_sel(&bv); | |
cout << zeros << endl; | |
for (auto i = 1; i <= zeros; i++) { | |
cout << i << ":" << b_sel(i) << " " << b_sel(rs.rank(i)) << endl; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment