include/AD/contain/fbitset.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 faster_bit_set_h
  26 #define faster_bit_set_h
  27
  28 //////////////////////////////////////////////////////////////////////////////
  29 //  Faster bitsets which changes its internal representation according
  30 //  to need.
  31 //////////////////////////////////////////////////////////////////////////////
  32 #include <string.h>
  33 #include <AD/contain/bitset.h>
  34
  35 class ostream;
  36
  37 class FastBitSet {
  38 protected:
  39    Mem& mem;
  40    enum { EMPTY, SINGLETON, SPARSE, DENSE } kind;
  41    enum { MAX_SPARSE = 8 };
  42    int      capacity;   // maximum number of elements
  43    short *  sparse_set; // place to store the sparse set
  44    BitSet * dense_set;  // place to store the dense set
  45    union {
  46       int one_bit;      // place to store one bit
  47       int count;        // number of elements stored
  48    };
  49
  50 public:
  51
  52    class Iter
  53    {  const short  * cursor;
  54       int            index;
  55       const BitSet * bitset;
  56       union {
  57          short tmp[2];
  58          int   size;
  59       };
  60    public:
  61       inline Iter() : cursor(tmp) { tmp[0] = -1; }
  62       inline Iter(const Iter& i) { *this = i; }
  63       inline Iter(const FastBitSet& s);
  64       inline int next()
  65       {  if (cursor) return *cursor++;
  66          for (int i = index;i < size; i++)
  67             if (bitset->contains(i)) { index = i+1; return i; }
  68          return -1;
  69       }
  70    };
  71
  72    friend class Iter;
  73
  74 private:
  75
  76    void copy_sparse   (const FastBitSet&);
  77    void copy_dense    (const FastBitSet&);
  78    void init_sparse   (const FastBitSet&);
  79    void init_dense    (const FastBitSet&);
  80    void init_dense    (const BitSet&);
  81    void create_sparse (int bit);
  82    Bool add_sparse    (int bit);
  83    Bool find_sparse   (int bit) const;
  84    void basic_sparse_to_dense ();
  85    void sparse_to_dense ();
  86
  87 public:
  88    inline FastBitSet(Mem& m, int number_of_bits);
  89    inline FastBitSet(const FastBitSet& s);
  90
  91    inline int  size       ()        const { return capacity; }
  92    inline Bool contains   (int bit) const;
  93    inline Bool operator[] (int bit) const;
  94    inline void clear      ();
  95    inline void add        (int bit);
  96    inline int  first_bit  () const;
  97           void complement ();
  98           void Union      (const FastBitSet&);
  99    inline FastBitSet& operator = (const FastBitSet&);
 100
 101    friend ostream& operator << (ostream&, const FastBitSet&);
 102    inline friend unsigned int hash (const FastBitSet *);
 103    inline friend Bool equal (const FastBitSet *, const FastBitSet *);
 104 };
 105
 106 //////////////////////////////////////////////////////////////////////////////
 107 //
 108 //  Inlined member functions.
 109 //
 110 //////////////////////////////////////////////////////////////////////////////
 111 inline FastBitSet::Iter::Iter(const FastBitSet& s)
 112    {  switch (s.kind)
 113       {  case EMPTY:     tmp[0] = -1; cursor = tmp; break;
 114          case SINGLETON: tmp[0] = s.one_bit; tmp[1] = -1; cursor = tmp;
 115                          break;
 116          case SPARSE:    cursor = s.sparse_set; break;
 117          case DENSE:     cursor = 0; bitset = s.dense_set; index = 0;
 118                          size = bitset->size();
 119                          break;
 120       }
 121    }
 122
 123 inline FastBitSet::FastBitSet(Mem& m, int number_of_bits)
 124    : mem(m),
 125      kind(EMPTY),
 126      capacity(number_of_bits),
 127      sparse_set(0), dense_set(0)
 128      {}
 129
 130 inline FastBitSet::FastBitSet(const FastBitSet& s)
 131    : mem(s.mem), capacity(s.capacity), sparse_set(0), dense_set(0)
 132      {  switch (kind = s.kind)
 133         {  case SINGLETON:  one_bit = s.one_bit; break;
 134            case SPARSE:     init_sparse(s); break;
 135            case DENSE:      init_dense(s); break;
 136            case EMPTY:      break;
 137         }
 138      }
 139
 140 inline FastBitSet& FastBitSet::operator = (const FastBitSet& s)
 141 {  if (kind == s.kind)
 142    {  switch (kind)
 143       {  case SINGLETON:  one_bit = s.one_bit; break;
 144          case SPARSE:     copy_sparse(s); break;
 145          case DENSE:      copy_dense(s); break;
 146          case EMPTY:      break;
 147       }
 148    } else
 149    {  switch (kind = s.kind)
 150       {  case SINGLETON:  one_bit = s.one_bit; break;
 151          case SPARSE:     init_sparse(s); break;
 152          case DENSE:      init_dense(s);  break;
 153          case EMPTY:      break;
 154       }
 155    }
 156    return *this;
 157 }
 158
 159 inline Bool FastBitSet::contains (int bit) const
 160 {  switch (kind)
 161    {  case EMPTY:     return false;
 162       case SINGLETON: return bit == one_bit;
 163       case SPARSE:    return find_sparse(bit);
 164       default:        return dense_set->contains(bit);
 165    }
 166 }
 167
 168 inline Bool FastBitSet::operator[] (int bit) const { return contains(bit); }
 169
 170 inline void FastBitSet::add (int bit)
 171 {  switch (kind)
 172    {  case EMPTY:     { kind = SINGLETON; one_bit = bit; }
 173       case SINGLETON: if (bit != one_bit) create_sparse(bit);
 174                       break;
 175       case SPARSE:    add_sparse(bit); break;
 176       default:        dense_set->add(bit); break;
 177    }
 178 }
 179
 180 inline void FastBitSet::clear () { kind = EMPTY; }
 181
 182 inline unsigned hash (const FastBitSet * set)
 183 {  switch (set->kind)
 184    {  case FastBitSet::EMPTY:     return 257;
 185       case FastBitSet::SINGLETON: return 8 * set->one_bit;
 186       case FastBitSet::SPARSE:
 187       {  unsigned int h = 0;
 188          for (const short * p = set->sparse_set; *p >= 0; p++)
 189             h += *p;
 190          return h;
 191       }
 192       default:   return hash(set->dense_set);
 193    }
 194 }
 195
 196 inline Bool equal (const FastBitSet * a, const FastBitSet * b)
 197 {  if (a->kind != b->kind) return false;
 198    switch (a->kind)
 199    {  case FastBitSet::EMPTY:      return true;
 200       case FastBitSet::SINGLETON:  return a->one_bit == b->one_bit;
 201       case FastBitSet::SPARSE:
 202       {  const short * p, * q;
 203          for (p = a->sparse_set, q = b->sparse_set; ; p++, q++)
 204          {  if (*p != *q) return false;
 205             if (*p < 0)   return true;
 206          }
 207          return false;
 208       }
 209       default:  return equal(a->dense_set, b->dense_set);
 210    }
 211 }
 212
 213 inline int FastBitSet::first_bit () const
 214 {  switch (kind)
 215    {  case SINGLETON:  return one_bit;
 216       case SPARSE:     return sparse_set[0];
 217       case DENSE:
 218       {  for (int i = 0, j = dense_set->size(); i < j; i++)
 219             if (dense_set->contains(i)) return i;
 220       }
 221       default:         break;
 222    }
 223    return 32767*65536; // not found
 224 }
 225
 226 //////////////////////////////////////////////////////////////////////////////
 227 //
 228 //  Union
 229 //
 230 //////////////////////////////////////////////////////////////////////////////
 231 inline void FastBitSet::Union (const FastBitSet& f)
 232 {  if (this == &f) return;
 233    switch (kind)
 234    {  case EMPTY:     *this = f; break;
 235       case SINGLETON:
 236       {  switch (f.kind)
 237          {  case SINGLETON: if (one_bit != f.one_bit) create_sparse(f.one_bit);
 238                             break;
 239             case SPARSE:    { int b = one_bit; init_sparse(f); add_sparse(b);
 240                             }  break;
 241             case DENSE:     { int b = one_bit; init_dense(f); dense_set->add(b);
 242                             }  break;
 243             default:        break;
 244          }
 245       }  break;
 246       case SPARSE:
 247       {  switch (f.kind)
 248          {  case SINGLETON: add_sparse(f.one_bit); break;
 249             case SPARSE:
 250             {
 251                short buf[MAX_SPARSE*3];
 252                const short * p = sparse_set, * q = f.sparse_set;
 253                short * r = buf;
 254                while (1)
 255                {  if (*p < 0) { while (*q >= 0) *r++ = *q++; goto DONE; }
 256                   if (*q < 0) { while (*p >= 0) *r++ = *p++; goto DONE; }
 257                   if (*p == *q)     { *r++ = *p++; q++; }
 258                   else if (*p < *q) { *r++ = *p++; }
 259                   else              { *r++ = *q++; }
 260                }
 261                DONE:
 262                count = r - buf;
 263                if (count >= MAX_SPARSE)
 264                {  sparse_to_dense();
 265                   for (const short * pp = f.sparse_set; *pp >= 0; pp++)
 266                      dense_set->add(*pp);
 267                } else
 268                {  *r = -1;
 269                   memcpy(sparse_set,buf,sizeof(short)*(count+1));
 270                }
 271             }  break;
 272             case DENSE:
 273                sparse_to_dense(); dense_set->Union(*f.dense_set); break;
 274             default:        break;
 275          }
 276       }  break;
 277       default:
 278       {  switch (f.kind)
 279          {  case SINGLETON: dense_set->add(f.one_bit); break;
 280             case SPARSE:
 281             {  for (const short * p = f.sparse_set; *p >= 0; p++)
 282                   dense_set->add(*p);
 283             }  break;
 284             case DENSE:     dense_set->Union(*f.dense_set); break;
 285             default:         break;
 286          }
 287       }  break;
 288    }
 289 }
 290
 291 #endif