Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/pygtrie.py: 35%
Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1# -*- coding: utf-8 -*-
2"""Pure Python implementation of a trie data structure compatible with Python
32.x and Python 3.x.
5`Trie data structure <http://en.wikipedia.org/wiki/Trie>`_, also known as radix
6or prefix tree, is a tree associating keys to values where all the descendants
7of a node have a common prefix (associated with that node).
9The trie module contains :class:`pygtrie.Trie`, :class:`pygtrie.CharTrie` and
10:class:`pygtrie.StringTrie` classes each implementing a mutable mapping
11interface, i.e. :class:`dict` interface. As such, in most circumstances,
12:class:`pygtrie.Trie` could be used as a drop-in replacement for
13a :class:`dict`, but the prefix nature of the data structure is trie’s real
14strength.
16The module also contains :class:`pygtrie.PrefixSet` class which uses a trie to
17store a set of prefixes such that a key is contained in the set if it or its
18prefix is stored in the set.
20Features
21--------
23- A full mutable mapping implementation.
25- Supports iterating over as well as deleting of a branch of a trie
26 (i.e. subtrie)
28- Supports prefix checking as well as shortest and longest prefix
29 look-up.
31- Extensible for any kind of user-defined keys.
33- A PrefixSet supports “all keys starting with given prefix” logic.
35- Can store any value including None.
37For a few simple examples see ``example.py`` file.
38"""
40from __future__ import absolute_import, division, print_function
42__author__ = 'Michal Nazarewicz <mina86@mina86.com>'
43__copyright__ = ('Copyright 2014-2017 Google LLC',
44 'Copyright 2018-2020 Michal Nazarewicz <mina86@mina86.com>')
45__version__ = '2.5.0'
48import copy as _copy
49try:
50 import collections.abc as _abc
51except ImportError: # Python 2 compatibility
52 import collections as _abc
55class ShortKeyError(KeyError):
56 """Raised when given key is a prefix of an existing longer key
57 but does not have a value associated with itself."""
60class _NoChildren(object):
61 """Collection representing lack of any children.
63 Also acts as an empty iterable and an empty iterator. This isn’t the
64 cleanest designs but it makes various things more concise and avoids object
65 allocations in a few places.
67 Don’t create objects of this type directly; instead use _EMPTY singleton.
68 """
69 __slots__ = ()
71 def __bool__(self):
72 return False
73 __nonzero__ = __bool__
74 def __len__(self):
75 return 0
76 def __iter__(self):
77 return self
78 iteritems = sorted_items = __iter__
79 def __next__(self):
80 raise StopIteration()
81 next = __next__
83 def get(self, _step):
84 return None
86 def add(self, parent, step):
87 node = _Node()
88 parent.children = _OneChild(step, node)
89 return node
91 require = add
93 def copy(self, _make_copy, _queue):
94 return self
96 def __deepcopy__(self, memo):
97 return self
99 # delete is not implemented on purpose since it should never be called on
100 # a node with no children.
103_EMPTY = _NoChildren()
106class _OneChild(object):
107 """Children collection representing a single child."""
109 __slots__ = ('step', 'node')
111 def __init__(self, step, node):
112 self.step = step
113 self.node = node
115 def __bool__(self):
116 return True
117 __nonzero__ = __bool__
118 def __len__(self):
119 return 1
121 def sorted_items(self):
122 return [(self.step, self.node)]
124 def iteritems(self):
125 return iter(((self.step, self.node),))
127 def get(self, step):
128 return self.node if step == self.step else None
130 def add(self, parent, step):
131 node = _Node()
132 parent.children = _Children((self.step, self.node), (step, node))
133 return node
135 def require(self, parent, step):
136 return self.node if self.step == step else self.add(parent, step)
138 def merge(self, other, queue):
139 """Moves children from other into this object."""
140 if type(other) == _OneChild and other.step == self.step:
141 queue.append((self.node, other.node))
142 return self
143 else:
144 children = _Children((self.step, self.node))
145 children.merge(other, queue)
146 return children
148 def delete(self, parent, _step):
149 parent.children = _EMPTY
151 def copy(self, make_copy, queue):
152 cpy = _OneChild(make_copy(self.step), self.node.shallow_copy(make_copy))
153 queue.append((cpy.node,))
154 return cpy
157class _Children(dict):
158 """Children collection representing more than one child."""
160 __slots__ = ()
162 def __init__(self, *items):
163 super(_Children, self).__init__(items)
165 if hasattr(dict, 'iteritems'): # Python 2 compatibility
166 def sorted_items(self):
167 items = self.items()
168 items.sort()
169 return items
170 else:
171 def sorted_items(self):
172 return sorted(self.items())
174 def iteritems(self):
175 return iter(self.items())
177 def add(self, _parent, step):
178 self[step] = node = _Node()
179 return node
181 def require(self, _parent, step):
182 return self.setdefault(step, _Node())
184 def merge(self, other, queue):
185 """Moves children from other into this object."""
186 for step, other_node in other.iteritems():
187 node = self.setdefault(step, other_node)
188 if node is not other_node:
189 queue.append((node, other_node))
190 return self
192 def delete(self, parent, step):
193 del self[step]
194 if len(self) == 1:
195 parent.children = _OneChild(*self.popitem())
197 def copy(self, make_copy, queue):
198 cpy = _Children()
199 cpy.update((make_copy(step), node.shallow_copy(make_copy))
200 for step, node in self.items())
201 queue.append(cpy.values())
202 return cpy
205class _Node(object):
206 """A single node of a trie.
208 Stores value associated with the node and dictionary of children.
209 """
210 __slots__ = ('children', 'value')
212 def __init__(self):
213 self.children = _EMPTY
214 self.value = _EMPTY
216 def merge(self, other, overwrite):
217 """Move children from other node into this one.
219 Args:
220 other: Other node to move children and value from.
221 overwrite: Whether to overwrite existing node values.
222 """
223 queue = [(self, other)]
224 while queue:
225 lhs, rhs = queue.pop()
226 if lhs.value is _EMPTY or (overwrite and rhs.value is not _EMPTY):
227 lhs.value = rhs.value
228 if lhs.children is _EMPTY:
229 lhs.children = rhs.children
230 elif rhs.children is not _EMPTY:
231 lhs.children = lhs.children.merge(rhs.children, queue)
232 rhs.children = _EMPTY
234 def iterate(self, path, shallow, iteritems):
235 """Yields all the nodes with values associated to them in the trie.
237 Args:
238 path: Path leading to this node. Used to construct the key when
239 returning value of this node and as a prefix for children.
240 shallow: Perform a shallow traversal, i.e. do not yield nodes if
241 their prefix has been yielded.
242 iteritems: A callable taking ``node.children`` as sole argument and
243 returning an iterable of children as ``(step, node)`` pair. The
244 callable would typically call ``iteritems`` or ``sorted_items``
245 method on the argument depending on whether sorted output is
246 desired.
248 Yields:
249 ``(path, value)`` tuples.
250 """
251 # Use iterative function with stack on the heap so we don't hit Python's
252 # recursion depth limits.
253 node = self
254 stack = []
255 while True:
256 if node.value is not _EMPTY:
257 yield path, node.value
259 if (not shallow or node.value is _EMPTY) and node.children:
260 stack.append(iter(iteritems(node.children)))
261 path.append(None)
263 while True:
264 try:
265 step, node = next(stack[-1])
266 path[-1] = step
267 break
268 except StopIteration:
269 stack.pop()
270 path.pop()
271 except IndexError:
272 return
274 def traverse(self, node_factory, path_conv, path, iteritems):
275 """Traverses the node and returns another type of node from factory.
277 Args:
278 node_factory: Callable to construct return value.
279 path_conv: Callable to convert node path to a key.
280 path: Current path for this node.
281 iteritems: A callable taking ``node.children`` as sole argument and
282 returning an iterable of children as ``(step, node)`` pair. The
283 callable would typically call ``iteritems`` or ``sorted_items``
284 method on the argument depending on whether sorted output is
285 desired.
287 Returns:
288 An object constructed by calling node_factory(path_conv, path,
289 children, value=...), where children are constructed by node_factory
290 from the children of this node. There doesn't need to be 1:1
291 correspondence between original nodes in the trie and constructed
292 nodes (see make_test_node_and_compress in test.py).
293 """
294 children = self.children and (
295 node.traverse(node_factory, path_conv, path + [step], iteritems)
296 for step, node in iteritems(self.children))
298 value_maybe = ()
299 if self.value is not _EMPTY:
300 value_maybe = (self.value,)
302 return node_factory(path_conv, tuple(path), children, *value_maybe)
304 def equals(self, other):
305 """Returns whether this and other node are recursively equal."""
306 # Like iterate, we don't recurse so this works on deep tries.
307 a, b = self, other
308 stack = []
309 while True:
310 if a.value != b.value or len(a.children) != len(b.children):
311 return False
312 if len(a.children) == 1:
313 # We know a.children and b.children are both _OneChild objects
314 # but pylint doesn’t recognise that: pylint: disable=no-member
315 if a.children.step != b.children.step:
316 return False
317 a = a.children.node
318 b = b.children.node
319 continue
320 if a.children:
321 stack.append((a.children.iteritems(), b.children))
323 while True:
324 try:
325 key, a = next(stack[-1][0])
326 b = stack[-1][1][key]
327 break
328 except StopIteration:
329 stack.pop()
330 except IndexError:
331 return True
332 except KeyError:
333 return False
335 __bool__ = __nonzero__ = __hash__ = None
337 def shallow_copy(self, make_copy):
338 """Returns a copy of the node which shares the children property."""
339 cpy = _Node()
340 cpy.children = self.children
341 cpy.value = make_copy(self.value)
342 return cpy
344 def copy(self, make_copy):
345 """Returns a copy of the node structure."""
346 cpy = self.shallow_copy(make_copy)
347 queue = [(cpy,)]
348 while queue:
349 for node in queue.pop():
350 node.children = node.children.copy(make_copy, queue)
351 return cpy
353 def __getstate__(self):
354 """Get state used for pickling.
356 The state is encoded as a list of simple commands which consist of an
357 integer and some command-dependent number of arguments. The commands
358 modify what the current node is by navigating the trie up and down and
359 setting node values. Possible commands are:
361 * [n, step0, step1, ..., stepn-1, value], for n >= 0, specifies step
362 needed to reach the next current node as well as its new value. There
363 is no way to create a child node without setting its (or its
364 descendant's) value.
366 * [-n], for -n < 0, specifies to go up n steps in the trie.
368 When encoded as a state, the commands are flattened into a single list.
370 For example::
372 [ 0, 'Root',
373 2, 'Foo', 'Bar', 'Root/Foo/Bar Node',
374 -1,
375 1, 'Baz', 'Root/Foo/Baz Node',
376 -2,
377 1, 'Qux', 'Root/Qux Node' ]
379 Creates the following hierarchy::
381 -* value: Root
382 +-- Foo --* no value
383 | +-- Bar -- * value: Root/Foo/Bar Node
384 | +-- Baz -- * value: Root/Foo/Baz Node
385 +-- Qux -- * value: Root/Qux Node
387 Returns:
388 A pickable state which can be passed to :func:`_Node.__setstate__`
389 to reconstruct the node and its full hierarchy.
390 """
391 # Like iterate, we don't recurse so pickling works on deep tries.
392 state = [] if self.value is _EMPTY else [0]
393 last_cmd = 0
394 node = self
395 stack = []
396 while True:
397 if node.value is not _EMPTY:
398 last_cmd = 0
399 state.append(node.value)
400 stack.append(node.children.iteritems())
402 while True:
403 step, node = next(stack[-1], (None, None))
404 if node is not None:
405 break
407 if last_cmd < 0:
408 state[-1] -= 1
409 else:
410 last_cmd = -1
411 state.append(-1)
412 stack.pop()
413 if not stack:
414 state.pop() # Final -n command is not necessary
415 return state
417 if last_cmd > 0:
418 last_cmd += 1
419 state[-last_cmd] += 1
420 else:
421 last_cmd = 1
422 state.append(1)
423 state.append(step)
425 def __setstate__(self, state):
426 """Unpickles node. See :func:`_Node.__getstate__`."""
427 self.__init__()
428 state = iter(state)
429 stack = [self]
430 for cmd in state:
431 if cmd < 0:
432 del stack[cmd:]
433 else:
434 while cmd > 0:
435 parent = stack[-1]
436 stack.append(parent.children.add(parent, next(state)))
437 cmd -= 1
438 stack[-1].value = next(state)
441class Trie(_abc.MutableMapping):
442 """A trie implementation with dict interface plus some extensions.
444 Keys used with the :class:`pygtrie.Trie` class must be iterable which each
445 component being a hashable objects. In other words, for a given key,
446 ``dict.fromkeys(key)`` must be valid expression.
448 In particular, strings work well as trie keys, however when getting them
449 back (for example via :func:`Trie.iterkeys` method), instead of strings,
450 tuples of characters are produced. For that reason,
451 :class:`pygtrie.CharTrie` or :class:`pygtrie.StringTrie` classes may be
452 preferred when using string keys.
453 """
455 def __init__(self, *args, **kwargs):
456 """Initialises the trie.
458 Arguments are interpreted the same way :func:`Trie.update` interprets
459 them.
460 """
461 self._root = _Node()
462 self._iteritems = self._ITERITEMS_CALLBACKS[0]
463 self.update(*args, **kwargs)
465 _ITERITEMS_CALLBACKS = (lambda x: x.iteritems(), lambda x: x.sorted_items())
467 def enable_sorting(self, enable=True):
468 """Enables sorting of child nodes when iterating and traversing.
470 Normally, child nodes are not sorted when iterating or traversing over
471 the trie (just like dict elements are not sorted). This method allows
472 sorting to be enabled (which was the behaviour prior to pygtrie 2.0
473 release).
475 For Trie class, enabling sorting of children is identical to simply
476 sorting the list of items since Trie returns keys as tuples. However,
477 for other implementations such as StringTrie the two may behave subtly
478 different. For example, sorting items might produce::
480 root/foo-bar
481 root/foo/baz
483 even though foo comes before foo-bar.
485 Args:
486 enable: Whether to enable sorting of child nodes.
487 """
488 self._iteritems = self._ITERITEMS_CALLBACKS[bool(enable)]
490 def __getstate__(self):
491 # encode self._iteritems as self._sorted when pickling
492 state = self.__dict__.copy()
493 callback = state.pop('_iteritems', None)
494 state['_sorted'] = callback is self._ITERITEMS_CALLBACKS[1]
495 return state
497 def __setstate__(self, state):
498 # translate self._sorted back to _iteritems when unpickling
499 self.__dict__ = state
500 self.enable_sorting(state.pop('_sorted'))
502 def clear(self):
503 """Removes all the values from the trie."""
504 self._root = _Node()
506 def update(self, *args, **kwargs): # pylint: disable=arguments-differ
507 """Updates stored values. Works like :meth:`dict.update`."""
508 if len(args) > 1:
509 raise ValueError('update() takes at most one positional argument, '
510 '%d given.' % len(args))
511 # We have this here instead of just letting MutableMapping.update()
512 # handle things because it will iterate over keys and for each key
513 # retrieve the value. With Trie, this may be expensive since the path
514 # to the node would have to be walked twice. Instead, we have our own
515 # implementation where iteritems() is used avoiding the unnecessary
516 # value look-up.
517 if args and isinstance(args[0], Trie):
518 for key, value in args[0].items():
519 self[key] = value
520 args = ()
521 super(Trie, self).update(*args, **kwargs)
523 def merge(self, other, overwrite=False):
524 """Moves nodes from other trie into this one.
526 The merging happens at trie structure level and as such is different
527 than iterating over items of one trie and setting them in the other
528 trie.
530 The merging may happen between different types of tries resulting in
531 different (key, value) pairs in the destination trie compared to the
532 source. For example, merging two :class:`pygtrie.StringTrie` objects
533 each using different separators will work as if the other trie had
534 separator of this trie. Similarly, a :class:`pygtrie.CharTrie` may be
535 merged into a :class:`pygtrie.StringTrie` but when keys are read those
536 will be joined by the separator. For example:
538 >>> import pygtrie
539 >>> st = pygtrie.StringTrie(separator='.')
540 >>> st.merge(pygtrie.StringTrie({'foo/bar': 42}))
541 >>> list(st.items())
542 [('foo.bar', 42)]
543 >>> st.merge(pygtrie.CharTrie({'baz': 24}))
544 >>> sorted(st.items())
545 [('b.a.z', 24), ('foo.bar', 42)]
547 Not all tries can be merged into other tries. For example,
548 a :class:`pygtrie.StringTrie` may not be merged into
549 a :class:`pygtrie.CharTrie` because the latter imposes a requirement for
550 each component in the key to be exactly one character while in the
551 former components may be arbitrary length.
553 Note that the other trie is cleared and any references or iterators over
554 it are invalidated. To preserve other’s value it needs to be copied
555 first.
557 Args:
558 other: Other trie to move nodes from.
559 overwrite: Whether to overwrite existing values in this trie.
560 """
561 if isinstance(self, type(other)):
562 self._merge_impl(self, other, overwrite=overwrite)
563 else:
564 other._merge_impl(self, other, overwrite=overwrite) # pylint: disable=protected-access
565 other.clear()
567 @classmethod
568 def _merge_impl(cls, dst, src, overwrite):
569 # pylint: disable=protected-access
570 dst._root.merge(src._root, overwrite=overwrite)
572 def copy(self, __make_copy=lambda x: x):
573 """Returns a shallow copy of the object."""
574 # pylint: disable=protected-access
575 cpy = self.__class__()
576 cpy.__dict__ = self.__dict__.copy()
577 cpy._root = self._root.copy(__make_copy)
578 return cpy
580 def __copy__(self):
581 return self.copy()
583 def __deepcopy__(self, memo):
584 return self.copy(lambda x: _copy.deepcopy(x, memo))
586 @classmethod
587 def fromkeys(cls, keys, value=None):
588 """Creates a new trie with given keys set.
590 This is roughly equivalent to calling the constructor with a ``(key,
591 value) for key in keys`` generator.
593 Args:
594 keys: An iterable of keys that should be set in the new trie.
595 value: Value to associate with given keys.
597 Returns:
598 A new trie where each key from ``keys`` has been set to the given
599 value.
600 """
601 trie = cls()
602 for key in keys:
603 trie[key] = value
604 return trie
606 def _get_node(self, key):
607 """Returns node for given key. Creates it if requested.
609 Args:
610 key: A key to look for.
612 Returns:
613 ``(node, trace)`` tuple where ``node`` is the node for given key and
614 ``trace`` is a list specifying path to reach the node including all
615 the encountered nodes. Each element of trace is a ``(step, node)``
616 tuple where ``step`` is a step from parent node to given node and
617 ``node`` is node on the path. The first element of the path is
618 always ``(None, self._root)``.
620 Raises:
621 KeyError: If there is no node for the key.
622 """
623 node = self._root
624 trace = [(None, node)]
625 for step in self.__path_from_key(key):
626 # pylint thinks node.children is always _NoChildren and thus that
627 # we’re assigning None here; pylint: disable=assignment-from-none
628 node = node.children.get(step)
629 if node is None:
630 raise KeyError(key)
631 trace.append((step, node))
632 return node, trace
634 def _set_node(self, key, value, only_if_missing=False):
635 """Sets value for a given key.
637 Args:
638 key: Key to set value of.
639 value: Value to set to.
640 only_if_missing: If true, value won't be changed if the key is
641 already associated with a value.
643 Returns:
644 The node.
645 """
646 node = self._root
647 for step in self.__path_from_key(key):
648 node = node.children.require(node, step)
649 if node.value is _EMPTY or not only_if_missing:
650 node.value = value
651 return node
653 def _set_node_if_no_prefix(self, key):
654 """Sets given key to True but only if none of its prefixes are present.
656 If value is set, removes all ancestors of the node.
658 This is a method for exclusive use by PrefixSet.
660 Args:
661 key: Key to set value of.
662 """
663 steps = iter(self.__path_from_key(key))
664 node = self._root
665 try:
666 while node.value is _EMPTY:
667 node = node.children.require(node, next(steps))
668 except StopIteration:
669 node.value = True
670 node.children = _EMPTY
672 def __iter__(self):
673 return self.iterkeys()
675 # pylint: disable=arguments-differ
677 def iteritems(self, prefix=_EMPTY, shallow=False):
678 """Yields all nodes with associated values with given prefix.
680 Only nodes with values are output. For example::
682 >>> import pygtrie
683 >>> t = pygtrie.StringTrie()
684 >>> t['foo'] = 'Foo'
685 >>> t['foo/bar/baz'] = 'Baz'
686 >>> t['qux'] = 'Qux'
687 >>> sorted(t.items())
688 [('foo', 'Foo'), ('foo/bar/baz', 'Baz'), ('qux', 'Qux')]
690 Items are generated in topological order (i.e. parents before child
691 nodes) but the order of siblings is unspecified. At an expense of
692 efficiency, :func:`Trie.enable_sorting` method can turn deterministic
693 ordering of siblings.
695 With ``prefix`` argument, only items with specified prefix are generated
696 (i.e. only given subtrie is traversed) as demonstrated by::
698 >>> t.items(prefix='foo')
699 [('foo', 'Foo'), ('foo/bar/baz', 'Baz')]
701 With ``shallow`` argument, if a node has value associated with it, it's
702 children are not traversed even if they exist which can be seen in::
704 >>> sorted(t.items(shallow=True))
705 [('foo', 'Foo'), ('qux', 'Qux')]
707 Args:
708 prefix: Prefix to limit iteration to.
709 shallow: Perform a shallow traversal, i.e. do not yield items if
710 their prefix has been yielded.
712 Yields:
713 ``(key, value)`` tuples.
715 Raises:
716 KeyError: If ``prefix`` does not match any node.
717 """
718 node, _ = self._get_node(prefix)
719 for path, value in node.iterate(list(self.__path_from_key(prefix)),
720 shallow, self._iteritems):
721 yield (self._key_from_path(path), value)
723 def iterkeys(self, prefix=_EMPTY, shallow=False):
724 """Yields all keys having associated values with given prefix.
726 This is equivalent to taking first element of tuples generated by
727 :func:`Trie.iteritems` which see for more detailed documentation.
729 Args:
730 prefix: Prefix to limit iteration to.
731 shallow: Perform a shallow traversal, i.e. do not yield keys if
732 their prefix has been yielded.
734 Yields:
735 All the keys (with given prefix) with associated values in the trie.
737 Raises:
738 KeyError: If ``prefix`` does not match any node.
739 """
740 for key, _ in self.iteritems(prefix=prefix, shallow=shallow):
741 yield key
743 def itervalues(self, prefix=_EMPTY, shallow=False):
744 """Yields all values associated with keys with given prefix.
746 This is equivalent to taking second element of tuples generated by
747 :func:`Trie.iteritems` which see for more detailed documentation.
749 Args:
750 prefix: Prefix to limit iteration to.
751 shallow: Perform a shallow traversal, i.e. do not yield values if
752 their prefix has been yielded.
754 Yields:
755 All the values associated with keys (with given prefix) in the trie.
757 Raises:
758 KeyError: If ``prefix`` does not match any node.
759 """
760 node, _ = self._get_node(prefix)
761 for _, value in node.iterate(list(self.__path_from_key(prefix)),
762 shallow, self._iteritems):
763 yield value
765 def items(self, prefix=_EMPTY, shallow=False):
766 """Returns a list of ``(key, value)`` pairs in given subtrie.
768 This is equivalent to constructing a list from generator returned by
769 :func:`Trie.iteritems` which see for more detailed documentation.
770 """
771 return list(self.iteritems(prefix=prefix, shallow=shallow))
773 def keys(self, prefix=_EMPTY, shallow=False):
774 """Returns a list of all the keys, with given prefix, in the trie.
776 This is equivalent to constructing a list from generator returned by
777 :func:`Trie.iterkeys` which see for more detailed documentation.
778 """
779 return list(self.iterkeys(prefix=prefix, shallow=shallow))
781 def values(self, prefix=_EMPTY, shallow=False):
782 """Returns a list of values in given subtrie.
784 This is equivalent to constructing a list from generator returned by
785 :func:`Trie.itervalues` which see for more detailed documentation.
786 """
787 return list(self.itervalues(prefix=prefix, shallow=shallow))
789 def __len__(self):
790 """Returns number of values in a trie.
792 Note that this method is expensive as it iterates over the whole trie.
793 """
794 return sum(1 for _ in self.itervalues())
796 def __bool__(self):
797 return self._root.value is not _EMPTY or bool(self._root.children)
799 __nonzero__ = __bool__
800 __hash__ = None
802 HAS_VALUE = 1
803 HAS_SUBTRIE = 2
805 def has_node(self, key):
806 """Returns whether given node is in the trie.
808 Return value is a bitwise or of ``HAS_VALUE`` and ``HAS_SUBTRIE``
809 constants indicating node has a value associated with it and that it is
810 a prefix of another existing key respectively. Both of those are
811 independent of each other and all of the four combinations are possible.
812 For example::
814 >>> import pygtrie
815 >>> t = pygtrie.StringTrie()
816 >>> t['foo/bar'] = 'Bar'
817 >>> t['foo/bar/baz'] = 'Baz'
818 >>> t.has_node('qux') == 0
819 True
820 >>> t.has_node('foo/bar/baz') == pygtrie.Trie.HAS_VALUE
821 True
822 >>> t.has_node('foo') == pygtrie.Trie.HAS_SUBTRIE
823 True
824 >>> t.has_node('foo/bar') == (pygtrie.Trie.HAS_VALUE |
825 ... pygtrie.Trie.HAS_SUBTRIE)
826 True
828 There are two higher level methods built on top of this one which give
829 easier interface for the information. :func:`Trie.has_key` returns
830 whether node has a value associated with it and :func:`Trie.has_subtrie`
831 checks whether node is a prefix. Continuing previous example::
833 >>> t.has_key('qux'), t.has_subtrie('qux')
834 (False, False)
835 >>> t.has_key('foo/bar/baz'), t.has_subtrie('foo/bar/baz')
836 (True, False)
837 >>> t.has_key('foo'), t.has_subtrie('foo')
838 (False, True)
839 >>> t.has_key('foo/bar'), t.has_subtrie('foo/bar')
840 (True, True)
842 Args:
843 key: A key to look for.
845 Returns:
846 Non-zero if node exists and if it does a bit-field denoting whether
847 it has a value associated with it and whether it has a subtrie.
848 """
849 try:
850 node, _ = self._get_node(key)
851 except KeyError:
852 return 0
853 return ((self.HAS_VALUE * (node.value is not _EMPTY)) |
854 (self.HAS_SUBTRIE * bool(node.children)))
856 def has_key(self, key):
857 """Indicates whether given key has value associated with it.
859 See :func:`Trie.has_node` for more detailed documentation.
860 """
861 return bool(self.has_node(key) & self.HAS_VALUE)
863 def has_subtrie(self, key):
864 """Returns whether given key is a prefix of another key in the trie.
866 See :func:`Trie.has_node` for more detailed documentation.
867 """
868 return bool(self.has_node(key) & self.HAS_SUBTRIE)
870 @staticmethod
871 def _slice_maybe(key_or_slice):
872 """Checks whether argument is a slice or a plain key.
874 Args:
875 key_or_slice: A key or a slice to test.
877 Returns:
878 ``(key, is_slice)`` tuple. ``is_slice`` indicates whether
879 ``key_or_slice`` is a slice and ``key`` is either ``key_or_slice``
880 itself (if it's not a slice) or slice's start position.
882 Raises:
883 TypeError: If ``key_or_slice`` is a slice whose stop or step are not
884 ``None`` In other words, only ``[key:]`` slices are valid.
885 """
886 if isinstance(key_or_slice, slice):
887 if key_or_slice.stop is not None or key_or_slice.step is not None:
888 raise TypeError(key_or_slice)
889 return key_or_slice.start, True
890 return key_or_slice, False
892 def __getitem__(self, key_or_slice):
893 """Returns value associated with given key or raises KeyError.
895 When argument is a single key, value for that key is returned (or
896 :class:`KeyError` exception is thrown if the node does not exist or has
897 no value associated with it).
899 When argument is a slice, it must be one with only `start` set in which
900 case the access is identical to :func:`Trie.itervalues` invocation with
901 prefix argument.
903 Example:
905 >>> import pygtrie
906 >>> t = pygtrie.StringTrie()
907 >>> t['foo/bar'] = 'Bar'
908 >>> t['foo/baz'] = 'Baz'
909 >>> t['qux'] = 'Qux'
910 >>> t['foo/bar']
911 'Bar'
912 >>> sorted(t['foo':])
913 ['Bar', 'Baz']
914 >>> t['foo'] # doctest: +IGNORE_EXCEPTION_DETAIL
915 Traceback (most recent call last):
916 ...
917 ShortKeyError: 'foo'
919 Args:
920 key_or_slice: A key or a slice to look for.
922 Returns:
923 If a single key is passed, a value associated with given key. If
924 a slice is passed, a generator of values in specified subtrie.
926 Raises:
927 ShortKeyError: If the key has no value associated with it but is
928 a prefix of some key with a value. Note that
929 :class:`ShortKeyError` is subclass of :class:`KeyError`.
930 KeyError: If key has no value associated with it nor is a prefix of
931 an existing key.
932 TypeError: If ``key_or_slice`` is a slice but it's stop or step are
933 not ``None``.
934 """
935 if self._slice_maybe(key_or_slice)[1]:
936 return self.itervalues(key_or_slice.start)
937 node, _ = self._get_node(key_or_slice)
938 if node.value is _EMPTY:
939 raise ShortKeyError(key_or_slice)
940 return node.value
942 def __setitem__(self, key_or_slice, value):
943 """Sets value associated with given key.
945 If `key_or_slice` is a key, simply associate it with given value. If it
946 is a slice (which must have `start` set only), it in addition clears any
947 subtrie that might have been attached to particular key. For example::
949 >>> import pygtrie
950 >>> t = pygtrie.StringTrie()
951 >>> t['foo/bar'] = 'Bar'
952 >>> t['foo/baz'] = 'Baz'
953 >>> sorted(t.keys())
954 ['foo/bar', 'foo/baz']
955 >>> t['foo':] = 'Foo'
956 >>> t.keys()
957 ['foo']
959 Args:
960 key_or_slice: A key to look for or a slice. If it is a slice, the
961 whole subtrie (if present) will be replaced by a single node
962 with given value set.
963 value: Value to set.
965 Raises:
966 TypeError: If key is a slice whose stop or step are not None.
967 """
968 key, is_slice = self._slice_maybe(key_or_slice)
969 node = self._set_node(key, value)
970 if is_slice:
971 node.children = _EMPTY
973 def setdefault(self, key, default=None):
974 """Sets value of a given node if not set already. Also returns it.
976 In contrast to :func:`Trie.__setitem__`, this method does not accept
977 slice as a key.
978 """
979 return self._set_node(key, default, only_if_missing=True).value
981 @staticmethod
982 def _pop_value(trace):
983 """Removes value from given node and removes any empty nodes.
985 Args:
986 trace: Trace to the node to cleanup as returned by
987 :func:`Trie._get_node`. The last element of the trace denotes
988 the node to get value of.
990 Returns:
991 Value which was held in the node at the end of specified trace.
992 This may be _EMPTY if the node didn’t have a value in the first
993 place.
994 """
995 i = len(trace) - 1 # len(path) >= 1 since root is always there
996 step, node = trace[i]
997 value, node.value = node.value, _EMPTY
998 while i and node.value is _EMPTY and not node.children:
999 i -= 1
1000 parent_step, parent = trace[i]
1001 parent.children.delete(parent, step)
1002 step, node = parent_step, parent
1003 return value
1005 def pop(self, key, default=_EMPTY):
1006 """Deletes value associated with given key and returns it.
1008 Args:
1009 key: A key to look for.
1010 default: If specified, value that will be returned if given key has
1011 no value associated with it. If not specified, method will
1012 throw KeyError in such cases.
1014 Returns:
1015 Removed value, if key had value associated with it, or ``default``
1016 (if given).
1018 Raises:
1019 ShortKeyError: If ``default`` has not been specified and the key has
1020 no value associated with it but is a prefix of some key with
1021 a value. Note that :class:`ShortKeyError` is subclass of
1022 :class:`KeyError`.
1023 KeyError: If default has not been specified and key has no value
1024 associated with it nor is a prefix of an existing key.
1025 """
1026 try:
1027 _, trace = self._get_node(key)
1028 except KeyError:
1029 if default is not _EMPTY:
1030 return default
1031 raise
1032 value = self._pop_value(trace)
1033 if value is not _EMPTY:
1034 return value
1035 if default is not _EMPTY:
1036 return default
1037 raise ShortKeyError()
1039 def popitem(self):
1040 """Deletes an arbitrary value from the trie and returns it.
1042 There is no guarantee as to which item is deleted and returned. Neither
1043 in respect to its lexicographical nor topological order.
1045 Returns:
1046 ``(key, value)`` tuple indicating deleted key.
1048 Raises:
1049 KeyError: If the trie is empty.
1050 """
1051 if not self:
1052 raise KeyError()
1053 node = self._root
1054 trace = [(None, node)]
1055 while node.value is _EMPTY:
1056 step, node = next(node.children.iteritems())
1057 trace.append((step, node))
1058 key = self._key_from_path((step for step, _ in trace[1:]))
1059 return key, self._pop_value(trace)
1061 def __delitem__(self, key_or_slice):
1062 """Deletes value associated with given key or raises KeyError.
1064 If argument is a key, value associated with it is deleted. If the key
1065 is also a prefix, its descendents are not affected. On the other hand,
1066 if the argument is a slice (in which case it must have only start set),
1067 the whole subtrie is removed. For example::
1069 >>> import pygtrie
1070 >>> t = pygtrie.StringTrie()
1071 >>> t['foo'] = 'Foo'
1072 >>> t['foo/bar'] = 'Bar'
1073 >>> t['foo/bar/baz'] = 'Baz'
1074 >>> del t['foo/bar']
1075 >>> t.keys()
1076 ['foo', 'foo/bar/baz']
1077 >>> del t['foo':]
1078 >>> t.keys()
1079 []
1081 Args:
1082 key_or_slice: A key to look for or a slice. If key is a slice, the
1083 whole subtrie will be removed.
1085 Raises:
1086 ShortKeyError: If the key has no value associated with it but is
1087 a prefix of some key with a value. This is not thrown if
1088 key_or_slice is a slice -- in such cases, the whole subtrie is
1089 removed. Note that :class:`ShortKeyError` is subclass of
1090 :class:`KeyError`.
1091 KeyError: If key has no value associated with it nor is a prefix of
1092 an existing key.
1093 TypeError: If key is a slice whose stop or step are not ``None``.
1094 """
1095 key, is_slice = self._slice_maybe(key_or_slice)
1096 node, trace = self._get_node(key)
1097 if is_slice:
1098 node.children = _EMPTY
1099 elif node.value is _EMPTY:
1100 raise ShortKeyError(key)
1101 self._pop_value(trace)
1103 class _NoneStep(object):
1104 """Representation of a non-existent step towards non-existent node."""
1106 __slots__ = ()
1108 def __bool__(self):
1109 return False
1110 __nonzero__ = __bool__
1112 def get(self, default=None):
1113 return default
1115 is_set = has_subtrie = property(__bool__)
1116 key = value = property(lambda self: None)
1118 def __getitem__(self, index):
1119 """Makes object appear like a (key, value) tuple.
1121 This is deprecated and for backwards-compatibility only. Prefer
1122 using ``key`` and ``value`` properties directly.
1124 Args:
1125 index: Element index to return. Zero for key, one for value.
1127 Returns:
1128 ``self.key`` if index is ``0``, ``self.value`` if it's ``1``.
1129 Otherwise raises an IndexError exception.
1131 Raises:
1132 IndexError: if index is not 0 or 1.
1133 KeyError: if index is 1 but node has no value assigned.
1134 """
1135 if index == 0:
1136 return self.key
1137 if index == 1:
1138 return self.value
1139 raise IndexError('index out of range')
1141 def __repr__(self):
1142 return '(None Step)'
1144 class _Step(_NoneStep):
1145 """Representation of a single step on a path towards particular node."""
1147 __slots__ = ('_trie', '_path', '_pos', '_node', '__key')
1149 def __init__(self, trie, path, pos, node):
1150 self._trie = trie
1151 self._path = path
1152 self._pos = pos
1153 self._node = node
1155 def __bool__(self):
1156 return True
1157 __nonzero__ = __bool__
1159 @property
1160 def is_set(self):
1161 """Returns whether the node has value assigned to it."""
1162 return self._node.value is not _EMPTY
1164 @property
1165 def has_subtrie(self):
1166 """Returns whether the node has any children."""
1167 return bool(self._node.children)
1169 def get(self, default=None):
1170 """Returns node's value or the default if value is not assigned."""
1171 v = self._node.value
1172 return default if v is _EMPTY else v
1174 def set(self, value):
1175 """Deprecated. Use ``step.value = value`` instead."""
1176 self._node.value = value
1178 def setdefault(self, value):
1179 """Assigns value to the node if one is not set then returns it."""
1180 if self._node.value is _EMPTY:
1181 self._node.value = value
1182 return self._node.value
1184 def __repr__(self):
1185 return '(%r: %r)' % (self.key, self.value)
1187 @property
1188 def key(self):
1189 """Returns key of the node."""
1190 if not hasattr(self, '_Step__key'):
1191 # pylint:disable=protected-access,attribute-defined-outside-init
1192 self.__key = self._trie._key_from_path(self._path[:self._pos])
1193 return self.__key
1195 @property
1196 def value(self):
1197 """Returns node's value or raises KeyError."""
1198 v = self._node.value
1199 if v is _EMPTY:
1200 raise ShortKeyError(self.key)
1201 return v
1203 @value.setter
1204 def value(self, value):
1205 self._node.value = value
1207 _NONE_STEP = _NoneStep()
1209 def walk_towards(self, key):
1210 """Yields nodes on the path to given node.
1212 Args:
1213 key: Key of the node to look for.
1215 Yields:
1216 :class:`pygtrie.Trie._Step` objects which can be used to extract or
1217 set node's value as well as get node's key.
1219 When representing nodes with assigned values, the objects can be
1220 treated as ``(k, value)`` pairs denoting keys with associated values
1221 encountered on the way towards the specified key. This is
1222 deprecated, prefer using ``key`` and ``value`` properties or ``get``
1223 method of the object.
1225 Raises:
1226 KeyError: If node with given key does not exist. It's all right if
1227 they value is not assigned to the node provided it has a child
1228 node. Because the method is a generator, the exception is
1229 raised only once a missing node is encountered.
1230 """
1231 node = self._root
1232 path = self.__path_from_key(key)
1233 pos = 0
1234 while True:
1235 yield self._Step(self, path, pos, node)
1236 if pos == len(path):
1237 break
1238 # pylint thinks node.children is always _NoChildren and thus that
1239 # we’re assigning None here; pylint: disable=assignment-from-none
1240 node = node.children.get(path[pos])
1241 if node is None:
1242 raise KeyError(key)
1243 pos += 1
1245 def prefixes(self, key):
1246 """Walks towards the node specified by key and yields all found items.
1248 Example:
1250 >>> import pygtrie
1251 >>> t = pygtrie.StringTrie()
1252 >>> t['foo'] = 'Foo'
1253 >>> t['foo/bar/baz'] = 'Baz'
1254 >>> list(t.prefixes('foo/bar/baz/qux'))
1255 [('foo': 'Foo'), ('foo/bar/baz': 'Baz')]
1256 >>> list(t.prefixes('does/not/exist'))
1257 []
1259 Args:
1260 key: Key to look for.
1262 Yields:
1263 :class:`pygtrie.Trie._Step` objects which can be used to extract or
1264 set node's value as well as get node's key.
1266 The objects can be treated as ``(k, value)`` pairs denoting keys
1267 with associated values encountered on the way towards the specified
1268 key. This is deprecated, prefer using ``key`` and ``value``
1269 properties of the object.
1270 """
1271 try:
1272 for step in self.walk_towards(key):
1273 if step.is_set:
1274 yield step
1275 except KeyError:
1276 pass
1278 def shortest_prefix(self, key):
1279 """Finds the shortest prefix of a key with a value.
1281 This is roughly equivalent to taking the first object yielded by
1282 :func:`Trie.prefixes` with additional handling for situations when no
1283 prefixes are found.
1285 Example:
1287 >>> import pygtrie
1288 >>> t = pygtrie.StringTrie()
1289 >>> t['foo'] = 'Foo'
1290 >>> t['foo/bar/baz'] = 'Baz'
1291 >>> t.shortest_prefix('foo/bar/baz/qux')
1292 ('foo': 'Foo')
1293 >>> t.shortest_prefix('foo/bar/baz/qux').key
1294 'foo'
1295 >>> t.shortest_prefix('foo/bar/baz/qux').value
1296 'Foo'
1297 >>> t.shortest_prefix('does/not/exist')
1298 (None Step)
1299 >>> bool(t.shortest_prefix('does/not/exist'))
1300 False
1302 Args:
1303 key: Key to look for.
1305 Returns:
1306 :class:`pygtrie.Trie._Step` object (which can be used to extract or
1307 set node's value as well as get node's key), or
1308 a :class:`pygtrie.Trie._NoneStep` object (which is falsy value
1309 simulating a _Step with ``None`` key and value) if no prefix is
1310 found.
1312 The object can be treated as ``(key, value)`` pair denoting key with
1313 associated value of the prefix. This is deprecated, prefer using
1314 ``key`` and ``value`` properties of the object.
1315 """
1316 return next(self.prefixes(key), self._NONE_STEP)
1318 def longest_prefix(self, key):
1319 """Finds the longest prefix of a key with a value.
1321 This is roughly equivalent to taking the last object yielded by
1322 :func:`Trie.prefixes` with additional handling for situations when no
1323 prefixes are found.
1325 Example:
1327 >>> import pygtrie
1328 >>> t = pygtrie.StringTrie()
1329 >>> t['foo'] = 'Foo'
1330 >>> t['foo/bar/baz'] = 'Baz'
1331 >>> t.longest_prefix('foo/bar/baz/qux')
1332 ('foo/bar/baz': 'Baz')
1333 >>> t.longest_prefix('foo/bar/baz/qux').key
1334 'foo/bar/baz'
1335 >>> t.longest_prefix('foo/bar/baz/qux').value
1336 'Baz'
1337 >>> t.longest_prefix('does/not/exist')
1338 (None Step)
1339 >>> bool(t.longest_prefix('does/not/exist'))
1340 False
1342 Args:
1343 key: Key to look for.
1345 Returns:
1346 :class:`pygtrie.Trie._Step` object (which can be used to extract or
1347 set node's value as well as get node's key), or
1348 a :class:`pygtrie.Trie._NoneStep` object (which is falsy value
1349 simulating a _Step with ``None`` key and value) if no prefix is
1350 found.
1352 The object can be treated as ``(key, value)`` pair denoting key with
1353 associated value of the prefix. This is deprecated, prefer using
1354 ``key`` and ``value`` properties of the object.
1355 """
1356 ret = self._NONE_STEP
1357 for ret in self.prefixes(key):
1358 pass
1359 return ret
1361 def strictly_equals(self, other):
1362 """Checks whether tries are equal with the same structure.
1364 This is stricter comparison than the one performed by equality operator.
1365 It not only requires for keys and values to be equal but also for the
1366 two tries to be of the same type and have the same structure.
1368 For example, for two :class:`pygtrie.StringTrie` objects to be equal,
1369 they need to have the same structure as well as the same separator as
1370 seen below:
1372 >>> import pygtrie
1373 >>> t0 = StringTrie({'foo/bar': 42}, separator='/')
1374 >>> t1 = StringTrie({'foo.bar': 42}, separator='.')
1375 >>> t0.strictly_equals(t1)
1376 False
1378 >>> t0 = StringTrie({'foo/bar.baz': 42}, separator='/')
1379 >>> t1 = StringTrie({'foo/bar.baz': 42}, separator='.')
1380 >>> t0 == t1
1381 True
1382 >>> t0.strictly_equals(t1)
1383 False
1385 Args:
1386 other: Other trie to compare to.
1388 Returns:
1389 Whether the two tries are the same type and have the same structure.
1390 """
1391 if self is other:
1392 return True
1393 if type(self) != type(other):
1394 return False
1395 result = self._eq_impl(other)
1396 if result is NotImplemented:
1397 return False
1398 else:
1399 return result
1401 def __eq__(self, other):
1402 """Compares this trie’s mapping with another mapping.
1404 Note that this method doesn’t take trie’s structure into consideration.
1405 What matters is whether keys and values in both mappings are the same.
1406 This may lead to unexpected results, for example:
1408 >>> import pygtrie
1409 >>> t0 = StringTrie({'foo/bar': 42}, separator='/')
1410 >>> t1 = StringTrie({'foo.bar': 42}, separator='.')
1411 >>> t0 == t1
1412 False
1414 >>> t0 = StringTrie({'foo/bar.baz': 42}, separator='/')
1415 >>> t1 = StringTrie({'foo/bar.baz': 42}, separator='.')
1416 >>> t0 == t1
1417 True
1419 >>> t0 = Trie({'foo': 42})
1420 >>> t1 = CharTrie({'foo': 42})
1421 >>> t0 == t1
1422 False
1424 This behaviour is required to maintain consistency with Mapping
1425 interface and its __eq__ method. For example, this implementation
1426 maintains transitivity of the comparison:
1428 >>> t0 = StringTrie({'foo/bar.baz': 42}, separator='/')
1429 >>> d = {'foo/bar.baz': 42}
1430 >>> t1 = StringTrie({'foo/bar.baz': 42}, separator='.')
1431 >>> t0 == d
1432 True
1433 >>> d == t1
1434 True
1435 >>> t0 == t1
1436 True
1438 >>> t0 = Trie({'foo': 42})
1439 >>> d = {'foo': 42}
1440 >>> t1 = CharTrie({'foo': 42})
1441 >>> t0 == d
1442 False
1443 >>> d == t1
1444 True
1445 >>> t0 == t1
1446 False
1448 Args:
1449 other: Other object to compare to.
1451 Returns:
1452 ``NotImplemented`` if this method does not know how to perform the
1453 comparison or a ``bool`` denoting whether the two objects are equal
1454 or not.
1455 """
1456 if self is other:
1457 return True
1458 if type(other) == type(self):
1459 result = self._eq_impl(other)
1460 if result is not NotImplemented:
1461 return result
1462 return super(Trie, self).__eq__(other)
1464 def _eq_impl(self, other):
1465 return self._root.equals(other._root) # pylint: disable=protected-access
1467 def __ne__(self, other):
1468 return not self == other
1470 def _str_items(self, fmt='%s: %s'):
1471 return ', '.join(fmt % item for item in self.iteritems())
1473 def __str__(self):
1474 return '%s(%s)' % (type(self).__name__, self._str_items())
1476 def __repr__(self):
1477 return '%s([%s])' % (type(self).__name__, self._str_items('(%r, %r)'))
1479 def __path_from_key(self, key):
1480 """Converts a user visible key object to internal path representation.
1482 Args:
1483 key: User supplied key or ``_EMPTY``.
1485 Returns:
1486 An empty tuple if ``key`` was ``_EMPTY``, otherwise whatever
1487 :func:`Trie._path_from_key` returns.
1489 Raises:
1490 TypeError: If ``key`` is of invalid type.
1491 """
1492 return () if key is _EMPTY else self._path_from_key(key)
1494 def _path_from_key(self, key):
1495 """Converts a user visible key object to internal path representation.
1497 The default implementation simply returns key.
1499 Args:
1500 key: User supplied key.
1502 Returns:
1503 A path, which is an iterable of steps. Each step must be hashable.
1505 Raises:
1506 TypeError: If key is of invalid type.
1507 """
1508 return key
1510 def _key_from_path(self, path):
1511 """Converts an internal path into a user visible key object.
1513 The default implementation creates a tuple from the path.
1515 Args:
1516 path: Internal path representation.
1517 Returns:
1518 A user visible key object.
1519 """
1520 return tuple(path)
1522 def traverse(self, node_factory, prefix=_EMPTY):
1523 """Traverses the tree using node_factory object.
1525 node_factory is a callable which accepts (path_conv, path, children,
1526 value=...) arguments, where path_conv is a lambda converting path
1527 representation to key, path is the path to this node, children is an
1528 iterable of children nodes constructed by node_factory, optional value
1529 is the value associated with the path.
1531 node_factory's children argument is an iterator which has a few
1532 consequences:
1534 * To traverse into node's children, the object must be iterated over.
1535 This can by accomplished by a simple ``children = list(children)``
1536 statement.
1537 * Ignoring the argument allows node_factory to stop the traversal from
1538 going into the children of the node. In other words, whole subtries
1539 can be removed from traversal if node_factory chooses so.
1540 * If children is stored as is (i.e. as a iterator) when it is iterated
1541 over later on it may see an inconsistent state of the trie if it has
1542 changed between invocation of this method and the iteration.
1544 However, to allow constant-time determination whether the node has
1545 children or not, the iterator implements bool conversion such that
1546 ``has_children = bool(children)`` will tell whether node has children
1547 without iterating over them. (Note that ``bool(children)`` will
1548 continue returning ``True`` even if the iterator has been iterated
1549 over).
1551 :func:`Trie.traverse` has two advantages over :func:`Trie.iteritems` and
1552 similar methods:
1554 1. it allows subtries to be skipped completely when going through the
1555 list of nodes based on the property of the parent node; and
1557 2. it represents structure of the trie directly making it easy to
1558 convert structure into a different representation.
1560 For example, the below snippet prints all files in current directory
1561 counting how many HTML files were found but ignores hidden files and
1562 directories (i.e. those whose names start with a dot)::
1564 import os
1565 import pygtrie
1567 t = pygtrie.StringTrie(separator=os.sep)
1569 # Construct a trie with all files in current directory and all
1570 # of its sub-directories. Files get set a True value.
1571 # Directories are represented implicitly by being prefixes of
1572 # files.
1573 for root, _, files in os.walk('.'):
1574 for name in files: t[os.path.join(root, name)] = True
1576 def traverse_callback(path_conv, path, children, is_file=False):
1577 if path and path[-1] != '.' and path[-1][0] == '.':
1578 # Ignore hidden directory (but accept root node and '.')
1579 return 0
1580 elif is_file:
1581 print path_conv(path)
1582 return int(path[-1].endswith('.html'))
1583 else:
1584 # Otherwise, it's a directory. Traverse into children.
1585 return sum(children)
1587 print t.traverse(traverse_callback)
1589 As documented, ignoring the children argument causes subtrie to be
1590 omitted and not walked into.
1592 In the next example, the trie is converted to a tree representation
1593 where child nodes include a pointer to their parent. As before, hidden
1594 files and directories are ignored::
1596 import os
1597 import pygtrie
1599 t = pygtrie.StringTrie(separator=os.sep)
1600 for root, _, files in os.walk('.'):
1601 for name in files: t[os.path.join(root, name)] = True
1603 class File(object):
1604 def __init__(self, name):
1605 self.name = name
1606 self.parent = None
1608 class Directory(File):
1609 def __init__(self, name, children):
1610 super(Directory, self).__init__(name)
1611 self._children = children
1612 for child in children:
1613 child.parent = self
1615 def traverse_callback(path_conv, path, children, is_file=False):
1616 if not path or path[-1] == '.' or path[-1][0] != '.':
1617 if is_file:
1618 return File(path[-1])
1619 children = filter(None, children)
1620 return Directory(path[-1] if path else '', children)
1622 root = t.traverse(traverse_callback)
1624 Note: Unlike iterators, when used on a deep trie, traverse method is
1625 prone to rising a RuntimeError exception when Python's maximum recursion
1626 depth is reached. This can be addressed by not iterating over children
1627 inside of the node_factory. For example, the below code converts a trie
1628 into an undirected graph using adjacency list representation::
1630 def undirected_graph_from_trie(t):
1631 '''Converts trie into a graph and returns its nodes.'''
1633 Node = collections.namedtuple('Node', 'path neighbours')
1635 class Builder(object):
1636 def __init__(self, path_conv, path, children, _=None):
1637 self.node = Node(path_conv(path), [])
1638 self.children = children
1639 self.parent = None
1641 def build(self, queue):
1642 for builder in self.children:
1643 builder.parent = self.node
1644 queue.append(builder)
1645 if self.parent:
1646 self.parent.neighbours.append(self.node)
1647 self.node.neighbours.append(self.parent)
1648 return self.node
1650 nodes = [t.traverse(Builder)]
1651 i = 0
1652 while i < len(nodes):
1653 nodes[i] = nodes[i].build(nodes)
1654 i += 1
1655 return nodes
1657 Args:
1658 node_factory: Makes opaque objects from the keys and values of the
1659 trie.
1660 prefix: Prefix for node to start traversal, by default starts at
1661 root.
1663 Returns:
1664 Node object constructed by node_factory corresponding to the root
1665 node.
1666 """
1667 node, _ = self._get_node(prefix)
1668 return node.traverse(node_factory, self._key_from_path,
1669 list(self.__path_from_key(prefix)),
1670 self._iteritems)
1672 traverse.uses_bool_convertible_children = True
1674class CharTrie(Trie):
1675 """A variant of a :class:`pygtrie.Trie` which accepts strings as keys.
1677 The only difference between :class:`pygtrie.CharTrie` and
1678 :class:`pygtrie.Trie` is that when :class:`pygtrie.CharTrie` returns keys
1679 back to the client (for instance when :func:`Trie.keys` method is called),
1680 those keys are returned as strings.
1682 Common example where this class can be used is a dictionary of words in
1683 a natural language. For example::
1685 >>> import pygtrie
1686 >>> t = pygtrie.CharTrie()
1687 >>> t['wombat'] = True
1688 >>> t['woman'] = True
1689 >>> t['man'] = True
1690 >>> t['manhole'] = True
1691 >>> t.has_subtrie('wo')
1692 True
1693 >>> t.has_key('man')
1694 True
1695 >>> t.has_subtrie('man')
1696 True
1697 >>> t.has_subtrie('manhole')
1698 False
1699 """
1701 def _key_from_path(self, path):
1702 return ''.join(path)
1705class StringTrie(Trie):
1706 """:class:`pygtrie.Trie` variant accepting strings with a separator as keys.
1708 The trie accepts strings as keys which are split into components using
1709 a separator specified during initialisation (forward slash, i.e. ``/``, by
1710 default).
1712 Common example where this class can be used is when keys are paths. For
1713 example, it could map from a path to a request handler::
1715 import pygtrie
1717 def handle_root(): pass
1718 def handle_admin(): pass
1719 def handle_admin_images(): pass
1721 handlers = pygtrie.StringTrie()
1722 handlers[''] = handle_root
1723 handlers['/admin'] = handle_admin
1724 handlers['/admin/images'] = handle_admin_images
1726 request_path = '/admin/images/foo'
1728 handler = handlers.longest_prefix(request_path)
1729 """
1731 def __init__(self, *args, **kwargs): # pylint: disable=differing-param-doc
1732 """Initialises the trie.
1734 Except for a ``separator`` named argument, all other arguments are
1735 interpreted the same way :func:`Trie.update` interprets them.
1737 Args:
1738 *args: Passed to super class initialiser.
1739 **kwargs: Passed to super class initialiser.
1740 separator: A separator to use when splitting keys into paths used by
1741 the trie. "/" is used if this argument is not specified. This
1742 named argument is not specified on the function's prototype
1743 because of Python's limitations.
1745 Raises:
1746 TypeError: If ``separator`` is not a string.
1747 ValueError: If ``separator`` is empty.
1748 """
1749 separator = kwargs.pop('separator', '/')
1750 if not isinstance(separator, getattr(__builtins__, 'basestring', str)):
1751 raise TypeError('separator must be a string')
1752 if not separator:
1753 raise ValueError('separator can not be empty')
1754 self._separator = separator
1755 super(StringTrie, self).__init__(*args, **kwargs)
1757 @classmethod
1758 def fromkeys(cls, keys, value=None, separator='/'): # pylint: disable=arguments-differ
1759 trie = cls(separator=separator)
1760 for key in keys:
1761 trie[key] = value
1762 return trie
1764 @classmethod
1765 def _merge_impl(cls, dst, src, overwrite):
1766 if not isinstance(dst, StringTrie):
1767 raise TypeError('%s cannot be merged into a %s' % (
1768 type(src).__name__, type(dst).__name__))
1769 super(StringTrie, cls)._merge_impl(dst, src, overwrite=overwrite)
1771 def __str__(self):
1772 if not self:
1773 return '%s(separator=%s)' % (type(self).__name__, self._separator)
1774 return '%s(%s, separator=%s)' % (
1775 type(self).__name__, self._str_items(), self._separator)
1777 def __repr__(self):
1778 return '%s([%s], separator=%r)' % (
1779 type(self).__name__, self._str_items('(%r, %r)'), self._separator)
1781 def _eq_impl(self, other):
1782 # If separators differ, fall back to slow generic comparison. This is
1783 # because we want StringTrie(foo/bar.baz: 42, separator=/) compare equal
1784 # to StringTrie(foo/bar.baz: 42, separator=.) even though they have
1785 # different trie structure.
1786 if self._separator != other._separator: # pylint: disable=protected-access
1787 return NotImplemented
1788 return super(StringTrie, self)._eq_impl(other)
1790 def _path_from_key(self, key):
1791 return key.split(self._separator)
1793 def _key_from_path(self, path):
1794 return self._separator.join(path)
1797class PrefixSet(_abc.MutableSet):
1798 """A set of prefixes.
1800 :class:`pygtrie.PrefixSet` works similar to a normal set except it is said
1801 to contain a key if the key or it's prefix is stored in the set. For
1802 instance, if "foo" is added to the set, the set contains "foo" as well as
1803 "foobar".
1805 The set supports addition of elements but does *not* support removal of
1806 elements. This is because there's no obvious consistent and intuitive
1807 behaviour for element deletion.
1808 """
1810 def __init__(self, iterable=(), factory=Trie, **kwargs):
1811 """Initialises the prefix set.
1813 Args:
1814 iterable: A sequence of keys to add to the set.
1815 factory: A function used to create a trie used by the
1816 :class:`pygtrie.PrefixSet`.
1817 kwargs: Additional keyword arguments passed to the factory function.
1818 """
1819 super(PrefixSet, self).__init__()
1820 self._trie = factory(**kwargs)
1821 for key in iterable:
1822 self.add(key)
1824 def copy(self):
1825 """Returns a shallow copy of the object."""
1826 return self.__copy__()
1828 def __copy__(self):
1829 # pylint: disable=protected-access
1830 cpy = self.__class__()
1831 cpy.__dict__ = self.__dict__.copy()
1832 cpy._trie = self._trie.__copy__()
1833 return cpy
1835 def __deepcopy__(self, memo):
1836 # pylint: disable=protected-access
1837 cpy = self.__class__()
1838 cpy.__dict__ = self.__dict__.copy()
1839 cpy._trie = self._trie.__deepcopy__(memo)
1840 return cpy
1842 def clear(self):
1843 """Removes all keys from the set."""
1844 self._trie.clear()
1846 def __contains__(self, key):
1847 """Checks whether set contains key or its prefix."""
1848 return bool(self._trie.shortest_prefix(key)[1])
1850 def __iter__(self):
1851 """Return iterator over all prefixes in the set.
1853 See :func:`PrefixSet.iter` method for more info.
1854 """
1855 return self._trie.iterkeys()
1857 def iter(self, prefix=_EMPTY):
1858 """Iterates over all keys in the set optionally starting with a prefix.
1860 Since a key does not have to be explicitly added to the set to be an
1861 element of the set, this method does not iterate over all possible keys
1862 that the set contains, but only over the shortest set of prefixes of all
1863 the keys the set contains.
1865 For example, if "foo" has been added to the set, the set contains also
1866 "foobar", but this method will *not* iterate over "foobar".
1868 If ``prefix`` argument is given, method will iterate over keys with
1869 given prefix only. The keys yielded from the function if prefix is
1870 given does not have to be a subset (in mathematical sense) of the keys
1871 yielded when there is not prefix. This happens, if the set contains
1872 a prefix of the given prefix.
1874 For example, if only "foo" has been added to the set, iter method called
1875 with no arguments will yield "foo" only. However, when called with
1876 "foobar" argument, it will yield "foobar" only.
1877 """
1878 if prefix is _EMPTY:
1879 return iter(self)
1880 if self._trie.has_node(prefix):
1881 return self._trie.iterkeys(prefix=prefix)
1882 if prefix in self:
1883 # Make sure the type of returned keys is consistent.
1884 # pylint: disable=protected-access
1885 return (
1886 self._trie._key_from_path(self._trie._path_from_key(prefix)),)
1887 return ()
1889 def __len__(self):
1890 """Returns number of keys stored in the set.
1892 Since a key does not have to be explicitly added to the set to be an
1893 element of the set, this method does not count over all possible keys
1894 that the set contains (since that would be infinity), but only over the
1895 shortest set of prefixes of all the keys the set contains.
1897 For example, if "foo" has been added to the set, the set contains also
1898 "foobar", but this method will *not* count "foobar".
1900 """
1901 return len(self._trie)
1903 def add(self, value):
1904 """Adds given value to the set.
1906 If the set already contains prefix of the value being added, this
1907 operation has no effect. If the value being added is a prefix of some
1908 existing values in the set, those values are deleted and replaced by
1909 a single entry for the value being added.
1911 For example, if the set contains value "foo" adding a value "foobar"
1912 does not change anything. On the other hand, if the set contains values
1913 "foobar" and "foobaz", adding a value "foo" will replace those two
1914 values with a single value "foo".
1916 This makes a difference when iterating over the values or counting
1917 number of values. Counter intuitively, adding of a value can *decrease*
1918 size of the set.
1920 Args:
1921 value: Value to add.
1922 """
1923 # We're friends with Trie; pylint: disable=protected-access
1924 self._trie._set_node_if_no_prefix(value)
1926 def discard(self, value):
1927 """Raises NotImplementedError."""
1928 raise NotImplementedError(
1929 'Removing values from PrefixSet is not implemented.')
1931 def remove(self, value):
1932 """Raises NotImplementedError."""
1933 raise NotImplementedError(
1934 'Removing values from PrefixSet is not implemented.')
1936 def pop(self):
1937 """Raises NotImplementedError."""
1938 raise NotImplementedError(
1939 'Removing values from PrefixSet is not implemented.')