Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/boltons/dictutils.py: 29%

1# -*- coding: utf-8 -*- 

2 

3# Copyright (c) 2013, Mahmoud Hashemi 

4# 

5# Redistribution and use in source and binary forms, with or without 

6# modification, are permitted provided that the following conditions are 

7# met: 

8# 

9# * Redistributions of source code must retain the above copyright 

10# notice, this list of conditions and the following disclaimer. 

11# 

12# * Redistributions in binary form must reproduce the above 

13# copyright notice, this list of conditions and the following 

14# disclaimer in the documentation and/or other materials provided 

15# with the distribution. 

16# 

17# * The names of the contributors may not be used to endorse or 

18# promote products derived from this software without specific 

19# prior written permission. 

20# 

21# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 

22# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 

23# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 

24# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 

25# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 

26# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 

27# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 

28# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 

29# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 

30# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 

31# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 

32 

33"""Python has a very powerful mapping type at its core: the :class:`dict` 

34type. While versatile and featureful, the :class:`dict` prioritizes 

35simplicity and performance. As a result, it does not retain the order 

36of item insertion [1]_, nor does it store multiple values per key. It 

37is a fast, unordered 1:1 mapping. 

38 

39The :class:`OrderedMultiDict` contrasts to the built-in :class:`dict`, 

40as a relatively maximalist, ordered 1:n subtype of 

41:class:`dict`. Virtually every feature of :class:`dict` has been 

42retooled to be intuitive in the face of this added 

43complexity. Additional methods have been added, such as 

44:class:`collections.Counter`-like functionality. 

45 

46A prime advantage of the :class:`OrderedMultiDict` (OMD) is its 

47non-destructive nature. Data can be added to an :class:`OMD` without being 

48rearranged or overwritten. The property can allow the developer to 

49work more freely with the data, as well as make more assumptions about 

50where input data will end up in the output, all without any extra 

51work. 

52 

53One great example of this is the :meth:`OMD.inverted()` method, which 

54returns a new OMD with the values as keys and the keys as values. All 

55the data and the respective order is still represented in the inverted 

56form, all from an operation which would be outright wrong and reckless 

57with a built-in :class:`dict` or :class:`collections.OrderedDict`. 

58 

59The OMD has been performance tuned to be suitable for a wide range of 

60usages, including as a basic unordered MultiDict. Special 

61thanks to `Mark Williams`_ for all his help. 

62 

63.. [1] As of 2015, `basic dicts on PyPy are ordered 

64 <http://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html>`_, 

65 and as of December 2017, `basic dicts in CPython 3 are now ordered 

66 <https://mail.python.org/pipermail/python-dev/2017-December/151283.html>`_, as 

67 well. 

68.. _Mark Williams: https://github.com/markrwilliams 

69 

70""" 

71 

72try: 

73 from collections.abc import KeysView, ValuesView, ItemsView 

74except ImportError: 

75 from collections import KeysView, ValuesView, ItemsView 

76 

77import itertools 

78 

79try: 

80 from itertools import izip_longest 

81except ImportError: 

82 from itertools import zip_longest as izip_longest 

83 

84try: 

85 from .typeutils import make_sentinel 

86 _MISSING = make_sentinel(var_name='_MISSING') 

87except ImportError: 

88 _MISSING = object() 

89 

90 

91PREV, NEXT, KEY, VALUE, SPREV, SNEXT = range(6) 

92 

93 

94__all__ = ['MultiDict', 'OMD', 'OrderedMultiDict', 'OneToOne', 'ManyToMany', 'subdict', 'FrozenDict'] 

95 

96try: 

97 profile 

98except NameError: 

99 profile = lambda x: x 

100 

101 

102class OrderedMultiDict(dict): 

