112 lines
2.9 KiB
Python
112 lines
2.9 KiB
Python
class IntSet:
|
|
def __init__(self, *bounds):
|
|
"""Bounds must be tuples of the form (a, b),
|
|
where integers a <= x < b are included in the set.
|
|
"""
|
|
|
|
if not bounds:
|
|
bounds = [0, 0]
|
|
|
|
self.bounds = list(bounds)
|
|
|
|
def simplify(self):
|
|
i = 0
|
|
while i < len(self.bounds) - 1:
|
|
if i % 2 == 0:
|
|
if self.bounds[i] >= self.bounds[i + 1]:
|
|
del self.bounds[i:i + 2]
|
|
else:
|
|
i += 1
|
|
else:
|
|
if self.bounds[i] >= self.bounds[i + 1]:
|
|
if self.bounds[i] >= self.bounds[i + 2]:
|
|
del self.bounds[i + 1:i + 3]
|
|
else:
|
|
del self.bounds[i:i + 2]
|
|
else:
|
|
i += 1
|
|
|
|
def __or__(self, other):
|
|
bounds = None
|
|
j = k = 0
|
|
|
|
while j < len(self.bounds) - 1 or k < len(other.bounds) - 1:
|
|
if k >= len(other.bounds) - 1:
|
|
a, b = self.bounds[j:j + 2]
|
|
j += 2
|
|
elif j >= len(self.bounds) - 1:
|
|
a, b = other.bounds[k:k + 2]
|
|
k += 2
|
|
elif self.bounds[j] < other.bounds[k]:
|
|
a, b = self.bounds[j:j + 2]
|
|
j += 2
|
|
else:
|
|
a, b = other.bounds[k:k + 2]
|
|
k += 2
|
|
|
|
if a >= b:
|
|
continue
|
|
|
|
if not bounds:
|
|
bounds = [a, b]
|
|
continue
|
|
|
|
e = bounds[-1]
|
|
|
|
if e >= a:
|
|
if e >= b:
|
|
continue
|
|
bounds[-1] = b
|
|
else:
|
|
bounds.append(a)
|
|
bounds.append(b)
|
|
|
|
if not bounds:
|
|
bounds = [0, 0]
|
|
|
|
new = IntSet()
|
|
new.bounds = bounds
|
|
return new
|
|
|
|
def __and__(self, other):
|
|
bounds = []
|
|
|
|
i = j = 0
|
|
while i < len(self.bounds) - 1 and j < len(other.bounds) - 1:
|
|
a, b = self.bounds[i:i + 2]
|
|
c, d = other.bounds[j:j + 2]
|
|
if b > c and a < d:
|
|
bounds.append(max(a, c))
|
|
bounds.append(min(b, d))
|
|
if b < d:
|
|
i += 2 # toss a b
|
|
else:
|
|
j += 2 # toss c d
|
|
|
|
new = IntSet()
|
|
new.bounds = bounds
|
|
new.simplify()
|
|
return new
|
|
|
|
def __eq__(self, other):
|
|
return self.bounds == other.bounds
|
|
|
|
def __iter__(self):
|
|
for a, b in self.pairs:
|
|
yield from range(a, b)
|
|
|
|
def __len__(self):
|
|
return sum(b - a if b > a else 0 for a, b in self.pairs)
|
|
|
|
def __lt__(self, other):
|
|
return len(self) < len(other)
|
|
|
|
@property
|
|
def pairs(self):
|
|
it = iter(self.bounds)
|
|
while True:
|
|
yield next(it), next(it)
|
|
|
|
def __repr__(self):
|
|
return 'U'.join('[{0},{1})'.format(a, b) for a, b in self.pairs)
|