1
|
|
|
from abc import ABCMeta, abstractmethod |
2
|
|
|
|
3
|
|
|
from pyalgs.algorithms.commons import util |
4
|
|
|
from pyalgs.data_structures.commons.queue import Queue |
5
|
|
|
|
6
|
|
|
|
7
|
|
|
class SearchTries(object): |
8
|
|
|
__metaclass__ = ABCMeta |
9
|
|
|
|
10
|
|
|
@abstractmethod |
11
|
|
|
def put(self, key, value): |
12
|
|
|
pass |
13
|
|
|
|
14
|
|
|
@abstractmethod |
15
|
|
|
def get(self, key): |
16
|
|
|
pass |
17
|
|
|
|
18
|
|
|
@abstractmethod |
19
|
|
|
def is_empty(self): |
20
|
|
|
pass |
21
|
|
|
|
22
|
|
|
@abstractmethod |
23
|
|
|
def size(self): |
24
|
|
|
pass |
25
|
|
|
|
26
|
|
|
@abstractmethod |
27
|
|
|
def delete(self, key): |
28
|
|
|
pass |
29
|
|
|
|
30
|
|
|
@abstractmethod |
31
|
|
|
def keys(self): |
32
|
|
|
pass |
33
|
|
|
|
34
|
|
|
@abstractmethod |
35
|
|
|
def keys_with_prefix(self, prefix): |
36
|
|
|
pass |
37
|
|
|
|
38
|
|
|
@abstractmethod |
39
|
|
|
def contains_key(self, key): |
40
|
|
|
pass |
41
|
|
|
|
42
|
|
|
@staticmethod |
43
|
|
|
def create(): |
44
|
|
|
return RWaySearchTries() |
45
|
|
|
|
46
|
|
|
|
47
|
|
|
def char_at(key, d): |
48
|
|
|
return ord(key[d]) |
49
|
|
|
|
50
|
|
|
|
51
|
|
|
class Node(object): |
52
|
|
|
nodes = None |
53
|
|
|
value = None |
54
|
|
|
R = 256 |
55
|
|
|
|
56
|
|
|
def __init__(self): |
57
|
|
|
self.nodes = [None] * Node.R |
58
|
|
|
|
59
|
|
|
|
60
|
|
|
class RWaySearchTries(SearchTries): |
61
|
|
|
|
62
|
|
|
root = None |
63
|
|
|
N = 0 |
64
|
|
|
|
65
|
|
|
def contains_key(self, key): |
66
|
|
|
x = self._get(self.root, key, 0) |
67
|
|
|
if x is None: |
68
|
|
|
return None |
69
|
|
|
return x.value |
70
|
|
|
|
71
|
|
|
def keys_with_prefix(self, prefix): |
72
|
|
|
x = self._get(self.root, prefix, 0) |
73
|
|
|
if x is None: |
74
|
|
|
return None |
75
|
|
|
|
76
|
|
|
queue = Queue.create() |
77
|
|
|
self.collect(x, prefix, queue) |
78
|
|
|
return queue.iterate() |
79
|
|
|
|
80
|
|
|
def keys(self): |
81
|
|
|
queue = Queue.create() |
82
|
|
|
self.collect(self.root, '', queue) |
83
|
|
|
return queue.iterate() |
84
|
|
|
|
85
|
|
|
def collect(self, x, prefix, queue): |
86
|
|
|
if x is None: |
87
|
|
|
return |
88
|
|
|
|
89
|
|
|
if x.value is not None: |
90
|
|
|
queue.enqueue(prefix) |
91
|
|
|
return |
92
|
|
|
|
93
|
|
|
for r in range(Node.R): |
94
|
|
|
self.collect(x.nodes[r], prefix + str(chr(r)), queue) |
95
|
|
|
|
96
|
|
|
def is_empty(self): |
97
|
|
|
return self.N == 0 |
98
|
|
|
|
99
|
|
|
def get(self, key): |
100
|
|
|
x = self._get(self.root, key, 0) |
101
|
|
|
if x is not None: |
102
|
|
|
return x.value |
103
|
|
|
return None |
104
|
|
|
|
105
|
|
|
def _get(self, x, key, d): |
106
|
|
|
if x is None: |
107
|
|
|
return None |
108
|
|
|
if len(key) == d: |
109
|
|
|
return x |
110
|
|
|
|
111
|
|
|
return self._get(x.nodes[self.char_at(key, d)], key, d + 1) |
112
|
|
|
|
113
|
|
|
def delete(self, key): |
114
|
|
|
self.root = self._delete(self.root, key, 0) |
115
|
|
|
|
116
|
|
|
def _delete(self, x, key, d): |
117
|
|
|
if x is None: |
118
|
|
|
return None |
119
|
|
|
|
120
|
|
|
if len(key) == d: |
121
|
|
|
if x.value is not None: |
122
|
|
|
self.N -= 1 |
123
|
|
|
return None |
124
|
|
|
|
125
|
|
|
c = self.char_at(key, d) |
126
|
|
|
x.nodes[c] = self._delete(x.nodes[c], key, d + 1) |
127
|
|
|
return x |
128
|
|
|
|
129
|
|
|
def put(self, key, value): |
130
|
|
|
self.root = self._put(self.root, key, value, 0) |
131
|
|
|
|
132
|
|
|
def _put(self, x, key, value, d): |
133
|
|
|
if x is None: |
134
|
|
|
x = Node() |
135
|
|
|
if len(key) == d: |
136
|
|
|
if x.value is None: |
137
|
|
|
self.N += 1 |
138
|
|
|
x.value = value |
139
|
|
|
return x |
140
|
|
|
|
141
|
|
|
c = self.char_at(key, d) |
142
|
|
|
x.nodes[c] = self._put(x.nodes[c], key, value, d + 1) |
143
|
|
|
return x |
144
|
|
|
|
145
|
|
|
def size(self): |
146
|
|
|
return self.N |
147
|
|
|
|
148
|
|
|
|
149
|
|
|
class Node(object): |
150
|
|
|
value = None |
151
|
|
|
left = None |
152
|
|
|
mid = None |
153
|
|
|
right = None |
154
|
|
|
key = None |
155
|
|
|
|
156
|
|
|
def __init__(self, c): |
157
|
|
|
self.key = c |
158
|
|
|
|
159
|
|
|
|
160
|
|
|
class TernarySearchTries(SearchTries): |
161
|
|
|
|
162
|
|
|
root = None |
163
|
|
|
N = 0 |
164
|
|
|
|
165
|
|
|
def contains_key(self, key): |
166
|
|
|
x = self._get(self.root, key, 0) |
167
|
|
|
return x is not None and x.value is not None |
168
|
|
|
|
169
|
|
|
def size(self): |
170
|
|
|
return self.N |
171
|
|
|
|
172
|
|
|
def keys(self): |
173
|
|
|
queue = Queue.create() |
174
|
|
|
self.collect(self.root, '', queue) |
175
|
|
|
return queue.iterate() |
176
|
|
|
|
177
|
|
|
def collect(self, x, prefix, queue): |
178
|
|
|
if x is None: |
179
|
|
|
return |
180
|
|
|
if x.value is not None: |
181
|
|
|
queue.enqueue(prefix) |
182
|
|
|
c = chr(x.key) |
183
|
|
|
self.collect(x.left, prefix, queue) |
184
|
|
|
self.collect(x.mid, prefix + str(c), queue) |
185
|
|
|
self.collect(x.right, prefix, queue) |
186
|
|
|
|
187
|
|
|
def get(self, key): |
188
|
|
|
x = self._get(self.root, key, 0) |
189
|
|
|
if x is None: |
190
|
|
|
return None |
191
|
|
|
return x.value |
192
|
|
|
|
193
|
|
|
def _get(self, x, key, d): |
194
|
|
|
if x is None: |
195
|
|
|
return None |
196
|
|
|
c = char_at(key, d) |
197
|
|
|
compared = util.cmp(c, x.key) |
198
|
|
|
if compared < 0: |
199
|
|
|
return self._get(x.left, key, d) |
200
|
|
|
elif compared > 0: |
201
|
|
|
return self._get(x.right, key, d) |
202
|
|
|
elif len(key)-1 == d: |
203
|
|
|
return x |
204
|
|
|
else: |
205
|
|
|
return self._get(x.mid, key, d+1) |
206
|
|
|
|
207
|
|
|
def put(self, key, value): |
208
|
|
|
self.root = self._put(self.root, key, value, 0) |
209
|
|
|
|
210
|
|
|
def _put(self, x, key, value, d): |
211
|
|
|
c = char_at(key, d) |
212
|
|
|
if x is None: |
213
|
|
|
x = Node(c) |
214
|
|
|
compared = util.cmp(c, x.key) |
215
|
|
|
if compared < 0: |
216
|
|
|
x.left = self._put(x.left, key, value, d) |
217
|
|
|
elif compared > 0: |
218
|
|
|
x.right = self._put(x.right, key, value, d) |
219
|
|
|
elif len(key)-1 == d: |
220
|
|
|
if x.value is None: |
221
|
|
|
self.N += 1 |
222
|
|
|
x.value = value |
223
|
|
|
else: |
224
|
|
|
x.mid = self._put(x.mid, key, value, d+1) |
225
|
|
|
|
226
|
|
|
return x |
227
|
|
|
|
228
|
|
|
def delete(self, key): |
229
|
|
|
x = self._get(self.root, key, 0) |
230
|
|
|
if x is not None: |
231
|
|
|
if x.value is not None: |
232
|
|
|
self.N -= 1 |
233
|
|
|
x.value = None |
234
|
|
|
|
235
|
|
|
def is_empty(self): |
236
|
|
|
return self.N == 0 |
237
|
|
|
|
238
|
|
|
def keys_with_prefix(self, prefix): |
239
|
|
|
x = self._get(self.root, prefix, 0) |
240
|
|
|
if x is None: |
241
|
|
|
return None |
242
|
|
|
queue = Queue.create() |
243
|
|
|
self.collect(x, prefix, queue) |
244
|
|
|
return queue.iterate() |