103 """A MultiDict is a dictionary that can have multiple values per key 

104 and the OrderedMultiDict (OMD) is a MultiDict that retains 

105 original insertion order. Common use cases include: 

106 

107 * handling query strings parsed from URLs 

108 * inverting a dictionary to create a reverse index (values to keys) 

109 * stacking data from multiple dictionaries in a non-destructive way 

110 

111 The OrderedMultiDict constructor is identical to the built-in 

112 :class:`dict`, and overall the API constitutes an intuitive 

113 superset of the built-in type: 

114 

115 >>> omd = OrderedMultiDict() 

116 >>> omd['a'] = 1 

117 >>> omd['b'] = 2 

118 >>> omd.add('a', 3) 

119 >>> omd.get('a') 

120 3 

121 >>> omd.getlist('a') 

122 [1, 3] 

123 

124 Some non-:class:`dict`-like behaviors also make an appearance, 

125 such as support for :func:`reversed`: 

126 

127 >>> list(reversed(omd)) 

128 ['b', 'a'] 

129 

130 Note that unlike some other MultiDicts, this OMD gives precedence 

131 to the most recent value added. ``omd['a']`` refers to ``3``, not 

132 ``1``. 

133 

134 >>> omd 

135 OrderedMultiDict([('a', 1), ('b', 2), ('a', 3)]) 

136 >>> omd.poplast('a') 

137 3 

138 >>> omd 

139 OrderedMultiDict([('a', 1), ('b', 2)]) 

140 >>> omd.pop('a') 

141 1 

142 >>> omd 

143 OrderedMultiDict([('b', 2)]) 

144 

145 If you want a safe-to-modify or flat dictionary, use 

146 :meth:`OrderedMultiDict.todict()`. 

147 

148 >>> from pprint import pprint as pp # preserve printed ordering 

149 >>> omd = OrderedMultiDict([('a', 1), ('b', 2), ('a', 3)]) 

150 >>> pp(omd.todict()) 

151 {'a': 3, 'b': 2} 

152 >>> pp(omd.todict(multi=True)) 

153 {'a': [1, 3], 'b': [2]} 

154 

155 With ``multi=False``, items appear with the keys in to original 

156 insertion order, alongside the most-recently inserted value for 

157 that key. 

158 

159 >>> OrderedMultiDict([('a', 1), ('b', 2), ('a', 3)]).items(multi=False) 

160 [('a', 3), ('b', 2)] 

161 

162 .. warning:: 

163 

164 ``dict(omd)`` changed behavior `in Python 3.7 

165 <https://bugs.python.org/issue34320>`_ due to changes made to 

166 support the transition from :class:`collections.OrderedDict` to 

167 the built-in dictionary being ordered. Before 3.7, the result 

168 would be a new dictionary, with values that were lists, similar 

169 to ``omd.todict(multi=True)`` (but only shallow-copy; the lists 

170 were direct references to OMD internal structures). From 3.7 

171 onward, the values became singular, like 

172 ``omd.todict(multi=False)``. For reliable cross-version 

173 behavior, just use :meth:`~OrderedMultiDict.todict()`. 

174 

175 """ 

176 def __init__(self, *args, **kwargs): 

177 if len(args) > 1: 

178 raise TypeError('%s expected at most 1 argument, got %s' 

179 % (self.__class__.__name__, len(args))) 

180 super(OrderedMultiDict, self).__init__() 

181 

182 self._clear_ll() 

183 if args: 

184 self.update_extend(args[0]) 

185 if kwargs: 

186 self.update(kwargs) 

187 

188 def _clear_ll(self): 

189 try: 

190 _map = self._map 

191 except AttributeError: 

192 _map = self._map = {} 

193 self.root = [] 

194 _map.clear() 

195 self.root[:] = [self.root, self.root, None] 

196 

197 def _insert(self, k, v): 

198 root = self.root 

199 cells = self._map.setdefault(k, []) 

200 last = root[PREV] 

201 cell = [last, root, k, v] 

202 last[NEXT] = root[PREV] = cell 

203 cells.append(cell) 

204 

205 def add(self, k, v): 

206 """Add a single value *v* under a key *k*. Existing values under *k* 

207 are preserved. 

208 """ 

209 values = super(OrderedMultiDict, self).setdefault(k, []) 

210 self._insert(k, v) 

211 values.append(v) 

212 

213 def addlist(self, k, v): 

