| from rpython.rlib.rarithmetic import intmask
|
| from rpython.rlib.rbigint import SHIFT
|
|
|
|
|
| class Bitset(object):
|
| def __init__(self, ds=None):
|
| if ds is None: ds = []
|
| self.ds = ds
|
|
|
| def get(self, i):
|
| d = i // SHIFT
|
| j = i % SHIFT
|
| if d >= len(self.ds): return False
|
| return bool((self.ds[d] >> j) & 0x1)
|
| def set(self, i):
|
| d = i // SHIFT
|
| j = i % SHIFT
|
| while len(self.ds) <= d: self.ds.append(0x0)
|
| self.ds[d] |= 0x1 << j
|
|
|
| def any(self): return bool(len(self.ds))
|
|
|
| def intersect(self, other):
|
| stop = min(len(self.ds), len(other.ds))
|
| return Bitset([self.ds[i] & other.ds[i] for i in range(stop)])
|
|
|
| def union(self, other):
|
| if len(self.ds) > len(other.ds):
|
| smaller = other.ds
|
| rv = self.ds[:]
|
| else:
|
| smaller = self.ds
|
| rv = other.ds[:]
|
| for i, d in enumerate(smaller): rv[i] |= d
|
| return Bitset(rv)
|
|
|
| def bits(self):
|
| i = 0
|
| for d in self.ds:
|
| j = 0
|
| while d:
|
| if d & 0x1: yield i + j
|
| d >>= 1
|
| j += 1
|
| i += SHIFT
|