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
--
http://mail.python.org/mailman/listinfo/python-list
