Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.11/site-packages/boltons/setutils.py: 18%

1# Copyright (c) 2013, Mahmoud Hashemi 

2# 

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

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

5# met: 

6# 

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

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

9# 

10# * Redistributions in binary form must reproduce the above 

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

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

13# with the distribution. 

14# 

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

16# promote products derived from this software without specific 

17# prior written permission. 

18# 

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

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

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

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

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

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

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

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

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

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

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

30 

31"""\ 

32 

33The :class:`set` type brings the practical expressiveness of 

34set theory to Python. It has a very rich API overall, but lacks a 

35couple of fundamental features. For one, sets are not ordered. On top 

36of this, sets are not indexable, i.e, ``my_set[8]`` will raise an 

37:exc:`TypeError`. The :class:`IndexedSet` type remedies both of these 

38issues without compromising on the excellent complexity 

39characteristics of Python's built-in set implementation. 

40""" 

41 

42 

43from bisect import bisect_left 

44from collections.abc import MutableSet 

45from itertools import chain, islice 

46import operator 

47 

48try: 

49 from .typeutils import make_sentinel 

50 _MISSING = make_sentinel(var_name='_MISSING') 

51except ImportError: 

52 _MISSING = object() 

53 

54 

55__all__ = ['IndexedSet', 'complement'] 

56 

57 

58_COMPACTION_FACTOR = 8 

59_MAX_DEAD_INTERVALS = 384 

60 

61# TODO: inherit from set() 

62# TODO: .discard_many(), .remove_many() 

63# TODO: raise exception on non-set params? 

64# TODO: technically reverse operators should probably reverse the 

65# order of the 'other' inputs and put self last (to try and maintain 

66# insertion order) 

67 

68 

69class IndexedSet(MutableSet): 

70 """``IndexedSet`` is a :class:`collections.MutableSet` that maintains 

71 insertion order and uniqueness of inserted elements. It's a hybrid 

72 type, mostly like an OrderedSet, but also :class:`list`-like, in 

73 that it supports indexing and slicing. 

74 

75 Args: 

76 other (iterable): An optional iterable used to initialize the set. 

77 

78 >>> x = IndexedSet(list(range(4)) + list(range(8))) 

79 >>> x 

80 IndexedSet([0, 1, 2, 3, 4, 5, 6, 7]) 

81 >>> x - set(range(2)) 

82 IndexedSet([2, 3, 4, 5, 6, 7]) 

83 >>> x[-1] 

84 7 

85 >>> fcr = IndexedSet('freecreditreport.com') 

86 >>> ''.join(fcr[:fcr.index('.')]) 

87 'frecditpo' 

88 

89 Standard set operators and interoperation with :class:`set` are 

90 all supported: 

91 

92 >>> fcr & set('cash4gold.com') 

93 IndexedSet(['c', 'd', 'o', '.', 'm']) 

94 

95 As you can see, the ``IndexedSet`` is almost like a ``UniqueList``, 

96 retaining only one copy of a given value, in the order it was 

97 first added. For the curious, the reason why IndexedSet does not 

98 support setting items based on index (i.e, ``__setitem__()``), 

99 consider the following dilemma:: 

100 

101 my_indexed_set = [A, B, C, D] 

102 my_indexed_set[2] = A 

103 

104 At this point, a set requires only one *A*, but a :class:`list` would 

105 overwrite *C*. Overwriting *C* would change the length of the list, 

106 meaning that ``my_indexed_set[2]`` would not be *A*, as expected with a 

107 list, but rather *D*. So, no ``__setitem__()``. 

108 

109 Otherwise, the API strives to be as complete a union of the 

110 :class:`list` and :class:`set` APIs as possible. 

111 """ 

112 def __init__(self, other=None): 

113 self.item_index_map = dict() 

114 self.item_list = [] 

115 self.dead_indices = [] 

116 self._compactions = 0 

117 self._c_max_size = 0 

118 if other: 

119 self.update(other) 

120 

121 # internal functions 

122 @property 

123 def _dead_index_count(self): 

124 return len(self.item_list) - len(self.item_index_map) 

125 

126 def _compact(self): 

127 if not self.dead_indices: 

