-
-
Notifications
You must be signed in to change notification settings - Fork 63
/
_common.py
281 lines (224 loc) · 9.65 KB
/
_common.py
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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
"""
Implements :class:`BidirectionalMapping`, the bidirectional map base class.
Also provides related exception classes and collision behaviors.
"""
from .compat import PY2, ifilter, iterkeys, iteritems, itervalues, viewkeys, viewitems
from .util import pairs
from collections import Mapping
from itertools import chain
def _proxied(methodname, ivarname='_fwd', doc=None):
"""Make a func that calls methodname on the indicated instance variable."""
def proxy(self, *args):
ivar = getattr(self, ivarname)
meth = getattr(ivar, methodname)
return meth(*args)
proxy.__name__ = methodname
proxy.__doc__ = doc or 'Like :py:meth:`dict.%s`.' % methodname
return proxy
class CollisionBehavior(object):
"""
Provide RAISE, OVERWRITE, and IGNORE collision behaviors.
.. py:attribute:: RAISE
Raise an exception when a collision is encountered.
.. py:attribute:: OVERWRITE
Overwrite an existing item when a collision is encountered.
.. py:attribute:: IGNORE
Keep the existing item and ignore the new item when a collision is
encountered.
"""
def __init__(self, id):
"""Create a collision behavior with the given *id*."""
self.id = id
def __repr__(self):
return '<%s>' % self.id
CollisionBehavior.RAISE = RAISE = CollisionBehavior('RAISE')
CollisionBehavior.OVERWRITE = OVERWRITE = CollisionBehavior('OVERWRITE')
CollisionBehavior.IGNORE = IGNORE = CollisionBehavior('IGNORE')
class BidirectionalMapping(Mapping):
"""
Base class for all provided bidirectional map types.
Mutable and immutable bidict types extend this class,
which implements all the shared logic.
Users will typically only interact with subclasses of this class.
.. py:attribute:: inv
The inverse bidict.
"""
_dcls = dict
_on_key_coll = OVERWRITE
_on_val_coll = RAISE
def __init__(self, *args, **kw):
"""Like :py:meth:`dict.__init__`, but maintaining bidirectionality."""
self._fwd = self._dcls() # dictionary of forward mappings
self._inv = self._dcls() # dictionary of inverse mappings
if args or kw:
self._update(self._on_key_coll, self._on_val_coll, *args, **kw)
inv = object.__new__(self.__class__)
inv._fwd = self._inv
inv._inv = self._fwd
inv.inv = self
self.inv = inv
def __repr__(self):
return '%s(%r)' % (self.__class__.__name__, self._fwd)
def __eq__(self, other):
return self._fwd == other
def __ne__(self, other):
return not self.__eq__(other)
def __inverted__(self):
"""Get an iterator over the inverse mappings."""
return iteritems(self._inv)
def __getitem__(self, key):
return self._fwd[key]
def _put(self, key, val, on_key_coll, on_val_coll):
_fwd = self._fwd
_inv = self._inv
missing = object()
oldkey = _inv.get(val, missing)
oldval = _fwd.get(key, missing)
if key == oldkey and val == oldval:
return
if oldval is not missing: # key exists
if on_key_coll is RAISE:
# since multiple values can have the same hash value, refer
# to the existing key via `_inv[oldval]` rather than `key`
raise KeyExistsError((_inv[oldval], oldval))
elif on_key_coll is IGNORE:
return
if oldkey is not missing: # val exists
if on_val_coll is RAISE:
# since multiple values can have the same hash value, refer
# to the existing value via `_fwd[oldkey]` rather than `val`
raise ValueExistsError((oldkey, _fwd[oldkey]))
elif on_val_coll is IGNORE:
return
_fwd.pop(oldkey, None)
_inv.pop(oldval, None)
_fwd[key] = val
_inv[val] = key
def _update(self, on_key_coll, on_val_coll, *args, **kw):
if not args and not kw:
return
_fwd = self._fwd
_inv = self._inv
missing = object()
# Optimization: Try to detect duplicate keys and values early
# before doing any mallocs.
arg0 = args[0] if args else {}
if isinstance(arg0, Mapping):
if on_key_coll is RAISE:
if arg0 and kw:
# New mappings in both arg0 and kw ->
# Check if new key given twice with different values.
d1, d2 = (arg0, kw) if len(arg0) < len(kw) else (kw, arg0)
for (k, v) in iteritems(d1):
v2 = d2.get(k, missing)
if v2 is not missing and v2 != v:
raise KeyNotUniqueError(k)
# Check if a new key duplicates an existing key.
dupk = next(ifilter(_fwd.__contains__, chain(iterkeys(arg0), iterkeys(kw))), missing)
if dupk is not missing:
raise KeyExistsError((dupk, _fwd[dupk]))
if on_val_coll is RAISE:
# Want to check if a new value was given twice with different keys,
# but there's no way to do this in O(n) time without a malloc.
# So skip checking this here; we'll catch it below.
# ---
# Check if a new value duplicates an existing value.
dupv = next(ifilter(_inv.__contains__, chain(itervalues(arg0), itervalues(kw))), missing)
if dupv is not missing:
raise ValueExistsError((_inv[dupv], dupv))
# End optimization.
updatefwd = self._dcls()
updateinv = self._dcls()
for (k, v) in pairs(*args, **kw):
cont = False
oldk = _inv.get(v, missing)
oldv = _fwd.get(k, missing)
if k == oldk and v == oldv:
cont = True
else:
if oldv is not missing: # key exists
if on_key_coll is RAISE:
raise KeyExistsError((_inv[oldv], oldv))
elif on_key_coll is IGNORE:
cont = True
if oldk is not missing: # val exists
if on_val_coll is RAISE:
raise ValueExistsError((oldk, _fwd[oldk]))
elif on_val_coll is IGNORE:
cont = True
newk = updateinv.get(v, missing)
newv = updatefwd.get(k, missing)
if k == newk and v == newv:
cont = True
else:
if newv is not missing: # new key given twice
if on_key_coll is RAISE:
raise KeyNotUniqueError(k)
elif on_key_coll is IGNORE:
cont = True
if newk is not missing: # new val given twice
if on_val_coll is RAISE:
raise ValueNotUniqueError(v)
elif on_val_coll is IGNORE:
cont = True
if cont:
continue
if newv is not missing and on_key_coll is OVERWRITE:
del updateinv[newv]
if newk is not missing and on_val_coll is OVERWRITE:
del updatefwd[newk]
updatefwd[k] = v
updateinv[v] = k
commonkeys = viewkeys(updatefwd) & viewkeys(_fwd)
for k in commonkeys:
del _inv[_fwd.pop(k)]
commonvals = viewkeys(updateinv) & viewkeys(_inv)
for v in commonvals:
del _fwd[_inv.pop(v)]
_fwd.update(updatefwd)
_inv.update(updateinv)
def copy(self):
"""Like :py:meth:`dict.copy`."""
return self.__class__(self._fwd)
__len__ = _proxied('__len__')
__iter__ = _proxied('__iter__')
__contains__ = _proxied('__contains__')
get = _proxied('get')
keys = _proxied('keys')
items = _proxied('items')
values = _proxied('keys', ivarname='_inv')
values.__doc__ = \
"B.values() -> a set-like object providing a view on B's values.\n\n" \
'Note that because values of a BidirectionalMapping are also keys ' \
'of its inverse, this returns a *dict_keys* object rather than a ' \
'*dict_values* object, conferring set-like benefits.'
if PY2: # pragma: no cover
iterkeys = _proxied('iterkeys')
viewkeys = _proxied('viewkeys')
iteritems = _proxied('iteritems')
viewitems = _proxied('viewitems')
itervalues = _proxied('iterkeys', ivarname='_inv',
doc=dict.itervalues.__doc__)
viewvalues = _proxied('viewkeys', ivarname='_inv',
doc=values.__doc__.replace('values()', 'viewvalues()'))
values.__doc__ = 'Like :py:meth:`dict.values`.'
class BidictException(Exception):
"""Base class for bidict exceptions."""
class UniquenessError(BidictException):
"""Base class for KeyNotUniqueError and ValueNotUniqueError."""
class KeyNotUniqueError(UniquenessError):
"""Raised when a given key is not unique."""
def __str__(self):
return 'Key not unique: %r' % self.args[0]
class ValueNotUniqueError(UniquenessError):
"""Raised when a given value is not unique."""
def __str__(self):
return 'Value not unique: %r' % self.args[0]
class KeyExistsError(KeyNotUniqueError):
"""Raised when attempting to insert an already-existing key."""
def __str__(self):
return 'Key {0!r} exists with value {1!r}'.format(*self.args[0])
class ValueExistsError(ValueNotUniqueError):
"""Raised when attempting to insert an already-existing value."""
def __str__(self):
return 'Value {1!r} exists with key {0!r}'.format(*self.args[0])