source: trunk/third/rx/rx/rxbitset.c @ 10430

/*      Copyright (C) 1995, 1996 Tom Lord
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public License
 * along with this software; see the file COPYING.  If not, write to
 * the Free Software Foundation, 59 Temple Place - Suite 330, 
 * Boston, MA 02111-1307, USA. 
 */


/*
 * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
 */


#include "rxall.h"
#include "rxbitset.h"


#ifdef __STDC__
int
rx_bitset_is_equal (int size, rx_Bitset a, rx_Bitset b)
#else
int
rx_bitset_is_equal (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  RX_subset s;

  if (size == 0)
    return 1;

  s = b[0];
  b[0] = ~a[0];

  for (x = rx_bitset_numb_subsets(size) - 1; a[x] == b[x]; --x)
    ;

  b[0] = s;
  return !x && (s == a[0]);
}


#ifdef __STDC__
int
rx_bitset_is_subset (int size, rx_Bitset a, rx_Bitset b)
#else
int
rx_bitset_is_subset (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  x = rx_bitset_numb_subsets(size) - 1;
  while (x-- && ((a[x] & b[x]) == a[x]));
  return x == -1;
}


#ifdef __STDC__
int
rx_bitset_empty (int size, rx_Bitset set)
#else
int
rx_bitset_empty (size, set)
     int size;
     rx_Bitset set;
#endif
{
  int x;
  RX_subset s;
  s = set[0];
  set[0] = 1;
  for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x)
    ;
  set[0] = s;
  return !s;
}

#ifdef __STDC__
void
rx_bitset_null (int size, rx_Bitset b)
#else
void
rx_bitset_null (size, b)
     int size;
     rx_Bitset b;
#endif
{
  rx_bzero ((char *)b, rx_sizeof_bitset(size));
}


#ifdef __STDC__
void
rx_bitset_universe (int size, rx_Bitset b)
#else
void
rx_bitset_universe (size, b)
     int size;
     rx_Bitset b;
#endif
{
  int x = rx_bitset_numb_subsets (size);
  while (x--)
    *b++ = ~(RX_subset)0;
}


#ifdef __STDC__
void
rx_bitset_complement (int size, rx_Bitset b)
#else
void
rx_bitset_complement (size, b)
     int size;
     rx_Bitset b;
#endif
{
  int x = rx_bitset_numb_subsets (size);
  while (x--)
    {
      *b = ~*b;
      ++b;
    }
}


#ifdef __STDC__
void
rx_bitset_assign (int size, rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_assign (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] = b[x];
}


#ifdef __STDC__
void
rx_bitset_union (int size, rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_union (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] |= b[x];
}


#ifdef __STDC__
void
rx_bitset_intersection (int size,
                        rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_intersection (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] &= b[x];
}


#ifdef __STDC__
void
rx_bitset_difference (int size, rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_difference (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] &=  ~ b[x];
}


#ifdef __STDC__
void
rx_bitset_revdifference (int size,
                         rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_revdifference (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] = ~a[x] & b[x];
}

#ifdef __STDC__
void
rx_bitset_xor (int size, rx_Bitset a, rx_Bitset b)
#else
void
rx_bitset_xor (size, a, b)
     int size;
     rx_Bitset a;
     rx_Bitset b;
#endif
{
  int x;
  for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
    a[x] ^= b[x];
}


#ifdef __STDC__
unsigned long
rx_bitset_hash (int size, rx_Bitset b)
#else
unsigned long
rx_bitset_hash (size, b)
     int size;
     rx_Bitset b;
#endif
{
  int x;
  unsigned long answer;

  answer = 0;

  for (x = 0; x < size; ++x)
    {
      if (RX_bitset_member (b, x))
        answer += (answer << 3) + x;
    }
  return answer;
}


RX_subset rx_subset_singletons [RX_subset_bits] = 
{
  0x1,
  0x2,
  0x4,
  0x8,
  0x10,
  0x20,
  0x40,
  0x80,
  0x100,
  0x200,
  0x400,
  0x800,
  0x1000,
  0x2000,
  0x4000,
  0x8000,
  0x10000,
  0x20000,
  0x40000,
  0x80000,
  0x100000,
  0x200000,
  0x400000,
  0x800000,
  0x1000000,
  0x2000000,
  0x4000000,
  0x8000000,
  0x10000000,
  0x20000000,
  0x40000000,
  0x80000000
};


/* 
 * (define l (let loop ((x 0) (l '())) (if (eq? x 256) l (loop (+ x 1) (cons x l)))))
 * (define lb (map (lambda (n) (number->string n 2)) l))
 * (define lc (map string->list lb))
 * (define ln (map (lambda (l) (map (lambda (c) (if (eq? c #\1) 1 0)) l)) lc))
 * (define lt (map (lambda (l) (apply + l)) ln))
 */

static int char_pops[256] = 
{
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

#define RX_char_population(C) (char_pops[C])

#ifdef __STDC__
int
rx_bitset_population (int size, rx_Bitset a)
#else
int
rx_bitset_population (size, a)
     int size;
     rx_Bitset a;
#endif
{
  int x;
  int total;
  unsigned char s;

  if (size == 0)
    return 0;

  total = 0;
  x = sizeof (RX_subset) * rx_bitset_numb_subsets(size) - 1;
  while (x >= 0)
    {
      s = ((unsigned char *)a)[x];
      --x;
      total = total + RX_char_population (s);
    }
  return total;
}