3 from typing import Any, Sequence
8 This is a Trie class, see: https://en.wikipedia.org/wiki/Trie.
10 It attempts to follow Pythonic container patterns. See doctests
19 def insert(self, item: Sequence[Any]):
25 >>> t.__contains__('test')
31 current = current.setdefault(child, {})
32 current[self.end] = self.end
35 def __contains__(self, item: Sequence[Any]) -> bool:
37 Check whether an item is in the Trie.
41 >>> t.__contains__('test')
43 >>> t.__contains__('testing')
49 current = self.__traverse__(item)
53 return self.end in current
55 def contains_prefix(self, item: Sequence[Any]):
57 Check whether a prefix is in the Trie. The prefix may or may not
61 >>> t.insert('testicle')
62 >>> t.contains_prefix('test')
64 >>> t.contains_prefix('testicle')
66 >>> t.contains_prefix('tessel')
70 current = self.__traverse__(item)
71 return current is not None
73 def __traverse__(self, item: Sequence[Any]):
77 current = current[child]
82 def __getitem__(self, item: Sequence[Any]):
83 """Given an item, return its Trie node which contains all
84 of the successor (child) node pointers. If the item is not
85 a node in the Trie, raise a KeyError.
89 >>> t.insert('testicle')
90 >>> t.insert('tessera')
91 >>> t.insert('tesack')
93 {'t': {'~END~': '~END~', 'i': {'c': {'l': {'e': {'~END~': '~END~'}}}}}, 's': {'e': {'r': {'a': {'~END~': '~END~'}}}}, 'a': {'c': {'k': {'~END~': '~END~'}}}}
96 ret = self.__traverse__(item)
98 raise KeyError(f"Node '{item}' is not in the trie")
101 def delete_recursively(self, node, item: Sequence[Any]) -> bool:
104 if len(node) == 0 and node is not self.root:
113 if self.delete_recursively(lower, cdr):
114 return self.delete_recursively(node, car)
117 def __delitem__(self, item: Sequence[Any]):
119 Delete an item from the Trie.
124 >>> t.insert('tessel')
128 {'t': {'e': {'s': {'t': {'~END~': '~END~'}, 's': {'~END~': '~END~', 'e': {'l': {'~END~': '~END~'}}}}}}}
129 >>> t.__delitem__('test')
133 {'t': {'e': {'s': {'s': {'~END~': '~END~', 'e': {'l': {'~END~': '~END~'}}}}}}}
138 >>> t.__delitem__('tessel')
142 {'t': {'e': {'s': {'s': {'~END~': '~END~'}}}}}
146 >>> t.__delitem__('tess')
151 >>> t.insert('testy')
157 raise KeyError(f"Node '{item}' is not in the trie")
158 self.delete_recursively(self.root, item)
163 Returns a count of the Trie's item population.
171 >>> t.insert('testicle')
179 self.content_generator = self.generate_recursively(self.root, '')
182 def generate_recursively(self, node, path: Sequence[Any]):
184 Generate items in the trie one by one.
188 >>> t.insert('tickle')
189 >>> for item in t.generate_recursively(t.root, ''):
196 if child == self.end:
199 yield from self.generate_recursively(node[child], path + child)
203 Iterate through the contents of the trie.
207 >>> t.insert('tickle')
214 ret = next(self.content_generator)
219 def successors(self, item: Sequence[Any]):
221 Return a list of the successors of an item.
227 >>> t.successors('wh')
231 >>> u.insert(['this', 'is', 'a', 'test'])
232 >>> u.insert(['this', 'is', 'a', 'robbery'])
233 >>> u.insert(['this', 'is', 'a', 'walrus'])
234 >>> u.successors(['this', 'is', 'a'])
235 ['test', 'robbery', 'walrus']
238 node = self.__traverse__(item)
241 return [x for x in node if x != self.end]
243 def repr_recursive(self, node, delimiter):
245 A friendly string representation of the contents of the Trie.
248 >>> t.insert([10, 0, 0, 1])
249 >>> t.insert([10, 0, 0, 2])
250 >>> t.insert([10, 10, 10, 1])
251 >>> t.insert([10, 10, 10, 2])
252 >>> t.repr_recursive(t.root, '.')
253 '10.[0.0.[1, 2], 10.10.[1, 2]]'
255 10[00[1, 2], 1010[1, 2]]
261 if child != self.end:
263 child_rep = self.repr_recursive(node[child], delimiter)
264 if len(child_rep) > 0:
265 my_rep += str(child) + delimiter + child_rep + ", "
267 my_rep += str(child) + ", "
271 my_rep = f'[{my_rep}]'
276 A friendly string representation of the contents of the Trie. Under
277 the covers uses repr_recursive with no delimiter
280 >>> t.insert([10, 0, 0, 1])
281 >>> t.insert([10, 0, 0, 2])
282 >>> t.insert([10, 10, 10, 1])
283 >>> t.insert([10, 10, 10, 2])
285 10[00[1, 2], 1010[1, 2]]
288 return self.repr_recursive(self.root, '')
291 if __name__ == '__main__':