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        keys = super().keys()
11
12        if prefix is None:
13            return set(keys)
14
15        # Python 2.6: no set comprehensions
16        return set([x for x in keys if x.startswith(prefix)])
17
18    def has_keys_with_prefix(self, prefix):
19        for key in self.keys():
20            if key.startswith(prefix):
21                return True
22
23        return False
24
25    def longest_prefix(self, prefix):
26        if prefix in self:
27            return prefix
28
29        for i in range(1, len(prefix) + 1):
30            if prefix[:-i] in self:
31                return prefix[:-i]
32
33        raise KeyError(prefix)
34
35    def longest_prefix_item(self, prefix):
36        lprefix = self.longest_prefix(prefix)
37        return (lprefix, self[lprefix])
38