3 """This is a Trie class, see: https://en.wikipedia.org/wiki/Trie.
5 It attempts to follow Pythonic container patterns. See doctests
8 from typing import Any, Generator, Sequence
13 This is a Trie class, see: https://en.wikipedia.org/wiki/Trie.
15 It attempts to follow Pythonic container patterns. See doctests
25 self.content_generator: Generator[str] = None
27 def insert(self, item: Sequence[Any]):
33 >>> t.__contains__('test')
39 current = current.setdefault(child, {})
40 current[self.end] = self.end
43 def __contains__(self, item: Sequence[Any]) -> bool:
45 Check whether an item is in the Trie.
49 >>> t.__contains__('test')
51 >>> t.__contains__('testing')
57 current = self.__traverse__(item)
61 return self.end in current
63 def contains_prefix(self, item: Sequence[Any]):
65 Check whether a prefix is in the Trie. The prefix may or may not
69 >>> t.insert('testicle')
70 >>> t.contains_prefix('test')
72 >>> t.contains_prefix('testicle')
74 >>> t.contains_prefix('tessel')
78 current = self.__traverse__(item)
79 return current is not None
81 def __traverse__(self, item: Sequence[Any]):
85 current = current[child]
90 def __getitem__(self, item: Sequence[Any]):
91 """Given an item, return its Trie node which contains all
92 of the successor (child) node pointers. If the item is not
93 a node in the Trie, raise a KeyError.
97 >>> t.insert('testicle')
98 >>> t.insert('tessera')
99 >>> t.insert('tesack')
101 {'t': {'~END~': '~END~', 'i': {'c': {'l': {'e': {'~END~': '~END~'}}}}}, 's': {'e': {'r': {'a': {'~END~': '~END~'}}}}, 'a': {'c': {'k': {'~END~': '~END~'}}}}
104 ret = self.__traverse__(item)
106 raise KeyError(f"Node '{item}' is not in the trie")
109 def delete_recursively(self, node, item: Sequence[Any]) -> bool:
112 if len(node) == 0 and node is not self.root:
121 if self.delete_recursively(lower, cdr):
122 return self.delete_recursively(node, car)
125 def __delitem__(self, item: Sequence[Any]):
127 Delete an item from the Trie.
132 >>> t.insert('tessel')
136 {'t': {'e': {'s': {'t': {'~END~': '~END~'}, 's': {'~END~': '~END~', 'e': {'l': {'~END~': '~END~'}}}}}}}
137 >>> t.__delitem__('test')
141 {'t': {'e': {'s': {'s': {'~END~': '~END~', 'e': {'l': {'~END~': '~END~'}}}}}}}
146 >>> t.__delitem__('tessel')
150 {'t': {'e': {'s': {'s': {'~END~': '~END~'}}}}}
154 >>> t.__delitem__('tess')
159 >>> t.insert('testy')
165 raise KeyError(f"Node '{item}' is not in the trie")
166 self.delete_recursively(self.root, item)
171 Returns a count of the Trie's item population.
179 >>> t.insert('testicle')
187 self.content_generator = self.generate_recursively(self.root, '')
190 def generate_recursively(self, node, path: Sequence[Any]):
192 Generate items in the trie one by one.
196 >>> t.insert('tickle')
197 >>> for item in t.generate_recursively(t.root, ''):
204 if child == self.end:
207 yield from self.generate_recursively(node[child], path + child)
211 Iterate through the contents of the trie.
215 >>> t.insert('tickle')
222 ret = next(self.content_generator)
227 def successors(self, item: Sequence[Any]):
229 Return a list of the successors of an item.
235 >>> t.successors('wh')
239 >>> u.insert(['this', 'is', 'a', 'test'])
240 >>> u.insert(['this', 'is', 'a', 'robbery'])
241 >>> u.insert(['this', 'is', 'a', 'walrus'])
242 >>> u.successors(['this', 'is', 'a'])
243 ['test', 'robbery', 'walrus']
246 node = self.__traverse__(item)
249 return [x for x in node if x != self.end]
260 if node is not self.root:
261 ret = f'\n{padding}{pointer}'
271 if child != self.end:
275 if child != self.end:
282 pointer += f'{child}'
284 ret += self.repr_fancy(padding, pointer, node[child], has_sibling)
287 def repr_brief(self, node, delimiter):
289 A friendly string representation of the contents of the Trie.
292 >>> t.insert([10, 0, 0, 1])
293 >>> t.insert([10, 0, 0, 2])
294 >>> t.insert([10, 10, 10, 1])
295 >>> t.insert([10, 10, 10, 2])
296 >>> t.repr_brief(t.root, '.')
297 '10.[0.0.[1,2],10.10.[1,2]]'
303 if child != self.end:
305 child_rep = self.repr_brief(node[child], delimiter)
306 if len(child_rep) > 0:
307 my_rep += str(child) + delimiter + child_rep + ","
309 my_rep += str(child) + ","
313 my_rep = f'[{my_rep}]'
318 A friendly string representation of the contents of the Trie. Under
319 the covers uses repr_fancy.
322 >>> t.insert([10, 0, 0, 1])
323 >>> t.insert([10, 0, 0, 2])
324 >>> t.insert([10, 10, 10, 1])
325 >>> t.insert([10, 10, 10, 2])
339 return self.repr_fancy('', '*', self.root, False)
342 if __name__ == '__main__':