-
Notifications
You must be signed in to change notification settings - Fork 0
/
Coors2D.py
171 lines (135 loc) · 5.87 KB
/
Coors2D.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
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
from veb import *
from Node import NodeItem, Node
from xarray import XArray
from cache.memory import Memory
from Ors2D import ORS2D
import time
x_coord = lambda x: x[0]
y_coord = lambda x: x[1]
class COORS2D2Sided(object):
def __init__(self, memory, points, x_upper_bound=True, y_upper_bound=True):
assert len(points) > 0
self.memory = memory
self.x_upper_bound = x_upper_bound
self.y_upper_bound = y_upper_bound
# Points are stored in yveb sorted by y coordinate
self.points = sorted(points, key=y_coord)
node_items = [NodeItem(y, x) for x, y in points]
self.yveb = VEB2Sided(self.memory, node_items)
# Construct the xarray, must pass in pre-sorted (by y) points
self.alpha = 2
self.base_case_length = 10
self.xarray = XArray(self.memory, self.points, self.alpha, \
self.base_case_length, self.x_upper_bound, self.y_upper_bound)
# initialize xarray_index field in each Node2Sided object
self.link_nodes_to_xarray()
def link_nodes_to_xarray(self):
# iterate through yveb, uses hashmap to update self.xarray_index for each node
for node in self.yveb.veb_ordered_nodes:
node.xarray_index = self.xarray.y_to_xarray_chunk_map[node.key]
def query(self, x_bound, y_bound):
"""
Returns list of point tuples in closed query quadrant
Only supports points with distinct x values
"""
if self.y_upper_bound:
rep_node = self.yveb.successor(y_bound)
if rep_node is None:
rep_node = self.yveb.predecessor(y_bound)
else:
rep_node = self.yveb.predecessor(y_bound)
if rep_node is None:
rep_node = self.yveb.successor(y_bound)
solutions = []
if self.x_upper_bound:
prev_x = -float('inf')
else:
prev_x = float('inf')
for i in range(rep_node.xarray_index, len(self.xarray.xarray)):
point = self.xarray.xarray[i].read().key
if self.x_upper_bound and point[0] > x_bound:
break
if not self.x_upper_bound and point[0] < x_bound:
break
if self.x_upper_bound and point[0] <= prev_x:
continue
if not self.x_upper_bound and point[0] >= prev_x:
continue
prev_x = point[0]
if self.y_upper_bound and point[1] <= y_bound:
solutions.append(point)
self.memory.update_buffer()
if not self.y_upper_bound and point[1] >= y_bound:
solutions.append(point)
self.memory.update_buffer()
return solutions
class COORS2D3Sided(object):
def __init__(self, memory, points, y_upper_bound=True):
assert len(points) > 0
self.memory = memory
self.y_upper_bound = y_upper_bound
self.points = sorted(points, key=x_coord)
node_items = [NodeItem(x, y) for x, y in points]
self.xveb = VEB3Sided(memory, node_items)
self.link_nodes_to_2Sided()
def link_nodes_to_2Sided(self):
# store 2Sided structs on points in subtrees for every node in xveb
for node in self.xveb.veb_ordered_nodes:
points = [(v.key, v.data) for v in self.xveb.subtree(node, leaves=True)]
node.x_upper_struct = COORS2D2Sided(self.memory, points, \
x_upper_bound=True, y_upper_bound=self.y_upper_bound)
node.x_lower_struct = COORS2D2Sided(self.memory, points, \
x_upper_bound=False, y_upper_bound=self.y_upper_bound)
def query(self, x_min, x_max, y_bound):
assert x_min <= x_max
solutions = []
lca = self.xveb.fast_LCA(x_min, x_max)
if lca.is_leaf():
x, y = lca.point()
if x_min <= x <= x_max and (self.y_upper_bound and y <= y_bound \
or not self.y_upper_bound and y >= y_bound):
solutions.append(lca.point())
else:
solutions.extend(lca.left.x_lower_struct.query(x_min, y_bound))
solutions.extend(lca.right.x_upper_struct.query(x_max, y_bound))
return solutions
class COORS2D4Sided(ORS2D):
"""
We will use the natural O(n log^2 n) space implementation instead of
the O(n log^2 n / log log n) space implementation given in class
(query time bounds are the same)
"""
def __init__(self, memory, points):
assert len(points) > 0
self.memory = memory
self.points = sorted(points, key=y_coord)
node_items = [NodeItem(y, x) for x, y in points]
self.yveb = VEB4Sided(memory, node_items)
self.link_nodes_to_3Sided()
def link_nodes_to_3Sided(self):
counter = 0
target = 1
start_time = time.time()
for node in self.yveb.veb_ordered_nodes:
cur_time = time.time()
if counter == target:
target *= 2
print("Constructed %s nodes in %s time" % (counter, cur_time - start_time))
points = [(v.data, v.key) for v in self.yveb.subtree(node, leaves=True)]
node.y_upper_struct = COORS2D3Sided(self.memory, points, \
y_upper_bound=True)
node.y_lower_struct = COORS2D3Sided(self.memory, points, \
y_upper_bound=False)
counter += 1
def query(self, x_min, x_max, y_min, y_max):
assert x_min <= x_max and y_min <= y_max
solutions = []
lca = self.yveb.fast_LCA(y_min, y_max)
if lca.is_leaf():
x, y = lca.point()
if x_min <= x <= x_max and y_min <= y <= y_max:
solutions.append((x, y))
else:
solutions.extend(lca.left.y_lower_struct.query(x_min, x_max, y_min))
solutions.extend(lca.right.y_upper_struct.query(x_min, x_max, y_max))
return solutions