1from __future__ import absolute_import, division, unicode_literals
2
3from collections import Mapping
4
5
6class Trie(Mapping):
7    """Abstract base class for tries"""
8
9    def keys(self, prefix=None):
10        # pylint:disable=arguments-differ
11        keys = super(Trie, self).keys()
12
13        if prefix is None:
14            return set(keys)
15
16        # Python 2.6: no set comprehensions
17        return set([x for x in keys if x.startswith(prefix)])
18
19    def has_keys_with_prefix(self, prefix):
20        for key in self.keys():
21            if key.startswith(prefix):
22                return True
23
24        return False
25
26    def longest_prefix(self, prefix):
27        if prefix in self:
28            return prefix
29
30        for i in range(1, len(prefix) + 1):
31            if prefix[:-i] in self:
32                return prefix[:-i]
33
34        raise KeyError(prefix)
35
36    def longest_prefix_item(self, prefix):
37        lprefix = self.longest_prefix(prefix)
38        return (lprefix, self[lprefix])
39