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             if (isheap) {
 255                 strip_heap();
 256                 return heapsize == 0;
 257             } else
 258                 return array.size() == 0;
 259         }
 260
 261         /** Print this vector */
 262         void print(std::ostream &os) const {
 263             if (isheap) {
 264                 os << "heap:";
 265                 _print_container(os, array.begin(), array.begin() + heapsize);
 266             } else {
 267                 os << "sorted:";
 268                 _print_container(os, array.begin(), array.end());
 269             }
 270         }
 271
 272     private:
 273         /** Pop an element from the heap */
 274         void pop_heap() {
 275             assert(isheap);
 276             assert(heapsize > 0);
 277
 278             if (heapsize > 0) {
 279                 std::pop_heap(array.begin(), array.begin() + heapsize);
 280                 --heapsize;
 281             }
 282
 283             assert(is_heap());
 284         }
 285
 286         /** If heap representation is used then repeatedly pop top two
 287          * elements if they are equal. */
 288         void strip_heap() const {
 289             if (!isheap)
 290                 return;
 291
 292             heapsorted_boolean_vector<IT> *th = const_cast<heapsorted_boolean_vector<IT>*>(this);
 293
 294             // Get rid of top two elements
 295             while (true) {
 296                 // Top two elements of heap are equal
 297                 if ((heapsize >= 2 && array[0] == array[1]) ||
 298                     (heapsize >= 3 && array[0] == array[2])) {
 299 #ifndef NDEBUG
 300                     index_type t = back();
 301 #endif
 302                     th->pop_heap();
 303                     assert(t == back());
 304                     th->pop_heap();
 305                 }
 306                 else
 307                     break;
 308             }
 309
 310             assert(is_heap());
 311         }
 312
 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 {
 316             if (isheap)
 317                 return heapsize;
 318             else
 319                 return array.size();
 320         }
 321
 322         /** Convert representation to sorted array, takes O(n log n) time. */
 323         void deheapify() const {
 324             if (!isheap)
 325                 return;
 326
 327             heapsorted_boolean_vector<IT> *th = const_cast<heapsorted_boolean_vector<IT>*>(this);
 328             th->isheap = false;
 329
 330             // Trivial special cases
 331             if (heapsize == 0) {
 332                 th->array.clear();
 333                 return;
 334             }
 335             if (heapsize == 1) {
 336                 th->array.resize(1);
 337                 return;
 338             }
 339
 340             // Increase temporary array
 341             if (tmp.size() < heapsize)
 342                 th->tmp.resize(heapsize);
 343
 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);
 347
 348             // Copy back to array, but get rid of pairs of equal elements,
 349             // takes O(n) time.
 350             th->array.clear();
 351             for (unsigned i=0; ; ++i) {
 352                 // Skip pairs of equal elements
 353                 while (i+1 < heapsize && tmp[i] == tmp[i+1])
 354                     i += 2;
 355
 356                 // Reached end of array
 357                 if (i >= heapsize)
 358                     break;
 359
 360                 th->array.push_back(tmp[i]);
 361             }
 362
 363             assert(is_sorted());
 364         }
 365
 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])
 370                     return false;
 371             return true;
 372         }
 373
 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])
 378                     return false;
 379             return true;
 380         }
 381
 382     private:
 383         /** Heap or sorted array of 1's indices. */
 384         indexarray array;
 385         /** If isheap==true, the number of elements in the heap (this->array) */
 386         size_t heapsize;
 387         /** Is this->array currently a heap, or a sorted array? */
 388         bool isheap;
 389
 390         /** To reduce memory allocation and improve performance, here is a
 391          * static temporary array. */
 392         static indexarray tmp;
 393 };
 394
 395 template<class IT>
 396 typename heapsorted_boolean_vector<IT>::indexarray heapsorted_boolean_vector<IT>::tmp;
 397
 398 template<class IT>
 399 std::ostream& operator<<(std::ostream &os, const heapsorted_boolean_vector<IT> &v) {
 400     v.print(os);
 401     return os;
 402 }
 403
 404
 405 }
 406
 407 #endif