include/AD/contain/bitset.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef bit_set_h
  26 #define bit_set_h
  27
  28 //////////////////////////////////////////////////////////////////////////////
  29 //  BitSets allocated from a Mem.  Hmmm... perhaps this should be
  30 //  merged with class IntSet.  Oh well...
  31 //////////////////////////////////////////////////////////////////////////////
  32
  33 #include <new>
  34 #include <iostream>
  35 #include <AD/generic/generic.h>
  36 #include <AD/memory/mem.h>
  37
  38 class BitSet {
  39
  40 public:
  41    typedef unsigned long Blob; // We'll assume this is 32 bits
  42
  43    int  n;                     // size of array
  44    Blob set[1];                // the actual bitset
  45
  46    //////////////////////////////////////////////////////////////////////////
  47    //  Allocation/deallocation.  Notice that a BitSet must be created
  48    //  thru `operator new'.
  49    //////////////////////////////////////////////////////////////////////////
  50    inline void * operator new    (size_t sz, Mem& pool, int bits);
  51    inline void   operator delete (void *);
  52
  53    //////////////////////////////////////////////////////////////////////////
  54    //  Size of set
  55    //////////////////////////////////////////////////////////////////////////
  56    inline int    byte_len() const;  // size in bytes
  57    inline int    size()     const;  // size in bits
  58    inline int    count()    const;  // number of one bits
  59
  60    //////////////////////////////////////////////////////////////////////////
  61    //  Indexing
  62    //////////////////////////////////////////////////////////////////////////
  63    inline int    byte(int i) const;         // by byte
  64    inline Bool   operator [] (int i) const; // by bit
  65    inline Bool   contains (int i) const;    // by bit
  66
  67    //////////////////////////////////////////////////////////////////////////
  68    //  Insertion/deletion/set operations
  69    //////////////////////////////////////////////////////////////////////////
  70    inline void   add(int i);            // insert one bit
  71    inline Bool   add_if_changed(int i); // insert one bit, returns true if self is changed
  72    inline void   remove(int i);         // remove one bit
  73    inline void   clear();               // clear all bits
  74
  75    inline void   Union(const BitSet&);                // union with a set
  76    inline void   Union(const BitSet&, const BitSet&); // union two sets and assign
  77    inline Bool   Union_if_changed(const BitSet&);     // union with a set, returns true if self is changed
  78    inline void   copy (const BitSet&);
  79
  80    inline void   Intersect(const BitSet&);                // intersect with a set
  81    inline void   Intersect(const BitSet&, const BitSet&); // intersect two sets and assign
  82    inline void   Difference(const BitSet&);               // difference with a set
  83    inline void   complement();                            // complement self [ good boy, self ]
  84
  85    //////////////////////////////////////////////////////////////////////////
  86    //  Test for intersection and containment
  87    //////////////////////////////////////////////////////////////////////////
  88    inline Bool   intersects(const BitSet&);  // do we intersect with a set?
  89    inline Bool   contains(const BitSet&);    // do we contain a set?
  90
  91    //////////////////////////////////////////////////////////////////////////
  92    //  Equality and hashing
  93    //////////////////////////////////////////////////////////////////////////
  94    inline friend Bool equal(const BitSet *, const BitSet *);
  95    inline friend unsigned int hash (const BitSet *);
  96
  97    //////////////////////////////////////////////////////////////////////////
  98    //  Iterator macro for BitSet
  99    //////////////////////////////////////////////////////////////////////////
 100 #define foreach_bit(i,set) \
 101    for (i = (set).size() - 1; i >= 0; i--) if ((set)[i])
 102 #define foreach_bit_fast(i,S)                            \
 103    register const BitSet::Blob * _p_;                    \
 104    register int _i_, _j_;                                \
 105    register BitSet::Blob _mask_;                         \
 106    for (_p_ = (S).set + (S).n - 1,                       \
 107         _i_ = ((S).n - 1) * sizeof(BitSet::Blob) * 8;    \
 108         _i_ >= 0;                                        \
 109         _i_ -= sizeof(BitSet::Blob) * 8, _p_--)          \
 110       for (_mask_ = *_p_, _j_ = 0;                       \
 111            _mask_; _j_++, _mask_ >>= 1)                  \
 112          if ((_mask_ & 1) && ((i = _i_ + _j_) || 1))
 113
 114    //////////////////////////////////////////////////////////////////////////
 115    //  Printing
 116    //////////////////////////////////////////////////////////////////////////
 117    friend std::ostream& operator << (std::ostream&, const BitSet&);
 118 };
 119
 120 //////////////////////////////////////////////////////////////////////////////
 121 //  Implementation of all the inlined methods
 122 //////////////////////////////////////////////////////////////////////////////
 123
 124 //////////////////////////////////////////////////////////////////////////////
 125 //  Memory management
 126 //////////////////////////////////////////////////////////////////////////////
 127 inline void * BitSet::operator new (size_t sz, Mem& pool, int bits)
 128    { int blobs = (bits + sizeof(Blob)*8-1)/(sizeof(Blob)*8);
 129      BitSet * b = (BitSet*)pool.c_alloc(sz + (blobs - 1) * sizeof(Blob));
 130      b->n = blobs;
 131      return b;
 132    }
 133 inline void BitSet::operator delete (void *) {} // do nothing
 134
 135 //////////////////////////////////////////////////////////////////////////
 136 // Set operations; inline'd for a self deceiving sense of efficiency.
 137 //////////////////////////////////////////////////////////////////////////
 138 inline Bool BitSet::operator [] (int i) const
 139    { return set[i/(sizeof(Blob)*8)] & (1 << (i & (sizeof(Blob)*8-1))); }
 140 inline Bool BitSet::contains (int i) const
 141    { return set[i/(sizeof(Blob)*8)] & (1 << (i & (sizeof(Blob)*8-1))); }
 142 inline int  BitSet::size() const  { return n * sizeof(Blob) * 8; }
 143 inline int  BitSet::count() const
 144    { int m = 0; int i; foreach_bit_fast(i,*this) { m++; } return m; }
 145 inline void BitSet::add(int i)    { set[i/(sizeof(Blob)*8)] |= (1 << (i & (sizeof(Blob)*8-1))); }
 146 inline Bool BitSet::add_if_changed(int i) { return (*this)[i] ? false : (add(i), true); }
 147 inline void BitSet::remove(int i) { set[i/(sizeof(Blob)*8)] &= ~(1 << (i & (sizeof(Blob)*8-1))); }
 148 inline int  BitSet::byte_len()  const { return n * sizeof(Blob); }
 149 inline int  BitSet::byte(int i) const
 150    { return (set[i/sizeof(Blob)] >> ((i % sizeof(Blob)) * 8)) & 0xff; }
 151 inline void BitSet::clear()
 152    { for (register Blob * p = set, * q = p + n; p < q; *p++ = 0); }
 153
 154 inline void BitSet::copy(const BitSet& b)
 155    {  register Blob * p       = set;
 156       register Blob * q       = p + n;
 157       register const Blob * r = b.set;
 158       while (p < q) *p++ = *r++;
 159    }
 160
 161 inline void BitSet::Union(const BitSet& b)
 162    {  register Blob * p       = set;
 163       register Blob * q       = p + n;
 164       register const Blob * r = b.set;
 165       while (p < q) *p++ |= *r++;
 166    }
 167
 168 inline void BitSet::Union(const BitSet& a, const BitSet& b)
 169    {  register Blob * p       = set;
 170       register Blob * q       = p + n;
 171       register const Blob * r = a.set;
 172       register const Blob * s = b.set;
 173       while (p < q) *p++ = *r++ | *s++;
 174    }
 175
 176 inline Bool BitSet::Union_if_changed(const BitSet& b)
 177    {  Blob changed = 0;
 178       register Blob * p       = set;
 179       register Blob * q       = p + n;
 180       register const Blob * r = b.set;
 181       while (p < q) {
 182          changed |= ((~ *p) & *r);
 183          *p++ |= *r++;
 184       }
 185       return (Bool)changed;
 186    }
 187 inline void BitSet::Intersect(const BitSet& b)
 188    {  register Blob * p       = set;
 189       register Blob * q       = p + n;
 190       register const Blob * r = b.set;
 191       while (p < q) *p++ &= *r++;
 192    }
 193 inline void BitSet::Intersect(const BitSet& a, const BitSet& b)
 194    {  register Blob * p       = set;
 195       register Blob * q       = p + n;
 196       register const Blob * r = a.set;
 197       register const Blob * s = b.set;
 198       while (p < q) *p++ = *r++ & *s++;
 199    }
 200 inline void BitSet::Difference(const BitSet& b)
 201    {  register Blob * p       = set;
 202       register Blob * q       = p + n;
 203       register const Blob * r = b.set;
 204       while (p < q) *p++ &= ~*r++;
 205    }
 206 inline void BitSet::complement()
 207    { for (register Blob * p = set, * q = p + n; p < q; p++) *p = ~ *p; }
 208
 209 //////////////////////////////////////////////////////////////////////////
 210 //  Containment operations
 211 //////////////////////////////////////////////////////////////////////////
 212 inline Bool BitSet::intersects(const BitSet& b)
 213    { for (register const Blob * p = set, * q = p + n, * r = b.set; p < q;)
 214         if (*p++ & *r++) return true;
 215      return false;
 216    }
 217
 218 inline Bool BitSet::contains(const BitSet& b)
 219    { for (register const Blob * p = set, * q = p + n, * r = b.set; p < q;)
 220         if (~ *p++ & *r++) return false;
 221      return true;
 222    }
 223
 224 //////////////////////////////////////////////////////////////////////////
 225 // Comparison and hashing
 226 //////////////////////////////////////////////////////////////////////////
 227 inline Bool equal(const BitSet * a, const BitSet * b)
 228    {  for (register const BitSet::Blob * p = a->set, * q = p + a->n, * r = b->set;
 229            p < q; p++, r++)
 230          if (*p != *r) return false;
 231       return true;
 232    }
 233
 234 inline unsigned int hash (const BitSet * a)
 235    {  register unsigned int h = 4783;
 236       for (register const BitSet::Blob * p = a->set, * q = p + a->n; p < q; p++)
 237           h += *p;
 238       return h;
 239    }
 240
 241 #endif