1 from __future__ import absolute_import, division, unicode_literals 2 3 from collections import Mapping 4 5 6 class 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