From 210f77d2c32f14d2e99577fd3c9842bb19d47e50 Mon Sep 17 00:00:00 2001 From: Tuowen Zhao Date: Mon, 19 Sep 2016 21:14:58 +0000 Subject: Moved most modules into lib --- lib/omega/include/basic/BoolSet.h | 641 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 641 insertions(+) create mode 100755 lib/omega/include/basic/BoolSet.h (limited to 'lib/omega/include/basic/BoolSet.h') diff --git a/lib/omega/include/basic/BoolSet.h b/lib/omega/include/basic/BoolSet.h new file mode 100755 index 0000000..a78af2e --- /dev/null +++ b/lib/omega/include/basic/BoolSet.h @@ -0,0 +1,641 @@ +/***************************************************************************** + 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 +#include +#include +#include +#include + +namespace omega { + + //! BoolSet class, used as a set of integers from 0 to n-1 where n is a very small integer. +template +class BoolSet { +protected: + unsigned int size_; + std::vector 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 &) const; + bool empty() const; + void dump() const; + + BoolSet &operator|=(const BoolSet &); + BoolSet &operator&=(const BoolSet &); + BoolSet &operator-=(const BoolSet &); + + //! union + template friend BoolSet operator|(const BoolSet &, const BoolSet &); + //! intersection + template friend BoolSet operator&(const BoolSet &, const BoolSet &); + //! difference + template friend BoolSet operator-(const BoolSet &, const BoolSet &); + //! complement + template friend BoolSet operator~(const BoolSet &); + template friend bool operator==(const BoolSet &, const BoolSet &); + template friend bool operator!=(const BoolSet &, const BoolSet &); + template friend std::ostream& operator<<(std::ostream &, const BoolSet &); + template friend bool operator<(const BoolSet &, const BoolSet &); + +public: + class iterator; + class const_iterator; + iterator begin(); + iterator end(); + const_iterator begin() const; + const_iterator end() const; +}; + + +template +BoolSet::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(n, static_cast(0)); +} + + +template +void BoolSet::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(1) << r; + set_[n] |= t; +} + + +template +void BoolSet::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(1) << r; + t = ~t; + set_[n] &= t; +} + + +template +void BoolSet::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(0); + } + else { + for (unsigned int i = 0; i < set_.size()-1; i++) + set_[i] = ~static_cast(0); + set_[set_.size()-1] = static_cast(0); + T t = static_cast(1); + for (unsigned int i = 0; i < r; i++) { + set_[set_.size()-1] |= t; + t = t<<1; + } + } +} + + +template +void BoolSet::unset_all() { + for (unsigned int i = 0; i < set_.size(); i++) + set_[i] = static_cast(0); +} + + +template +bool BoolSet::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(1) << r; + t = set_[n] & t; + if (t) + return true; + else + return false; +} + + +template +unsigned int BoolSet::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(0)) { + for (unsigned int i = 0; i < m; i++) { + if (v & static_cast(1)) + c++; + v >>= 1; + } + } + } + + return c; +} + + +template +bool BoolSet::imply(const BoolSet &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(0)) + return false; + } + + return true; +} + + +template +bool BoolSet::empty() const { + for (int i = 0; i < set_.size(); i++) + if (set_[i] != static_cast(0)) + return false; + + return true; +} + + +template +void BoolSet::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 +BoolSet operator|(const BoolSet &a, const BoolSet &b) { + if (a.size_ >= b.size_) { + BoolSet c = a; + for (unsigned int i = 0; i < b.set_.size(); i++) + c.set_[i] |= b.set_[i]; + return c; + } + else { + BoolSet c = b; + for (unsigned int i = 0; i < a.set_.size(); i++) + c.set_[i] |= a.set_[i]; + return c; + } +} + + +template +BoolSet operator&(const BoolSet &a, const BoolSet &b) { + if (a.size_ >= b.size_) { + BoolSet 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(0); + return c; + } + else { + BoolSet 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(0); + return c; + } +} + + +template +BoolSet operator-(const BoolSet &a, const BoolSet &b) { + BoolSet 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 +BoolSet operator~(const BoolSet &b) { + unsigned int r = b.size_ % (sizeof(T)*8); + BoolSet 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(1); + for (unsigned int i = 1; i < r; i++) + t = (t << 1) | static_cast(1); + a.set_[a.set_.size()-1] &= t; + } + return a; +} + + +template +bool operator==(const BoolSet &a, const BoolSet &b) { + return (a.size_ == b.size_) && (a.set_ == b.set_); +} + + +template +bool operator!=(const BoolSet &a, const BoolSet &b) { + return !(a == b); +} + + + +template +BoolSet & BoolSet::operator|=(const BoolSet &b) { + *this = *this | b; + return *this; +} + + +template +BoolSet & BoolSet::operator&=(const BoolSet &b) { + *this = *this & b; + return *this; +} + + +template +BoolSet & BoolSet::operator-=(const BoolSet &b) { + *this = *this - b; + return *this; +} + + +template +std::ostream& operator<<(std::ostream &os, const BoolSet &b) { + os << '{'; + for (typename BoolSet::const_iterator i = b.begin(); i != b.end(); i++) { + os << *i; + if (i+1 != b.end()) + os << ','; + } + os << '}'; + + return os; +} + + +template +bool operator<(const BoolSet &a, const BoolSet &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 BoolSet::iterator BoolSet::begin() { + typename BoolSet::iterator it(this, 0); + if (size_ == 0) + return it; + else if (set_[0] & static_cast(1)) + return it; + else + return ++it; +} + + +template +typename BoolSet::iterator BoolSet::end() { + return typename BoolSet::iterator(this, size_); +} + + +template +typename BoolSet::const_iterator BoolSet::begin() const { + typename BoolSet::const_iterator it(this, 0); + if (size_ == 0) + return it; + else if (set_[0] & static_cast(1)) + return it; + else + return ++it; +} + + +template +typename BoolSet::const_iterator BoolSet::end() const { + return typename BoolSet::const_iterator(this, size_); +} + + +template +class BoolSet::iterator: public std::iterator { +protected: + BoolSet *s_; + unsigned int pos_; + +protected: + iterator(BoolSet *s, unsigned int pos) { s_ = s; pos_ = pos; } + +public: + ~iterator() {} + + typename BoolSet::iterator &operator++(); + typename BoolSet::iterator operator++(int); + typename BoolSet::iterator operator+(int) const; + unsigned int operator*() const; + bool operator==(const BoolSet::iterator &) const; + bool operator!=(const BoolSet::iterator &) const; + operator typename BoolSet::const_iterator(); + + friend class BoolSet; +}; + + +template +typename BoolSet::iterator &BoolSet::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(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(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(1) << i) { + pos_ = pos_+i-r; + return *this; + } + + pos_ += sizeof(T)*8-r; + n++; + r = 0; + } + + pos_ = s_->size_; + return *this; +} + + +template +typename BoolSet::iterator BoolSet::iterator::operator++(int) { + typename BoolSet::iterator it(*this); + ++(*this); + return it; +} + + +template +typename BoolSet::iterator BoolSet::iterator::operator+(int n) const { + assert(n >= 0); + typename BoolSet::iterator it(*this); + while (n > 0) { + ++it; + --n; + } + return it; +} + + +template +unsigned int BoolSet::iterator::operator*() const { + assert(pos_ < s_->size_); + return pos_; +} + + +template +bool BoolSet::iterator::operator==(const BoolSet::iterator &other) const { + return s_ == other.s_ && pos_ == other.pos_; +} + + +template +bool BoolSet::iterator::operator!=(const BoolSet::iterator &other) const { + return !((*this) == other); +} + + +template +BoolSet::iterator::operator typename BoolSet::const_iterator() { + return BoolSet::const_iterator(s_, pos_); +} + + +template +class BoolSet::const_iterator: public std::iterator { +protected: + const BoolSet *s_; + unsigned int pos_; + +protected: + const_iterator(const BoolSet *s, unsigned int pos) { s_ = s; pos_ = pos; } + +public: + ~const_iterator() {} + + typename BoolSet::const_iterator &operator++(); + typename BoolSet::const_iterator operator++(int); + typename BoolSet::const_iterator operator+(int) const; + unsigned int operator*() const; + bool operator==(const BoolSet::const_iterator &) const; + bool operator!=(const BoolSet::const_iterator &) const; + + friend class BoolSet; +}; + + +template +typename BoolSet::const_iterator &BoolSet::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(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(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(1) << i) { + pos_ = pos_+i-r; + return *this; + } + + pos_ += sizeof(T)*8-r; + n++; + r = 0; + } + + pos_ = s_->size_; + return *this; +} + + +template +typename BoolSet::const_iterator BoolSet::const_iterator::operator++(int) { + typename BoolSet::const_iterator it(*this); + ++(*this); + return it; +} + + +template +typename BoolSet::const_iterator BoolSet::const_iterator::operator+(int n) const { + assert(n >= 0); + typename BoolSet::const_iterator it(*this); + while (n > 0) { + ++it; + --n; + } + return it; +} + + +template +unsigned int BoolSet::const_iterator::operator*() const { + assert(pos_ < s_->size_); + return pos_; +} + + +template +bool BoolSet::const_iterator::operator==(const BoolSet::const_iterator &other) const { + return s_ == other.s_ && pos_ == other.pos_; +} + + +template +bool BoolSet::const_iterator::operator!=(const BoolSet::const_iterator &other) const { + return !((*this) == other); +} + +} + +#endif -- cgit v1.2.3-70-g09d2