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 /** Two vectors are equal if they contain the same indices. */
51 bool operator==(const sorted_boolean_vector
<IT
> &vec
) const {
52 return get_ones() == vec
.get_ones();
55 /** Set value at given index. That is, add/remove idx to index-array if
56 * value is true/false. */
57 void set(index_type idx
, bool value
) {
58 // Get the position where to insert/remove
59 typename
indexarray::iterator it
= lower_bound(array
.begin(), array
.end(), idx
);
60 bool exists
= (it
!= array
.end() && *it
== idx
);
61 assert(get(idx
) == exists
);
63 // Add 'idx' in sorted array
65 array
.insert(it
, idx
);
71 assert(get(idx
) == value
);
76 /** Add another vector to us by means of XOR */
77 void add(const sorted_boolean_vector
<IT
> &vec
) {
82 // Make target array large enough
83 const size_t maxsize
= array
.size() + vec
.array
.size();
84 if (tmp
.size() < maxsize
)
87 // Compute symmetric difference
88 typename
indexarray::iterator it
= std::set_symmetric_difference(
89 array
.begin(), array
.end(), vec
.array
.begin(), vec
.array
.end(), tmp
.begin());
91 // Copy back to the original vector
92 array
.resize(it
- tmp
.begin());
93 std::copy(tmp
.begin(), it
, array
.begin());
96 /** Remove one with largest index. */
101 /** Get largest index among all ones. */
102 index_type
back() const {
106 /** Returns true if vector contains no 1. */
107 bool isempty() const {
108 return array
.size() == 0;
111 /** Print this vector */
112 void print(std::ostream
&os
) const {
113 _print_container(os
, array
.begin(), array
.end());
117 bool is_sorted() const {
118 // C++11 would have is_sorted
119 for (unsigned i
=1; i
< array
.size(); ++i
)
120 if(array
[i
-1] > array
[i
])
126 /** Heap or sorted array of 1's indices. */
129 /** To reduce memory allocation and improve performance, here is a
130 * static temporary array. */
131 static indexarray tmp
;
135 typename sorted_boolean_vector
<IT
>::indexarray sorted_boolean_vector
<IT
>::tmp
;
138 std::ostream
& operator<<(std::ostream
&os
, const sorted_boolean_vector
<IT
> &v
) {
144 /** Like sorted_boolean_vector. Depending on the access-pattern, it switches
145 * between a max-heap and sorted array structure. */
147 class heapsorted_boolean_vector
{
149 typedef IT index_type
;
150 typedef std::vector
<index_type
> indexarray
;
152 heapsorted_boolean_vector() {
162 /** Get value at given index. That is, return true/false if idx exists
163 * in index-array. This function converts representation to a sorted
165 bool get(index_type idx
) const {
167 return binary_search(array
.begin(), array
.end(), idx
);
170 /** Return a sorted list of indices of ones. */
171 const indexarray
& get_ones() const {
176 /** Two vectors are equal if they contain the same indices. */
177 bool operator==(const heapsorted_boolean_vector
<IT
> &vec
) const {
178 return get_ones() == vec
.get_ones();
181 /** Set value at given index. That is, add/remove idx to index-array if
182 * value is true/false. This function converts representation to a
184 void set(index_type idx
, bool value
) {
187 // Get the position where to insert/remove
188 typename
indexarray::iterator it
= lower_bound(array
.begin(), array
.end(), idx
);
189 bool exists
= (it
!= array
.end() && *it
== idx
);
190 assert(get(idx
) == exists
);
192 // Add 'idx' in sorted array
193 if (value
&& !exists
)
194 array
.insert(it
, idx
);
196 if (!value
&& exists
)
200 assert(get(idx
) == value
);
205 /** Add another vector to us by means of XOR. This function converts
206 * the representation to a heap. */
207 void add(const heapsorted_boolean_vector
<IT
> &vec
) {
208 // Make space for the combined stuff
209 size_t size1
= get_indices_count();
210 size_t size2
= vec
.get_indices_count();
212 // We will become a heap!
214 heapsize
= size1
+ size2
;
215 array
.resize(heapsize
);
217 // Append elements of vec to our own array
218 std::copy(vec
.array
.begin(), vec
.array
.begin() + size2
, array
.begin() + size1
);
219 // Make a heap out of it
220 std::make_heap(array
.begin(), array
.begin() + heapsize
);
223 /** Remove one with largest index. */
234 /** Get largest index among all ones. */
235 index_type
back() const {
239 return isheap
? array
[0] : array
.back();
242 /** Returns true if vector contains no 1. */
243 bool isempty() const {
245 return isheap
? heapsize
==0 : array
.size()==0;
248 /** Print this vector */
249 void print(std::ostream
&os
) const {
252 _print_container(os
, array
.begin(), array
.begin() + heapsize
);
255 _print_container(os
, array
.begin(), array
.end());
260 /** Pop an element from the heap */
263 assert(heapsize
> 0);
266 std::pop_heap(array
.begin(), array
.begin() + heapsize
);
273 /** If heap representation is used then repeatedly pop top two
274 * elements if they are equal. */
275 void strip_heap() const {
279 heapsorted_boolean_vector
<IT
> *th
= const_cast<heapsorted_boolean_vector
<IT
>*>(this);
281 // Get rid of top two elements
283 // Top two elements of heap are equal
284 if ((heapsize
>= 2 && array
[0] == array
[1]) ||
285 (heapsize
>= 3 && array
[0] == array
[2])) {
287 index_type t
= back();
300 /** Get the number of indices saved. If heap representation is
301 * used, indices may be saved multiple times. */
302 size_t get_indices_count() const {
309 /** Convert representation to sorted array, takes O(n log n) time. */
310 void deheapify() const {
314 heapsorted_boolean_vector
<IT
> *th
= const_cast<heapsorted_boolean_vector
<IT
>*>(this);
317 // Trivial special cases
327 // Increase temporary array
328 if (tmp
.size() < heapsize
)
329 th
->tmp
.resize(heapsize
);
331 // Get a sorted copy of the heap, takes O(n log n) time.
332 std::copy(array
.begin(), array
.begin() + heapsize
, th
->tmp
.begin());
333 std::sort_heap(th
->tmp
.begin(), th
->tmp
.begin() + heapsize
);
335 // Copy back to array, but get rid of pairs of equal elements,
338 for (unsigned i
=0; ; ++i
) {
339 // Skip pairs of equal elements
340 while (i
+1 < heapsize
&& tmp
[i
] == tmp
[i
+1])
343 // Reached end of array
347 th
->array
.push_back(tmp
[i
]);
353 bool is_sorted() const {
354 // C++11 would have is_sorted
355 for (unsigned i
=1; i
< array
.size(); ++i
)
356 if(array
[i
-1] > array
[i
])
361 bool is_heap() const {
362 // C++11 would have is_heap
363 for (unsigned i
=1; i
< heapsize
; ++i
)
364 if(array
[i
/2] < array
[i
])
370 /** Heap or sorted array of 1's indices. */
372 /** If isheap==true, the number of elements in the heap (this->array) */
374 /** Is this->array currently a heap, or a sorted array? */
377 /** To reduce memory allocation and improve performance, here is a
378 * static temporary array. */
379 static indexarray tmp
;
383 typename heapsorted_boolean_vector
<IT
>::indexarray heapsorted_boolean_vector
<IT
>::tmp
;
386 std::ostream
& operator<<(std::ostream
&os
, const heapsorted_boolean_vector
<IT
> &v
) {