What is the best way to store integers mapped to strings so that the keys can be ranges in python?

Question

What would be the best way to store (non-mutable) data that is of format:

doodahs = {
0-256: "FOO",
257: "BAR",
258: "FISH",
279: "MOOSE",
280-65534: "Darth Vader",
65535: "Death to all newbies" }

I have a relatively large amount of these type of data sets, so something that I can define the way of dictionaries (or close to it) and access via indexes.

Oh, and this is on Python 2.4, so please give really really good reason for upgrade if you want me to use a newer version (and I'll go for 3 :)

Answer 1

I'd split the range into a tuple and then inside your class, keep the items in an ordered list. You can use the bisect module to make inserts O(n) and lookup O(logn).

If you are converting a dict to your new class, you can build an unordered list and sort it at the end

doodahs = [
    (0, 256, "FOO"),
    (257, 257, "BAR"),
    (258, 258, "FISH"),
    (279, 279, "MOOSE"),
    (280, 65534, "Darth Vader"),
    (65535, 65535, "Death to all newbies")]

Your __getitem__ might work something like this:

def __getitem__(self, key):
    return self.doodahs[bisect.bisect(self.doodahs, (key,))]

__setitem__ might be something like this:

def __setitem__(self,range,value):
    bisect.insort(self.doodahs, range+(value,))

Answer 2

If your integers have an upper bound that's less than a few million, then you simply expand the ranges into individual values.

class RangedDict( dict ):
    def addRange( self, iterator, value ):
        for k in iterator:
            self[k]= value

d= RangedDict()
d.addRange( xrange(0,257), "FOO" )
d[257]= "BAR"
d[258]= "FISH"
d[279]= "MOOSE"
d.addRange( xrange(280,65535), "Darth Vader" )
d[65535]= "Death to all newbies"

All your lookups work, and are instant.

Answer 3

class dict2(dict):
    def __init__(self,obj):
            dict.__init__(self,obj)
    def __getitem__(self,key):
            if self.has_key(key):
                    return super(dict2,self).__getitem__(key)
            else:
                    for k in self:
                            if '-' in k:
                                    [x,y] = str(k).split('-')
                                    if key in range(int(x),int(y)+1):
                                            return super(dict2,self).__getitem__(k)
                    return None


d = {"0-10":"HELLO"}
d2 = dict2(d)
print d,d2,d2["0-10"], d2[1]

Answer 4

Given that you don't have any "gaps" in your keys, why you just don't store the beginning of each segment and then lookup with bisect like suggested?

doodahs = (
    (0, "FOO"),
    (257, "BAR"),
    (258, "FISH"),
    (279, "MOOSE"),
    (280, "Darth Vader"),
    (65535, "Death to all newbies")
)