128 return 

129 self._compactions += 1 

130 dead_index_count = self._dead_index_count 

131 items, index_map = self.item_list, self.item_index_map 

132 self._c_max_size = max(self._c_max_size, len(items)) 

133 for i, item in enumerate(self): 

134 items[i] = item 

135 index_map[item] = i 

136 del items[-dead_index_count:] 

137 del self.dead_indices[:] 

138 

139 def _cull(self): 

140 ded = self.dead_indices 

141 if not ded: 

142 return 

143 items, ii_map = self.item_list, self.item_index_map 

144 if not ii_map: 

145 del items[:] 

146 del ded[:] 

147 elif len(ded) > _MAX_DEAD_INTERVALS: 

148 self._compact() 

149 elif self._dead_index_count > (len(items) / _COMPACTION_FACTOR): 

150 self._compact() 

151 elif items[-1] is _MISSING: # get rid of dead right hand side 

152 num_dead = 1 

153 while items[-(num_dead + 1)] is _MISSING: 

154 num_dead += 1 

155 if ded and ded[-1][1] == len(items): 

156 del ded[-1] 

157 del items[-num_dead:] 

158 

159 def _get_real_index(self, index): 

160 if index < 0: 

161 index += len(self) 

162 if index < 0 or index >= len(self): 

163 raise IndexError('IndexedSet index out of range') 

164 if not self.dead_indices: 

165 return index 

166 real_index = index 

167 for d_start, d_stop in self.dead_indices: 

168 if real_index < d_start: 

169 break 

170 real_index += d_stop - d_start 

171 return real_index 

172 

173 def _get_apparent_index(self, index): 

174 if index < 0: 

175 index += len(self) 

176 if not self.dead_indices: 

177 return index 

178 apparent_index = index 

179 for d_start, d_stop in self.dead_indices: 

180 if index < d_start: 

181 break 

182 apparent_index -= d_stop - d_start 

183 return apparent_index 

184 

185 def _add_dead(self, start, stop=None): 

186 # TODO: does not handle when the new interval subsumes 

187 # multiple existing intervals 

188 dints = self.dead_indices 

189 if stop is None: 

190 stop = start + 1 

191 cand_int = [start, stop] 

192 if not dints: 

193 dints.append(cand_int) 

194 return 

195 int_idx = bisect_left(dints, cand_int) 

196 dint = dints[int_idx - 1] 

197 d_start, d_stop = dint 

198 if start <= d_start <= stop: 

199 dint[0] = start 

200 elif start <= d_stop <= stop: 

201 dint[1] = stop 

202 else: 

203 dints.insert(int_idx, cand_int) 

204 return 

205 

206 def _bulk_discard(self, to_remove): 

207 """Remove many items in a single O(n) pass. 

208 

209 Removing k scattered items via repeated :meth:`discard` triggers a 

210 full O(n) compaction every ``_MAX_DEAD_INTERVALS`` removals, i.e. 

211 O(n * k) overall. Rebuilding once keeps bulk updates linear. 

212 """ 

213 self.item_list = [item for item in self.item_list 

214 if item is not _MISSING and item not in to_remove] 

215 self.item_index_map = {item: i 

216 for i, item in enumerate(self.item_list)} 

217 del self.dead_indices[:] 

218 

219 # common operations (shared by set and list) 

220 def __len__(self): 

221 return len(self.item_index_map) 

222 

223 def __contains__(self, item): 

224 return item in self.item_index_map 

225 

226 def __iter__(self): 

227 return (item for item in self.item_list if item is not _MISSING) 

228 

229 def __reversed__(self): 

230 item_list = self.item_list 

231 return (item for item in reversed(item_list) if item is not _MISSING) 

232 

233 def __repr__(self): 

234 return f'{self.__class__.__name__}({list(self)!r})' 

235 

236 def __eq__(self, other): 

237 if isinstance(other, IndexedSet): 

238 return len(self) == len(other) and list(self) == list(other) 

239 try: 

240 return set(self) == set(other) 

241 except TypeError: 

242 return False 

243 

244 @classmethod 

245 def from_iterable(cls, it): 

246 "from_iterable(it) -> create a set from an iterable" 

