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