bit-set.hpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 namespace Gecode { namespace Int { namespace Extensional {
00039
00040 template<class IndexType>
00041 forceinline
00042 BitSet<IndexType>::BitSet(Space& home, unsigned int n)
00043 : _limit(static_cast<IndexType>(n)),
00044 index(home.alloc<IndexType>(n)),
00045 bits(home.alloc<BitSetData>(n)) {
00046
00047 for (IndexType i=_limit; i--; ) {
00048 bits[i].init(true);
00049 index[i] = i;
00050 }
00051 }
00052
00053 template<class IndexType>
00054 template<class OldIndexType>
00055 forceinline
00056 BitSet<IndexType>::BitSet(Space& home,
00057 const BitSet<OldIndexType>& bs)
00058 : _limit(bs._limit),
00059 index(home.alloc<IndexType>(_limit)),
00060 bits(home.alloc<BitSetData>(_limit)) {
00061 assert(_limit > 0U);
00062 for (IndexType i = _limit; i--; ) {
00063 bits[i] = bs.bits[i];
00064 index[i] = bs.index[i];
00065 }
00066 }
00067
00068 template<class IndexType>
00069 forceinline
00070 BitSet<IndexType>::BitSet(Space&, const TinyBitSet<1U>&) {
00071 GECODE_NEVER;
00072 }
00073 template<class IndexType>
00074 forceinline
00075 BitSet<IndexType>::BitSet(Space&, const TinyBitSet<2U>&) {
00076 GECODE_NEVER;
00077 }
00078 template<class IndexType>
00079 forceinline
00080 BitSet<IndexType>::BitSet(Space&, const TinyBitSet<3U>&) {
00081 GECODE_NEVER;
00082 }
00083 template<class IndexType>
00084 forceinline
00085 BitSet<IndexType>::BitSet(Space&, const TinyBitSet<4U>&) {
00086 GECODE_NEVER;
00087 }
00088
00089 template<class IndexType>
00090 forceinline void
00091 BitSet<IndexType>::replace_and_decrease(IndexType i, BitSetData w) {
00092 assert(_limit > 0U);
00093 BitSetData w_i = bits[i];
00094 if (w != w_i) {
00095 bits[i] = w;
00096 if (w.none()) {
00097 assert(bits[i].none());
00098 bits[i] = bits[_limit-1];
00099 index[i] = index[_limit-1];
00100 _limit--;
00101 }
00102 }
00103 }
00104
00105 template<class IndexType>
00106 forceinline void
00107 BitSet<IndexType>::clear_mask(BitSetData* mask) const {
00108 assert(_limit > 0U);
00109 for (IndexType i = _limit; i--; ) {
00110 mask[i].init(false);
00111 assert(mask[i].none());
00112 }
00113 }
00114
00115 template<class IndexType>
00116 forceinline void
00117 BitSet<IndexType>::add_to_mask(const BitSetData* b, BitSetData* mask) const {
00118 assert(_limit > 0U);
00119 for (IndexType i = _limit; i--; )
00120 mask[i] = BitSetData::o(mask[i],b[index[i]]);
00121 }
00122
00123 template<class IndexType>
00124 template<bool sparse>
00125 forceinline void
00126 BitSet<IndexType>::intersect_with_mask(const BitSetData* mask) {
00127 assert(_limit > 0U);
00128 if (sparse) {
00129 for (IndexType i = _limit; i--; ) {
00130 assert(!bits[i].none());
00131 BitSetData w_i = bits[i];
00132 BitSetData w_a = BitSetData::a(w_i, mask[index[i]]);
00133 replace_and_decrease(i,w_a);
00134 assert(i == _limit || !bits[i].none());
00135 }
00136 } else {
00137 for (IndexType i = _limit; i--; ) {
00138 assert(!bits[i].none());
00139 BitSetData w_i = bits[i];
00140 BitSetData w_a = BitSetData::a(w_i, mask[i]);
00141 replace_and_decrease(i,w_a);
00142 assert(i == _limit || !bits[i].none());
00143 }
00144 }
00145 }
00146
00147 template<class IndexType>
00148 forceinline void
00149 BitSet<IndexType>::intersect_with_masks(const BitSetData* a,
00150 const BitSetData* b) {
00151 assert(_limit > 0U);
00152 for (IndexType i = _limit; i--; ) {
00153 assert(!bits[i].none());
00154 BitSetData w_i = bits[i];
00155 IndexType offset = index[i];
00156 BitSetData w_o = BitSetData::o(a[offset], b[offset]);
00157 BitSetData w_a = BitSetData::a(w_i,w_o);
00158 replace_and_decrease(i,w_a);
00159 assert(i == _limit || !bits[i].none());
00160 }
00161 }
00162
00163 template<class IndexType>
00164 forceinline void
00165 BitSet<IndexType>::nand_with_mask(const BitSetData* b) {
00166 assert(_limit > 0U);
00167 for (IndexType i = _limit; i--; ) {
00168 assert(!bits[i].none());
00169 BitSetData w = BitSetData::a(bits[i],~(b[index[i]]));
00170 replace_and_decrease(i,w);
00171 assert(i == _limit || !bits[i].none());
00172 }
00173 }
00174
00175 template<class IndexType>
00176 forceinline bool
00177 BitSet<IndexType>::intersects(const BitSetData* b) const {
00178 for (IndexType i = _limit; i--; )
00179 if (!BitSetData::a(bits[i],b[index[i]]).none())
00180 return true;
00181 return false;
00182 }
00183
00184
00185 template<class IndexType>
00186 forceinline unsigned int
00187 BitSet<IndexType>::limit(void) const {
00188 return static_cast<unsigned int>(_limit);
00189 }
00190
00191 template<class IndexType>
00192 forceinline bool
00193 BitSet<IndexType>::empty(void) const {
00194 return _limit == 0U;
00195 }
00196
00197 template<class IndexType>
00198 forceinline unsigned int
00199 BitSet<IndexType>::words(void) const {
00200 return static_cast<unsigned int>(_limit);
00201 }
00202
00203 template<class IndexType>
00204 forceinline unsigned int
00205 BitSet<IndexType>::size(void) const {
00206 return words();
00207 }
00208
00209 template<class IndexType>
00210 forceinline unsigned int
00211 BitSet<IndexType>::width(void) const {
00212 assert(!empty());
00213 IndexType width = index[0];
00214 for (IndexType i = _limit; i--; ) {
00215 width = std::max(width,index[i]);
00216 }
00217 assert(static_cast<unsigned int>(width+1U) >= words());
00218 return static_cast<unsigned int>(width+1U);
00219 }
00220
00221 }}}
00222
00223