247 return cls(it) 

248 

249 # set operations 

250 def add(self, item): 

251 "add(item) -> add item to the set" 

252 if item not in self.item_index_map: 

253 self.item_index_map[item] = len(self.item_list) 

254 self.item_list.append(item) 

255 

256 def remove(self, item): 

257 "remove(item) -> remove item from the set, raises if not present" 

258 try: 

259 didx = self.item_index_map.pop(item) 

260 except KeyError: 

261 raise KeyError(item) 

262 self.item_list[didx] = _MISSING 

263 self._add_dead(didx) 

264 self._cull() 

265 

266 def discard(self, item): 

267 "discard(item) -> discard item from the set (does not raise)" 

268 try: 

269 self.remove(item) 

270 except KeyError: 

271 pass 

272 

273 def clear(self): 

274 "clear() -> empty the set" 

275 del self.item_list[:] 

276 del self.dead_indices[:] 

277 self.item_index_map.clear() 

278 

279 def isdisjoint(self, other): 

280 "isdisjoint(other) -> return True if no overlap with other" 

281 iim = self.item_index_map 

282 for k in other: 

283 if k in iim: 

284 return False 

285 return True 

286 

287 def issubset(self, other): 

288 "issubset(other) -> return True if other contains this set" 

289 if len(other) < len(self): 

290 return False 

291 for k in self.item_index_map: 

292 if k not in other: 

293 return False 

294 return True 

295 

296 def issuperset(self, other): 

297 "issuperset(other) -> return True if set contains other" 

298 if len(other) > len(self): 

299 return False 

300 iim = self.item_index_map 

301 for k in other: 

302 if k not in iim: 

303 return False 

304 return True 

305 

306 def union(self, *others): 

307 "union(*others) -> return a new set containing this set and others" 

308 return self.from_iterable(chain(self, *others)) 

309 

310 def iter_intersection(self, *others): 

311 "iter_intersection(*others) -> iterate over elements also in others" 

312 for k in self: 

313 for other in others: 

314 if k not in other: 

315 break 

316 else: 

317 yield k 

318 return 

319 

320 def intersection(self, *others): 

321 "intersection(*others) -> get a set with overlap of this and others" 

322 if len(others) == 1: 

323 other = others[0] 

324 return self.from_iterable(k for k in self if k in other) 

325 return self.from_iterable(self.iter_intersection(*others)) 

326 

327 def iter_difference(self, *others): 

328 "iter_difference(*others) -> iterate over elements not in others" 

329 for k in self: 

330 for other in others: 

331 if k in other: 

332 break 

333 else: 

334 yield k 

335 return 

336 

337 def difference(self, *others): 

338 "difference(*others) -> get a new set with elements not in others" 

339 if len(others) == 1: 

340 other = others[0] 

341 return self.from_iterable(k for k in self if k not in other) 

342 return self.from_iterable(self.iter_difference(*others)) 

343 

344 def symmetric_difference(self, *others): 

345 "symmetric_difference(*others) -> XOR set of this and others" 

346 ret = self.union(*others) 

347 return ret.difference(self.intersection(*others)) 

348 

349 __or__ = __ror__ = union 

350 __and__ = __rand__ = intersection 

351 __sub__ = difference 

352 __xor__ = __rxor__ = symmetric_difference 

353 

354 def __rsub__(self, other): 

355 vals = [x for x in other if x not in self] 

356 return type(other)(vals) 

357 

358 # in-place set operations 

359 def update(self, *others): 

360 "update(*others) -> add values from one or more iterables" 

361 if not others: 

362 return # raise? 

363 elif len(others) == 1: 

364 other = others[0] 

365 else: 

366 other = chain.from_iterable(others) 

367 for o in other: 

368 self.add(o) 

369 

370 def intersection_update(self, *others): 

371 "intersection_update(*others) -> discard self.difference(*others)" 

372 to_remove = self.difference(*others) 

373 if len(to_remove) > _MAX_DEAD_INTERVALS: 

374 self._bulk_discard(to_remove) 

375 return 

376 for val in to_remove: 

377 self.discard(val) 

378 

379 def difference_update(self, *others): 