214 """Add an iterable of values underneath a specific key, preserving 

215 any values already under that key. 

216 

217 >>> omd = OrderedMultiDict([('a', -1)]) 

218 >>> omd.addlist('a', range(3)) 

219 >>> omd 

220 OrderedMultiDict([('a', -1), ('a', 0), ('a', 1), ('a', 2)]) 

221 

222 Called ``addlist`` for consistency with :meth:`getlist`, but 

223 tuples and other sequences and iterables work. 

224 """ 

225 if not v: 

226 return 

227 self_insert = self._insert 

228 values = super(OrderedMultiDict, self).setdefault(k, []) 

229 for subv in v: 

230 self_insert(k, subv) 

231 values.extend(v) 

232 

233 def get(self, k, default=None): 

234 """Return the value for key *k* if present in the dictionary, else 

235 *default*. If *default* is not given, ``None`` is returned. 

236 This method never raises a :exc:`KeyError`. 

237 

238 To get all values under a key, use :meth:`OrderedMultiDict.getlist`. 

239 """ 

240 return super(OrderedMultiDict, self).get(k, [default])[-1] 

241 

242 def getlist(self, k, default=_MISSING): 

243 """Get all values for key *k* as a list, if *k* is in the 

244 dictionary, else *default*. The list returned is a copy and 

245 can be safely mutated. If *default* is not given, an empty 

246 :class:`list` is returned. 

247 """ 

248 try: 

249 return super(OrderedMultiDict, self).__getitem__(k)[:] 

250 except KeyError: 

251 if default is _MISSING: 

252 return [] 

253 return default 

254 

255 def clear(self): 

256 "Empty the dictionary." 

257 super(OrderedMultiDict, self).clear() 

258 self._clear_ll() 

259 

260 def setdefault(self, k, default=_MISSING): 

261 """If key *k* is in the dictionary, return its value. If not, insert 

262 *k* with a value of *default* and return *default*. *default* 

263 defaults to ``None``. See :meth:`dict.setdefault` for more 

264 information. 

265 """ 

266 if not super(OrderedMultiDict, self).__contains__(k): 

267 self[k] = None if default is _MISSING else default 

268 return self[k] 

269 

270 def copy(self): 

271 "Return a shallow copy of the dictionary." 

272 return self.__class__(self.iteritems(multi=True)) 

273 

274 @classmethod 

275 def fromkeys(cls, keys, default=None): 

276 """Create a dictionary from a list of keys, with all the values 

277 set to *default*, or ``None`` if *default* is not set. 

278 """ 

279 return cls([(k, default) for k in keys]) 

280 

281 def update(self, E, **F): 

282 """Add items from a dictionary or iterable (and/or keyword arguments), 

283 overwriting values under an existing key. See 

284 :meth:`dict.update` for more details. 

285 """ 

286 # E and F are throwback names to the dict() __doc__ 

287 if E is self: 

288 return 

289 self_add = self.add 

290 if isinstance(E, OrderedMultiDict): 

291 for k in E: 

292 if k in self: 

293 del self[k] 

294 for k, v in E.iteritems(multi=True): 

295 self_add(k, v) 

296 elif callable(getattr(E, 'keys', None)): 

297 for k in E.keys(): 

298 self[k] = E[k] 

299 else: 

300 seen = set() 

301 seen_add = seen.add 

302 for k, v in E: 

303 if k not in seen and k in self: 

304 del self[k] 

305 seen_add(k) 

306 self_add(k, v) 

307 for k in F: 

308 self[k] = F[k] 

309 return 

310 

311 def update_extend(self, E, **F): 

312 """Add items from a dictionary, iterable, and/or keyword 

313 arguments without overwriting existing items present in the 

314 dictionary. Like :meth:`update`, but adds to existing keys 

315 instead of overwriting them. 

316 """ 

317 if E is self: 

318 iterator = iter(E.items()) 

319 elif isinstance(E, OrderedMultiDict): 

320 iterator = E.iteritems(multi=True) 

321 elif hasattr(E, 'keys'): 

322 iterator = ((k, E[k]) for k in E.keys()) 

323 else: 

324 iterator = E 

