|
import collections |
|
import functools |
|
import itertools |
|
import operator |
|
|
|
|
|
|
|
class DictStack(list, collections.abc.Mapping): |
|
""" |
|
A stack of dictionaries that behaves as a view on those dictionaries, |
|
giving preference to the last. |
|
|
|
>>> stack = DictStack([dict(a=1, c=2), dict(b=2, a=2)]) |
|
>>> stack['a'] |
|
2 |
|
>>> stack['b'] |
|
2 |
|
>>> stack['c'] |
|
2 |
|
>>> len(stack) |
|
3 |
|
>>> stack.push(dict(a=3)) |
|
>>> stack['a'] |
|
3 |
|
>>> set(stack.keys()) == set(['a', 'b', 'c']) |
|
True |
|
>>> set(stack.items()) == set([('a', 3), ('b', 2), ('c', 2)]) |
|
True |
|
>>> dict(**stack) == dict(stack) == dict(a=3, c=2, b=2) |
|
True |
|
>>> d = stack.pop() |
|
>>> stack['a'] |
|
2 |
|
>>> d = stack.pop() |
|
>>> stack['a'] |
|
1 |
|
>>> stack.get('b', None) |
|
>>> 'c' in stack |
|
True |
|
""" |
|
|
|
def __iter__(self): |
|
dicts = list.__iter__(self) |
|
return iter(set(itertools.chain.from_iterable(c.keys() for c in dicts))) |
|
|
|
def __getitem__(self, key): |
|
for scope in reversed(tuple(list.__iter__(self))): |
|
if key in scope: |
|
return scope[key] |
|
raise KeyError(key) |
|
|
|
push = list.append |
|
|
|
def __contains__(self, other): |
|
return collections.abc.Mapping.__contains__(self, other) |
|
|
|
def __len__(self): |
|
return len(list(iter(self))) |
|
|
|
|
|
|
|
class RangeMap(dict): |
|
""" |
|
A dictionary-like object that uses the keys as bounds for a range. |
|
Inclusion of the value for that range is determined by the |
|
key_match_comparator, which defaults to less-than-or-equal. |
|
A value is returned for a key if it is the first key that matches in |
|
the sorted list of keys. |
|
|
|
One may supply keyword parameters to be passed to the sort function used |
|
to sort keys (i.e. key, reverse) as sort_params. |
|
|
|
Let's create a map that maps 1-3 -> 'a', 4-6 -> 'b' |
|
|
|
>>> r = RangeMap({3: 'a', 6: 'b'}) # boy, that was easy |
|
>>> r[1], r[2], r[3], r[4], r[5], r[6] |
|
('a', 'a', 'a', 'b', 'b', 'b') |
|
|
|
Even float values should work so long as the comparison operator |
|
supports it. |
|
|
|
>>> r[4.5] |
|
'b' |
|
|
|
But you'll notice that the way rangemap is defined, it must be open-ended |
|
on one side. |
|
|
|
>>> r[0] |
|
'a' |
|
>>> r[-1] |
|
'a' |
|
|
|
One can close the open-end of the RangeMap by using undefined_value |
|
|
|
>>> r = RangeMap({0: RangeMap.undefined_value, 3: 'a', 6: 'b'}) |
|
>>> r[0] |
|
Traceback (most recent call last): |
|
... |
|
KeyError: 0 |
|
|
|
One can get the first or last elements in the range by using RangeMap.Item |
|
|
|
>>> last_item = RangeMap.Item(-1) |
|
>>> r[last_item] |
|
'b' |
|
|
|
.last_item is a shortcut for Item(-1) |
|
|
|
>>> r[RangeMap.last_item] |
|
'b' |
|
|
|
Sometimes it's useful to find the bounds for a RangeMap |
|
|
|
>>> r.bounds() |
|
(0, 6) |
|
|
|
RangeMap supports .get(key, default) |
|
|
|
>>> r.get(0, 'not found') |
|
'not found' |
|
|
|
>>> r.get(7, 'not found') |
|
'not found' |
|
|
|
One often wishes to define the ranges by their left-most values, |
|
which requires use of sort params and a key_match_comparator. |
|
|
|
>>> r = RangeMap({1: 'a', 4: 'b'}, |
|
... sort_params=dict(reverse=True), |
|
... key_match_comparator=operator.ge) |
|
>>> r[1], r[2], r[3], r[4], r[5], r[6] |
|
('a', 'a', 'a', 'b', 'b', 'b') |
|
|
|
That wasn't nearly as easy as before, so an alternate constructor |
|
is provided: |
|
|
|
>>> r = RangeMap.left({1: 'a', 4: 'b', 7: RangeMap.undefined_value}) |
|
>>> r[1], r[2], r[3], r[4], r[5], r[6] |
|
('a', 'a', 'a', 'b', 'b', 'b') |
|
|
|
""" |
|
|
|
def __init__(self, source, sort_params={}, key_match_comparator=operator.le): |
|
dict.__init__(self, source) |
|
self.sort_params = sort_params |
|
self.match = key_match_comparator |
|
|
|
@classmethod |
|
def left(cls, source): |
|
return cls( |
|
source, sort_params=dict(reverse=True), key_match_comparator=operator.ge |
|
) |
|
|
|
def __getitem__(self, item): |
|
sorted_keys = sorted(self.keys(), **self.sort_params) |
|
if isinstance(item, RangeMap.Item): |
|
result = self.__getitem__(sorted_keys[item]) |
|
else: |
|
key = self._find_first_match_(sorted_keys, item) |
|
result = dict.__getitem__(self, key) |
|
if result is RangeMap.undefined_value: |
|
raise KeyError(key) |
|
return result |
|
|
|
def get(self, key, default=None): |
|
""" |
|
Return the value for key if key is in the dictionary, else default. |
|
If default is not given, it defaults to None, so that this method |
|
never raises a KeyError. |
|
""" |
|
try: |
|
return self[key] |
|
except KeyError: |
|
return default |
|
|
|
def _find_first_match_(self, keys, item): |
|
is_match = functools.partial(self.match, item) |
|
matches = list(filter(is_match, keys)) |
|
if matches: |
|
return matches[0] |
|
raise KeyError(item) |
|
|
|
def bounds(self): |
|
sorted_keys = sorted(self.keys(), **self.sort_params) |
|
return (sorted_keys[RangeMap.first_item], sorted_keys[RangeMap.last_item]) |
|
|
|
|
|
undefined_value = type('RangeValueUndefined', (), {})() |
|
|
|
class Item(int): |
|
"RangeMap Item" |
|
|
|
first_item = Item(0) |
|
last_item = Item(-1) |
|
|
