-
Notifications
You must be signed in to change notification settings - Fork 5
Expand file tree
/
Copy pathsegmentTree.py
More file actions
236 lines (199 loc) · 8.17 KB
/
Copy pathsegmentTree.py
File metadata and controls
236 lines (199 loc) · 8.17 KB
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
# -*- coding: utf-8 -*-
"""segmentTree.py
This module implements segment tree as described in:
https://en.wikipedia.org/wiki/Segment_tree
A segment tree also known as a statistic tree is a tree data structure used
for storing information about intervals, or segments. It allows querying
which of the stored segments contain a given point. It is, in principle, a
static structure; that is, it's a structure that cannot be modified once it's
built.
A segment tree for a set I of n intervals uses O(n log n) storage and can be
built in O(n log n) time. Segment trees support searching for all the intervals
that contain a query point in O(log n + k), k being the number of retrieved
intervals or segments.
"""
import math
class Interval():
def __init__(self, left_endpoint, right_endpoint, l_closed, r_closed):
self.left_endpoint = left_endpoint # float or int
self.right_endpoint = right_endpoint # float or int
self.left_closed = l_closed # bool, whether left enpoint is closed
self.right_closed = r_closed # bool, whether right enpoint is closed
def __repr__(self):
""" mathematical representation of an interval """
s = "{}, {}".format(self.left_endpoint, self.right_endpoint)
if self.left_closed:
left_bracket = '['
else:
left_bracket = '('
if self.right_closed:
right_bracket = ']'
else:
right_bracket = ')'
interval_string = left_bracket + s + right_bracket
return 'Interval({})'.format(interval_string)
def contains(self, another_interval):
""" check if this interval contains another_interval """
if another_interval.left_endpoint < self.left_endpoint:
return False
if another_interval.left_endpoint == self.left_endpoint:
if not self.left_closed and another_interval.left_closed:
return False
if another_interval.right_endpoint > self.right_endpoint:
return False
if another_interval.right_endpoint == self.right_endpoint:
if not self.right_closed and another_interval.right_closed:
return False
return True
def intersects(self, interval):
raise NotImplementedError('To do: implement intersection check')
class TreeNode():
def __init__(self, left_endpoint, right_endpoint, l_closed, r_closed):
self.left = None
self.right = None
intv = Interval(left_endpoint, right_endpoint, l_closed, r_closed)
self.interval = intv
self.left_endpoint = left_endpoint
self.right_endpoint = right_endpoint
self.left_closed = l_closed
self.right_closed = r_closed
self.subset = [] # the canonical subset of given intervals
def __repr__(self):
""" mathematical representation of the node's interval """
s = "{}, {}".format(self.left_endpoint, self.right_endpoint)
if self.left_closed:
left_bracket = '['
else:
left_bracket = '('
if self.right_closed:
right_bracket = ']'
else:
right_bracket = ')'
interval_string = left_bracket + s + right_bracket
return 'TreeNode({})'.format(interval_string)
def query(self, point):
""" return list of Interval objects containing point in the subtree """
point_interval = Interval(point, point, True, True)
# point is also a closed interval [p, p]
if not self.interval.contains(point_interval):
# this node's interval doesn't contain point
return []
found = []
for intv in self.subset:
found.append(intv)
# because intv contains the node's interval, which contains point
if self.left is not None:
for intv in self.left.query(point):
found.append(intv)
if self.right is not None:
for intv in self.right.query(point):
found.append(intv)
return found
class SegmentTree():
def __init__(self, intervals):
self.intervals = intervals
self.root = None
self.build_tree()
def query(self, point):
""" return list of all Interval objects containing point """
if self.root is None:
raise Exception('tree must be built first')
return self.root.query(point)
def build_tree(self):
""" Build segment tree from given intervals and return the root.
Takes O(n log(n)) time.
"""
intervals = self.intervals
# sort all endpoints and make intervals for leaf nodes
endpoints = []
for interval in intervals:
endpoints.append(interval.left_endpoint)
endpoints.append(interval.right_endpoint)
endpoints.append(float('inf'))
endpoints.append(float('-inf'))
endpoints.sort()
unique_endpoints = []
for i, ep in enumerate(endpoints):
if i + 1 < len(endpoints) and ep == endpoints[i + 1]:
continue
else:
unique_endpoints.append(ep)
# append tuples for making intervals:
# (left_endpoint, right_endpoint, l_closed, r_closed)
# if left_enpoint == right_endpoint: it represents a point
endpoints = unique_endpoints
elements = []
for i, ep in enumerate(endpoints):
if i == 0:
prev = ep
continue
elif i < len(endpoints) - 1:
elements.append((prev, ep, False, False))
elements.append((ep, ep, True, True))
prev = ep
else: # i == len(endpoints)-1
elements.append((prev, ep, False, False))
num_leaves = len(elements)
max_depth = int(math.log(num_leaves) / math.log(2)) + 1
num_last_leaves = 2 * (num_leaves - 2**(max_depth - 1))
# build tree from bottom to up
# make a queue for each depth
q = []
for i, elem in enumerate(elements):
if i < num_last_leaves:
if i % 2 == 0:
prev = elem
else:
left_node = TreeNode(*prev)
right_node = TreeNode(*elem)
node = TreeNode(prev[0], elem[1], prev[2], elem[3])
node.left = left_node
node.right = right_node
q.append(node)
else:
node = TreeNode(*elem)
q.append(node)
# while depth > 0
while len(q) > 1:
tmp_q = []
for i, node in enumerate(q):
if i % 2 == 0:
prev = node
else:
left_ep = prev.left_endpoint
right_ep = node.right_endpoint
l_closed = prev.left_closed
r_closed = node.right_closed
new_node = TreeNode(left_ep, right_ep, l_closed, r_closed)
new_node.left = prev
new_node.right = node
tmp_q.append(new_node)
q = tmp_q
self.root = q[0]
# add canonical subsets
for interval in intervals:
self._append_subset(self.root, interval)
return self.root
def _append_subset(self, node, interval):
"""Recursive function to add canonical subsets"""
if interval.contains(node.interval):
node.subset.append(interval)
return None
if node.left is not None:
self._append_subset(node.left, interval)
if node.right is not None:
self._append_subset(node.right, interval)
if __name__ == '__main__':
import random
intervals = []
for _ in range(10):
endpoints = []
endpoints.append(random.choice(list(range(100))))
endpoints.append(random.choice(list(range(100))))
l_closed = random.choice([False, True])
r_closed = random.choice([False, True])
intv = Interval(min(endpoints), max(endpoints), l_closed, r_closed)
intervals.append(intv)
print('intervals:', intervals)
seg_tree = SegmentTree(intervals)
print('intervals containing 34:', seg_tree.query(34))