Home | History | Annotate | Download | only in trie 
      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