Welcome, guest | Sign In | My Account | Store | Cart

Storage for store information about prefixes (Python recipe) by Dmitry Vasiliev
ActiveState Code (http://code.activestate.com/recipes/335555/)

Storage for store information about domains determined by key prefixes. See the docsting for details.

Python, 42 lines
Download
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class PrefixStorage(object):
    """Storage for store information about prefixes.

    >>> s = PrefixStorage()

    First we save information for some prefixes:

    >>> s["123"] = "123 domain"
    >>> s["12"] = "12 domain"

    Then we can retrieve prefix information by full key
    (longest prefix always win):

    >>> s.getByPrefix("123456")
    '123 domain'
    >>> s.getByPrefix("12456")
    '12 domain'

    If no prefix has been found then getByPrefix() returns default value:

    >>> s.getByPrefix("13456", "None")
    'None'
    """

    def __init__(self):
        self._mapping = {}
        self._sizes = []

    def __setitem__(self, key, value):
        ln = len(key)
        if ln not in self._sizes:
            self._sizes.append(ln)
            self._sizes.sort()
            self._sizes.reverse()
        self._mapping[key] = value

    def getByPrefix(self, key, default=None):
        for ln in self._sizes:
            k = key[:ln]
            if k in self._mapping:
                return self._mapping[k]
        return default
Tags: algorithms

2 comments

Andreas Kloss 19 years, 5 months ago  # | flag

subclass dict. PrefixStorage is ultimately a kind of dict, so it should subclass dict. By overriding the get, __getitem__ and __setitem__ methods one could create a drop-in-replacement, so that:

>>> x=prefixStorage()



>>> x['12'] = '1234Server'



>>> x['123'] = '12345andnowforsomethingcompletelydifferent'



>>> x['125']

'1234Server'

Dmitry Vasiliev (author) 19 years, 5 months ago  # | flag

just an algorithm example. If you want PrefixStorage subclass dict then it should override most of dict methods for maintaining self._sizes. Better way is to subclass UserDict.DictMixin. But I think you should always distinguish get/__getitem__ and getByPrefix, so:

>>> x.getByPrefix('125')
'1234Server'

but

>>> x.get('125', 'No such prefix')
'No such prefix'

BTW someone may set self._mapping on some persistent dict-like object.

Created by Dmitry Vasiliev on Mon, 15 Nov 2004 (PSF)
◄ Python recipes (4591) ►
◄ Dmitry Vasiliev's recipes (9) ►

Required Modules

  • (none specified)

Other Information and Tasks