summaryrefslogtreecommitdiff
path: root/omegalib/omega/include/basic/BoolSet.h
diff options
context:
space:
mode:
Diffstat (limited to 'omegalib/omega/include/basic/BoolSet.h')
-rwxr-xr-xomegalib/omega/include/basic/BoolSet.h641
1 files changed, 0 insertions, 641 deletions
diff --git a/omegalib/omega/include/basic/BoolSet.h b/omegalib/omega/include/basic/BoolSet.h
deleted file mode 100755
index a78af2e..0000000
--- a/omegalib/omega/include/basic/BoolSet.h
+++ /dev/null
@@ -1,641 +0,0 @@
-/*****************************************************************************
- Copyright (C) 2009-2011 Chun Chen
- All Rights Reserved.
-
- Purpose:
- BoolSet class, used as a set of integers from 0..n-1 where n is a very
- small integer.
-
- Notes:
- Set operands of binary operations can be of different sizes, missing
- elements are treated as false.
-
- History:
- 03/30/09 Created by Chun Chen.
- 03/26/11 iterator added, -chun
-*****************************************************************************/
-
-#ifndef _BOOLSET_H
-#define _BOOLSET_H
-
-#include <vector>
-#include <iostream>
-#include <assert.h>
-#include <stdexcept>
-#include <iterator>
-
-namespace omega {
-
- //! BoolSet class, used as a set of integers from 0 to n-1 where n is a very small integer.
-template<typename T = unsigned int>
-class BoolSet {
-protected:
- unsigned int size_;
- std::vector<T> set_;
-
-public:
- BoolSet(unsigned int size = 0);
- ~BoolSet() {}
-
- void set(unsigned int);
- void unset(unsigned int);
- void set_all();
- void unset_all();
- bool get(unsigned int) const;
- unsigned int size() const {return size_;}
- unsigned int num_elem() const;
- bool imply(const BoolSet<T> &) const;
- bool empty() const;
- void dump() const;
-
- BoolSet<T> &operator|=(const BoolSet<T> &);
- BoolSet<T> &operator&=(const BoolSet<T> &);
- BoolSet<T> &operator-=(const BoolSet<T> &);
-
- //! union
- template<typename TT> friend BoolSet<TT> operator|(const BoolSet<TT> &, const BoolSet<TT> &);
- //! intersection
- template<typename TT> friend BoolSet<TT> operator&(const BoolSet<TT> &, const BoolSet<TT> &);
- //! difference
- template<typename TT> friend BoolSet<TT> operator-(const BoolSet<TT> &, const BoolSet<TT> &);
- //! complement
- template<typename TT> friend BoolSet<TT> operator~(const BoolSet<TT> &);
- template<typename TT> friend bool operator==(const BoolSet<TT> &, const BoolSet<TT> &);
- template<typename TT> friend bool operator!=(const BoolSet<TT> &, const BoolSet<TT> &);
- template<typename TT> friend std::ostream& operator<<(std::ostream &, const BoolSet<TT> &);
- template<typename TT> friend bool operator<(const BoolSet<TT> &, const BoolSet<TT> &);
-
-public:
- class iterator;
- class const_iterator;
- iterator begin();
- iterator end();
- const_iterator begin() const;
- const_iterator end() const;
-};
-
-
-template<typename T>
-BoolSet<T>::BoolSet(unsigned int size) {
- assert(size >= 0);
- size_ = size;
- unsigned int n = size / (sizeof(T)*8);
- unsigned int r = size % (sizeof(T)*8);
- if (r != 0)
- n++;
- set_ = std::vector<T>(n, static_cast<T>(0));
-}
-
-
-template<typename T>
-void BoolSet<T>::set(unsigned int i) {
- assert(i < size_ && i >= 0);
- unsigned int n = i / (sizeof(T)*8);
- unsigned int r = i % (sizeof(T)*8);
-
- T t = static_cast<T>(1) << r;
- set_[n] |= t;
-}
-
-
-template<typename T>
-void BoolSet<T>::unset(unsigned int i) {
- assert(i < size_ && i >= 0);
- unsigned int n = i / (sizeof(T)*8);
- unsigned int r = i % (sizeof(T)*8);
-
- T t = static_cast<T>(1) << r;
- t = ~t;
- set_[n] &= t;
-}
-
-
-template<typename T>
-void BoolSet<T>::set_all() {
- unsigned int r = size_ % (sizeof(T)*8);
- if (r == 0) {
- for (unsigned int i = 0; i < set_.size(); i++)
- set_[i] = ~static_cast<T>(0);
- }
- else {
- for (unsigned int i = 0; i < set_.size()-1; i++)
- set_[i] = ~static_cast<T>(0);
- set_[set_.size()-1] = static_cast<T>(0);
- T t = static_cast<T>(1);
- for (unsigned int i = 0; i < r; i++) {
- set_[set_.size()-1] |= t;
- t = t<<1;
- }
- }
-}
-
-
-template<typename T>
-void BoolSet<T>::unset_all() {
- for (unsigned int i = 0; i < set_.size(); i++)
- set_[i] = static_cast<T>(0);
-}
-
-
-template<typename T>
-bool BoolSet<T>::get(unsigned int i) const {
- assert(i < size_ && i >= 0);
- unsigned int n = i / (sizeof(T)*8);
- unsigned int r = i % (sizeof(T)*8);
-
- T t = static_cast<T>(1) << r;
- t = set_[n] & t;
- if (t)
- return true;
- else
- return false;
-}
-
-
-template<typename T>
-unsigned int BoolSet<T>::num_elem() const {
- unsigned int n = size_;
- unsigned int c = 0;
- unsigned int p = 0;
- while (n != 0) {
- unsigned int m;
- if (n >= sizeof(T)*8) {
- m = sizeof(T)*8;
- n -= sizeof(T)*8;
- }
- else {
- m = n;
- n = 0;
- }
-
- T v = set_[p++];
- if (v != static_cast<T>(0)) {
- for (unsigned int i = 0; i < m; i++) {
- if (v & static_cast<T>(1))
- c++;
- v >>= 1;
- }
- }
- }
-
- return c;
-}
-
-
-template<typename T>
-bool BoolSet<T>::imply(const BoolSet<T> &b) const {
- if (size_ >= b.size_) {
- for (unsigned int i = 0; i < b.set_.size(); i++)
- if ((set_[i] & b.set_[i]) != b.set_[i])
- return false;
- }
- else {
- for (unsigned int i = 0; i < set_.size(); i++)
- if ((set_[i] & b.set_[i]) != b.set_[i])
- return false;
- for (unsigned int i = set_.size(); i < b.set_.size(); i++)
- if (b.set_[i] != static_cast<T>(0))
- return false;
- }
-
- return true;
-}
-
-
-template<typename T>
-bool BoolSet<T>::empty() const {
- for (int i = 0; i < set_.size(); i++)
- if (set_[i] != static_cast<T>(0))
- return false;
-
- return true;
-}
-
-
-template<typename T>
-void BoolSet<T>::dump() const {
- int j = 1;
- for (unsigned int i = 0; i < size(); i++) {
- if (get(i))
- std::cout << '1';
- else
- std::cout << '0';
- if (j%10 == 0 && i != size() - 1) {
- std::cout << ' ';
- j = 1;
- }
- else
- j++;
- }
- std::cout << std::endl;
- std::cout.flush();
-}
-
-
-template<typename T>
-BoolSet<T> operator|(const BoolSet<T> &a, const BoolSet<T> &b) {
- if (a.size_ >= b.size_) {
- BoolSet<T> c = a;
- for (unsigned int i = 0; i < b.set_.size(); i++)
- c.set_[i] |= b.set_[i];
- return c;
- }
- else {
- BoolSet<T> c = b;
- for (unsigned int i = 0; i < a.set_.size(); i++)
- c.set_[i] |= a.set_[i];
- return c;
- }
-}
-
-
-template<typename T>
-BoolSet<T> operator&(const BoolSet<T> &a, const BoolSet<T> &b) {
- if (a.size_ >= b.size_) {
- BoolSet<T> c = a;
- for (unsigned int i = 0; i < b.set_.size(); i++)
- c.set_[i] &= b.set_[i];
- for (unsigned int i = b.set_.size(); i < a.set_.size(); i++)
- c.set_[i] = static_cast<T>(0);
- return c;
- }
- else {
- BoolSet<T> c = b;
- for (unsigned int i = 0; i < a.set_.size(); i++)
- c.set_[i] &= a.set_[i];
- for (unsigned int i = a.set_.size(); i < b.set_.size(); i++)
- c.set_[i] = static_cast<T>(0);
- return c;
- }
-}
-
-
-template<typename T>
-BoolSet<T> operator-(const BoolSet<T> &a, const BoolSet<T> &b) {
- BoolSet<T> c(a.size_);
-
- int sz = a.set_.size();
- if (sz > b.set_.size())
- sz = b.set_.size();
- for (int i = 0; i < sz; i++)
- c.set_[i] = a.set_[i] ^ (a.set_[i] & b.set_[i]);
- for (int i = sz; i < a.set_.size(); i++)
- c.set_[i] = a.set_[i];
-
- return c;
-}
-
-
-template<typename T>
-BoolSet<T> operator~(const BoolSet<T> &b) {
- unsigned int r = b.size_ % (sizeof(T)*8);
- BoolSet<T> a(b.size_);
- for (unsigned int i = 0; i < b.set_.size(); i++)
- a.set_[i] = ~b.set_[i];
-
- if (r != 0) {
- T t = static_cast<T>(1);
- for (unsigned int i = 1; i < r; i++)
- t = (t << 1) | static_cast<T>(1);
- a.set_[a.set_.size()-1] &= t;
- }
- return a;
-}
-
-
-template<typename T>
-bool operator==(const BoolSet<T> &a, const BoolSet<T> &b) {
- return (a.size_ == b.size_) && (a.set_ == b.set_);
-}
-
-
-template<typename T>
-bool operator!=(const BoolSet<T> &a, const BoolSet<T> &b) {
- return !(a == b);
-}
-
-
-
-template<typename T>
-BoolSet<T> & BoolSet<T>::operator|=(const BoolSet<T> &b) {
- *this = *this | b;
- return *this;
-}
-
-
-template<typename T>
-BoolSet<T> & BoolSet<T>::operator&=(const BoolSet<T> &b) {
- *this = *this & b;
- return *this;
-}
-
-
-template<typename T>
-BoolSet<T> & BoolSet<T>::operator-=(const BoolSet<T> &b) {
- *this = *this - b;
- return *this;
-}
-
-
-template<typename T>
-std::ostream& operator<<(std::ostream &os, const BoolSet<T> &b) {
- os << '{';
- for (typename BoolSet<T>::const_iterator i = b.begin(); i != b.end(); i++) {
- os << *i;
- if (i+1 != b.end())
- os << ',';
- }
- os << '}';
-
- return os;
-}
-
-
-template<typename T>
-bool operator<(const BoolSet<T> &a, const BoolSet<T> &b) {
- unsigned int t1, t2;
- t1 = a.num_elem();
- t2 = b.num_elem();
- if (t1 < t2)
- return true;
- else if (t1 > t2)
- return false;
- else {
- t1 = a.size();
- t2 = b.size();
- if (t1 < t2)
- return true;
- else if (t1 > t2)
- return false;
- else
- for (unsigned int i = 0; i < a.set_.size(); i++)
- if (a.set_[i] < b.set_[i])
- return true;
- }
- return false;
-}
-
-
-//
-// iterator for BoolSet
-//
-
-template<typename T>
-typename BoolSet<T>::iterator BoolSet<T>::begin() {
- typename BoolSet<T>::iterator it(this, 0);
- if (size_ == 0)
- return it;
- else if (set_[0] & static_cast<T>(1))
- return it;
- else
- return ++it;
-}
-
-
-template<typename T>
-typename BoolSet<T>::iterator BoolSet<T>::end() {
- return typename BoolSet<T>::iterator(this, size_);
-}
-
-
-template<typename T>
-typename BoolSet<T>::const_iterator BoolSet<T>::begin() const {
- typename BoolSet<T>::const_iterator it(this, 0);
- if (size_ == 0)
- return it;
- else if (set_[0] & static_cast<T>(1))
- return it;
- else
- return ++it;
-}
-
-
-template<typename T>
-typename BoolSet<T>::const_iterator BoolSet<T>::end() const {
- return typename BoolSet<T>::const_iterator(this, size_);
-}
-
-
-template<typename T>
-class BoolSet<T>::iterator: public std::iterator<std::forward_iterator_tag, T> {
-protected:
- BoolSet<T> *s_;
- unsigned int pos_;
-
-protected:
- iterator(BoolSet<T> *s, unsigned int pos) { s_ = s; pos_ = pos; }
-
-public:
- ~iterator() {}
-
- typename BoolSet<T>::iterator &operator++();
- typename BoolSet<T>::iterator operator++(int);
- typename BoolSet<T>::iterator operator+(int) const;
- unsigned int operator*() const;
- bool operator==(const BoolSet<T>::iterator &) const;
- bool operator!=(const BoolSet<T>::iterator &) const;
- operator typename BoolSet<T>::const_iterator();
-
- friend class BoolSet<T>;
-};
-
-
-template<typename T>
-typename BoolSet<T>::iterator &BoolSet<T>::iterator::operator++() {
- assert(pos_ < s_->size_);
-
- pos_++;
- unsigned int n = pos_ / (sizeof(T)*8);
- unsigned int r = pos_ % (sizeof(T)*8);
- while (pos_ < s_->size_) {
- if (s_->set_[n] == static_cast<T>(0)) {
- pos_ += sizeof(T)*8-r;
- n++;
- r = 0;
- if (pos_ >= s_->size_)
- break;
- }
-
- if (r == 0) {
- while (pos_ < s_->size_) {
- if (s_->set_[n] == static_cast<T>(0)) {
- pos_ += sizeof(T)*8;
- n++;
- }
- else
- break;
- }
- if (pos_ >= s_->size_)
- break;
- }
-
- for (unsigned int i = r; i < sizeof(T)*8; i++)
- if (s_->set_[n] & static_cast<T>(1) << i) {
- pos_ = pos_+i-r;
- return *this;
- }
-
- pos_ += sizeof(T)*8-r;
- n++;
- r = 0;
- }
-
- pos_ = s_->size_;
- return *this;
-}
-
-
-template<typename T>
-typename BoolSet<T>::iterator BoolSet<T>::iterator::operator++(int) {
- typename BoolSet<T>::iterator it(*this);
- ++(*this);
- return it;
-}
-
-
-template<typename T>
-typename BoolSet<T>::iterator BoolSet<T>::iterator::operator+(int n) const {
- assert(n >= 0);
- typename BoolSet<T>::iterator it(*this);
- while (n > 0) {
- ++it;
- --n;
- }
- return it;
-}
-
-
-template<typename T>
-unsigned int BoolSet<T>::iterator::operator*() const {
- assert(pos_ < s_->size_);
- return pos_;
-}
-
-
-template<typename T>
-bool BoolSet<T>::iterator::operator==(const BoolSet<T>::iterator &other) const {
- return s_ == other.s_ && pos_ == other.pos_;
-}
-
-
-template<typename T>
-bool BoolSet<T>::iterator::operator!=(const BoolSet<T>::iterator &other) const {
- return !((*this) == other);
-}
-
-
-template<typename T>
-BoolSet<T>::iterator::operator typename BoolSet<T>::const_iterator() {
- return BoolSet<T>::const_iterator(s_, pos_);
-}
-
-
-template<typename T>
-class BoolSet<T>::const_iterator: public std::iterator<std::forward_iterator_tag, T> {
-protected:
- const BoolSet<T> *s_;
- unsigned int pos_;
-
-protected:
- const_iterator(const BoolSet<T> *s, unsigned int pos) { s_ = s; pos_ = pos; }
-
-public:
- ~const_iterator() {}
-
- typename BoolSet<T>::const_iterator &operator++();
- typename BoolSet<T>::const_iterator operator++(int);
- typename BoolSet<T>::const_iterator operator+(int) const;
- unsigned int operator*() const;
- bool operator==(const BoolSet<T>::const_iterator &) const;
- bool operator!=(const BoolSet<T>::const_iterator &) const;
-
- friend class BoolSet<T>;
-};
-
-
-template<typename T>
-typename BoolSet<T>::const_iterator &BoolSet<T>::const_iterator::operator++() {
- assert(pos_ < s_->size_);
-
- pos_++;
- unsigned int n = pos_ / (sizeof(T)*8);
- unsigned int r = pos_ % (sizeof(T)*8);
- while (pos_ < s_->size_) {
- if (s_->set_[n] == static_cast<T>(0)) {
- pos_ += sizeof(T)*8-r;
- n++;
- r = 0;
- if (pos_ >= s_->size_)
- break;
- }
-
- if (r == 0) {
- while (pos_ < s_->size_) {
- if (s_->set_[n] == static_cast<T>(0)) {
- pos_ += sizeof(T)*8;
- n++;
- }
- else
- break;
- }
- if (pos_ >= s_->size_)
- break;
- }
-
- for (unsigned int i = r; i < sizeof(T)*8; i++)
- if (s_->set_[n] & static_cast<T>(1) << i) {
- pos_ = pos_+i-r;
- return *this;
- }
-
- pos_ += sizeof(T)*8-r;
- n++;
- r = 0;
- }
-
- pos_ = s_->size_;
- return *this;
-}
-
-
-template<typename T>
-typename BoolSet<T>::const_iterator BoolSet<T>::const_iterator::operator++(int) {
- typename BoolSet<T>::const_iterator it(*this);
- ++(*this);
- return it;
-}
-
-
-template<typename T>
-typename BoolSet<T>::const_iterator BoolSet<T>::const_iterator::operator+(int n) const {
- assert(n >= 0);
- typename BoolSet<T>::const_iterator it(*this);
- while (n > 0) {
- ++it;
- --n;
- }
- return it;
-}
-
-
-template<typename T>
-unsigned int BoolSet<T>::const_iterator::operator*() const {
- assert(pos_ < s_->size_);
- return pos_;
-}
-
-
-template<typename T>
-bool BoolSet<T>::const_iterator::operator==(const BoolSet<T>::const_iterator &other) const {
- return s_ == other.s_ && pos_ == other.pos_;
-}
-
-
-template<typename T>
-bool BoolSet<T>::const_iterator::operator!=(const BoolSet<T>::const_iterator &other) const {
- return !((*this) == other);
-}
-
-}
-
-#endif
generated by cgit v1.2.3-70-g09d2 (git 2.48.1) at 2025-02-08 18:26:39 +0000