380 "difference_update(*others) -> discard self.intersection(*others)" 

381 if self in others: 

382 self.clear() 

383 to_remove = self.intersection(*others) 

384 if len(to_remove) > _MAX_DEAD_INTERVALS: 

385 self._bulk_discard(to_remove) 

386 return 

387 for val in to_remove: 

388 self.discard(val) 

389 

390 def symmetric_difference_update(self, other): # note singular 'other' 

391 "symmetric_difference_update(other) -> in-place XOR with other" 

392 if self is other: 

393 self.clear() 

394 for val in other: 

395 if val in self: 

396 self.discard(val) 

397 else: 

398 self.add(val) 

399 

400 def __ior__(self, *others): 

401 self.update(*others) 

402 return self 

403 

404 def __iand__(self, *others): 

405 self.intersection_update(*others) 

406 return self 

407 

408 def __isub__(self, *others): 

409 self.difference_update(*others) 

410 return self 

411 

412 def __ixor__(self, *others): 

413 self.symmetric_difference_update(*others) 

414 return self 

415 

416 def iter_slice(self, start, stop, step=None): 

417 "iterate over a slice of the set" 

418 iterable = self 

419 # start/stop are apparent (dead-slot-free) indices, the same space 

420 # islice consumes; mapping them through _get_real_index() (item_list 

421 # space) over-counted by the dead slots before each bound. Only 

422 # negatives need normalizing, as islice rejects them. 

423 # NB: a negative step slices the reversed stream with forward bounds 

424 # (x[2:4:-1] == reversed(x)[2:4]), behavior since 2013. 

425 if start is not None and start < 0: 

426 start = max(len(self) + start, 0) 

427 if stop is not None and stop < 0: 

428 stop = max(len(self) + stop, 0) 

429 if step is not None and step < 0: 

430 step = -step 

431 iterable = reversed(self) 

432 return islice(iterable, start, stop, step) 

433 

434 # list operations 

435 def __getitem__(self, index): 

436 try: 

437 start, stop, step = index.start, index.stop, index.step 

438 except AttributeError: 

439 index = operator.index(index) 

440 else: 

441 iter_slice = self.iter_slice(start, stop, step) 

442 return self.from_iterable(iter_slice) 

443 real_index = self._get_real_index(index) 

444 return self.item_list[real_index] 

445 

446 def pop(self, index=None): 

447 "pop(index) -> remove the item at a given index (-1 by default)" 

448 item_index_map = self.item_index_map 

449 len_self = len(item_index_map) 

450 if index is None or index == -1 or index == len_self - 1: 

451 ret = self.item_list.pop() 

452 del item_index_map[ret] 

453 else: 

454 real_index = self._get_real_index(index) 

455 ret = self.item_list[real_index] 

456 self.item_list[real_index] = _MISSING 

457 del item_index_map[ret] 

458 self._add_dead(real_index) 

459 self._cull() 

460 return ret 

461 

462 def count(self, val): 

463 "count(val) -> count number of instances of value (0 or 1)" 

464 if val in self.item_index_map: 

465 return 1 

466 return 0 

467 

468 def reverse(self): 

469 "reverse() -> reverse the contents of the set in-place" 

470 reversed_list = list(reversed(self)) 

471 self.item_list[:] = reversed_list 

472 for i, item in enumerate(self.item_list): 

473 self.item_index_map[item] = i 

474 del self.dead_indices[:] 

475 

476 def sort(self, **kwargs): 

477 "sort() -> sort the contents of the set in-place" 

478 sorted_list = sorted(self, **kwargs) 

479 if sorted_list == self.item_list: 

480 return 

481 self.item_list[:] = sorted_list 

482 for i, item in enumerate(self.item_list): 

483 self.item_index_map[item] = i 

484 del self.dead_indices[:] 

485 

486 def index(self, val): 

487 "index(val) -> get the index of a value, raises if not present" 

488 try: 

489 return self._get_apparent_index(self.item_index_map[val]) 

490 except KeyError: 

491 cn = self.__class__.__name__ 

492 raise ValueError(f'{val!r} is not in {cn}') 

493 

494 

495def complement(wrapped): 