325 

326 self_add = self.add 

327 for k, v in iterator: 

328 self_add(k, v) 

329 

330 def __setitem__(self, k, v): 

331 if super(OrderedMultiDict, self).__contains__(k): 

332 self._remove_all(k) 

333 self._insert(k, v) 

334 super(OrderedMultiDict, self).__setitem__(k, [v]) 

335 

336 def __getitem__(self, k): 

337 return super(OrderedMultiDict, self).__getitem__(k)[-1] 

338 

339 def __delitem__(self, k): 

340 super(OrderedMultiDict, self).__delitem__(k) 

341 self._remove_all(k) 

342 

343 def __eq__(self, other): 

344 if self is other: 

345 return True 

346 try: 

347 if len(other) != len(self): 

348 return False 

349 except TypeError: 

350 return False 

351 if isinstance(other, OrderedMultiDict): 

352 selfi = self.iteritems(multi=True) 

353 otheri = other.iteritems(multi=True) 

354 zipped_items = izip_longest(selfi, otheri, fillvalue=(None, None)) 

355 for (selfk, selfv), (otherk, otherv) in zipped_items: 

356 if selfk != otherk or selfv != otherv: 

357 return False 

358 if not(next(selfi, _MISSING) is _MISSING 

359 and next(otheri, _MISSING) is _MISSING): 

360 # leftovers (TODO: watch for StopIteration?) 

361 return False 

362 return True 

363 elif hasattr(other, 'keys'): 

364 for selfk in self: 

365 try: 

366 other[selfk] == self[selfk] 

367 except KeyError: 

368 return False 

369 return True 

370 return False 

371 

372 def __ne__(self, other): 

373 return not (self == other) 

374 

375 def pop(self, k, default=_MISSING): 

376 """Remove all values under key *k*, returning the most-recently 

377 inserted value. Raises :exc:`KeyError` if the key is not 

378 present and no *default* is provided. 

379 """ 

380 try: 

381 return self.popall(k)[-1] 

382 except KeyError: 

383 if default is _MISSING: 

384 raise KeyError(k) 

385 return default 

386 

387 def popall(self, k, default=_MISSING): 

388 """Remove all values under key *k*, returning them in the form of 

389 a list. Raises :exc:`KeyError` if the key is not present and no 

390 *default* is provided. 

391 """ 

392 super_self = super(OrderedMultiDict, self) 

393 if super_self.__contains__(k): 

394 self._remove_all(k) 

395 if default is _MISSING: 

396 return super_self.pop(k) 

397 return super_self.pop(k, default) 

398 

399 def poplast(self, k=_MISSING, default=_MISSING): 

400 """Remove and return the most-recently inserted value under the key 

401 *k*, or the most-recently inserted key if *k* is not 

402 provided. If no values remain under *k*, it will be removed 

403 from the OMD. Raises :exc:`KeyError` if *k* is not present in 

404 the dictionary, or the dictionary is empty. 

405 """ 

406 if k is _MISSING: 

407 if self: 

408 k = self.root[PREV][KEY] 

409 else: 

410 if default is _MISSING: 

411 raise KeyError('empty %r' % type(self)) 

412 return default 

413 try: 

414 self._remove(k) 

415 except KeyError: 

416 if default is _MISSING: 

417 raise KeyError(k) 

418 return default 

419 values = super(OrderedMultiDict, self).__getitem__(k) 

420 v = values.pop() 

421 if not values: 

422 super(OrderedMultiDict, self).__delitem__(k) 

423 return v 

424 

425 def _remove(self, k): 

426 values = self._map[k] 

427 cell = values.pop() 

428 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV] 

429 if not values: 

430 del self._map[k] 

431 

432 def _remove_all(self, k): 

433 values = self._map[k] 

434 while values: 

435 cell = values.pop() 

436 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV] 

437 del self._map[k] 

438 

439 def iteritems(self, multi=False): 

440 """Iterate over the OMD's items in insertion order. By default, 

441 yields only the most-recently inserted value for each key. Set 

442 *multi* to ``True`` to get all inserted items. 

443 """ 

