1 #ifndef booleanvector_h_yeephauChuengiil
2 #define booleanvector_h_yeephauChuengiil
13 /** Print this vector */
14 template<class Iterator
>
15 void _print_container(std::ostream
&os
, Iterator begin
, Iterator end
) {
17 while (begin
!= end
) {
26 /** A sparse boolean vector. It manages a std::vector containing the sorted
27 * indices of all ones, i.e. back() gives the index of the final one. Indices
30 class sorted_boolean_vector
{
32 typedef IT index_type
;
33 typedef std::vector
<index_type
> indexarray
;
39 /** Get value at given index. That is, return true/false if idx exists
41 bool get(index_type idx
) const {
42 return binary_search(array
.begin(), array
.end(), idx
);
45 /** Return a sorted list of indices of ones.*/
46 const indexarray
& get_ones() const {
50 /** Count the number of 1s. */
52 return get_ones().size();
55 /** Two vectors are equal if they contain the same indices. */
56 bool operator==(const sorted_boolean_vector
<IT
> &vec
) const {
57 return get_ones() == vec
.get_ones();
60 /** Set value at given index. That is, add/remove idx to index-array if
61 * value is true/false. */
62 void set(index_type idx
, bool value
) {
63 // Get the position where to insert/remove
64 typename
indexarray::iterator it
= lower_bound(array
.begin(), array
.end(), idx
);
65 bool exists
= (it
!= array
.end() && *it
== idx
);
66 assert(get(idx
) == exists
);
68 // Add 'idx' in sorted array
70 array
.insert(it
, idx
);
76 assert(get(idx
) == value
);
81 /** Add another vector to us by means of XOR */
82 void add(const sorted_boolean_vector
<IT
> &vec
) {
87 // Make target array large enough
88 const size_t maxsize
= array
.size() + vec
.array
.size();
89 if (tmp
.size() < maxsize
)
92 // Compute symmetric difference
93 typename
indexarray::iterator it
= std::set_symmetric_difference(
94 array
.begin(), array
.end(), vec
.array
.begin(), vec
.array
.end(), tmp
.begin());
96 // Copy back to the original vector
97 array
.resize(it
- tmp
.begin());
98 std::copy(tmp
.begin(), it
, array
.begin());
101 /** Remove one with largest index. */
106 /** Get largest index among all ones. */
107 index_type
back() const {
111 /** Returns true if vector contains no 1. */
112 bool isempty() const {
113 return array
.size() == 0;
116 /** Print this vector */
117 void print(std::ostream
&os
) const {
118 _print_container(os
, array
.begin(), array
.end());
122 bool is_sorted() const {
123 // C++11 would have is_sorted
124 for (unsigned i
=1; i
< array
.size(); ++i
)
125 if(array
[i
-1] > array
[i
])
131 /** Heap or sorted array of 1's indices. */
134 /** To reduce memory allocation and improve performance, here is a
135 * static temporary array. */
136 static indexarray tmp
;
140 typename sorted_boolean_vector
<IT
>::indexarray sorted_boolean_vector
<IT
>::tmp
;
143 std::ostream
& operator<<(std::ostream
&os
, const sorted_boolean_vector
<IT
> &v
) {
149 /** Like sorted_boolean_vector. Depending on the access-pattern, it switches
150 * between a max-heap and sorted array structure. */
152 class heapsorted_boolean_vector
{
154 typedef IT index_type
;
155 typedef std::vector
<index_type
> indexarray
;
157 heapsorted_boolean_vector() {
167 /** Get value at given index. That is, return true/false if idx exists
168 * in index-array. This function converts representation to a sorted
170 bool get(index_type idx
) const {
172 return binary_search(array
.begin(), array
.end(), idx
);
175 /** Return a sorted list of indices of ones. */
176 const indexarray
& get_ones() const {
181 /** Count the number of 1s. */
182 size_t size() const {
183 return get_ones().size();
186 /** Two vectors are equal if they contain the same indices. */
187 bool operator==(const heapsorted_boolean_vector
<IT
> &vec
) const {
188 return get_ones() == vec
.get_ones();
191 /** Set value at given index. That is, add/remove idx to index-array if
192 * value is true/false. This function converts representation to a
194 void set(index_type idx
, bool value
) {
197 // Get the position where to insert/remove
198 typename
indexarray::iterator it
= lower_bound(array
.begin(), array
.end(), idx
);
199 bool exists
= (it
!= array
.end() && *it
== idx
);
200 assert(get(idx
) == exists
);
202 // Add 'idx' in sorted array
203 if (value
&& !exists
)
204 array
.insert(it
, idx
);
206 if (!value
&& exists
)
210 assert(get(idx
) == value
);
215 /** Add another vector to us by means of XOR. This function converts
216 * the representation to a heap. */
217 void add(const heapsorted_boolean_vector
<IT
> &vec
) {
218 // Make space for the combined stuff
219 size_t size1
= get_indices_count();
220 size_t size2
= vec
.get_indices_count();
222 // We will become a heap!
224 heapsize
= size1
+ size2
;
225 array
.resize(heapsize
);
227 // Append elements of vec to our own array
228 std::copy(vec
.array
.begin(), vec
.array
.begin() + size2
, array
.begin() + size1
);
229 // Make a heap out of it
230 std::make_heap(array
.begin(), array
.begin() + heapsize
);
233 /** Remove one with largest index. */
244 /** Get largest index among all ones. */
245 index_type
back() const {
249 return isheap
? array
[0] : array
.back();
252 /** Returns true if vector contains no 1. */
253 bool isempty() const {
256 return heapsize
== 0;
258 return array
.size() == 0;
261 /** Print this vector */
262 void print(std::ostream
&os
) const {
265 _print_container(os
, array
.begin(), array
.begin() + heapsize
);
268 _print_container(os
, array
.begin(), array
.end());
273 /** Pop an element from the heap */
276 assert(heapsize
> 0);
279 std::pop_heap(array
.begin(), array
.begin() + heapsize
);
286 /** If heap representation is used then repeatedly pop top two
287 * elements if they are equal. */
288 void strip_heap() const {
292 heapsorted_boolean_vector
<IT
> *th
= const_cast<heapsorted_boolean_vector
<IT
>*>(this);
294 // Get rid of top two elements
296 // Top two elements of heap are equal
297 if ((heapsize
>= 2 && array
[0] == array
[1]) ||
298 (heapsize
>= 3 && array
[0] == array
[2])) {
300 index_type t
= back();
313 /** Get the number of indices saved. If heap representation is
314 * used, indices may be saved multiple times. */
315 size_t get_indices_count() const {
322 /** Convert representation to sorted array, takes O(n log n) time. */
323 void deheapify() const {
327 heapsorted_boolean_vector
<IT
> *th
= const_cast<heapsorted_boolean_vector
<IT
>*>(this);
330 // Trivial special cases
340 // Increase temporary array
341 if (tmp
.size() < heapsize
)
342 th
->tmp
.resize(heapsize
);
344 // Get a sorted copy of the heap, takes O(n log n) time.
345 std::copy(array
.begin(), array
.begin() + heapsize
, th
->tmp
.begin());
346 std::sort_heap(th
->tmp
.begin(), th
->tmp
.begin() + heapsize
);
348 // Copy back to array, but get rid of pairs of equal elements,
351 for (unsigned i
=0; ; ++i
) {
352 // Skip pairs of equal elements
353 while (i
+1 < heapsize
&& tmp
[i
] == tmp
[i
+1])
356 // Reached end of array
360 th
->array
.push_back(tmp
[i
]);
366 bool is_sorted() const {
367 // C++11 would have is_sorted
368 for (unsigned i
=1; i
< array
.size(); ++i
)
369 if(array
[i
-1] > array
[i
])
374 bool is_heap() const {
375 // C++11 would have is_heap
376 for (unsigned i
=1; i
< heapsize
; ++i
)
377 if(array
[i
/2] < array
[i
])
383 /** Heap or sorted array of 1's indices. */
385 /** If isheap==true, the number of elements in the heap (this->array) */
387 /** Is this->array currently a heap, or a sorted array? */
390 /** To reduce memory allocation and improve performance, here is a
391 * static temporary array. */
392 static indexarray tmp
;
396 typename heapsorted_boolean_vector
<IT
>::indexarray heapsorted_boolean_vector
<IT
>::tmp
;
399 std::ostream
& operator<<(std::ostream
&os
, const heapsorted_boolean_vector
<IT
> &v
) {