+++ /dev/null
-#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;
- }
-
- /** Count the number of 1s. */
- size_t size() const {
- return get_ones().size();
- }
-
- /** 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;
- }
-
- /** Count the number of 1s. */
- size_t size() const {
- return get_ones().size();
- }
-
- /** 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 {
- if (isheap) {
- strip_heap();
- return heapsize == 0;
- } else
- return 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 / blobdiff