1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
INFINITY = float('inf')
NEGATIVE_INFINITY = -INFINITY
class IntervalSet(object):
__slots__ = ('intervals', 'size')
def __init__(self, intervals, disjoint=False):
self.intervals = intervals
if not disjoint:
self.intervals = union_overlapping(self.intervals)
self.size = sum(i.size for i in self.intervals)
def __repr__(self):
return repr(self.intervals)
def __eq__(self, other):
return self.intervals == other.intervals
def __iter__(self):
return iter(self.intervals)
def __bool__(self):
return self.size != 0
__nonzero__ = __bool__ # python 2
def __sub__(self, other):
return self.intersect(other.complement())
def complement(self):
complementary = []
cursor = NEGATIVE_INFINITY
for interval in self.intervals:
if cursor < interval.start:
complementary.append(Interval(cursor, interval.start))
cursor = interval.end
if cursor < INFINITY:
complementary.append(Interval(cursor, INFINITY))
return IntervalSet(complementary, disjoint=True)
def intersect(self, other):
# XXX The last major bottleneck. Factorial-time hell.
# Then again, this function is entirely unused...
if not self or not other:
return IntervalSet([])
intersections = [x for x in (i.intersect(j)
for i in self.intervals
for j in other.intervals)
if x]
return IntervalSet(intersections, disjoint=True)
def intersect_interval(self, interval):
intersections = [x for x in (i.intersect(interval)
for i in self.intervals)
if x]
return IntervalSet(intersections, disjoint=True)
def union(self, other):
return IntervalSet(sorted(self.intervals + other.intervals))
class Interval(object):
__slots__ = ('start', 'end', 'tuple', 'size')
def __init__(self, start, end):
if end - start < 0:
raise ValueError("Invalid interval start=%s end=%s" % (start, end))
self.start = start
self.end = end
self.tuple = (start, end)
self.size = self.end - self.start
def __eq__(self, other):
return self.tuple == other.tuple
def __hash__(self):
return hash(self.tuple)
def __lt__(self, other):
return (self.start < other.start) - (self.start > other.start)
def __len__(self):
raise TypeError("len() doesn't support infinite values, use the "
"'size' attribute instead")
def __bool__(self):
return self.size != 0
__nonzero__ = __bool__ # python 2
def __repr__(self):
return '<Interval: %s>' % str(self.tuple)
def intersect(self, other):
start = max(self.start, other.start)
end = min(self.end, other.end)
if end > start:
return Interval(start, end)
def overlaps(self, other):
earlier = self if self.start <= other.start else other
later = self if earlier is other else other
return earlier.end >= later.start
def union(self, other):
if not self.overlaps(other):
raise TypeError("Union of disjoint intervals is not an interval")
start = min(self.start, other.start)
end = max(self.end, other.end)
return Interval(start, end)
def union_overlapping(intervals):
"""Union any overlapping intervals in the given set."""
disjoint_intervals = []
for interval in intervals:
if disjoint_intervals and disjoint_intervals[-1].overlaps(interval):
disjoint_intervals[-1] = disjoint_intervals[-1].union(interval)
else:
disjoint_intervals.append(interval)
return disjoint_intervals
|
