include/libstick-0.1/booleanvector.h

   1 #ifndef booleanvector_h_yeephauChuengiil
   2 #define booleanvector_h_yeephauChuengiil
   3
   4 #include <cassert>
   5 #include <vector>
   6 #include <algorithm>
   7 #include <ostream>
   8
   9
  10 namespace libstick {
  11
  12
  13 /** Print this vector */
  14 template<class Iterator>
  15 void _print_container(std::ostream &os, Iterator begin, Iterator end) {
  16     os << "[";
  17     while (begin != end) {
  18         os << *begin;
  19         if (begin+1 != end)
  20             os << " ";
  21         ++begin;
  22     }
  23     os << "]";
  24 }
  25
  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
  28  * are of type IT. */
  29 template<class IT>
  30 class sorted_boolean_vector {
  31     public:
  32         typedef IT index_type;
  33         typedef std::vector<index_type> indexarray;
  34
  35         void clear() {
  36             array.clear();
  37         }
  38
  39         /** Get value at given index. That is, return true/false if idx exists
  40          * in index-array.*/
  41         bool get(index_type idx) const {
  42             return binary_search(array.begin(), array.end(), idx);
  43         }
  44
  45         /** Return a sorted list of indices of ones.*/
  46         const indexarray& get_ones() const {
  47             return array;
  48         }
  49
  50         /** Count the number of 1s. */
  51         size_t size() const {
  52             return get_ones().size();
  53         }
  54
  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();
  58         }
  59
  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);
  67
  68             // Add 'idx' in sorted array
  69             if (value && !exists)
  70                 array.insert(it, idx);
  71             // Remove 'idx'
  72             if (!value && exists)
  73                 array.erase(it);
  74
  75 #ifndef NDEBUG
  76             assert(get(idx) == value);
  77             is_sorted();
  78 #endif
  79         }
  80
  81         /** Add another vector to us by means of XOR */
  82         void add(const sorted_boolean_vector<IT> &vec) {
  83 #ifndef NDEBUG
  84             is_sorted();
  85 #endif
  86
  87             // Make target array large enough
  88             const size_t maxsize = array.size() + vec.array.size();
  89             if (tmp.size() < maxsize)
  90                 tmp.resize(maxsize);
  91
  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());
  95
  96             // Copy back to the original vector
  97             array.resize(it - tmp.begin());
  98             std::copy(tmp.begin(), it, array.begin());
  99         }
 100
 101         /** Remove one with largest index. */
 102         void pop_back() {
 103             array.pop_back();
 104         }
 105
 106         /** Get largest index among all ones. */
 107         index_type back() const {
 108             return array.back();
 109         }
 110
 111         /** Returns true if vector contains no 1. */
 112         bool isempty() const {
 113             return array.size() == 0;
 114         }
 115
 116         /** Print this vector */
 117         void print(std::ostream &os) const {
 118             _print_container(os, array.begin(), array.end());
 119         }
 120
 121     private:
 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])
 126                     return false;
 127             return true;
 128         }
 129
 130     private:
 131         /** Heap or sorted array of 1's indices. */
 132         indexarray array;
 133
 134         /** To reduce memory allocation and improve performance, here is a
 135          * static temporary array. */
 136         static indexarray tmp;
 137 };
 138
 139 template<class IT>
 140 typename sorted_boolean_vector<IT>::indexarray sorted_boolean_vector<IT>::tmp;
 141
 142 template<class IT>
 143 std::ostream& operator<<(std::ostream &os, const sorted_boolean_vector<IT> &v) {
 144     v.print(os);
 145     return os;
 146 }
 147
 148
 149 /** Like sorted_boolean_vector. Depending on the access-pattern, it switches
 150  * between a max-heap and sorted array structure. */
 151 template<class IT>
 152 class heapsorted_boolean_vector {
 153     public:
 154         typedef IT index_type;
 155         typedef std::vector<index_type> indexarray;
 156
 157         heapsorted_boolean_vector() {
 158             clear();
 159         }
 160
 161         void clear() {
 162             isheap = false;
 163             heapsize = 0;
 164             array.clear();
 165         }
 166
 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
 169          * array. */
 170         bool get(index_type idx) const {
 171             deheapify();
 172             return binary_search(array.begin(), array.end(), idx);
 173         }
 174
 175         /** Return a sorted list of indices of ones. */
 176         const indexarray& get_ones() const {
 177             deheapify();
 178             return array;
 179         }
 180
 181         /** Count the number of 1s. */
 182         size_t size() const {
 183             return get_ones().size();
 184         }
 185
 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();
 189         }
 190
 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
 193          * sorted array.*/
 194         void set(index_type idx, bool value) {
 195             deheapify();
 196
 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);
 201
 202             // Add 'idx' in sorted array
 203             if (value && !exists)
 204                 array.insert(it, idx);
 205             // Remove 'idx'
 206             if (!value && exists)
 207                 array.erase(it);
 208
 209 #ifndef NDEBUG
 210             assert(get(idx) == value);
 211             is_sorted();
 212 #endif
 213         }
 214
 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();
 221
 222             // We will become a heap!
 223             isheap = true;
 224             heapsize = size1 + size2;
 225             array.resize(heapsize);
 226
 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);
 231         }
 232
 233         /** Remove one with largest index. */
 234         void pop_back() {
 235             assert(!isempty());
 236             strip_heap();
 237
 238             if (isheap)
 239                 pop_heap();
 240             else
 241                 array.pop_back();
 242         }
 243
 244         /** Get largest index among all ones. */
 245         index_type back() const {
 246             assert(!isempty());
 247             strip_heap();
 248
 249             return isheap ? array[0] : array.back();
 250         }
 251
 252         /** Returns true if vector contains no 1. */
 253         bool isempty() const {
 254             strip_heap();
 255             return isheap ? heapsize==0 : array.size()==0;
 256         }
 257
 258         /** Print this vector */
 259         void print(std::ostream &os) const {
 260             if (isheap) {
 261                 os << "heap:";
 262                 _print_container(os, array.begin(), array.begin() + heapsize);
 263             } else {
 264                 os << "sorted:";
 265                 _print_container(os, array.begin(), array.end());
 266             }
 267         }
 268
 269     private:
 270         /** Pop an element from the heap */
 271         void pop_heap() {
 272             assert(isheap);
 273             assert(heapsize > 0);
 274
 275             if (heapsize > 0) {
 276                 std::pop_heap(array.begin(), array.begin() + heapsize);
 277                 --heapsize;
 278             }
 279
 280             assert(is_heap());
 281         }
 282
 283         /** If heap representation is used then repeatedly pop top two
 284          * elements if they are equal. */
 285         void strip_heap() const {
 286             if (!isheap)
 287                 return;
 288
 289             heapsorted_boolean_vector<IT> *th = const_cast<heapsorted_boolean_vector<IT>*>(this);
 290
 291             // Get rid of top two elements
 292             while (true) {
 293                 // Top two elements of heap are equal
 294                 if ((heapsize >= 2 && array[0] == array[1]) ||
 295                     (heapsize >= 3 && array[0] == array[2])) {
 296 #ifndef NDEBUG
 297                     index_type t = back();
 298 #endif
 299                     th->pop_heap();
 300                     assert(t == back());
 301                     th->pop_heap();
 302                 }
 303                 else
 304                     break;
 305             }
 306
 307             assert(is_heap());
 308         }
 309
 310         /** Get the number of indices saved. If heap representation is
 311          * used, indices may be saved multiple times. */
 312         size_t get_indices_count() const {
 313             if (isheap)
 314                 return heapsize;
 315             else
 316                 return array.size();
 317         }
 318
 319         /** Convert representation to sorted array, takes O(n log n) time. */
 320         void deheapify() const {
 321             if (!isheap)
 322                 return;
 323
 324             heapsorted_boolean_vector<IT> *th = const_cast<heapsorted_boolean_vector<IT>*>(this);
 325             th->isheap = false;
 326
 327             // Trivial special cases
 328             if (heapsize == 0) {
 329                 th->array.clear();
 330                 return;
 331             }
 332             if (heapsize == 1) {
 333                 th->array.resize(1);
 334                 return;
 335             }
 336
 337             // Increase temporary array
 338             if (tmp.size() < heapsize)
 339                 th->tmp.resize(heapsize);
 340
 341             // Get a sorted copy of the heap, takes O(n log n) time.
 342             std::copy(array.begin(), array.begin() + heapsize, th->tmp.begin());
 343             std::sort_heap(th->tmp.begin(), th->tmp.begin() + heapsize);
 344
 345             // Copy back to array, but get rid of pairs of equal elements,
 346             // takes O(n) time.
 347             th->array.clear();
 348             for (unsigned i=0; ; ++i) {
 349                 // Skip pairs of equal elements
 350                 while (i+1 < heapsize && tmp[i] == tmp[i+1])
 351                     i += 2;
 352
 353                 // Reached end of array
 354                 if (i >= heapsize)
 355                     break;
 356
 357                 th->array.push_back(tmp[i]);
 358             }
 359
 360             assert(is_sorted());
 361         }
 362
 363         bool is_sorted() const {
 364             // C++11 would have is_sorted
 365             for (unsigned i=1; i < array.size(); ++i)
 366                 if(array[i-1] > array[i])
 367                     return false;
 368             return true;
 369         }
 370
 371         bool is_heap() const {
 372             // C++11 would have is_heap
 373             for (unsigned i=1; i < heapsize; ++i)
 374                 if(array[i/2] < array[i])
 375                     return false;
 376             return true;
 377         }
 378
 379     private:
 380         /** Heap or sorted array of 1's indices. */
 381         indexarray array;
 382         /** If isheap==true, the number of elements in the heap (this->array) */
 383         size_t heapsize;
 384         /** Is this->array currently a heap, or a sorted array? */
 385         bool isheap;
 386
 387         /** To reduce memory allocation and improve performance, here is a
 388          * static temporary array. */
 389         static indexarray tmp;
 390 };
 391
 392 template<class IT>
 393 typename heapsorted_boolean_vector<IT>::indexarray heapsorted_boolean_vector<IT>::tmp;
 394
 395 template<class IT>
 396 std::ostream& operator<<(std::ostream &os, const heapsorted_boolean_vector<IT> &v) {
 397     v.print(os);
 398     return os;
 399 }
 400
 401
 402 }
 403
 404 #endif