444 root = self.root 

445 curr = root[NEXT] 

446 if multi: 

447 while curr is not root: 

448 yield curr[KEY], curr[VALUE] 

449 curr = curr[NEXT] 

450 else: 

451 for key in self.iterkeys(): 

452 yield key, self[key] 

453 

454 def iterkeys(self, multi=False): 

455 """Iterate over the OMD's keys in insertion order. By default, yields 

456 each key once, according to the most recent insertion. Set 

457 *multi* to ``True`` to get all keys, including duplicates, in 

458 insertion order. 

459 """ 

460 root = self.root 

461 curr = root[NEXT] 

462 if multi: 

463 while curr is not root: 

464 yield curr[KEY] 

465 curr = curr[NEXT] 

466 else: 

467 yielded = set() 

468 yielded_add = yielded.add 

469 while curr is not root: 

470 k = curr[KEY] 

471 if k not in yielded: 

472 yielded_add(k) 

473 yield k 

474 curr = curr[NEXT] 

475 

476 def itervalues(self, multi=False): 

477 """Iterate over the OMD's values in insertion order. By default, 

478 yields the most-recently inserted value per unique key. Set 

479 *multi* to ``True`` to get all values according to insertion 

480 order. 

481 """ 

482 for k, v in self.iteritems(multi=multi): 

483 yield v 

484 

485 def todict(self, multi=False): 

486 """Gets a basic :class:`dict` of the items in this dictionary. Keys 

487 are the same as the OMD, values are the most recently inserted 

488 values for each key. 

489 

490 Setting the *multi* arg to ``True`` is yields the same 

491 result as calling :class:`dict` on the OMD, except that all the 

492 value lists are copies that can be safely mutated. 

493 """ 

494 if multi: 

495 return dict([(k, self.getlist(k)) for k in self]) 

496 return dict([(k, self[k]) for k in self]) 

497 

498 def sorted(self, key=None, reverse=False): 

499 """Similar to the built-in :func:`sorted`, except this method returns 

500 a new :class:`OrderedMultiDict` sorted by the provided key 

501 function, optionally reversed. 

502 

503 Args: 

504 key (callable): A callable to determine the sort key of 

505 each element. The callable should expect an **item** 

506 (key-value pair tuple). 

507 reverse (bool): Set to ``True`` to reverse the ordering. 

508 

509 >>> omd = OrderedMultiDict(zip(range(3), range(3))) 

510 >>> omd.sorted(reverse=True) 

511 OrderedMultiDict([(2, 2), (1, 1), (0, 0)]) 

512 

513 Note that the key function receives an **item** (key-value 

514 tuple), so the recommended signature looks like: 

515 

516 >>> omd = OrderedMultiDict(zip('hello', 'world')) 

517 >>> omd.sorted(key=lambda i: i[1]) # i[0] is the key, i[1] is the val 

518 OrderedMultiDict([('o', 'd'), ('l', 'l'), ('e', 'o'), ('l', 'r'), ('h', 'w')]) 

519 """ 

520 cls = self.__class__ 

521 return cls(sorted(self.iteritems(multi=True), key=key, reverse=reverse)) 

522 

523 def sortedvalues(self, key=None, reverse=False): 

524 """Returns a copy of the :class:`OrderedMultiDict` with the same keys 

525 in the same order as the original OMD, but the values within 

526 each keyspace have been sorted according to *key* and 

527 *reverse*. 

528 

529 Args: 

530 key (callable): A single-argument callable to determine 

531 the sort key of each element. The callable should expect 

532 an **item** (key-value pair tuple). 

533 reverse (bool): Set to ``True`` to reverse the ordering. 

534 

535 >>> omd = OrderedMultiDict() 

536 >>> omd.addlist('even', [6, 2]) 

537 >>> omd.addlist('odd', [1, 5]) 

538 >>> omd.add('even', 4) 

539 >>> omd.add('odd', 3) 

540 >>> somd = omd.sortedvalues() 

541 >>> somd.getlist('even') 

542 [2, 4, 6] 

543 >>> somd.keys(multi=True) == omd.keys(multi=True) 

544 True 

545 >>> omd == somd 

546 False 

547 >>> somd 

548 OrderedMultiDict([('even', 2), ('even', 4), ('odd', 1), ('odd', 3), ('even', 6), ('odd', 5)]) 

549 

550 As demonstrated above, contents and key order are 

551 retained. Only value order changes. 

552 """ 

