-
Notifications
You must be signed in to change notification settings - Fork 1
/
IntervalTree.py
101 lines (73 loc) · 2.43 KB
/
IntervalTree.py
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
'''
Interval Tree implementation in Python
Copyright (C) 2010 Tyler Kahn
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, 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 General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <http://www.gnu.org/licenses/>.
'''
class IntervalTree:
def __init__(self, intervals):
self.top_node = self.divide_intervals(intervals)
def divide_intervals(self, intervals):
if not intervals:
return None
x_center = self.center(intervals)
s_center = []
s_left = []
s_right = []
for k in intervals:
if k.get_end() < x_center:
s_left.append(k)
elif k.get_begin() > x_center:
s_right.append(k)
else:
s_center.append(k)
return Node(x_center, s_center, self.divide_intervals(s_left), self.divide_intervals(s_right))
def center(self, intervals):
fs = sort_by_begin(intervals)
length = len(fs)
return fs[int(length/2)].get_begin()
def search(self, begin, end=None):
if end:
result = []
for j in xrange(begin, end+1):
for k in self.search(j):
result.append(k)
result = list(set(result))
return sort_by_begin(result)
else:
return self._search(self.top_node, begin, [])
def _search(self, node, point, result):
for k in node.s_center:
if k.get_begin() <= point <= k.get_end():
result.append(k)
if point < node.x_center and node.left_node:
for k in self._search(node.left_node, point, []):
result.append(k)
if point > node.x_center and node.right_node:
for k in self._search(node.right_node, point, []):
result.append(k)
return list(set(result))
class Interval:
def __init__(self, begin, end):
self.begin = begin
self.end = end
def get_begin(self):
return self.begin
def get_end(self):
return self.end
class Node:
def __init__(self, x_center, s_center, left_node, right_node):
self.x_center = x_center
self.s_center = sort_by_begin(s_center)
self.left_node = left_node
self.right_node = right_node
def sort_by_begin(intervals):
return sorted(intervals, key=lambda x: x.get_begin())