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]
244 if __name__ == '__main__':