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