File size: 5,300 Bytes
3362754 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 |
import collections
import functools
import itertools
import operator
# from jaraco.collections 3.5.1
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)))
# from jaraco.collections 3.7
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])
# some special values for the RangeMap
undefined_value = type('RangeValueUndefined', (), {})()
class Item(int):
"RangeMap Item"
first_item = Item(0)
last_item = Item(-1)
|