blob: db820ede09f43acf960221dc6ee01755b9823604 (
plain) (
blame)
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
|
#ifndef COMPRESSED_VECTOR
#define COMPRESSED_VECTOR
#include <cstdint>
#include <cstddef>
#include <vector>
template <class T, int B>
struct compressed_vector_hash;
/*limitations:
* current implementation never returns a reference
*/
template <class T, int B>
class compressed_vector
{
static_assert(std::is_unsigned<T>::value);
static_assert(sizeof(T) * 8 >= B);
static_assert(B > 0 && B < 64);
private:
const int P = 64 / B;
const uint64_t M = (1 << B) - 1;
std::vector<uint64_t> v;
size_t sz;
public:
compressed_vector() : sz(0) {}
void push_back(T val)
{
//assert(v <= M);
if (sz % P == 0)
v.push_back(0);
set(sz, val);
++sz;
}
void pop_back()
{
//assert(sz > 0);
if (--sz % P == 0)
v.pop_back();
else
//zero out the now unused bits
v[sz / P] &= ~(M << (sz % P * B));
}
T front() const {return get(0);}
T back() const {return get(sz - 1);}
T get(size_t i) const
{
//assert(i < sz);
return (T)((v[i / P] >> (i % P * B)) & M);
}
void set(size_t i, T val)
{
//assert(i < sz);
v[i / P] &= ~(M << (i % P * B));
v[i / P] |= ((uint64_t) val) << (i % P * B);
}
size_t size() const
{
return sz;
}
void clear()
{
sz = 0;
v.clear();
}
bool operator ==(const compressed_vector& other) const
{
return sz == other.sz && v == other.v;
}
friend struct compressed_vector_hash<T, B>;
};
template <class T, int B>
struct compressed_vector_hash
{
size_t operator()(compressed_vector<T, B> const& s) const noexcept
{
size_t ret = 0;
//Fibonacci hashing
for (size_t i = 0; i < s.v.size(); ++i) {
ret ^= (size_t)(s.v[i] & ~0U) + 0x9e3779b9 + (ret << 6) + (ret >> 2);
ret ^= (size_t)(s.v[i] >> 32) + 0x9e3779b9 + (ret << 6) + (ret >> 2);
}
return ret;
}
};
#endif
|