553 try: 

554 superself_iteritems = super(OrderedMultiDict, self).iteritems() 

555 except AttributeError: 

556 superself_iteritems = super(OrderedMultiDict, self).items() 

557 # (not reverse) because they pop off in reverse order for reinsertion 

558 sorted_val_map = dict([(k, sorted(v, key=key, reverse=(not reverse))) 

559 for k, v in superself_iteritems]) 

560 ret = self.__class__() 

561 for k in self.iterkeys(multi=True): 

562 ret.add(k, sorted_val_map[k].pop()) 

563 return ret 

564 

565 def inverted(self): 

566 """Returns a new :class:`OrderedMultiDict` with values and keys 

567 swapped, like creating dictionary transposition or reverse 

568 index. Insertion order is retained and all keys and values 

569 are represented in the output. 

570 

571 >>> omd = OMD([(0, 2), (1, 2)]) 

572 >>> omd.inverted().getlist(2) 

573 [0, 1] 

574 

575 Inverting twice yields a copy of the original: 

576 

577 >>> omd.inverted().inverted() 

578 OrderedMultiDict([(0, 2), (1, 2)]) 

579 """ 

580 return self.__class__((v, k) for k, v in self.iteritems(multi=True)) 

581 

582 def counts(self): 

583 """Returns a mapping from key to number of values inserted under that 

584 key. Like :py:class:`collections.Counter`, but returns a new 

585 :class:`OrderedMultiDict`. 

586 """ 

587 # Returns an OMD because Counter/OrderedDict may not be 

588 # available, and neither Counter nor dict maintain order. 

589 super_getitem = super(OrderedMultiDict, self).__getitem__ 

590 return self.__class__((k, len(super_getitem(k))) for k in self) 

591 

592 def keys(self, multi=False): 

593 """Returns a list containing the output of :meth:`iterkeys`. See 

594 that method's docs for more details. 

595 """ 

596 return list(self.iterkeys(multi=multi)) 

597 

598 def values(self, multi=False): 

599 """Returns a list containing the output of :meth:`itervalues`. See 

600 that method's docs for more details. 

601 """ 

602 return list(self.itervalues(multi=multi)) 

603 

604 def items(self, multi=False): 

605 """Returns a list containing the output of :meth:`iteritems`. See 

606 that method's docs for more details. 

607 """ 

608 return list(self.iteritems(multi=multi)) 

609 

610 def __iter__(self): 

611 return self.iterkeys() 

612 

613 def __reversed__(self): 

614 root = self.root 

615 curr = root[PREV] 

616 lengths = {} 

617 lengths_sd = lengths.setdefault 

618 get_values = super(OrderedMultiDict, self).__getitem__ 

619 while curr is not root: 

620 k = curr[KEY] 

621 vals = get_values(k) 

622 if lengths_sd(k, 1) == len(vals): 

623 yield k 

624 lengths[k] += 1 

625 curr = curr[PREV] 

626 

627 def __repr__(self): 

628 cn = self.__class__.__name__ 

629 kvs = ', '.join([repr((k, v)) for k, v in self.iteritems(multi=True)]) 

630 return '%s([%s])' % (cn, kvs) 

631 

632 def viewkeys(self): 

633 "OMD.viewkeys() -> a set-like object providing a view on OMD's keys" 

634 return KeysView(self) 

635 

636 def viewvalues(self): 

637 "OMD.viewvalues() -> an object providing a view on OMD's values" 

638 return ValuesView(self) 

639 

640 def viewitems(self): 

641 "OMD.viewitems() -> a set-like object providing a view on OMD's items" 

642 return ItemsView(self) 

643 

644 

645# A couple of convenient aliases 

646OMD = OrderedMultiDict 

647MultiDict = OrderedMultiDict 