496 """Given a :class:`set`, convert it to a **complement set**. 

497 

498 Whereas a :class:`set` keeps track of what it contains, a 

499 `complement set 

500 <https://en.wikipedia.org/wiki/Complement_(set_theory)>`_ keeps 

501 track of what it does *not* contain. For example, look what 

502 happens when we intersect a normal set with a complement set:: 

503 

504 >>> list(set(range(5)) & complement(set([2, 3]))) 

505 [0, 1, 4] 

506 

507 We get the everything in the left that wasn't in the right, 

508 because intersecting with a complement is the same as subtracting 

509 a normal set. 

510 

511 Args: 

512 wrapped (set): A set or any other iterable which should be 

513 turned into a complement set. 

514 

515 All set methods and operators are supported by complement sets, 

516 between other :func:`complement`-wrapped sets and/or regular 

517 :class:`set` objects. 

518 

519 Because a complement set only tracks what elements are *not* in 

520 the set, functionality based on set contents is unavailable: 

521 :func:`len`, :func:`iter` (and for loops), and ``.pop()``. But a 

522 complement set can always be turned back into a regular set by 

523 complementing it again: 

524 

525 >>> s = set(range(5)) 

526 >>> complement(complement(s)) == s 

527 True 

528 

529 .. note:: 

530 

531 An empty complement set corresponds to the concept of a 

532 `universal set <https://en.wikipedia.org/wiki/Universal_set>`_ 

533 from mathematics. 

534 

535 Complement sets by example 

536 ^^^^^^^^^^^^^^^^^^^^^^^^^^ 

537 

538 Many uses of sets can be expressed more simply by using a 

539 complement. Rather than trying to work out in your head the proper 

540 way to invert an expression, you can just throw a complement on 

541 the set. Consider this example of a name filter:: 

542 

543 >>> class NamesFilter(object): 

544 ... def __init__(self, allowed): 

545 ... self._allowed = allowed 

546 ... 

547 ... def filter(self, names): 

548 ... return [name for name in names if name in self._allowed] 

549 >>> NamesFilter(set(['alice', 'bob'])).filter(['alice', 'bob', 'carol']) 

550 ['alice', 'bob'] 

551 

552 What if we want to just express "let all the names through"? 

553 

554 We could try to enumerate all of the expected names:: 

555 

556 ``NamesFilter({'alice', 'bob', 'carol'})`` 

557 

558 But this is very brittle -- what if at some point over this 

559 object is changed to filter ``['alice', 'bob', 'carol', 'dan']``? 

560 

561 Even worse, what about the poor programmer who next works 

562 on this piece of code? They cannot tell whether the purpose 

563 of the large allowed set was "allow everything", or if 'dan' 

564 was excluded for some subtle reason. 

565 

566 A complement set lets the programmer intention be expressed 

567 succinctly and directly:: 

568 

569 NamesFilter(complement(set())) 

570 

571 Not only is this code short and robust, it is easy to understand 

572 the intention. 

573 

574 """ 

575 if type(wrapped) is _ComplementSet: 

576 return wrapped.complemented() 

577 if type(wrapped) is frozenset: 

578 return _ComplementSet(excluded=wrapped) 

579 return _ComplementSet(excluded=set(wrapped)) 

580 

581 

582def _norm_args_typeerror(other): 

583 '''normalize args and raise type-error if there is a problem''' 

584 if type(other) in (set, frozenset): 

585 inc, exc = other, None 

586 elif type(other) is _ComplementSet: 

587 inc, exc = other._included, other._excluded 

588 else: 

589 raise TypeError('argument must be another set or complement(set)') 

590 return inc, exc 

591 

592 

593def _norm_args_notimplemented(other): 

594 '''normalize args and return NotImplemented (for overloaded operators)''' 

595 if type(other) in (set, frozenset): 

596 inc, exc = other, None 

597 elif type(other) is _ComplementSet: 

598 inc, exc = other._included, other._excluded 

599 else: 

600 return NotImplemented, None 

601 return inc, exc 

602 

603 

604class _ComplementSet: 

605 """ 

606 helper class for complement() that implements the set methods 

607 """ 

