| 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(str('RangeValueUndefined'), (), {})() |
|
|
| class Item(int): |
| "RangeMap Item" |
|
|
| first_item = Item(0) |
| last_item = Item(-1) |
|
|
