gecode » int » extensional
bitset.hpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Christian Schulte <schulte@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Mikael Lagerkvist, 2007
00011  *     Christian Schulte, 2007
00012  *
00013  *  Last modified:
00014  *     $Date: 2009-06-08 19:25:59 +0200 (Mon, 08 Jun 2009) $ by $Author: schulte $
00015  *     $Revision: 9219 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  Permission is hereby granted, free of charge, to any person obtaining
00022  *  a copy of this software and associated documentation files (the
00023  *  "Software"), to deal in the Software without restriction, including
00024  *  without limitation the rights to use, copy, modify, merge, publish,
00025  *  distribute, sublicense, and/or sell copies of the Software, and to
00026  *  permit persons to whom the Software is furnished to do so, subject to
00027  *  the following conditions:
00028  *
00029  *  The above copyright notice and this permission notice shall be
00030  *  included in all copies or substantial portions of the Software.
00031  *
00032  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00033  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00034  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00035  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00036  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00037  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00038  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00039  *
00040  */
00041 
00042 #include <climits>
00043 #include <cmath>
00044 
00045 namespace Gecode { namespace Int { namespace Extensional {
00046 
00048   class BitSet {
00050     typedef unsigned int Base;
00052     Base* data;
00054     unsigned int size;
00055   public:
00057     BitSet(void);
00059     BitSet(Space& home, unsigned int s, bool value = false);
00061     BitSet(Space& home, const BitSet& bs);
00063     void init(Space& home, unsigned int s, bool value=false);
00065     bool get(unsigned int i) const;
00067     void set(unsigned int i, bool value=true);
00068   };
00069 
00070   forceinline void
00071   BitSet::init(Space& home, unsigned int s, bool value) {
00072     size = static_cast<unsigned int>(std::ceil(static_cast<double>(s)
00073                                                /(CHAR_BIT*sizeof(Base))));
00074     data = home.alloc<Base>(size);
00075     Base ival = value ? ~0 : 0;
00076     for (unsigned int i = size; i--; ) data[i] = ival;
00077   }
00078 
00079   forceinline
00080   BitSet::BitSet(void) : data(NULL), size(0) {}
00081 
00082   forceinline
00083   BitSet::BitSet(Space& home, unsigned int s, bool value)
00084     : data(NULL), size(0) {
00085     init(home, s, value);
00086   }
00087   forceinline
00088   BitSet::BitSet(Space& home, const BitSet& bs)
00089     : data(home.alloc<Base>(bs.size)), size(bs.size) {
00090     for (unsigned int i = size; i--; ) data[i] = bs.data[i];
00091   }
00092   forceinline bool
00093   BitSet::get(unsigned int i) const {
00094     unsigned int pos = i / (sizeof(Base)*CHAR_BIT);
00095     unsigned int bit = i % (sizeof(Base)*CHAR_BIT);
00096     assert(pos < size);
00097     return (data[pos] & ((Base)1 << bit)) != 0;
00098   }
00099   forceinline void
00100   BitSet::set(unsigned int i, bool value) {
00101     unsigned int pos = i / (sizeof(Base)*CHAR_BIT);
00102     unsigned int bit = i % (sizeof(Base)*CHAR_BIT);
00103     assert(pos < size);
00104     if (value)
00105       data[pos] |= 1 << bit;
00106     else
00107       data[pos] &= ~(1 << bit);
00108   }
00109 
00110 }}}
00111 
00112 // STATISTICS: int-other
00113