-
Notifications
You must be signed in to change notification settings - Fork 16
Expand file tree
/
Copy pathtrie.py
More file actions
138 lines (121 loc) · 3.54 KB
/
trie.py
File metadata and controls
138 lines (121 loc) · 3.54 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
class Trie(object):
def __init__(self):
self.path = {}
self.value = None
self.value_valid = False
def __setitem__(self, key, value):
head = key[0]
if head in self.path:
node = self.path[head]
else:
node = Trie()
self.path[head] = node
if len(key) > 1:
remains = key[1:]
node.__setitem__(remains, value)
else:
node.value = value
node.value_valid = True
def __delitem__(self, key):
head = key[0]
if head in self.path:
node = self.path[head]
if len(key) > 1:
remains = key[1:]
node.__delitem__(remains)
else:
node.value_valid = False
node.value = None
if len(node) == 0:
del self.path[head]
def __getitem__(self, key):
head = key[0]
if head in self.path:
node = self.path[head]
else:
raise KeyError(key)
if len(key) > 1:
remains = key[1:]
try:
return node.__getitem__(remains)
except KeyError:
raise KeyError(key)
elif node.value_valid:
return node.value
else:
raise KeyError(key)
def __contains__(self, key):
try:
self.__getitem__(key)
except KeyError:
return False
return True
def __len__(self):
n = 1 if self.value_valid else 0
for k in self.path.keys():
n = n + len(self.path[k])
return n
def get(self, key, default=None):
try:
return self.__getitem__(key)
except KeyError:
return default
def nodeCount(self):
n = 0
for k in self.path.keys():
n = n + 1 + self.path[k].nodeCount()
return n
def keys(self, prefix=[]):
return self.__keys__(prefix)
def __keys__(self, prefix=[], seen=[]):
result = []
if self.value_valid:
isStr = True
val = ""
for k in seen:
if k is not str or len(k) > 2:
isStr = False
break
else:
val += k
if isStr:
result.append(val)
else:
result.append(prefix)
if len(prefix) > 0:
head = prefix[0]
prefix = prefix[1:]
if head in self.path:
nextpaths = [head]
else:
nextpaths = []
else:
nextpaths = self.path.keys()
for k in nextpaths:
nextseen = []
nextseen.extend(seen)
nextseen.append(k)
result.extend(self.path[k].__keys__(prefix, nextseen))
return result
def __iter__(self):
for k in self.keys():
yield k
raise StopIteration
def __add__(self, other):
result = Trie()
result += self
result += other
return result
def __sub__(self, other):
result = Trie()
result += self
result -= other
return result
def __iadd__(self, other):
for k in other:
self[k] = other[k]
return self
def __isub__(self, other):
for k in other:
del self[k]
return self