Any way to use a range as a key in a dictionary?

[andrew cooke]

andrew cooke wrote:
> i don't completely follow what you are doing, but i currently use the
> following to find a transition in a finite automaton for a regular
> expression, and i suspect it's similar to what you want.

i get the impression the original poster went away, and maybe they just
wanted dict.get(x, default) anyway, but i ended up needing this, so here
it is.  it makes a vague attempt to trade memory for lookup speed (which
will be in a tight loop) and is for open intervals (eg integer intervals,
not floats).

class IntervalMap(dict):
    '''
    Note - this is for open intervals!  This means it will not work as
    expected for continuous variables (which will overlap when two intervals
    share a single boundary value).  In other words, you cannot store
    (1,2) and (2,3) together because both contain 2.
    '''

    def __init__(self):
        # None is used as a flag to indicate that a new index is needed
        self.__index = None

    def index(self):
        '''
        Build the internal indices.  Called automatically when necessary.
        '''
        second = lambda x: x[1]
        self.__intervals = list(sorted(self.keys(), key=second))
        self.__index = list(map(second, self.__intervals))

    def __setitem__(self, interval, value):
        # these are rather inefficient, but perhaps useful during development
        assert None == self[interval[0]], 'Overlap'
        assert None == self[interval[1]], 'Overlap'
        self.__index = None
        super(IntervalMap, self).__setitem__(interval, value)

    def __getitem__(self, point):
        '''
        The argument here is a single value, not an interval.
        '''
        if self.__index is None:
            self.index()
        if self.__index:
            index = bisect_left(self.__index, point)
            if index < len(self.__index):
                # keep interval for identity on retrieval, just in case
                (a, b) = interval = self.__intervals[index]
                if a <= point <= b:
                    return super(IntervalMap, self).__getitem__(interval)
        return None

    def __delitem__(self, interval):
        self.__index = None
        super(IntervalMap, self).__delitem__(interval)

andrew