608 __slots__ = ('_included', '_excluded') 

609 

610 def __init__(self, included=None, excluded=None): 

611 if included is None: 

612 assert type(excluded) in (set, frozenset) 

613 elif excluded is None: 

614 assert type(included) in (set, frozenset) 

615 else: 

616 raise ValueError('one of included or excluded must be a set') 

617 self._included, self._excluded = included, excluded 

618 

619 def __repr__(self): 

620 if self._included is None: 

621 return f'complement({repr(self._excluded)})' 

622 return f'complement(complement({repr(self._included)}))' 

623 

624 def complemented(self): 

625 '''return a complement of the current set''' 

626 if type(self._included) is frozenset or type(self._excluded) is frozenset: 

627 return _ComplementSet(included=self._excluded, excluded=self._included) 

628 return _ComplementSet( 

629 included=None if self._excluded is None else set(self._excluded), 

630 excluded=None if self._included is None else set(self._included)) 

631 

632 __invert__ = complemented 

633 

634 def complement(self): 

635 '''convert the current set to its complement in-place''' 

636 self._included, self._excluded = self._excluded, self._included 

637 

638 def __contains__(self, item): 

639 if self._included is None: 

640 return not item in self._excluded 

641 return item in self._included 

642 

643 def add(self, item): 

644 if self._included is None: 

645 if item in self._excluded: 

646 self._excluded.remove(item) 

647 else: 

648 self._included.add(item) 

649 

650 def remove(self, item): 

651 if self._included is None: 

652 self._excluded.add(item) 

653 else: 

654 self._included.remove(item) 

655 

656 def pop(self): 

657 if self._included is None: 

658 raise NotImplementedError # self.missing.add(random.choice(gc.objects())) 

659 return self._included.pop() 

660 

661 def intersection(self, other): 

662 try: 

663 return self & other 

664 except NotImplementedError: 

665 raise TypeError('argument must be another set or complement(set)') 

666 

667 def __and__(self, other): 

668 inc, exc = _norm_args_notimplemented(other) 

669 if inc is NotImplemented: 

670 return NotImplemented 

671 if self._included is None: 

672 if exc is None: # - + 

673 return _ComplementSet(included=inc - self._excluded) 

674 else: # - - 

675 return _ComplementSet(excluded=self._excluded.union(other._excluded)) 

676 else: 

677 if inc is None: # + - 

678 return _ComplementSet(included=exc - self._included) 

679 else: # + + 

680 return _ComplementSet(included=self._included.intersection(inc)) 

681 

682 __rand__ = __and__ 

683 

684 def __iand__(self, other): 

685 inc, exc = _norm_args_notimplemented(other) 

686 if inc is NotImplemented: 

687 return NotImplemented 

688 if self._included is None: 

689 if exc is None: # - + 

690 self._excluded = inc - self._excluded # TODO: do this in place? 

691 else: # - - 

692 self._excluded |= exc 

693 else: 

694 if inc is None: # + - 

695 self._included -= exc 

696 self._included, self._excluded = None, self._included 

697 else: # + + 

698 self._included &= inc 

699 return self 

700 

701 def union(self, other): 

702 try: 

703 return self | other 

704 except NotImplementedError: 

705 raise TypeError('argument must be another set or complement(set)') 

706 

707 def __or__(self, other): 

708 inc, exc = _norm_args_notimplemented(other) 

709 if inc is NotImplemented: 

710 return NotImplemented 

711 if self._included is None: 

712 if exc is None: # - + 

713 return _ComplementSet(excluded=self._excluded - inc) 

714 else: # - - 

715 return _ComplementSet(excluded=self._excluded.intersection(exc)) 

716 else: 

717 if inc is None: # + - 

718 return _ComplementSet(excluded=exc - self._included) 

719 else: # + + 

720 return _ComplementSet(included=self._included.union(inc)) 

721 

722 __ror__ = __or__ 

723 

724 def __ior__(self, other): 

725 inc, exc = _norm_args_notimplemented(other) 

726 if inc is NotImplemented: 

727 return NotImplemented 

728 if self._included is None: 

729 if exc is None: # - + 

730 self._excluded -= inc 

