rx/rxbitset.c

   1 /*      Copyright (C) 1995, 1996 Tom Lord
   2  *
   3  * This program is free software; you can redistribute it and/or modify
   4  * it under the terms of the GNU Library General Public License as published by
   5  * the Free Software Foundation; either version 2, or (at your option)
   6  * any later version.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU Library General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Library General Public License
  14  * along with this software; see the file COPYING.  If not, write to
  15  * the Free Software Foundation, 59 Temple Place - Suite 330,
  16  * Boston, MA 02111-1307, USA.
  17  */
  18
  19 \f
  20 /*
  21  * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
  22  */
  23 \f
  24
  25 #include "rxall.h"
  26 #include "rxbitset.h"
  27
  28
  29 #ifdef __STDC__
  30 int
  31 rx_bitset_is_equal (int size, rx_Bitset a, rx_Bitset b)
  32 #else
  33 int
  34 rx_bitset_is_equal (size, a, b)
  35      int size;
  36      rx_Bitset a;
  37      rx_Bitset b;
  38 #endif
  39 {
  40   int x;
  41   RX_subset s;
  42
  43   if (size == 0)
  44     return 1;
  45
  46   s = b[0];
  47   b[0] = ~a[0];
  48
  49   for (x = rx_bitset_numb_subsets(size) - 1; a[x] == b[x]; --x)
  50     ;
  51
  52   b[0] = s;
  53   return !x && (s == a[0]);
  54 }
  55
  56
  57 #ifdef __STDC__
  58 int
  59 rx_bitset_is_subset (int size, rx_Bitset a, rx_Bitset b)
  60 #else
  61 int
  62 rx_bitset_is_subset (size, a, b)
  63      int size;
  64      rx_Bitset a;
  65      rx_Bitset b;
  66 #endif
  67 {
  68   int x;
  69   x = rx_bitset_numb_subsets(size) - 1;
  70   while (x-- && ((a[x] & b[x]) == a[x]));
  71   return x == -1;
  72 }
  73
  74
  75 #ifdef __STDC__
  76 int
  77 rx_bitset_empty (int size, rx_Bitset set)
  78 #else
  79 int
  80 rx_bitset_empty (size, set)
  81      int size;
  82      rx_Bitset set;
  83 #endif
  84 {
  85   int x;
  86   RX_subset s;
  87   s = set[0];
  88   set[0] = 1;
  89   for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x)
  90     ;
  91   set[0] = s;
  92   return !s;
  93 }
  94
  95 #ifdef __STDC__
  96 void
  97 rx_bitset_null (int size, rx_Bitset b)
  98 #else
  99 void
 100 rx_bitset_null (size, b)
 101      int size;
 102      rx_Bitset b;
 103 #endif
 104 {
 105   rx_bzero ((char *)b, rx_sizeof_bitset(size));
 106 }
 107
 108
 109 #ifdef __STDC__
 110 void
 111 rx_bitset_universe (int size, rx_Bitset b)
 112 #else
 113 void
 114 rx_bitset_universe (size, b)
 115      int size;
 116      rx_Bitset b;
 117 #endif
 118 {
 119   int x = rx_bitset_numb_subsets (size);
 120   while (x--)
 121     *b++ = ~(RX_subset)0;
 122 }
 123
 124
 125 #ifdef __STDC__
 126 void
 127 rx_bitset_complement (int size, rx_Bitset b)
 128 #else
 129 void
 130 rx_bitset_complement (size, b)
 131      int size;
 132      rx_Bitset b;
 133 #endif
 134 {
 135   int x = rx_bitset_numb_subsets (size);
 136   while (x--)
 137     {
 138       *b = ~*b;
 139       ++b;
 140     }
 141 }
 142
 143
 144 #ifdef __STDC__
 145 void
 146 rx_bitset_assign (int size, rx_Bitset a, rx_Bitset b)
 147 #else
 148 void
 149 rx_bitset_assign (size, a, b)
 150      int size;
 151      rx_Bitset a;
 152      rx_Bitset b;
 153 #endif
 154 {
 155   int x;
 156   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 157     a[x] = b[x];
 158 }
 159
 160
 161 #ifdef __STDC__
 162 void
 163 rx_bitset_union (int size, rx_Bitset a, rx_Bitset b)
 164 #else
 165 void
 166 rx_bitset_union (size, a, b)
 167      int size;
 168      rx_Bitset a;
 169      rx_Bitset b;
 170 #endif
 171 {
 172   int x;
 173   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 174     a[x] |= b[x];
 175 }
 176
 177
 178 #ifdef __STDC__
 179 void
 180 rx_bitset_intersection (int size,
 181                         rx_Bitset a, rx_Bitset b)
 182 #else
 183 void
 184 rx_bitset_intersection (size, a, b)
 185      int size;
 186      rx_Bitset a;
 187      rx_Bitset b;
 188 #endif
 189 {
 190   int x;
 191   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 192     a[x] &= b[x];
 193 }
 194
 195
 196 #ifdef __STDC__
 197 void
 198 rx_bitset_difference (int size, rx_Bitset a, rx_Bitset b)
 199 #else
 200 void
 201 rx_bitset_difference (size, a, b)
 202      int size;
 203      rx_Bitset a;
 204      rx_Bitset b;
 205 #endif
 206 {
 207   int x;
 208   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 209     a[x] &=  ~ b[x];
 210 }
 211
 212
 213 #ifdef __STDC__
 214 void
 215 rx_bitset_revdifference (int size,
 216                          rx_Bitset a, rx_Bitset b)
 217 #else
 218 void
 219 rx_bitset_revdifference (size, a, b)
 220      int size;
 221      rx_Bitset a;
 222      rx_Bitset b;
 223 #endif
 224 {
 225   int x;
 226   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 227     a[x] = ~a[x] & b[x];
 228 }
 229
 230 #ifdef __STDC__
 231 void
 232 rx_bitset_xor (int size, rx_Bitset a, rx_Bitset b)
 233 #else
 234 void
 235 rx_bitset_xor (size, a, b)
 236      int size;
 237      rx_Bitset a;
 238      rx_Bitset b;
 239 #endif
 240 {
 241   int x;
 242   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 243     a[x] ^= b[x];
 244 }
 245
 246
 247 #ifdef __STDC__
 248 unsigned long
 249 rx_bitset_hash (int size, rx_Bitset b)
 250 #else
 251 unsigned long
 252 rx_bitset_hash (size, b)
 253      int size;
 254      rx_Bitset b;
 255 #endif
 256 {
 257   int x;
 258   unsigned long answer;
 259
 260   answer = 0;
 261
 262   for (x = 0; x < size; ++x)
 263     {
 264       if (RX_bitset_member (b, x))
 265         answer += (answer << 3) + x;
 266     }
 267   return answer;
 268 }
 269
 270
 271 RX_subset rx_subset_singletons [RX_subset_bits] =
 272 {
 273   0x1,
 274   0x2,
 275   0x4,
 276   0x8,
 277   0x10,
 278   0x20,
 279   0x40,
 280   0x80,
 281   0x100,
 282   0x200,
 283   0x400,
 284   0x800,
 285   0x1000,
 286   0x2000,
 287   0x4000,
 288   0x8000,
 289   0x10000,
 290   0x20000,
 291   0x40000,
 292   0x80000,
 293   0x100000,
 294   0x200000,
 295   0x400000,
 296   0x800000,
 297   0x1000000,
 298   0x2000000,
 299   0x4000000,
 300   0x8000000,
 301   0x10000000,
 302   0x20000000,
 303   0x40000000,
 304   0x80000000
 305 };
 306
 307
 308 /*
 309  * (define l (let loop ((x 0) (l '())) (if (eq? x 256) l (loop (+ x 1) (cons x l)))))
 310  * (define lb (map (lambda (n) (number->string n 2)) l))
 311  * (define lc (map string->list lb))
 312  * (define ln (map (lambda (l) (map (lambda (c) (if (eq? c #\1) 1 0)) l)) lc))
 313  * (define lt (map (lambda (l) (apply + l)) ln))
 314  */
 315
 316 static int char_pops[256] =
 317 {
 318   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
 319   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 320   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 321   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 322   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 323   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 324   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 325   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 326   1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
 327   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 328   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 329   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 330   2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
 331   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 332   3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
 333   4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
 334 };
 335
 336 #define RX_char_population(C) (char_pops[C])
 337
 338 #ifdef __STDC__
 339 int
 340 rx_bitset_population (int size, rx_Bitset a)
 341 #else
 342 int
 343 rx_bitset_population (size, a)
 344      int size;
 345      rx_Bitset a;
 346 #endif
 347 {
 348   int x;
 349   int total;
 350   unsigned char s;
 351
 352   if (size == 0)
 353     return 0;
 354
 355   total = 0;
 356   x = sizeof (RX_subset) * rx_bitset_numb_subsets(size) - 1;
 357   while (x >= 0)
 358     {
 359       s = ((unsigned char *)a)[x];
 360       --x;
 361       total = total + RX_char_population (s);
 362     }
 363   return total;
 364 }