+#ifndef booleanvector_h_yeephauChuengiil
+#define booleanvector_h_yeephauChuengiil
+
+#include <cassert>
+#include <vector>
+#include <algorithm>
+#include <ostream>
+
+
+namespace libstick {
+
+
+/** Print this vector */
+template<class Iterator>
+void _print_container(std::ostream &os, Iterator begin, Iterator end) {
+ os << "[";
+ while (begin != end) {
+ os << *begin;
+ if (begin+1 != end)
+ os << " ";
+ ++begin;
+ }
+ os << "]";
+}
+
+/** A sparse boolean vector. It manages a std::vector containing the sorted
+ * indices of all ones, i.e. back() gives the index of the final one. Indices
+ * are of type IT. */
+template<class IT>
+class sorted_boolean_vector {
+ public:
+ typedef IT index_type;
+ typedef std::vector<index_type> indexarray;
+
+ void clear() {
+ array.clear();
+ }
+
+ /** Get value at given index. That is, return true/false if idx exists
+ * in index-array.*/
+ bool get(index_type idx) const {
+ return binary_search(array.begin(), array.end(), idx);
+ }
+
+ /** Return a sorted list of indices of ones.*/
+ const indexarray& get_ones() const {
+ return array;
+ }
+
+ /** Two vectors are equal if they contain the same indices. */
+ bool operator==(const sorted_boolean_vector<IT> &vec) const {
+ return get_ones() == vec.get_ones();
+ }
+
+ /** Set value at given index. That is, add/remove idx to index-array if
+ * value is true/false. */
+ void set(index_type idx, bool value) {
+ // Get the position where to insert/remove
+ typename indexarray::iterator it = lower_bound(array.begin(), array.end(), idx);
+ bool exists = (it != array.end() && *it == idx);
+ assert(get(idx) == exists);
+
+ // Add 'idx' in sorted array
+ if (value && !exists)
+ array.insert(it, idx);
+ // Remove 'idx'
+ if (!value && exists)
+ array.erase(it);
+
+#ifndef NDEBUG
+ assert(get(idx) == value);
+ is_sorted();
+#endif
+ }
+
+ /** Add another vector to us by means of XOR */
+ void add(const sorted_boolean_vector<IT> &vec) {
+#ifndef NDEBUG
+ is_sorted();
+#endif
+
+ // Make target array large enough
+ const size_t maxsize = array.size() + vec.array.size();
+ if (tmp.size() < maxsize)
+ tmp.resize(maxsize);
+
+ // Compute symmetric difference
+ typename indexarray::iterator it = std::set_symmetric_difference(
+ array.begin(), array.end(), vec.array.begin(), vec.array.end(), tmp.begin());
+
+ // Copy back to the original vector
+ array.resize(it - tmp.begin());
+ std::copy(tmp.begin(), it, array.begin());
+ }
+
+ /** Remove one with largest index. */
+ void pop_back() {
+ array.pop_back();
+ }
+
+ /** Get largest index among all ones. */
+ index_type back() const {
+ return array.back();
+ }
+
+ /** Returns true if vector contains no 1. */
+ bool isempty() const {
+ return array.size() == 0;
+ }
+
+ /** Print this vector */
+ void print(std::ostream &os) const {
+ _print_container(os, array.begin(), array.end());
+ }
+
+ private:
+ bool is_sorted() const {
+ // C++11 would have is_sorted
+ for (unsigned i=1; i < array.size(); ++i)
+ if(array[i-1] > array[i])
+ return false;
+ return true;
+ }
+
+ private:
+ /** Heap or sorted array of 1's indices. */
+ indexarray array;
+
+ /** To reduce memory allocation and improve performance, here is a
+ * static temporary array. */
+ static indexarray tmp;
+};
+
+template<class IT>
+typename sorted_boolean_vector<IT>::indexarray sorted_boolean_vector<IT>::tmp;
+
+template<class IT>
+std::ostream& operator<<(std::ostream &os, const sorted_boolean_vector<IT> &v) {
+ v.print(os);
+ return os;
+}
+
+
+/** Like sorted_boolean_vector. Depending on the access-pattern, it switches
+ * between a max-heap and sorted array structure. */
+template<class IT>
+class heapsorted_boolean_vector {
+ public:
+ typedef IT index_type;
+ typedef std::vector<index_type> indexarray;
+
+ heapsorted_boolean_vector() {
+ clear();
+ }
+
+ void clear() {
+ isheap = false;
+ heapsize = 0;
+ array.clear();
+ }
+
+ /** Get value at given index. That is, return true/false if idx exists
+ * in index-array. This function converts representation to a sorted
+ * array. */
+ bool get(index_type idx) const {
+ deheapify();
+ return binary_search(array.begin(), array.end(), idx);
+ }
+
+ /** Return a sorted list of indices of ones. */
+ const indexarray& get_ones() const {
+ deheapify();
+ return array;
+ }
+
+ /** Two vectors are equal if they contain the same indices. */
+ bool operator==(const heapsorted_boolean_vector<IT> &vec) const {
+ return get_ones() == vec.get_ones();
+ }
+
+ /** Set value at given index. That is, add/remove idx to index-array if
+ * value is true/false. This function converts representation to a
+ * sorted array.*/
+ void set(index_type idx, bool value) {
+ deheapify();
+
+ // Get the position where to insert/remove
+ typename indexarray::iterator it = lower_bound(array.begin(), array.end(), idx);
+ bool exists = (it != array.end() && *it == idx);
+ assert(get(idx) == exists);
+
+ // Add 'idx' in sorted array
+ if (value && !exists)
+ array.insert(it, idx);
+ // Remove 'idx'
+ if (!value && exists)
+ array.erase(it);
+
+#ifndef NDEBUG
+ assert(get(idx) == value);
+ is_sorted();
+#endif
+ }
+
+ /** Add another vector to us by means of XOR. This function converts
+ * the representation to a heap. */
+ void add(const heapsorted_boolean_vector<IT> &vec) {
+ // Make space for the combined stuff
+ size_t size1 = get_indices_count();
+ size_t size2 = vec.get_indices_count();
+
+ // We will become a heap!
+ isheap = true;
+ heapsize = size1 + size2;
+ array.resize(heapsize);
+
+ // Append elements of vec to our own array
+ std::copy(vec.array.begin(), vec.array.begin() + size2, array.begin() + size1);
+ // Make a heap out of it
+ std::make_heap(array.begin(), array.begin() + heapsize);
+ }
+
+ /** Remove one with largest index. */
+ void pop_back() {
+ assert(!isempty());
+ strip_heap();
+
+ if (isheap)
+ pop_heap();
+ else
+ array.pop_back();
+ }
+
+ /** Get largest index among all ones. */
+ index_type back() const {
+ assert(!isempty());
+ strip_heap();
+
+ return isheap ? array[0] : array.back();
+ }
+
+ /** Returns true if vector contains no 1. */
+ bool isempty() const {
+ strip_heap();
+ return isheap ? heapsize==0 : array.size()==0;
+ }
+
+ /** Print this vector */
+ void print(std::ostream &os) const {
+ if (isheap) {
+ os << "heap:";
+ _print_container(os, array.begin(), array.begin() + heapsize);
+ } else {
+ os << "sorted:";
+ _print_container(os, array.begin(), array.end());
+ }
+ }
+
+ private:
+ /** Pop an element from the heap */
+ void pop_heap() {
+ assert(isheap);
+ assert(heapsize > 0);
+
+ if (heapsize > 0) {
+ std::pop_heap(array.begin(), array.begin() + heapsize);
+ --heapsize;
+ }
+
+ assert(is_heap());
+ }
+
+ /** If heap representation is used then repeatedly pop top two
+ * elements if they are equal. */
+ void strip_heap() const {
+ if (!isheap)
+ return;
+
+ heapsorted_boolean_vector<IT> *th = const_cast<heapsorted_boolean_vector<IT>*>(this);
+
+ // Get rid of top two elements
+ while (true) {
+ // Top two elements of heap are equal
+ if ((heapsize >= 2 && array[0] == array[1]) ||
+ (heapsize >= 3 && array[0] == array[2])) {
+#ifndef NDEBUG
+ index_type t = back();
+#endif
+ th->pop_heap();
+ assert(t == back());
+ th->pop_heap();
+ }
+ else
+ break;
+ }
+
+ assert(is_heap());
+ }
+
+ /** Get the number of indices saved. If heap representation is
+ * used, indices may be saved multiple times. */
+ size_t get_indices_count() const {
+ if (isheap)
+ return heapsize;
+ else
+ return array.size();
+ }
+
+ /** Convert representation to sorted array, takes O(n log n) time. */
+ void deheapify() const {
+ if (!isheap)
+ return;
+
+ heapsorted_boolean_vector<IT> *th = const_cast<heapsorted_boolean_vector<IT>*>(this);
+ th->isheap = false;
+
+ // Trivial special cases
+ if (heapsize == 0) {
+ th->array.clear();
+ return;
+ }
+ if (heapsize == 1) {
+ th->array.resize(1);
+ return;
+ }
+
+ // Increase temporary array
+ if (tmp.size() < heapsize)
+ th->tmp.resize(heapsize);
+
+ // Get a sorted copy of the heap, takes O(n log n) time.
+ std::copy(array.begin(), array.begin() + heapsize, th->tmp.begin());
+ std::sort_heap(th->tmp.begin(), th->tmp.begin() + heapsize);
+
+ // Copy back to array, but get rid of pairs of equal elements,
+ // takes O(n) time.
+ th->array.clear();
+ for (unsigned i=0; ; ++i) {
+ // Skip pairs of equal elements
+ while (i+1 < heapsize && tmp[i] == tmp[i+1])
+ i += 2;
+
+ // Reached end of array
+ if (i >= heapsize)
+ break;
+
+ th->array.push_back(tmp[i]);
+ }
+
+ assert(is_sorted());
+ }
+
+ bool is_sorted() const {
+ // C++11 would have is_sorted
+ for (unsigned i=1; i < array.size(); ++i)
+ if(array[i-1] > array[i])
+ return false;
+ return true;
+ }
+
+ bool is_heap() const {
+ // C++11 would have is_heap
+ for (unsigned i=1; i < heapsize; ++i)
+ if(array[i/2] < array[i])
+ return false;
+ return true;
+ }
+
+ private:
+ /** Heap or sorted array of 1's indices. */
+ indexarray array;
+ /** If isheap==true, the number of elements in the heap (this->array) */
+ size_t heapsize;
+ /** Is this->array currently a heap, or a sorted array? */
+ bool isheap;
+
+ /** To reduce memory allocation and improve performance, here is a
+ * static temporary array. */
+ static indexarray tmp;
+};
+
+template<class IT>
+typename heapsorted_boolean_vector<IT>::indexarray heapsorted_boolean_vector<IT>::tmp;
+
+template<class IT>
+std::ostream& operator<<(std::ostream &os, const heapsorted_boolean_vector<IT> &v) {
+ v.print(os);
+ return os;
+}
+
+
+}
+
+#endif
projects / libstick.git / commitdiff