648 

649 

650class FastIterOrderedMultiDict(OrderedMultiDict): 

651 """An OrderedMultiDict backed by a skip list. Iteration over keys 

652 is faster and uses constant memory but adding duplicate key-value 

653 pairs is slower. Brainchild of Mark Williams. 

654 """ 

655 def _clear_ll(self): 

656 # TODO: always reset objects? (i.e., no else block below) 

657 try: 

658 _map = self._map 

659 except AttributeError: 

660 _map = self._map = {} 

661 self.root = [] 

662 _map.clear() 

663 self.root[:] = [self.root, self.root, 

664 None, None, 

665 self.root, self.root] 

666 

667 def _insert(self, k, v): 

668 root = self.root 

669 empty = [] 

670 cells = self._map.setdefault(k, empty) 

671 last = root[PREV] 

672 

673 if cells is empty: 

674 cell = [last, root, 

675 k, v, 

676 last, root] 

677 # was the last one skipped? 

678 if last[SPREV][SNEXT] is root: 

679 last[SPREV][SNEXT] = cell 

680 last[NEXT] = last[SNEXT] = root[PREV] = root[SPREV] = cell 

681 cells.append(cell) 

682 else: 

683 # if the previous was skipped, go back to the cell that 

684 # skipped it 

685 sprev = last[SPREV] if (last[SPREV][SNEXT] is not last) else last 

686 cell = [last, root, 

687 k, v, 

688 sprev, root] 

689 # skip me 

690 last[SNEXT] = root 

691 last[NEXT] = root[PREV] = root[SPREV] = cell 

692 cells.append(cell) 

693 

694 def _remove(self, k): 

695 cells = self._map[k] 

696 cell = cells.pop() 

697 if not cells: 

698 del self._map[k] 

699 cell[PREV][SNEXT] = cell[SNEXT] 

700 

701 if cell[PREV][SPREV][SNEXT] is cell: 

702 cell[PREV][SPREV][SNEXT] = cell[NEXT] 

703 elif cell[SNEXT] is cell[NEXT]: 

704 cell[SPREV][SNEXT], cell[SNEXT][SPREV] = cell[SNEXT], cell[SPREV] 

705 

706 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV] 

707 

708 def _remove_all(self, k): 

709 cells = self._map.pop(k) 

710 while cells: 

711 cell = cells.pop() 

712 if cell[PREV][SPREV][SNEXT] is cell: 

713 cell[PREV][SPREV][SNEXT] = cell[NEXT] 

714 elif cell[SNEXT] is cell[NEXT]: 

715 cell[SPREV][SNEXT], cell[SNEXT][SPREV] = cell[SNEXT], cell[SPREV] 

716 

717 cell[PREV][NEXT], cell[NEXT][PREV] = cell[NEXT], cell[PREV] 

718 cell[PREV][SNEXT] = cell[SNEXT] 

719 

720 def iteritems(self, multi=False): 

721 next_link = NEXT if multi else SNEXT 

722 root = self.root 

723 curr = root[next_link] 

724 while curr is not root: 

725 yield curr[KEY], curr[VALUE] 

726 curr = curr[next_link] 

727 

728 def iterkeys(self, multi=False): 

729 next_link = NEXT if multi else SNEXT 

730 root = self.root 

731 curr = root[next_link] 

732 while curr is not root: 

733 yield curr[KEY] 

734 curr = curr[next_link] 

735 

736 def __reversed__(self): 

737 root = self.root 

738 curr = root[PREV] 

739 while curr is not root: 

740 if curr[SPREV][SNEXT] is not curr: 

741 curr = curr[SPREV] 

742 if curr is root: 

743 break 

744 yield curr[KEY] 

745 curr = curr[PREV] 

746 

747 

748_OTO_INV_MARKER = object() 

749_OTO_UNIQUE_MARKER = object() 

750 

751 

752class OneToOne(dict): 

