Generated on Mon Nov 30 23:53:26 2009 for Gecode by doxygen 1.6.1

bitset.hpp

Go to the documentation of this file.
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-09-15 14:24:56 +0200 (Tue, 15 Sep 2009) $ by $Author: schulte $
00015  *     $Revision: 9748 $
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 Support {
00046 
00048   template<class A>
00049   class BitSet {
00051     A& a;
00053     typedef unsigned int Base;
00055     Base* data;
00057     int sz;
00059     static int base(int s);
00060   public:
00062     BitSet(A& a, int s);
00064     BitSet(A& a, const BitSet& bs);
00066     bool get(int i) const;
00068     void set(int i);
00070     void clear(int i);
00072     int size(void) const;
00073   };
00074 
00075 
00076   template<class A>
00077   forceinline int
00078   BitSet<A>::base(int s) {
00079     return static_cast<int>(std::ceil(static_cast<double>(s)
00080                                       /(CHAR_BIT*sizeof(Base))));
00081   }
00082 
00083   template<class A>
00084   forceinline
00085   BitSet<A>::BitSet(A& a0, int s)
00086     : a(a0), sz(s) {
00087     data = a.template alloc<Base>(base(sz));
00088     for (int i=base(sz); i--; ) data[i] = 0;
00089   }
00090 
00091   template<class A>
00092   forceinline
00093   BitSet<A>::BitSet(A& a0, const BitSet<A>& bs)
00094     : a(a0), data(a.template alloc<Base>(base(bs.sz))), sz(bs.sz) {
00095     for (int i = base(sz); i--; ) 
00096       data[i] = bs.data[i];
00097   }
00098 
00099   template<class A>
00100   forceinline bool
00101   BitSet<A>::get(int i) const {
00102     assert(i < sz);
00103     int pos = i / static_cast<int>(sizeof(Base)*CHAR_BIT);
00104     int bit = i % static_cast<int>(sizeof(Base)*CHAR_BIT);
00105     return (data[pos] & ((Base)1 << bit)) != 0;
00106   }
00107 
00108   template<class A>
00109   forceinline void
00110   BitSet<A>::set(int i) {
00111     assert(i < sz);
00112     int pos = i / static_cast<int>(sizeof(Base)*CHAR_BIT);
00113     int bit = i % static_cast<int>(sizeof(Base)*CHAR_BIT);
00114     data[pos] |= 1 << bit;
00115   }
00116 
00117   template<class A>
00118   forceinline void
00119   BitSet<A>::clear(int i) {
00120     assert(i < sz);
00121     int pos = i / static_cast<int>(sizeof(Base)*CHAR_BIT);
00122     int bit = i % static_cast<int>(sizeof(Base)*CHAR_BIT);
00123     data[pos] &= ~(1 << bit);
00124   }
00125 
00126   template<class A>
00127   forceinline int
00128   BitSet<A>::size(void) const {
00129     return sz;
00130   }
00131 
00132 }}
00133 
00134 // STATISTICS: support-any
00135