731 else: # - - 

732 self._excluded &= exc 

733 else: 

734 if inc is None: # + - 

735 self._included, self._excluded = None, exc - self._included # TODO: do this in place? 

736 else: # + + 

737 self._included |= inc 

738 return self 

739 

740 def update(self, items): 

741 if type(items) in (set, frozenset): 

742 inc, exc = items, None 

743 elif type(items) is _ComplementSet: 

744 inc, exc = items._included, items._excluded 

745 else: 

746 inc, exc = frozenset(items), None 

747 if self._included is None: 

748 if exc is None: # - + 

749 self._excluded &= inc 

750 else: # - - 

751 self._excluded.discard(exc) 

752 else: 

753 if inc is None: # + - 

754 self._included &= exc 

755 self._included, self._excluded = None, self._excluded 

756 else: # + + 

757 self._included.update(inc) 

758 

759 def discard(self, items): 

760 if type(items) in (set, frozenset): 

761 inc, exc = items, None 

762 elif type(items) is _ComplementSet: 

763 inc, exc = items._included, items._excluded 

764 else: 

765 inc, exc = frozenset(items), None 

766 if self._included is None: 

767 if exc is None: # - + 

768 self._excluded.update(inc) 

769 else: # - - 

770 self._included, self._excluded = exc - self._excluded, None 

771 else: 

772 if inc is None: # + - 

773 self._included &= exc 

774 else: # + + 

775 self._included.discard(inc) 

776 

777 def symmetric_difference(self, other): 

778 try: 

779 return self ^ other 

780 except NotImplementedError: 

781 raise TypeError('argument must be another set or complement(set)') 

782 

783 def __xor__(self, other): 

784 inc, exc = _norm_args_notimplemented(other) 

785 if inc is NotImplemented: 

786 return NotImplemented 

787 if inc is NotImplemented: 

788 return NotImplemented 

789 if self._included is None: 

790 if exc is None: # - + 

791 return _ComplementSet(excluded=self._excluded - inc) 

792 else: # - - 

793 return _ComplementSet(included=self._excluded.symmetric_difference(exc)) 

794 else: 

795 if inc is None: # + - 

796 return _ComplementSet(excluded=exc - self._included) 

797 else: # + + 

798 return _ComplementSet(included=self._included.symmetric_difference(inc)) 

799 

800 __rxor__ = __xor__ 

801 

802 def symmetric_difference_update(self, other): 

803 inc, exc = _norm_args_typeerror(other) 

804 if self._included is None: 

805 if exc is None: # - + 

806 self._excluded |= inc 

807 else: # - - 

808 self._excluded.symmetric_difference_update(exc) 

809 self._included, self._excluded = self._excluded, None 

810 else: 

811 if inc is None: # + - 

812 self._included |= exc 

813 self._included, self._excluded = None, self._included 

814 else: # + + 

815 self._included.symmetric_difference_update(inc) 

816 

817 def isdisjoint(self, other): 

818 inc, exc = _norm_args_typeerror(other) 

819 if inc is NotImplemented: 

820 return NotImplemented 

821 if self._included is None: 

822 if exc is None: # - + 

823 return inc.issubset(self._excluded) 

824 else: # - - 

825 return False 

826 else: 

827 if inc is None: # + - 

828 return self._included.issubset(exc) 

829 else: # + + 

830 return self._included.isdisjoint(inc) 

831 

832 def issubset(self, other): 

833 '''everything missing from other is also missing from self''' 

834 try: 

835 return self <= other 

836 except NotImplementedError: 

837 raise TypeError('argument must be another set or complement(set)') 

838 

839 def __le__(self, other): 

840 inc, exc = _norm_args_notimplemented(other) 

841 if inc is NotImplemented: 

842 return NotImplemented 

843 if self._included is None: 

844 if exc is None: # - + 

845 return False 

846 else: # - - 

847 return self._excluded.issuperset(exc) 

848 else: 

849 if inc is None: # + - 

850 return self._included.isdisjoint(exc) 

851 else: # + + 

852 return self._included.issubset(inc) 

853 

854 def __lt__(self, other): 

855 inc, exc = _norm_args_notimplemented(other)