753 """Implements a one-to-one mapping dictionary. In addition to 

754 inheriting from and behaving exactly like the builtin 

755 :class:`dict`, all values are automatically added as keys on a 

756 reverse mapping, available as the `inv` attribute. This 

757 arrangement keeps key and value namespaces distinct. 

758 

759 Basic operations are intuitive: 

760 

761 >>> oto = OneToOne({'a': 1, 'b': 2}) 

762 >>> print(oto['a']) 

763 1 

764 >>> print(oto.inv[1]) 

765 a 

766 >>> len(oto) 

767 2 

768 

769 Overwrites happens in both directions: 

770 

771 >>> oto.inv[1] = 'c' 

772 >>> print(oto.get('a')) 

773 None 

774 >>> len(oto) 

775 2 

776 

777 For a very similar project, with even more one-to-one 

778 functionality, check out `bidict <https://github.com/jab/bidict>`_. 

779 """ 

780 __slots__ = ('inv',) 

781 

782 def __init__(self, *a, **kw): 

783 raise_on_dupe = False 

784 if a: 

785 if a[0] is _OTO_INV_MARKER: 

786 self.inv = a[1] 

787 dict.__init__(self, [(v, k) for k, v in self.inv.items()]) 

788 return 

789 elif a[0] is _OTO_UNIQUE_MARKER: 

790 a, raise_on_dupe = a[1:], True 

791 

792 dict.__init__(self, *a, **kw) 

793 self.inv = self.__class__(_OTO_INV_MARKER, self) 

794 

795 if len(self) == len(self.inv): 

796 # if lengths match, that means everything's unique 

797 return 

798 

799 if not raise_on_dupe: 

800 dict.clear(self) 

801 dict.update(self, [(v, k) for k, v in self.inv.items()]) 

802 return 

803 

804 # generate an error message if the values aren't 1:1 

805 

806 val_multidict = {} 

807 for k, v in self.items(): 

808 val_multidict.setdefault(v, []).append(k) 

809 

810 dupes = dict([(v, k_list) for v, k_list in 

811 val_multidict.items() if len(k_list) > 1]) 

812 

813 raise ValueError('expected unique values, got multiple keys for' 

814 ' the following values: %r' % dupes) 

815 

816 @classmethod 

817 def unique(cls, *a, **kw): 

818 """This alternate constructor for OneToOne will raise an exception 

819 when input values overlap. For instance: 

820 

821 >>> OneToOne.unique({'a': 1, 'b': 1}) 

822 Traceback (most recent call last): 

823 ... 

824 ValueError: expected unique values, got multiple keys for the following values: ... 

825 

826 This even works across inputs: 

827 

828 >>> a_dict = {'a': 2} 

829 >>> OneToOne.unique(a_dict, b=2) 

830 Traceback (most recent call last): 

831 ... 

832 ValueError: expected unique values, got multiple keys for the following values: ... 

833 """ 

834 return cls(_OTO_UNIQUE_MARKER, *a, **kw) 

835 

836 def __setitem__(self, key, val): 

837 hash(val) # ensure val is a valid key 

838 if key in self: 

839 dict.__delitem__(self.inv, self[key]) 

840 if val in self.inv: 

841 del self.inv[val] 

842 dict.__setitem__(self, key, val) 

843 dict.__setitem__(self.inv, val, key) 

844 

845 def __delitem__(self, key): 

846 dict.__delitem__(self.inv, self[key]) 

847 dict.__delitem__(self, key) 

848 

849 def clear(self): 

850 dict.clear(self) 

851 dict.clear(self.inv) 

852 

853 def copy(self): 

854 return self.__class__(self) 

855 

856 def pop(self, key, default=_MISSING): 

857 if key in self: 

858 dict.__delitem__(self.inv, self[key]) 

859 return dict.pop(self, key) 

860 if default is not _MISSING: 

861 return default 

862 raise KeyError() 

863 

864 def popitem(self): 

865 key, val = dict.popitem(self) 

866 dict.__delitem__(self.inv, val) 

867 return key, val 

868 

869 def setdefault(self, key, default=None): 

870 if key not in self: 

871 self[key] = default 

872 return self[key] 

873 

874 def update(self, dict_or_iterable, **kw): 

875 if isinstance(dict_or_iterable, dict):