include/AD/contain/variset.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 variable_length_integer_sets_h
  26 #define variable_length_integer_sets_h
  27
  28 ////////////////////////////////////////////////////////////////////////////
  29 //  Class VarIntSet is used to represent a set of positive integers
  30 //  from 0 to some ``small'' n.  The integer set can grow if necessary
  31 ////////////////////////////////////////////////////////////////////////////
  32
  33 #include <string.h>
  34 #include <stdlib.h>
  35 #include <AD/generic/generic.h>  // Generic definitions
  36
  37 class VarIntSet {
  38
  39    typedef unsigned long Glob;
  40
  41    Glob * array;    // A bit array representing the integer set
  42    size_t limit;    // The size of this array in 4-bytes glob
  43    size_t growth;   // Amount to grow when necessary
  44
  45    void grow(size_t new_limit);
  46
  47 public:
  48
  49    VarIntSet(size_t init_size = 0, size_t g = 8);
  50   ~VarIntSet();
  51
  52    ///////////////////////////////////////////////////////////////////////
  53    // Set operations
  54    ///////////////////////////////////////////////////////////////////////
  55    void clear () { memset(array,0,limit * sizeof(Glob)); }
  56    void setUnion (size_t i)
  57    {  register size_t index = i / (8 * sizeof(Glob));
  58       if (index >= limit)
  59          grow(index > limit + growth ? index : limit + growth);
  60       array[index] |= (1 << (i & (8 * sizeof(Glob) - 1)));
  61    }
  62    void setRemove (size_t i)
  63    {  register size_t index = i / (8 * sizeof(Glob));
  64       if (index >= limit)
  65          grow(index > limit + growth ? index : limit + growth);
  66       array[index] &= ~(1 << (i & (8 * sizeof(Glob) - 1)));
  67    }
  68    void setUnion   (const VarIntSet& a)
  69       {  if (a.limit >= limit) grow(a.limit);
  70          register long i;
  71          register Glob * p;
  72          register const Glob * q;
  73          for (i = limit - 1, p = array, q = a.array; i >= 0; i--)
  74             *p++ |= *q++;
  75       }
  76
  77    void setIntersection  (const VarIntSet& a)
  78       {  register long i;
  79          register Glob * p;
  80          register const Glob * q;
  81          for (i = (limit < a.limit ? limit : a.limit) - 1,
  82               p = array, q = a.array; i >= 0; i--)
  83             *p++ &= *q++;
  84       }
  85    void setDiff (const VarIntSet& a)
  86       {  register long i;
  87          register Glob * p;
  88          register const Glob * q;
  89          for (i = (limit < a.limit ? limit : a.limit) - 1,
  90               p = array, q = a.array; i >= 0; i--)
  91             *p++ &= ~ *q++;
  92       }
  93    Bool isDisjoint (const VarIntSet& a) const
  94       {  register long i;
  95          register const Glob * p, * q;
  96          for (i = (limit < a.limit ? limit : a.limit) - 1,
  97               p = array, q = a.array; i >= 0; i--)
  98             if (*p++ & *q++) return false;
  99          return true;
 100       }
 101
 102    ///////////////////////////////////////////////////////////////////////
 103    // Set membership and cardinality
 104    ///////////////////////////////////////////////////////////////////////
 105    Bool operator [] (size_t i) const
 106    {  register size_t index = i/(8*sizeof(Glob));
 107       return index < limit ?
 108          (array[index] & (1 << (i & (8 * sizeof(Glob)-1)))) : false;
 109    }
 110    size_t capacity() const { return limit * (8*sizeof(Glob)); }
 111
 112    ///////////////////////////////////////////////////////////////////////
 113    // Iteration
 114    ///////////////////////////////////////////////////////////////////////
 115    int next(int& i, int& j) const
 116    {  if (j == (8*sizeof(Glob))) goto next_glob;
 117       next:
 118          while ((array[i] & (1 << j)) == 0)
 119             if (++j == (8*sizeof(Glob))) goto next_glob;
 120          return i * (8*sizeof(Glob)) + j++;
 121       next_glob:
 122          while (array[i] == 0) { if (++i == (int)limit) return -1; }
 123          j = 0;
 124          goto next;
 125    }
 126 };
 127
 128 #endif