Line data Source code
1 : #ifndef ROUTING_KIT_BIT_VECTOR_H
2 : #define ROUTING_KIT_BIT_VECTOR_H
3 :
4 : #include <stdint.h>
5 : #include <assert.h>
6 : #include <utility>
7 :
8 : namespace RoutingKit{
9 :
10 : class BitVector{
11 : public:
12 : struct Uninitialized{};
13 : static constexpr Uninitialized uninitialized = {};
14 :
15 : BitVector();
16 : BitVector(uint64_t size, Uninitialized);
17 : explicit BitVector(uint64_t size, bool init_value = false);
18 : ~BitVector();
19 : BitVector(const BitVector&);
20 : BitVector(BitVector&&);
21 :
22 : BitVector&operator=(BitVector);
23 : void swap(BitVector&);
24 :
25 : bool empty()const { return size() == 0; }
26 6353 : uint64_t size()const { return size_; }
27 :
28 : void resize(uint64_t size, Uninitialized);
29 : void resize(uint64_t size, bool init_value = false);
30 :
31 : void make_large_enough_for(uint64_t x, Uninitialized);
32 : void make_large_enough_for(uint64_t x, bool init_value = false);
33 :
34 : bool is_set(uint64_t x)const{
35 : assert(x < size_ && "argument out of bounds");
36 79890915 : uint64_t a = x/64;
37 688852 : uint64_t b = x%64;
38 91717260 : uint64_t d = data_[a];
39 86970369 : return d & (1ull << b);
40 : }
41 :
42 : void set(uint64_t x){
43 : assert(x < size_ && "argument out of bounds");
44 1544142 : uint64_t a = x/64;
45 : uint64_t b = x%64;
46 4176455 : uint64_t d = data_[a];
47 4527290 : d |= (1ull << b);
48 1336173 : data_[a] = d;
49 3191117 : }
50 :
51 : void set_if(uint64_t x, bool value){
52 : assert(x < size_ && "argument out of bounds");
53 : uint64_t a = x/64;
54 : uint64_t b = x%64;
55 : uint64_t d = data_[a];
56 : d |= ((uint64_t)value << b);
57 : data_[a] = d;
58 : }
59 :
60 : void set(uint64_t x, bool value){
61 : assert(x < size_ && "argument out of bounds");
62 251597 : uint64_t a = x/64;
63 183964 : uint64_t b = x%64;
64 252444 : uint64_t d = data_[a];
65 252444 : d &= ~(1ull << b);
66 252444 : d |= ((uint64_t)value << b);
67 251597 : data_[a] = d;
68 847 : }
69 :
70 : void reset(uint64_t x){
71 : assert(x < size_ && "argument out of bounds");
72 0 : uint64_t a = x/64;
73 : uint64_t b = x%64;
74 0 : uint64_t d = data_[a];
75 286 : d &= ~(1ull << b);
76 286 : data_[a] = d;
77 286 : }
78 :
79 : void toggle(uint64_t x){
80 : assert(x < size_ && "argument out of bounds");
81 : uint64_t a = x/64;
82 : uint64_t b = x%64;
83 : uint64_t d = data_[a];
84 : d ^= (1ull << b);
85 : data_[a] = d;
86 : }
87 :
88 : void set_all();
89 : void set_all(bool value);
90 : void reset_all();
91 :
92 : bool are_all_set()const;
93 : bool is_any_set()const;
94 :
95 : uint64_t population_count() const;
96 :
97 : uint64_t count_true() const {return population_count();}
98 : uint64_t count_false() const {return size()-population_count();}
99 :
100 :
101 : BitVector&operator|=(const BitVector&);
102 : BitVector&operator^=(const BitVector&);
103 : BitVector&operator&=(const BitVector&);
104 :
105 : void inplace_not();
106 : BitVector operator~() const { BitVector v = *this; v.inplace_not(); return v; }
107 :
108 : friend bool operator==(const BitVector&l, const BitVector&r);
109 : friend bool operator<(const BitVector&l, const BitVector&r);
110 :
111 0 : uint64_t*data(){return data_;}
112 6353 : const uint64_t*data()const{return data_;}
113 :
114 : uint64_t uint512_count()const{ return (size_+511) / 512; }
115 :
116 : void reset_all_padding_bits();
117 : private:
118 : uint64_t*data_;
119 : uint64_t size_;
120 : };
121 :
122 : template<class F>
123 4655 : inline BitVector make_bit_vector(uint64_t size, const F&f){
124 4655 : BitVector v(size, BitVector::uninitialized);
125 188619 : for(uint64_t x=0; x<size; ++x)
126 183964 : v.set(x, f(x));
127 4655 : return v;
128 : }
129 :
130 : // I envy the day where C++ finally gets rid of this error prone boilerplate.
131 :
132 : inline BitVector operator|(BitVector&&l, BitVector&&r) { l |= r; return std::move(l); }
133 : inline BitVector operator|(BitVector&&l, const BitVector&r) { l |= r; return std::move(l); }
134 : inline BitVector operator|(const BitVector&l, BitVector&&r) { r |= l; return std::move(r); }
135 0 : inline BitVector operator|(const BitVector&l, const BitVector&r) { BitVector x = l; x |= r; return x; }
136 :
137 : inline BitVector operator&(BitVector&&l, BitVector&&r) { l &= r; return std::move(l); }
138 : inline BitVector operator&(BitVector&&l, const BitVector&r) { l &= r; return std::move(l); }
139 : inline BitVector operator&(const BitVector&l, BitVector&&r) { r &= l; return std::move(r); }
140 : inline BitVector operator&(const BitVector&l, const BitVector&r) { BitVector x = l; x &= r; return x; }
141 :
142 : inline BitVector operator^(BitVector&&l, BitVector&&r) { l ^= r; return std::move(l); }
143 : inline BitVector operator^(BitVector&&l, const BitVector&r) { l ^= r; return std::move(l); }
144 : inline BitVector operator^(const BitVector&l, BitVector&&r) { r ^= l; return std::move(r); }
145 : inline BitVector operator^(const BitVector&l, const BitVector&r) { BitVector x = l; x ^= r; return x; }
146 :
147 : inline bool operator!=(const BitVector&l, const BitVector&r){ return !(l == r); }
148 : inline bool operator>(const BitVector&l, const BitVector&r){ return r < l; }
149 : inline bool operator<=(const BitVector&l, const BitVector&r){ return !(l > r); }
150 : inline bool operator>=(const BitVector&l, const BitVector&r){ return !(l < r); }
151 :
152 : } // namespace RoutingKit
153 :
154 : #endif
|
