stl_treemap.tree_set
Ordered set backed by a red-black tree.
1"""Ordered set backed by a red-black tree.""" 2 3from __future__ import annotations 4 5from collections.abc import Callable, Collection, Iterable 6from typing import Any 7 8from stl_treemap.insertion_result import InsertionResult 9from stl_treemap.iterators import ReverseIterator, TreeIterator 10from stl_treemap.policies import KeyOnlyPolicy 11from stl_treemap.py_iterators import PyIterator, PyReverseIterator 12from stl_treemap.tree import Tree 13from stl_treemap.tree_node import TreeNode 14 15 16class TreeSet[K](Collection[K]): 17 """ 18 Ordered set of unique keys backed by a red-black tree. 19 20 Elements are kept in ascending order at all times. Lookup, insertion, 21 and deletion are all O(log n). 22 23 Example:: 24 25 s = TreeSet() 26 s.add(1) 27 s.add(2) 28 s.add(1) # duplicate; ignored 29 for key in s: 30 print(key) # 1, 2 31 """ 32 33 def __init__(self, iterable: Iterable[K] | None = None, *args) -> None: 34 """ 35 Create an empty set, or pre-populate it from an iterable of keys. 36 37 Duplicate keys in *iterable* are silently ignored (set semantics). 38 39 Args: 40 iterable: Optional iterable of keys. 41 args: another way to provide key-list 42 43 Raises: 44 TypeError: When *iterable* is not iterable. 45 46 Example:: 47 48 s = TreeSet() 49 s = TreeSet([3, 1, 2, 1]) # {1,2,3} — duplicates dropped 50 s = TreeSet({3, 1, 2}) # from a Python set 51 s = TreeSet(range(1, 4)) 52 53 """ 54 self._t: Tree[K, K] = Tree() 55 self._t.value_policy = KeyOnlyPolicy() 56 if iterable is not None: 57 self.update(iterable) 58 if args: 59 self.update(args) 60 61 def update(self, *iterables: Iterable[K]) -> None: 62 """ 63 Add all keys to the current set. 64 65 Duplicate keys in *iterable* are silently ignored (set semantics). 66 67 Args: 68 iterables: One or more list/tuple/etc 69 70 Raises: 71 TypeError: When *iterable* is not iterable. 72 73 Example:: 74 75 TreeSet().update(TreeSet({3, 1, 2})) # from a TreeSet 76 TreeSet().update([3, 1, 2, 1]) # {1,2,3} — duplicates dropped 77 TreeSet().update({3, 1, 2}) # from a Python set 78 TreeSet().update(range(1, 4)) 79 80 """ 81 if iterables is not None: 82 for iterable in iterables: 83 if not hasattr(iterable, "__iter__"): 84 raise TypeError("TreeSet accepts only iterable objects") 85 for k in iterable: 86 self.add(k) 87 88 # ------------------------------------------------------------------ 89 # Python set-compatible methods 90 # ------------------------------------------------------------------ 91 92 def clear(self) -> None: 93 """ 94 Remove all elements. 95 96 Example:: 97 98 s = TreeSet([1, 2, 3]) 99 s.clear() 100 len(s) # 0 101 102 """ 103 self._t.clear() 104 105 def add(self, key: K) -> None: 106 """ 107 Insert *key* if it is not already present. 108 109 Example:: 110 111 s = TreeSet() 112 s.add(1) 113 s.add(1) # ignored 114 len(s) # 1 115 116 """ 117 n: TreeNode[K, K] = TreeNode() 118 n.key = key 119 self._t.insert_unique(n) 120 121 def discard(self, key: K) -> None: 122 """ 123 Remove *key* if present; do nothing when it is absent. 124 125 Example:: 126 127 s = TreeSet([1, 2, 3]) 128 s.discard(2) # s is now {1,3} 129 s.discard(99) # no-op 130 131 """ 132 it = self._t.find(key) 133 if not it.equals(self._t.end()): 134 self._t.erase(it.node) 135 136 def remove(self, key: K) -> None: 137 """ 138 Remove *key*, raising KeyError when it is absent. 139 140 Args: 141 key: Key to remove. 142 143 Raises: 144 KeyError: When *key* is not present. 145 146 Example:: 147 148 s = TreeSet([1, 2, 3]) 149 s.remove(2) # s is now {1,3} 150 s.remove(99) # raises KeyError 151 152 """ 153 it = self._t.find(key) 154 if not it.equals(self._t.end()): 155 self._t.erase(it.node) 156 else: 157 raise KeyError(key) 158 159 def delete(self, key: K) -> None: 160 """ 161 @private Remove *key* if present; do nothing when absent. Alias for discard(). 162 163 Example:: 164 165 s = TreeSet([1, 2, 3]) 166 s.delete(2) # s is now {1,3} 167 s.delete(99) # no-op 168 169 """ 170 self.discard(key) 171 172 def pop(self, key: K | None = None, default: K | None = None) -> K | None: 173 """ 174 Remove *key* and return it, or return *default* when absent. 175 176 When called with no arguments, removes and returns the smallest element. 177 178 Args: 179 key: Key to remove. When None, the smallest element is removed. 180 default: Value to return when *key* is absent. 181 182 Raises: 183 KeyError: When called with no arguments on an empty set. 184 185 Example:: 186 187 s = TreeSet([1, 2, 3]) 188 s.pop(2) # 2, s is now {1,3} 189 s.pop(9) # None 190 s.pop(9, 0) # 0 191 s.pop() # 1 — removes and returns smallest element 192 193 """ 194 if self.size == 0: 195 raise KeyError("pop from an empty set") 196 it = self._t.find(key) if key is not None else self.begin() 197 if not it.equals(self._t.end()): 198 k = it.key 199 self._t.erase(it.node) 200 return k 201 return default 202 203 def has(self, key: K) -> bool: 204 """ 205 @private Return True when *key* exists in the set. 206 207 Example:: 208 209 s = TreeSet([1, 2, 3]) 210 s.has(1) # True 211 s.has(4) # False 212 213 """ 214 it = self._t.find(key) 215 return not it.equals(self._t.end()) 216 217 def keys(self) -> PyIterator[K]: 218 """ 219 @private Return a forward iterator over all keys in ascending order. 220 221 Example:: 222 223 s = TreeSet([1, 2, 3]) 224 list(s.keys()) # [1, 2, 3] 225 list(s.keys().backwards()) # [3, 2, 1] 226 227 """ 228 return self._t.keys() 229 230 @property 231 def size(self) -> int: 232 """ 233 @private Number of elements in the set. 234 235 Example:: 236 237 s = TreeSet([1, 2, 3]) 238 s.size # 3 239 240 """ 241 return self._t.size() 242 243 def __contains__(self, key: K) -> bool: 244 """ 245 Return True when *key* is in the set. 246 247 Example:: 248 249 s = TreeSet([1, 2, 3]) 250 1 in s # True 251 4 in s # False 252 253 """ 254 return self.has(key) 255 256 def __iter__(self) -> PyIterator[K]: 257 """ 258 Iterate over all keys in ascending order. 259 260 Example:: 261 262 s = TreeSet([1, 2, 3]) 263 for key in s: 264 print(key) # 1, 2, 3 265 266 """ 267 return self._t.keys() 268 269 def __len__(self) -> int: 270 """ 271 Return the number of elements in the set. 272 273 Example:: 274 275 s = TreeSet([1, 2, 3]) 276 len(s) # 3 277 278 """ 279 return self._t.size() 280 281 def __str__(self) -> str: 282 """ 283 Return a string representation in the form {key1,key2,...}. 284 285 Example:: 286 287 s = TreeSet([1, 2, 3]) 288 str(s) # "{1,2,3}" 289 290 """ 291 return str(self._t) 292 293 def __repr__(self) -> str: 294 """ 295 Return a string representation of the set's contents. 296 297 Example:: 298 299 s = TreeSet([1, 2, 3]) 300 repr(s) # "{1,2,3}" 301 302 """ 303 return self.__str__() 304 305 # ------------------------------------------------------------------ 306 # Set algebra operators 307 # ------------------------------------------------------------------ 308 309 def __or__(self, other: Iterable[K]) -> TreeSet[K]: 310 """ 311 Return a new set containing all keys from this set and *other*. 312 313 Example:: 314 315 s1 = TreeSet([1, 2, 3]) 316 s2 = TreeSet([2, 3, 4]) 317 str(s1 | s2) # "{1,2,3,4}" 318 319 """ 320 if not hasattr(other, "__iter__"): 321 return NotImplemented 322 res = TreeSet[K](self.keys()) 323 res.update(other) 324 return res 325 326 def __ror__(self, other: Any) -> TreeSet[K]: 327 """ 328 Return a union when this TreeSet is on the right-hand side of ``|``. 329 330 Example:: 331 332 s = TreeSet([2, 3, 4]) 333 str({1, 2, 3} | s) # "{1,2,3,4}" 334 335 """ 336 return self.__or__(other) 337 338 def __ior__(self, other: Any) -> TreeSet[K]: 339 """ 340 Add all keys from *other* to this set in-place. 341 342 Example:: 343 344 s = TreeSet([1, 2]) 345 s |= {3, 4} 346 str(s) # "{1,2,3,4}" 347 348 """ 349 if not hasattr(other, "__iter__"): 350 return NotImplemented 351 self.update(other) 352 return self 353 354 def __and__(self, other: Any) -> TreeSet[K]: 355 """ 356 Return a new set containing only keys present in both this set and *other*. 357 358 Example:: 359 360 s1 = TreeSet([1, 2, 3]) 361 s2 = TreeSet([2, 3, 4]) 362 str(s1 & s2) # "{2,3}" 363 364 """ 365 if not hasattr(other, "__iter__"): 366 return NotImplemented 367 res = TreeSet[K]() 368 for k in other: 369 if k in self: 370 res.add(k) 371 return res 372 373 def __rand__(self, other: Any) -> TreeSet[K]: 374 """ 375 Return intersection when this TreeSet is on the right-hand side of ``&``. 376 377 Example:: 378 379 s = TreeSet([2, 3, 4]) 380 str({1, 2, 3} & s) # "{2,3}" 381 382 """ 383 return self.__and__(other) 384 385 def __iand__(self, other: Any) -> TreeSet[K]: 386 """ 387 Keep only keys also in *other*, in-place. 388 389 Example:: 390 391 s = TreeSet([1, 2, 3]) 392 s &= {2, 3, 4} 393 str(s) # "{2,3}" 394 395 """ 396 if not hasattr(other, "__iter__"): 397 return NotImplemented 398 other_items = TreeSet[K](other) 399 for k in self: 400 if k not in other_items: 401 self.delete(k) 402 return self 403 404 def __sub__(self, other: Any) -> TreeSet[K]: 405 """ 406 Return a new set with keys from this set that are not in *other*. 407 408 Example:: 409 410 s1 = TreeSet([1, 2, 3]) 411 s2 = TreeSet([2, 3, 4]) 412 str(s1 - s2) # "{1}" 413 414 """ 415 if not hasattr(other, "__iter__"): 416 return NotImplemented 417 other_keys = TreeSet(other) 418 res = TreeSet[K]() 419 for k in self.keys(): 420 if k not in other_keys: 421 res.add(k) 422 return res 423 424 def __rsub__(self, other: Any) -> TreeSet[K]: 425 """ 426 Return *other* - this set when this TreeSet is on the right-hand side of ``-``. 427 428 Example:: 429 430 s = TreeSet([2, 3, 4]) 431 str({1, 2, 3} - s) # "{1}" 432 433 """ 434 if not hasattr(other, "__iter__"): 435 return NotImplemented 436 res = TreeSet[K](other) 437 for k in self.keys(): 438 res.delete(k) 439 return res 440 441 def __isub__(self, other: Any) -> TreeSet[K]: 442 """ 443 Remove all keys in *other* from this set in-place. 444 445 Example:: 446 447 s = TreeSet([1, 2, 3]) 448 s -= {2, 3, 4} 449 str(s) # "{1}" 450 451 """ 452 if not hasattr(other, "__iter__"): 453 return NotImplemented 454 for k in other: 455 self.delete(k) 456 return self 457 458 def __xor__(self, other: Any) -> TreeSet[K]: 459 """ 460 Return a new set with keys in exactly one of this set and *other*. 461 462 Example:: 463 464 s1 = TreeSet([1, 2, 3]) 465 s2 = TreeSet([2, 3, 4]) 466 str(s1 ^ s2) # "{1,4}" 467 468 """ 469 if not hasattr(other, "__iter__"): 470 return NotImplemented 471 other_set = TreeSet(other) 472 res = TreeSet[K]() 473 for k in self.keys(): 474 if k not in other_set: 475 res.add(k) 476 for k in other_set: 477 if not self.has(k): 478 res.add(k) 479 return res 480 481 def __rxor__(self, other: Any) -> TreeSet[K]: 482 """ 483 Return symmetric difference when this TreeSet is on the right-hand side of ``^``. 484 485 Example:: 486 487 s = TreeSet([2, 3, 4]) 488 str({1, 2, 3} ^ s) # "{1,4}" 489 490 """ 491 return self.__xor__(other) 492 493 def __ixor__(self, other: Any) -> TreeSet[K]: 494 """ 495 Apply symmetric difference with *other* to this set in-place. 496 497 Example:: 498 499 s = TreeSet([1, 2, 3]) 500 s ^= {2, 3, 4} 501 str(s) # "{1,4}" 502 503 """ 504 if not hasattr(other, "__iter__"): 505 return NotImplemented 506 for k in other: 507 if self.has(k): 508 self.delete(k) 509 else: 510 self.add(k) 511 return self 512 513 def __le__(self, other: Any) -> bool: 514 """ 515 Return True when every element of this set is in *other* (subset or equal). 516 517 Example:: 518 519 TreeSet([1, 2]) <= TreeSet([1, 2, 3]) # True 520 TreeSet([1, 2]) <= TreeSet([1, 2]) # True 521 522 """ 523 if not hasattr(other, "__iter__"): 524 return NotImplemented 525 other_set = TreeSet(other) 526 return all(k in other_set for k in self.keys()) 527 528 def __lt__(self, other: Any) -> bool: 529 """ 530 Return True when this set is a proper subset of *other*. 531 532 Example:: 533 534 TreeSet([1, 2]) < TreeSet([1, 2, 3]) # True 535 TreeSet([1, 2]) < TreeSet([1, 2]) # False 536 537 """ 538 if not hasattr(other, "__iter__"): 539 return NotImplemented 540 other_set = TreeSet(other) 541 return len(self) < len(other_set) and all(k in other_set for k in self.keys()) 542 543 def __ge__(self, other: Any) -> bool: 544 """ 545 Return True when every element of *other* is in this set (superset or equal). 546 547 Example:: 548 549 TreeSet([1, 2, 3]) >= TreeSet([1, 2]) # True 550 TreeSet([1, 2]) >= TreeSet([1, 2]) # True 551 552 """ 553 if not hasattr(other, "__iter__"): 554 return NotImplemented 555 return all(self.has(k) for k in other) 556 557 def __gt__(self, other: Any) -> bool: 558 """ 559 Return True when this set is a proper superset of *other*. 560 561 Example:: 562 563 TreeSet([1, 2, 3]) > TreeSet([1, 2]) # True 564 TreeSet([1, 2]) > TreeSet([1, 2]) # False 565 566 """ 567 if not hasattr(other, "__iter__"): 568 return NotImplemented 569 return len(self) > len(other) and all(self.has(k) for k in other) 570 571 def issubset(self, other: Any) -> bool: 572 """ 573 Return True when every element of this set is in *other*. 574 575 Example:: 576 577 TreeSet([1, 2]).issubset([1, 2, 3]) # True 578 TreeSet([1, 4]).issubset([1, 2, 3]) # False 579 580 """ 581 return self <= other 582 583 def issuperset(self, other: Any) -> bool: 584 """ 585 Return True when every element of *other* is in this set. 586 587 Example:: 588 589 TreeSet([1, 2, 3]).issuperset([1, 2]) # True 590 TreeSet([1, 2]).issuperset([1, 3]) # False 591 592 """ 593 return self >= other 594 595 def isdisjoint(self, other: Any) -> bool: 596 """ 597 Return True when this set and *other* share no common elements. 598 599 Example:: 600 601 TreeSet([1, 2]).isdisjoint([3, 4]) # True 602 TreeSet([1, 2]).isdisjoint([2, 3]) # False 603 604 """ 605 if not hasattr(other, "__iter__"): 606 raise TypeError(f"Operation is not supported with instance of {type(other)}") 607 return all(not self.has(k) for k in other) 608 609 def intersection_update(self, *others: Iterable[K]) -> None: 610 """ 611 Keep only keys present in this set and all of *others*, in-place. 612 613 Example:: 614 615 s = TreeSet([1, 2, 3, 4]) 616 s.intersection_update([2, 3, 5], [3, 6]) 617 str(s) # "{3}" 618 619 """ 620 all_others = TreeSet() 621 if len(others) >= 1: 622 all_others = TreeSet(others[0]) 623 for other in others[1:]: 624 if not hasattr(other, "__iter__"): 625 raise TypeError(f"Operation is not supported with instance of {type(other)}") 626 all_others &= other 627 for k in self: 628 if k not in all_others: 629 self.discard(k) 630 631 def difference_update(self, *others: Iterable[K]) -> None: 632 """ 633 Remove all keys found in any of *others* from this set, in-place. 634 635 Example:: 636 637 s = TreeSet([1, 2, 3, 4]) 638 s.difference_update([2, 3], [4]) 639 str(s) # "{1}" 640 641 """ 642 for other in others: 643 if not hasattr(other, "__iter__"): 644 raise TypeError(f"Operation is not supported with instance of {type(other)}") 645 for k in other: 646 self.discard(k) 647 648 def symmetric_difference_update(self, other: Iterable[K]) -> None: 649 """ 650 Apply symmetric difference with *other* to this set in-place. 651 652 Example:: 653 654 s = TreeSet([1, 2, 3]) 655 s.symmetric_difference_update([2, 3, 4]) 656 str(s) # "{1,4}" 657 658 """ 659 self ^= other 660 661 def union(self, *others: Iterable[K]) -> TreeSet[K]: 662 """ 663 Return a new set containing all keys from this set and all of *others*. 664 665 Example:: 666 667 s = TreeSet([1, 2]) 668 str(s.union([3, 4], [5])) # "{1,2,3,4,5}" 669 670 """ 671 res = TreeSet[K](self.keys()) 672 for other in others: 673 if not hasattr(other, "__iter__"): 674 raise TypeError(f"Operation is not supported with instance of {type(other)}") 675 for k in other: 676 res.add(k) 677 return res 678 679 def intersection(self, *others: Iterable[K]) -> TreeSet[K]: 680 """ 681 Return a new set with keys common to this set and all of *others*. 682 683 Example:: 684 685 s = TreeSet([1, 2, 3, 4]) 686 str(s.intersection([2, 3, 5], [3, 6])) # "{3}" 687 688 """ 689 combined: set = set(next(iter(others))) if others else set() 690 for other in list(others)[1:]: 691 combined &= set(other) 692 res = TreeSet[K]() 693 for k in self.keys(): 694 if k in combined: 695 res.add(k) 696 return res 697 698 def difference(self, *others: Iterable[K]) -> TreeSet[K]: 699 """ 700 Return a new set with keys in this set that are not in any of *others*. 701 702 Example:: 703 704 s = TreeSet([1, 2, 3, 4]) 705 str(s.difference([2, 3], [4])) # "{1}" 706 707 """ 708 excluded: set = set() 709 for other in others: 710 excluded |= set(other) 711 res = TreeSet[K]() 712 for k in self.keys(): 713 if k not in excluded: 714 res.add(k) 715 return res 716 717 def symmetric_difference(self, other: Iterable[K]) -> TreeSet[K]: 718 """ 719 Return a new set with keys in exactly one of this set and *other*. 720 721 Example:: 722 723 s = TreeSet([1, 2, 3]) 724 str(s.symmetric_difference([2, 3, 4])) # "{1,4}" 725 726 """ 727 return self ^ other 728 729 def __copy__(self) -> TreeSet[K]: 730 """ 731 Create a shallow copy of the set. 732 733 Example:: 734 735 import copy 736 737 s = TreeSet([1, 2, 3]) 738 s2 = copy.copy(s) 739 s2.add(4) 740 str(s) # "{1,2,3}" — original unchanged 741 str(s2) # "{1,2,3,4}" 742 743 """ 744 return TreeSet[K](self) 745 746 # ------------------------------------------------------------------ 747 # Additional iteration 748 # ------------------------------------------------------------------ 749 750 def backwards(self) -> PyReverseIterator[K]: 751 """ 752 Return a reverse iterator over all keys in descending order. 753 754 Example:: 755 756 s = TreeSet([1, 2, 3]) 757 list(s.backwards()) # [3, 2, 1] 758 759 """ 760 return self._t.keys().backwards() 761 762 # ------------------------------------------------------------------ 763 # Custom comparator 764 # ------------------------------------------------------------------ 765 766 @property 767 def compare_func(self) -> Callable[[Any, Any], int]: 768 """ 769 @private The current 3-way comparison function used to order keys. 770 771 Setting this property clears all existing elements because the 772 current ordering is no longer valid. 773 774 Example:: 775 776 s = TreeSet() 777 s.compare_func = lambda a, b: -1 if a < b else (1 if a > b else 0) 778 s.add(3) 779 s.add(1) 780 list(s) # [1, 3] 781 782 """ 783 return self._t.compare 784 785 @compare_func.setter 786 def compare_func(self, func: Callable[[Any, Any], int]) -> None: 787 """@private Replace the comparison function and clear all elements.""" 788 self.clear() 789 self._t.compare = func 790 791 # ------------------------------------------------------------------ 792 # STL-style iterators 793 # ------------------------------------------------------------------ 794 795 def begin(self) -> TreeIterator[K, K]: 796 """ 797 Return a forward STL-like iterator to the first element. 798 799 Example:: 800 801 s = TreeSet([1, 2, 3]) 802 it = s.begin() 803 while not it.equals(s.end()): 804 print(it.key) 805 it.next() 806 # 1, 2, 3 807 808 """ 809 return self._t.begin() 810 811 def end(self) -> TreeIterator[K, K]: 812 """ 813 Return a forward STL-like iterator past the last element. 814 815 Example:: 816 817 s = TreeSet([1, 2, 3]) 818 it = s.begin() 819 while not it.equals(s.end()): 820 print(it.key) 821 it.next() 822 823 """ 824 return self._t.end() 825 826 def find(self, key: K) -> TreeIterator[K, K]: 827 """ 828 Return an STL-like iterator to the element with *key*, or end() if absent. 829 830 Example:: 831 832 s = TreeSet([1, 2, 3]) 833 it = s.find(2) 834 if not it.equals(s.end()): 835 print(it.key) # 2 836 s.find(99).equals(s.end()) # True 837 838 """ 839 return self._t.find(key) 840 841 def insert_unique(self, key: K) -> InsertionResult[TreeIterator[K, K]]: 842 """ 843 Insert *key* only when it is not already present. 844 845 Returns: 846 InsertionResult with was_added=True when the key was new; 847 was_added=False when the key already existed. 848 849 Example:: 850 851 s = TreeSet() 852 res = s.insert_unique(1) 853 res.was_added # True 854 res2 = s.insert_unique(1) 855 res2.was_added # False 856 857 """ 858 n: TreeNode[K, K] = TreeNode() 859 n.key = key 860 return self._t.insert_unique(n) 861 862 def insert_or_replace(self, key: K) -> InsertionResult[TreeIterator[K, K]]: 863 """ 864 Insert *key* if absent; if present, "replace" (update the same node). 865 866 Returns: 867 InsertionResult with was_added=True on new insertion, or 868 was_replaced=True when the key already existed. 869 870 Example:: 871 872 s = TreeSet() 873 res = s.insert_or_replace(1) 874 res.was_added # True 875 res2 = s.insert_or_replace(1) 876 res2.was_replaced # True 877 878 """ 879 n: TreeNode[K, K] = TreeNode() 880 n.key = key 881 return self._t.insert_or_replace(n) 882 883 def erase(self, iterator: TreeIterator[K, K]) -> None: 884 """ 885 Remove the element pointed to by *iterator*. 886 887 Example:: 888 889 s = TreeSet([1, 2, 3]) 890 it = s.find(2) 891 s.erase(it) 892 str(s) # "{1,3}" 893 894 """ 895 self._t.erase(iterator.node) 896 897 def lower_bound(self, key: K) -> TreeIterator[K, K]: 898 """ 899 Return an STL-like iterator to the first element with key >= *key*, or end(). 900 901 Example:: 902 903 s = TreeSet([2, 4, 6, 8]) 904 lo = s.lower_bound(3) # iterator to 4 905 hi = s.upper_bound(6) # iterator to 8 906 it = lo 907 while not it.equals(hi): 908 print(it.key) # 4, 6 909 it.next() 910 911 """ 912 return self._t.lower_bound(key) 913 914 def rbegin(self) -> ReverseIterator[K, K]: 915 """ 916 Return a reverse STL-like iterator to the element with the largest key. 917 918 Example:: 919 920 s = TreeSet([1, 2, 3]) 921 it = s.rbegin() 922 while not it.equals(s.rend()): 923 print(it.key) # 3, 2, 1 924 it.next() 925 926 """ 927 return self._t.rbegin() 928 929 def rend(self) -> ReverseIterator[K, K]: 930 """ 931 Return a reverse STL-like iterator before the element with the smallest key. 932 933 Example:: 934 935 s = TreeSet([1, 2, 3]) 936 it = s.rbegin() 937 while not it.equals(s.rend()): 938 print(it.key) 939 it.next() 940 941 """ 942 return self._t.rend() 943 944 def upper_bound(self, key: K) -> TreeIterator[K, K]: 945 """ 946 Return an STL-like iterator to the first element with key > *key*, or end(). 947 948 Example:: 949 950 s = TreeSet([2, 4, 6, 8]) 951 lo = s.lower_bound(3) # iterator to 4 952 hi = s.upper_bound(6) # iterator to 8 953 it = lo 954 while not it.equals(hi): 955 print(it.key) # 4, 6 956 it.next() 957 958 """ 959 return self._t.upper_bound(key) 960 961 def first(self) -> K | None: 962 """ 963 Return the smallest element, or None when the set is empty. 964 965 Example:: 966 967 s = TreeSet([1, 2, 3]) 968 s.first() # 1 969 TreeSet().first() # None 970 971 """ 972 result = self._t.first() 973 return result 974 975 def last(self) -> K | None: 976 """ 977 Return the largest element, or None when the set is empty. 978 979 Example:: 980 981 s = TreeSet([1, 2, 3]) 982 s.last() # 3 983 TreeSet().last() # None 984 985 """ 986 result = self._t.last() 987 return result
class
TreeSet(collections.abc.Collection[K], typing.Generic[K]):
17class TreeSet[K](Collection[K]): 18 """ 19 Ordered set of unique keys backed by a red-black tree. 20 21 Elements are kept in ascending order at all times. Lookup, insertion, 22 and deletion are all O(log n). 23 24 Example:: 25 26 s = TreeSet() 27 s.add(1) 28 s.add(2) 29 s.add(1) # duplicate; ignored 30 for key in s: 31 print(key) # 1, 2 32 """ 33 34 def __init__(self, iterable: Iterable[K] | None = None, *args) -> None: 35 """ 36 Create an empty set, or pre-populate it from an iterable of keys. 37 38 Duplicate keys in *iterable* are silently ignored (set semantics). 39 40 Args: 41 iterable: Optional iterable of keys. 42 args: another way to provide key-list 43 44 Raises: 45 TypeError: When *iterable* is not iterable. 46 47 Example:: 48 49 s = TreeSet() 50 s = TreeSet([3, 1, 2, 1]) # {1,2,3} — duplicates dropped 51 s = TreeSet({3, 1, 2}) # from a Python set 52 s = TreeSet(range(1, 4)) 53 54 """ 55 self._t: Tree[K, K] = Tree() 56 self._t.value_policy = KeyOnlyPolicy() 57 if iterable is not None: 58 self.update(iterable) 59 if args: 60 self.update(args) 61 62 def update(self, *iterables: Iterable[K]) -> None: 63 """ 64 Add all keys to the current set. 65 66 Duplicate keys in *iterable* are silently ignored (set semantics). 67 68 Args: 69 iterables: One or more list/tuple/etc 70 71 Raises: 72 TypeError: When *iterable* is not iterable. 73 74 Example:: 75 76 TreeSet().update(TreeSet({3, 1, 2})) # from a TreeSet 77 TreeSet().update([3, 1, 2, 1]) # {1,2,3} — duplicates dropped 78 TreeSet().update({3, 1, 2}) # from a Python set 79 TreeSet().update(range(1, 4)) 80 81 """ 82 if iterables is not None: 83 for iterable in iterables: 84 if not hasattr(iterable, "__iter__"): 85 raise TypeError("TreeSet accepts only iterable objects") 86 for k in iterable: 87 self.add(k) 88 89 # ------------------------------------------------------------------ 90 # Python set-compatible methods 91 # ------------------------------------------------------------------ 92 93 def clear(self) -> None: 94 """ 95 Remove all elements. 96 97 Example:: 98 99 s = TreeSet([1, 2, 3]) 100 s.clear() 101 len(s) # 0 102 103 """ 104 self._t.clear() 105 106 def add(self, key: K) -> None: 107 """ 108 Insert *key* if it is not already present. 109 110 Example:: 111 112 s = TreeSet() 113 s.add(1) 114 s.add(1) # ignored 115 len(s) # 1 116 117 """ 118 n: TreeNode[K, K] = TreeNode() 119 n.key = key 120 self._t.insert_unique(n) 121 122 def discard(self, key: K) -> None: 123 """ 124 Remove *key* if present; do nothing when it is absent. 125 126 Example:: 127 128 s = TreeSet([1, 2, 3]) 129 s.discard(2) # s is now {1,3} 130 s.discard(99) # no-op 131 132 """ 133 it = self._t.find(key) 134 if not it.equals(self._t.end()): 135 self._t.erase(it.node) 136 137 def remove(self, key: K) -> None: 138 """ 139 Remove *key*, raising KeyError when it is absent. 140 141 Args: 142 key: Key to remove. 143 144 Raises: 145 KeyError: When *key* is not present. 146 147 Example:: 148 149 s = TreeSet([1, 2, 3]) 150 s.remove(2) # s is now {1,3} 151 s.remove(99) # raises KeyError 152 153 """ 154 it = self._t.find(key) 155 if not it.equals(self._t.end()): 156 self._t.erase(it.node) 157 else: 158 raise KeyError(key) 159 160 def delete(self, key: K) -> None: 161 """ 162 @private Remove *key* if present; do nothing when absent. Alias for discard(). 163 164 Example:: 165 166 s = TreeSet([1, 2, 3]) 167 s.delete(2) # s is now {1,3} 168 s.delete(99) # no-op 169 170 """ 171 self.discard(key) 172 173 def pop(self, key: K | None = None, default: K | None = None) -> K | None: 174 """ 175 Remove *key* and return it, or return *default* when absent. 176 177 When called with no arguments, removes and returns the smallest element. 178 179 Args: 180 key: Key to remove. When None, the smallest element is removed. 181 default: Value to return when *key* is absent. 182 183 Raises: 184 KeyError: When called with no arguments on an empty set. 185 186 Example:: 187 188 s = TreeSet([1, 2, 3]) 189 s.pop(2) # 2, s is now {1,3} 190 s.pop(9) # None 191 s.pop(9, 0) # 0 192 s.pop() # 1 — removes and returns smallest element 193 194 """ 195 if self.size == 0: 196 raise KeyError("pop from an empty set") 197 it = self._t.find(key) if key is not None else self.begin() 198 if not it.equals(self._t.end()): 199 k = it.key 200 self._t.erase(it.node) 201 return k 202 return default 203 204 def has(self, key: K) -> bool: 205 """ 206 @private Return True when *key* exists in the set. 207 208 Example:: 209 210 s = TreeSet([1, 2, 3]) 211 s.has(1) # True 212 s.has(4) # False 213 214 """ 215 it = self._t.find(key) 216 return not it.equals(self._t.end()) 217 218 def keys(self) -> PyIterator[K]: 219 """ 220 @private Return a forward iterator over all keys in ascending order. 221 222 Example:: 223 224 s = TreeSet([1, 2, 3]) 225 list(s.keys()) # [1, 2, 3] 226 list(s.keys().backwards()) # [3, 2, 1] 227 228 """ 229 return self._t.keys() 230 231 @property 232 def size(self) -> int: 233 """ 234 @private Number of elements in the set. 235 236 Example:: 237 238 s = TreeSet([1, 2, 3]) 239 s.size # 3 240 241 """ 242 return self._t.size() 243 244 def __contains__(self, key: K) -> bool: 245 """ 246 Return True when *key* is in the set. 247 248 Example:: 249 250 s = TreeSet([1, 2, 3]) 251 1 in s # True 252 4 in s # False 253 254 """ 255 return self.has(key) 256 257 def __iter__(self) -> PyIterator[K]: 258 """ 259 Iterate over all keys in ascending order. 260 261 Example:: 262 263 s = TreeSet([1, 2, 3]) 264 for key in s: 265 print(key) # 1, 2, 3 266 267 """ 268 return self._t.keys() 269 270 def __len__(self) -> int: 271 """ 272 Return the number of elements in the set. 273 274 Example:: 275 276 s = TreeSet([1, 2, 3]) 277 len(s) # 3 278 279 """ 280 return self._t.size() 281 282 def __str__(self) -> str: 283 """ 284 Return a string representation in the form {key1,key2,...}. 285 286 Example:: 287 288 s = TreeSet([1, 2, 3]) 289 str(s) # "{1,2,3}" 290 291 """ 292 return str(self._t) 293 294 def __repr__(self) -> str: 295 """ 296 Return a string representation of the set's contents. 297 298 Example:: 299 300 s = TreeSet([1, 2, 3]) 301 repr(s) # "{1,2,3}" 302 303 """ 304 return self.__str__() 305 306 # ------------------------------------------------------------------ 307 # Set algebra operators 308 # ------------------------------------------------------------------ 309 310 def __or__(self, other: Iterable[K]) -> TreeSet[K]: 311 """ 312 Return a new set containing all keys from this set and *other*. 313 314 Example:: 315 316 s1 = TreeSet([1, 2, 3]) 317 s2 = TreeSet([2, 3, 4]) 318 str(s1 | s2) # "{1,2,3,4}" 319 320 """ 321 if not hasattr(other, "__iter__"): 322 return NotImplemented 323 res = TreeSet[K](self.keys()) 324 res.update(other) 325 return res 326 327 def __ror__(self, other: Any) -> TreeSet[K]: 328 """ 329 Return a union when this TreeSet is on the right-hand side of ``|``. 330 331 Example:: 332 333 s = TreeSet([2, 3, 4]) 334 str({1, 2, 3} | s) # "{1,2,3,4}" 335 336 """ 337 return self.__or__(other) 338 339 def __ior__(self, other: Any) -> TreeSet[K]: 340 """ 341 Add all keys from *other* to this set in-place. 342 343 Example:: 344 345 s = TreeSet([1, 2]) 346 s |= {3, 4} 347 str(s) # "{1,2,3,4}" 348 349 """ 350 if not hasattr(other, "__iter__"): 351 return NotImplemented 352 self.update(other) 353 return self 354 355 def __and__(self, other: Any) -> TreeSet[K]: 356 """ 357 Return a new set containing only keys present in both this set and *other*. 358 359 Example:: 360 361 s1 = TreeSet([1, 2, 3]) 362 s2 = TreeSet([2, 3, 4]) 363 str(s1 & s2) # "{2,3}" 364 365 """ 366 if not hasattr(other, "__iter__"): 367 return NotImplemented 368 res = TreeSet[K]() 369 for k in other: 370 if k in self: 371 res.add(k) 372 return res 373 374 def __rand__(self, other: Any) -> TreeSet[K]: 375 """ 376 Return intersection when this TreeSet is on the right-hand side of ``&``. 377 378 Example:: 379 380 s = TreeSet([2, 3, 4]) 381 str({1, 2, 3} & s) # "{2,3}" 382 383 """ 384 return self.__and__(other) 385 386 def __iand__(self, other: Any) -> TreeSet[K]: 387 """ 388 Keep only keys also in *other*, in-place. 389 390 Example:: 391 392 s = TreeSet([1, 2, 3]) 393 s &= {2, 3, 4} 394 str(s) # "{2,3}" 395 396 """ 397 if not hasattr(other, "__iter__"): 398 return NotImplemented 399 other_items = TreeSet[K](other) 400 for k in self: 401 if k not in other_items: 402 self.delete(k) 403 return self 404 405 def __sub__(self, other: Any) -> TreeSet[K]: 406 """ 407 Return a new set with keys from this set that are not in *other*. 408 409 Example:: 410 411 s1 = TreeSet([1, 2, 3]) 412 s2 = TreeSet([2, 3, 4]) 413 str(s1 - s2) # "{1}" 414 415 """ 416 if not hasattr(other, "__iter__"): 417 return NotImplemented 418 other_keys = TreeSet(other) 419 res = TreeSet[K]() 420 for k in self.keys(): 421 if k not in other_keys: 422 res.add(k) 423 return res 424 425 def __rsub__(self, other: Any) -> TreeSet[K]: 426 """ 427 Return *other* - this set when this TreeSet is on the right-hand side of ``-``. 428 429 Example:: 430 431 s = TreeSet([2, 3, 4]) 432 str({1, 2, 3} - s) # "{1}" 433 434 """ 435 if not hasattr(other, "__iter__"): 436 return NotImplemented 437 res = TreeSet[K](other) 438 for k in self.keys(): 439 res.delete(k) 440 return res 441 442 def __isub__(self, other: Any) -> TreeSet[K]: 443 """ 444 Remove all keys in *other* from this set in-place. 445 446 Example:: 447 448 s = TreeSet([1, 2, 3]) 449 s -= {2, 3, 4} 450 str(s) # "{1}" 451 452 """ 453 if not hasattr(other, "__iter__"): 454 return NotImplemented 455 for k in other: 456 self.delete(k) 457 return self 458 459 def __xor__(self, other: Any) -> TreeSet[K]: 460 """ 461 Return a new set with keys in exactly one of this set and *other*. 462 463 Example:: 464 465 s1 = TreeSet([1, 2, 3]) 466 s2 = TreeSet([2, 3, 4]) 467 str(s1 ^ s2) # "{1,4}" 468 469 """ 470 if not hasattr(other, "__iter__"): 471 return NotImplemented 472 other_set = TreeSet(other) 473 res = TreeSet[K]() 474 for k in self.keys(): 475 if k not in other_set: 476 res.add(k) 477 for k in other_set: 478 if not self.has(k): 479 res.add(k) 480 return res 481 482 def __rxor__(self, other: Any) -> TreeSet[K]: 483 """ 484 Return symmetric difference when this TreeSet is on the right-hand side of ``^``. 485 486 Example:: 487 488 s = TreeSet([2, 3, 4]) 489 str({1, 2, 3} ^ s) # "{1,4}" 490 491 """ 492 return self.__xor__(other) 493 494 def __ixor__(self, other: Any) -> TreeSet[K]: 495 """ 496 Apply symmetric difference with *other* to this set in-place. 497 498 Example:: 499 500 s = TreeSet([1, 2, 3]) 501 s ^= {2, 3, 4} 502 str(s) # "{1,4}" 503 504 """ 505 if not hasattr(other, "__iter__"): 506 return NotImplemented 507 for k in other: 508 if self.has(k): 509 self.delete(k) 510 else: 511 self.add(k) 512 return self 513 514 def __le__(self, other: Any) -> bool: 515 """ 516 Return True when every element of this set is in *other* (subset or equal). 517 518 Example:: 519 520 TreeSet([1, 2]) <= TreeSet([1, 2, 3]) # True 521 TreeSet([1, 2]) <= TreeSet([1, 2]) # True 522 523 """ 524 if not hasattr(other, "__iter__"): 525 return NotImplemented 526 other_set = TreeSet(other) 527 return all(k in other_set for k in self.keys()) 528 529 def __lt__(self, other: Any) -> bool: 530 """ 531 Return True when this set is a proper subset of *other*. 532 533 Example:: 534 535 TreeSet([1, 2]) < TreeSet([1, 2, 3]) # True 536 TreeSet([1, 2]) < TreeSet([1, 2]) # False 537 538 """ 539 if not hasattr(other, "__iter__"): 540 return NotImplemented 541 other_set = TreeSet(other) 542 return len(self) < len(other_set) and all(k in other_set for k in self.keys()) 543 544 def __ge__(self, other: Any) -> bool: 545 """ 546 Return True when every element of *other* is in this set (superset or equal). 547 548 Example:: 549 550 TreeSet([1, 2, 3]) >= TreeSet([1, 2]) # True 551 TreeSet([1, 2]) >= TreeSet([1, 2]) # True 552 553 """ 554 if not hasattr(other, "__iter__"): 555 return NotImplemented 556 return all(self.has(k) for k in other) 557 558 def __gt__(self, other: Any) -> bool: 559 """ 560 Return True when this set is a proper superset of *other*. 561 562 Example:: 563 564 TreeSet([1, 2, 3]) > TreeSet([1, 2]) # True 565 TreeSet([1, 2]) > TreeSet([1, 2]) # False 566 567 """ 568 if not hasattr(other, "__iter__"): 569 return NotImplemented 570 return len(self) > len(other) and all(self.has(k) for k in other) 571 572 def issubset(self, other: Any) -> bool: 573 """ 574 Return True when every element of this set is in *other*. 575 576 Example:: 577 578 TreeSet([1, 2]).issubset([1, 2, 3]) # True 579 TreeSet([1, 4]).issubset([1, 2, 3]) # False 580 581 """ 582 return self <= other 583 584 def issuperset(self, other: Any) -> bool: 585 """ 586 Return True when every element of *other* is in this set. 587 588 Example:: 589 590 TreeSet([1, 2, 3]).issuperset([1, 2]) # True 591 TreeSet([1, 2]).issuperset([1, 3]) # False 592 593 """ 594 return self >= other 595 596 def isdisjoint(self, other: Any) -> bool: 597 """ 598 Return True when this set and *other* share no common elements. 599 600 Example:: 601 602 TreeSet([1, 2]).isdisjoint([3, 4]) # True 603 TreeSet([1, 2]).isdisjoint([2, 3]) # False 604 605 """ 606 if not hasattr(other, "__iter__"): 607 raise TypeError(f"Operation is not supported with instance of {type(other)}") 608 return all(not self.has(k) for k in other) 609 610 def intersection_update(self, *others: Iterable[K]) -> None: 611 """ 612 Keep only keys present in this set and all of *others*, in-place. 613 614 Example:: 615 616 s = TreeSet([1, 2, 3, 4]) 617 s.intersection_update([2, 3, 5], [3, 6]) 618 str(s) # "{3}" 619 620 """ 621 all_others = TreeSet() 622 if len(others) >= 1: 623 all_others = TreeSet(others[0]) 624 for other in others[1:]: 625 if not hasattr(other, "__iter__"): 626 raise TypeError(f"Operation is not supported with instance of {type(other)}") 627 all_others &= other 628 for k in self: 629 if k not in all_others: 630 self.discard(k) 631 632 def difference_update(self, *others: Iterable[K]) -> None: 633 """ 634 Remove all keys found in any of *others* from this set, in-place. 635 636 Example:: 637 638 s = TreeSet([1, 2, 3, 4]) 639 s.difference_update([2, 3], [4]) 640 str(s) # "{1}" 641 642 """ 643 for other in others: 644 if not hasattr(other, "__iter__"): 645 raise TypeError(f"Operation is not supported with instance of {type(other)}") 646 for k in other: 647 self.discard(k) 648 649 def symmetric_difference_update(self, other: Iterable[K]) -> None: 650 """ 651 Apply symmetric difference with *other* to this set in-place. 652 653 Example:: 654 655 s = TreeSet([1, 2, 3]) 656 s.symmetric_difference_update([2, 3, 4]) 657 str(s) # "{1,4}" 658 659 """ 660 self ^= other 661 662 def union(self, *others: Iterable[K]) -> TreeSet[K]: 663 """ 664 Return a new set containing all keys from this set and all of *others*. 665 666 Example:: 667 668 s = TreeSet([1, 2]) 669 str(s.union([3, 4], [5])) # "{1,2,3,4,5}" 670 671 """ 672 res = TreeSet[K](self.keys()) 673 for other in others: 674 if not hasattr(other, "__iter__"): 675 raise TypeError(f"Operation is not supported with instance of {type(other)}") 676 for k in other: 677 res.add(k) 678 return res 679 680 def intersection(self, *others: Iterable[K]) -> TreeSet[K]: 681 """ 682 Return a new set with keys common to this set and all of *others*. 683 684 Example:: 685 686 s = TreeSet([1, 2, 3, 4]) 687 str(s.intersection([2, 3, 5], [3, 6])) # "{3}" 688 689 """ 690 combined: set = set(next(iter(others))) if others else set() 691 for other in list(others)[1:]: 692 combined &= set(other) 693 res = TreeSet[K]() 694 for k in self.keys(): 695 if k in combined: 696 res.add(k) 697 return res 698 699 def difference(self, *others: Iterable[K]) -> TreeSet[K]: 700 """ 701 Return a new set with keys in this set that are not in any of *others*. 702 703 Example:: 704 705 s = TreeSet([1, 2, 3, 4]) 706 str(s.difference([2, 3], [4])) # "{1}" 707 708 """ 709 excluded: set = set() 710 for other in others: 711 excluded |= set(other) 712 res = TreeSet[K]() 713 for k in self.keys(): 714 if k not in excluded: 715 res.add(k) 716 return res 717 718 def symmetric_difference(self, other: Iterable[K]) -> TreeSet[K]: 719 """ 720 Return a new set with keys in exactly one of this set and *other*. 721 722 Example:: 723 724 s = TreeSet([1, 2, 3]) 725 str(s.symmetric_difference([2, 3, 4])) # "{1,4}" 726 727 """ 728 return self ^ other 729 730 def __copy__(self) -> TreeSet[K]: 731 """ 732 Create a shallow copy of the set. 733 734 Example:: 735 736 import copy 737 738 s = TreeSet([1, 2, 3]) 739 s2 = copy.copy(s) 740 s2.add(4) 741 str(s) # "{1,2,3}" — original unchanged 742 str(s2) # "{1,2,3,4}" 743 744 """ 745 return TreeSet[K](self) 746 747 # ------------------------------------------------------------------ 748 # Additional iteration 749 # ------------------------------------------------------------------ 750 751 def backwards(self) -> PyReverseIterator[K]: 752 """ 753 Return a reverse iterator over all keys in descending order. 754 755 Example:: 756 757 s = TreeSet([1, 2, 3]) 758 list(s.backwards()) # [3, 2, 1] 759 760 """ 761 return self._t.keys().backwards() 762 763 # ------------------------------------------------------------------ 764 # Custom comparator 765 # ------------------------------------------------------------------ 766 767 @property 768 def compare_func(self) -> Callable[[Any, Any], int]: 769 """ 770 @private The current 3-way comparison function used to order keys. 771 772 Setting this property clears all existing elements because the 773 current ordering is no longer valid. 774 775 Example:: 776 777 s = TreeSet() 778 s.compare_func = lambda a, b: -1 if a < b else (1 if a > b else 0) 779 s.add(3) 780 s.add(1) 781 list(s) # [1, 3] 782 783 """ 784 return self._t.compare 785 786 @compare_func.setter 787 def compare_func(self, func: Callable[[Any, Any], int]) -> None: 788 """@private Replace the comparison function and clear all elements.""" 789 self.clear() 790 self._t.compare = func 791 792 # ------------------------------------------------------------------ 793 # STL-style iterators 794 # ------------------------------------------------------------------ 795 796 def begin(self) -> TreeIterator[K, K]: 797 """ 798 Return a forward STL-like iterator to the first element. 799 800 Example:: 801 802 s = TreeSet([1, 2, 3]) 803 it = s.begin() 804 while not it.equals(s.end()): 805 print(it.key) 806 it.next() 807 # 1, 2, 3 808 809 """ 810 return self._t.begin() 811 812 def end(self) -> TreeIterator[K, K]: 813 """ 814 Return a forward STL-like iterator past the last element. 815 816 Example:: 817 818 s = TreeSet([1, 2, 3]) 819 it = s.begin() 820 while not it.equals(s.end()): 821 print(it.key) 822 it.next() 823 824 """ 825 return self._t.end() 826 827 def find(self, key: K) -> TreeIterator[K, K]: 828 """ 829 Return an STL-like iterator to the element with *key*, or end() if absent. 830 831 Example:: 832 833 s = TreeSet([1, 2, 3]) 834 it = s.find(2) 835 if not it.equals(s.end()): 836 print(it.key) # 2 837 s.find(99).equals(s.end()) # True 838 839 """ 840 return self._t.find(key) 841 842 def insert_unique(self, key: K) -> InsertionResult[TreeIterator[K, K]]: 843 """ 844 Insert *key* only when it is not already present. 845 846 Returns: 847 InsertionResult with was_added=True when the key was new; 848 was_added=False when the key already existed. 849 850 Example:: 851 852 s = TreeSet() 853 res = s.insert_unique(1) 854 res.was_added # True 855 res2 = s.insert_unique(1) 856 res2.was_added # False 857 858 """ 859 n: TreeNode[K, K] = TreeNode() 860 n.key = key 861 return self._t.insert_unique(n) 862 863 def insert_or_replace(self, key: K) -> InsertionResult[TreeIterator[K, K]]: 864 """ 865 Insert *key* if absent; if present, "replace" (update the same node). 866 867 Returns: 868 InsertionResult with was_added=True on new insertion, or 869 was_replaced=True when the key already existed. 870 871 Example:: 872 873 s = TreeSet() 874 res = s.insert_or_replace(1) 875 res.was_added # True 876 res2 = s.insert_or_replace(1) 877 res2.was_replaced # True 878 879 """ 880 n: TreeNode[K, K] = TreeNode() 881 n.key = key 882 return self._t.insert_or_replace(n) 883 884 def erase(self, iterator: TreeIterator[K, K]) -> None: 885 """ 886 Remove the element pointed to by *iterator*. 887 888 Example:: 889 890 s = TreeSet([1, 2, 3]) 891 it = s.find(2) 892 s.erase(it) 893 str(s) # "{1,3}" 894 895 """ 896 self._t.erase(iterator.node) 897 898 def lower_bound(self, key: K) -> TreeIterator[K, K]: 899 """ 900 Return an STL-like iterator to the first element with key >= *key*, or end(). 901 902 Example:: 903 904 s = TreeSet([2, 4, 6, 8]) 905 lo = s.lower_bound(3) # iterator to 4 906 hi = s.upper_bound(6) # iterator to 8 907 it = lo 908 while not it.equals(hi): 909 print(it.key) # 4, 6 910 it.next() 911 912 """ 913 return self._t.lower_bound(key) 914 915 def rbegin(self) -> ReverseIterator[K, K]: 916 """ 917 Return a reverse STL-like iterator to the element with the largest key. 918 919 Example:: 920 921 s = TreeSet([1, 2, 3]) 922 it = s.rbegin() 923 while not it.equals(s.rend()): 924 print(it.key) # 3, 2, 1 925 it.next() 926 927 """ 928 return self._t.rbegin() 929 930 def rend(self) -> ReverseIterator[K, K]: 931 """ 932 Return a reverse STL-like iterator before the element with the smallest key. 933 934 Example:: 935 936 s = TreeSet([1, 2, 3]) 937 it = s.rbegin() 938 while not it.equals(s.rend()): 939 print(it.key) 940 it.next() 941 942 """ 943 return self._t.rend() 944 945 def upper_bound(self, key: K) -> TreeIterator[K, K]: 946 """ 947 Return an STL-like iterator to the first element with key > *key*, or end(). 948 949 Example:: 950 951 s = TreeSet([2, 4, 6, 8]) 952 lo = s.lower_bound(3) # iterator to 4 953 hi = s.upper_bound(6) # iterator to 8 954 it = lo 955 while not it.equals(hi): 956 print(it.key) # 4, 6 957 it.next() 958 959 """ 960 return self._t.upper_bound(key) 961 962 def first(self) -> K | None: 963 """ 964 Return the smallest element, or None when the set is empty. 965 966 Example:: 967 968 s = TreeSet([1, 2, 3]) 969 s.first() # 1 970 TreeSet().first() # None 971 972 """ 973 result = self._t.first() 974 return result 975 976 def last(self) -> K | None: 977 """ 978 Return the largest element, or None when the set is empty. 979 980 Example:: 981 982 s = TreeSet([1, 2, 3]) 983 s.last() # 3 984 TreeSet().last() # None 985 986 """ 987 result = self._t.last() 988 return result
Ordered set of unique keys backed by a red-black tree.
Elements are kept in ascending order at all times. Lookup, insertion, and deletion are all O(log n).
Example::
s = TreeSet()
s.add(1)
s.add(2)
s.add(1) # duplicate; ignored
for key in s:
print(key) # 1, 2
TreeSet(iterable: 'Iterable[K] | None' = None, *args)
34 def __init__(self, iterable: Iterable[K] | None = None, *args) -> None: 35 """ 36 Create an empty set, or pre-populate it from an iterable of keys. 37 38 Duplicate keys in *iterable* are silently ignored (set semantics). 39 40 Args: 41 iterable: Optional iterable of keys. 42 args: another way to provide key-list 43 44 Raises: 45 TypeError: When *iterable* is not iterable. 46 47 Example:: 48 49 s = TreeSet() 50 s = TreeSet([3, 1, 2, 1]) # {1,2,3} — duplicates dropped 51 s = TreeSet({3, 1, 2}) # from a Python set 52 s = TreeSet(range(1, 4)) 53 54 """ 55 self._t: Tree[K, K] = Tree() 56 self._t.value_policy = KeyOnlyPolicy() 57 if iterable is not None: 58 self.update(iterable) 59 if args: 60 self.update(args)
Create an empty set, or pre-populate it from an iterable of keys.
Duplicate keys in iterable are silently ignored (set semantics).
Args: iterable: Optional iterable of keys. args: another way to provide key-list
Raises: TypeError: When iterable is not iterable.
Example::
s = TreeSet()
s = TreeSet([3, 1, 2, 1]) # {1,2,3} — duplicates dropped
s = TreeSet({3, 1, 2}) # from a Python set
s = TreeSet(range(1, 4))
def
update(self, *iterables: 'Iterable[K]') -> None:
62 def update(self, *iterables: Iterable[K]) -> None: 63 """ 64 Add all keys to the current set. 65 66 Duplicate keys in *iterable* are silently ignored (set semantics). 67 68 Args: 69 iterables: One or more list/tuple/etc 70 71 Raises: 72 TypeError: When *iterable* is not iterable. 73 74 Example:: 75 76 TreeSet().update(TreeSet({3, 1, 2})) # from a TreeSet 77 TreeSet().update([3, 1, 2, 1]) # {1,2,3} — duplicates dropped 78 TreeSet().update({3, 1, 2}) # from a Python set 79 TreeSet().update(range(1, 4)) 80 81 """ 82 if iterables is not None: 83 for iterable in iterables: 84 if not hasattr(iterable, "__iter__"): 85 raise TypeError("TreeSet accepts only iterable objects") 86 for k in iterable: 87 self.add(k)
Add all keys to the current set.
Duplicate keys in iterable are silently ignored (set semantics).
Args: iterables: One or more list/tuple/etc
Raises: TypeError: When iterable is not iterable.
Example::
TreeSet().update(TreeSet({3, 1, 2})) # from a TreeSet
TreeSet().update([3, 1, 2, 1]) # {1,2,3} — duplicates dropped
TreeSet().update({3, 1, 2}) # from a Python set
TreeSet().update(range(1, 4))
def
clear(self) -> None:
93 def clear(self) -> None: 94 """ 95 Remove all elements. 96 97 Example:: 98 99 s = TreeSet([1, 2, 3]) 100 s.clear() 101 len(s) # 0 102 103 """ 104 self._t.clear()
Remove all elements.
Example::
s = TreeSet([1, 2, 3])
s.clear()
len(s) # 0
def
add(self, key: 'K') -> None:
106 def add(self, key: K) -> None: 107 """ 108 Insert *key* if it is not already present. 109 110 Example:: 111 112 s = TreeSet() 113 s.add(1) 114 s.add(1) # ignored 115 len(s) # 1 116 117 """ 118 n: TreeNode[K, K] = TreeNode() 119 n.key = key 120 self._t.insert_unique(n)
Insert key if it is not already present.
Example::
s = TreeSet()
s.add(1)
s.add(1) # ignored
len(s) # 1
def
discard(self, key: 'K') -> None:
122 def discard(self, key: K) -> None: 123 """ 124 Remove *key* if present; do nothing when it is absent. 125 126 Example:: 127 128 s = TreeSet([1, 2, 3]) 129 s.discard(2) # s is now {1,3} 130 s.discard(99) # no-op 131 132 """ 133 it = self._t.find(key) 134 if not it.equals(self._t.end()): 135 self._t.erase(it.node)
Remove key if present; do nothing when it is absent.
Example::
s = TreeSet([1, 2, 3])
s.discard(2) # s is now {1,3}
s.discard(99) # no-op
def
remove(self, key: 'K') -> None:
137 def remove(self, key: K) -> None: 138 """ 139 Remove *key*, raising KeyError when it is absent. 140 141 Args: 142 key: Key to remove. 143 144 Raises: 145 KeyError: When *key* is not present. 146 147 Example:: 148 149 s = TreeSet([1, 2, 3]) 150 s.remove(2) # s is now {1,3} 151 s.remove(99) # raises KeyError 152 153 """ 154 it = self._t.find(key) 155 if not it.equals(self._t.end()): 156 self._t.erase(it.node) 157 else: 158 raise KeyError(key)
Remove key, raising KeyError when it is absent.
Args: key: Key to remove.
Raises: KeyError: When key is not present.
Example::
s = TreeSet([1, 2, 3])
s.remove(2) # s is now {1,3}
s.remove(99) # raises KeyError
def
pop(self, key: 'K | None' = None, default: 'K | None' = None) -> 'K | None':
173 def pop(self, key: K | None = None, default: K | None = None) -> K | None: 174 """ 175 Remove *key* and return it, or return *default* when absent. 176 177 When called with no arguments, removes and returns the smallest element. 178 179 Args: 180 key: Key to remove. When None, the smallest element is removed. 181 default: Value to return when *key* is absent. 182 183 Raises: 184 KeyError: When called with no arguments on an empty set. 185 186 Example:: 187 188 s = TreeSet([1, 2, 3]) 189 s.pop(2) # 2, s is now {1,3} 190 s.pop(9) # None 191 s.pop(9, 0) # 0 192 s.pop() # 1 — removes and returns smallest element 193 194 """ 195 if self.size == 0: 196 raise KeyError("pop from an empty set") 197 it = self._t.find(key) if key is not None else self.begin() 198 if not it.equals(self._t.end()): 199 k = it.key 200 self._t.erase(it.node) 201 return k 202 return default
Remove key and return it, or return default when absent.
When called with no arguments, removes and returns the smallest element.
Args: key: Key to remove. When None, the smallest element is removed. default: Value to return when key is absent.
Raises: KeyError: When called with no arguments on an empty set.
Example::
s = TreeSet([1, 2, 3])
s.pop(2) # 2, s is now {1,3}
s.pop(9) # None
s.pop(9, 0) # 0
s.pop() # 1 — removes and returns smallest element
def
issubset(self, other: Any) -> bool:
572 def issubset(self, other: Any) -> bool: 573 """ 574 Return True when every element of this set is in *other*. 575 576 Example:: 577 578 TreeSet([1, 2]).issubset([1, 2, 3]) # True 579 TreeSet([1, 4]).issubset([1, 2, 3]) # False 580 581 """ 582 return self <= other
Return True when every element of this set is in other.
Example::
TreeSet([1, 2]).issubset([1, 2, 3]) # True
TreeSet([1, 4]).issubset([1, 2, 3]) # False
def
issuperset(self, other: Any) -> bool:
584 def issuperset(self, other: Any) -> bool: 585 """ 586 Return True when every element of *other* is in this set. 587 588 Example:: 589 590 TreeSet([1, 2, 3]).issuperset([1, 2]) # True 591 TreeSet([1, 2]).issuperset([1, 3]) # False 592 593 """ 594 return self >= other
Return True when every element of other is in this set.
Example::
TreeSet([1, 2, 3]).issuperset([1, 2]) # True
TreeSet([1, 2]).issuperset([1, 3]) # False
def
isdisjoint(self, other: Any) -> bool:
596 def isdisjoint(self, other: Any) -> bool: 597 """ 598 Return True when this set and *other* share no common elements. 599 600 Example:: 601 602 TreeSet([1, 2]).isdisjoint([3, 4]) # True 603 TreeSet([1, 2]).isdisjoint([2, 3]) # False 604 605 """ 606 if not hasattr(other, "__iter__"): 607 raise TypeError(f"Operation is not supported with instance of {type(other)}") 608 return all(not self.has(k) for k in other)
Return True when this set and other share no common elements.
Example::
TreeSet([1, 2]).isdisjoint([3, 4]) # True
TreeSet([1, 2]).isdisjoint([2, 3]) # False
def
intersection_update(self, *others: 'Iterable[K]') -> None:
610 def intersection_update(self, *others: Iterable[K]) -> None: 611 """ 612 Keep only keys present in this set and all of *others*, in-place. 613 614 Example:: 615 616 s = TreeSet([1, 2, 3, 4]) 617 s.intersection_update([2, 3, 5], [3, 6]) 618 str(s) # "{3}" 619 620 """ 621 all_others = TreeSet() 622 if len(others) >= 1: 623 all_others = TreeSet(others[0]) 624 for other in others[1:]: 625 if not hasattr(other, "__iter__"): 626 raise TypeError(f"Operation is not supported with instance of {type(other)}") 627 all_others &= other 628 for k in self: 629 if k not in all_others: 630 self.discard(k)
Keep only keys present in this set and all of others, in-place.
Example::
s = TreeSet([1, 2, 3, 4])
s.intersection_update([2, 3, 5], [3, 6])
str(s) # "{3}"
def
difference_update(self, *others: 'Iterable[K]') -> None:
632 def difference_update(self, *others: Iterable[K]) -> None: 633 """ 634 Remove all keys found in any of *others* from this set, in-place. 635 636 Example:: 637 638 s = TreeSet([1, 2, 3, 4]) 639 s.difference_update([2, 3], [4]) 640 str(s) # "{1}" 641 642 """ 643 for other in others: 644 if not hasattr(other, "__iter__"): 645 raise TypeError(f"Operation is not supported with instance of {type(other)}") 646 for k in other: 647 self.discard(k)
Remove all keys found in any of others from this set, in-place.
Example::
s = TreeSet([1, 2, 3, 4])
s.difference_update([2, 3], [4])
str(s) # "{1}"
def
symmetric_difference_update(self, other: 'Iterable[K]') -> None:
649 def symmetric_difference_update(self, other: Iterable[K]) -> None: 650 """ 651 Apply symmetric difference with *other* to this set in-place. 652 653 Example:: 654 655 s = TreeSet([1, 2, 3]) 656 s.symmetric_difference_update([2, 3, 4]) 657 str(s) # "{1,4}" 658 659 """ 660 self ^= other
Apply symmetric difference with other to this set in-place.
Example::
s = TreeSet([1, 2, 3])
s.symmetric_difference_update([2, 3, 4])
str(s) # "{1,4}"
def
union(self, *others: 'Iterable[K]') -> 'TreeSet[K]':
662 def union(self, *others: Iterable[K]) -> TreeSet[K]: 663 """ 664 Return a new set containing all keys from this set and all of *others*. 665 666 Example:: 667 668 s = TreeSet([1, 2]) 669 str(s.union([3, 4], [5])) # "{1,2,3,4,5}" 670 671 """ 672 res = TreeSet[K](self.keys()) 673 for other in others: 674 if not hasattr(other, "__iter__"): 675 raise TypeError(f"Operation is not supported with instance of {type(other)}") 676 for k in other: 677 res.add(k) 678 return res
Return a new set containing all keys from this set and all of others.
Example::
s = TreeSet([1, 2])
str(s.union([3, 4], [5])) # "{1,2,3,4,5}"
def
intersection(self, *others: 'Iterable[K]') -> 'TreeSet[K]':
680 def intersection(self, *others: Iterable[K]) -> TreeSet[K]: 681 """ 682 Return a new set with keys common to this set and all of *others*. 683 684 Example:: 685 686 s = TreeSet([1, 2, 3, 4]) 687 str(s.intersection([2, 3, 5], [3, 6])) # "{3}" 688 689 """ 690 combined: set = set(next(iter(others))) if others else set() 691 for other in list(others)[1:]: 692 combined &= set(other) 693 res = TreeSet[K]() 694 for k in self.keys(): 695 if k in combined: 696 res.add(k) 697 return res
Return a new set with keys common to this set and all of others.
Example::
s = TreeSet([1, 2, 3, 4])
str(s.intersection([2, 3, 5], [3, 6])) # "{3}"
def
difference(self, *others: 'Iterable[K]') -> 'TreeSet[K]':
699 def difference(self, *others: Iterable[K]) -> TreeSet[K]: 700 """ 701 Return a new set with keys in this set that are not in any of *others*. 702 703 Example:: 704 705 s = TreeSet([1, 2, 3, 4]) 706 str(s.difference([2, 3], [4])) # "{1}" 707 708 """ 709 excluded: set = set() 710 for other in others: 711 excluded |= set(other) 712 res = TreeSet[K]() 713 for k in self.keys(): 714 if k not in excluded: 715 res.add(k) 716 return res
Return a new set with keys in this set that are not in any of others.
Example::
s = TreeSet([1, 2, 3, 4])
str(s.difference([2, 3], [4])) # "{1}"
def
symmetric_difference(self, other: 'Iterable[K]') -> 'TreeSet[K]':
718 def symmetric_difference(self, other: Iterable[K]) -> TreeSet[K]: 719 """ 720 Return a new set with keys in exactly one of this set and *other*. 721 722 Example:: 723 724 s = TreeSet([1, 2, 3]) 725 str(s.symmetric_difference([2, 3, 4])) # "{1,4}" 726 727 """ 728 return self ^ other
Return a new set with keys in exactly one of this set and other.
Example::
s = TreeSet([1, 2, 3])
str(s.symmetric_difference([2, 3, 4])) # "{1,4}"
def
backwards(self) -> 'PyReverseIterator[K]':
751 def backwards(self) -> PyReverseIterator[K]: 752 """ 753 Return a reverse iterator over all keys in descending order. 754 755 Example:: 756 757 s = TreeSet([1, 2, 3]) 758 list(s.backwards()) # [3, 2, 1] 759 760 """ 761 return self._t.keys().backwards()
Return a reverse iterator over all keys in descending order.
Example::
s = TreeSet([1, 2, 3])
list(s.backwards()) # [3, 2, 1]
def
begin(self) -> 'TreeIterator[K, K]':
796 def begin(self) -> TreeIterator[K, K]: 797 """ 798 Return a forward STL-like iterator to the first element. 799 800 Example:: 801 802 s = TreeSet([1, 2, 3]) 803 it = s.begin() 804 while not it.equals(s.end()): 805 print(it.key) 806 it.next() 807 # 1, 2, 3 808 809 """ 810 return self._t.begin()
Return a forward STL-like iterator to the first element.
Example::
s = TreeSet([1, 2, 3])
it = s.begin()
while not it.equals(s.end()):
print(it.key)
it.next()
# 1, 2, 3
def
end(self) -> 'TreeIterator[K, K]':
812 def end(self) -> TreeIterator[K, K]: 813 """ 814 Return a forward STL-like iterator past the last element. 815 816 Example:: 817 818 s = TreeSet([1, 2, 3]) 819 it = s.begin() 820 while not it.equals(s.end()): 821 print(it.key) 822 it.next() 823 824 """ 825 return self._t.end()
Return a forward STL-like iterator past the last element.
Example::
s = TreeSet([1, 2, 3])
it = s.begin()
while not it.equals(s.end()):
print(it.key)
it.next()
def
find(self, key: 'K') -> 'TreeIterator[K, K]':
827 def find(self, key: K) -> TreeIterator[K, K]: 828 """ 829 Return an STL-like iterator to the element with *key*, or end() if absent. 830 831 Example:: 832 833 s = TreeSet([1, 2, 3]) 834 it = s.find(2) 835 if not it.equals(s.end()): 836 print(it.key) # 2 837 s.find(99).equals(s.end()) # True 838 839 """ 840 return self._t.find(key)
Return an STL-like iterator to the element with key, or end() if absent.
Example::
s = TreeSet([1, 2, 3])
it = s.find(2)
if not it.equals(s.end()):
print(it.key) # 2
s.find(99).equals(s.end()) # True
def
insert_unique(self, key: 'K') -> 'InsertionResult[TreeIterator[K, K]]':
842 def insert_unique(self, key: K) -> InsertionResult[TreeIterator[K, K]]: 843 """ 844 Insert *key* only when it is not already present. 845 846 Returns: 847 InsertionResult with was_added=True when the key was new; 848 was_added=False when the key already existed. 849 850 Example:: 851 852 s = TreeSet() 853 res = s.insert_unique(1) 854 res.was_added # True 855 res2 = s.insert_unique(1) 856 res2.was_added # False 857 858 """ 859 n: TreeNode[K, K] = TreeNode() 860 n.key = key 861 return self._t.insert_unique(n)
Insert key only when it is not already present.
Returns: InsertionResult with was_added=True when the key was new; was_added=False when the key already existed.
Example::
s = TreeSet()
res = s.insert_unique(1)
res.was_added # True
res2 = s.insert_unique(1)
res2.was_added # False
def
insert_or_replace(self, key: 'K') -> 'InsertionResult[TreeIterator[K, K]]':
863 def insert_or_replace(self, key: K) -> InsertionResult[TreeIterator[K, K]]: 864 """ 865 Insert *key* if absent; if present, "replace" (update the same node). 866 867 Returns: 868 InsertionResult with was_added=True on new insertion, or 869 was_replaced=True when the key already existed. 870 871 Example:: 872 873 s = TreeSet() 874 res = s.insert_or_replace(1) 875 res.was_added # True 876 res2 = s.insert_or_replace(1) 877 res2.was_replaced # True 878 879 """ 880 n: TreeNode[K, K] = TreeNode() 881 n.key = key 882 return self._t.insert_or_replace(n)
Insert key if absent; if present, "replace" (update the same node).
Returns: InsertionResult with was_added=True on new insertion, or was_replaced=True when the key already existed.
Example::
s = TreeSet()
res = s.insert_or_replace(1)
res.was_added # True
res2 = s.insert_or_replace(1)
res2.was_replaced # True
def
erase(self, iterator: 'TreeIterator[K, K]') -> None:
884 def erase(self, iterator: TreeIterator[K, K]) -> None: 885 """ 886 Remove the element pointed to by *iterator*. 887 888 Example:: 889 890 s = TreeSet([1, 2, 3]) 891 it = s.find(2) 892 s.erase(it) 893 str(s) # "{1,3}" 894 895 """ 896 self._t.erase(iterator.node)
Remove the element pointed to by iterator.
Example::
s = TreeSet([1, 2, 3])
it = s.find(2)
s.erase(it)
str(s) # "{1,3}"
def
lower_bound(self, key: 'K') -> 'TreeIterator[K, K]':
898 def lower_bound(self, key: K) -> TreeIterator[K, K]: 899 """ 900 Return an STL-like iterator to the first element with key >= *key*, or end(). 901 902 Example:: 903 904 s = TreeSet([2, 4, 6, 8]) 905 lo = s.lower_bound(3) # iterator to 4 906 hi = s.upper_bound(6) # iterator to 8 907 it = lo 908 while not it.equals(hi): 909 print(it.key) # 4, 6 910 it.next() 911 912 """ 913 return self._t.lower_bound(key)
Return an STL-like iterator to the first element with key >= key, or end().
Example::
s = TreeSet([2, 4, 6, 8])
lo = s.lower_bound(3) # iterator to 4
hi = s.upper_bound(6) # iterator to 8
it = lo
while not it.equals(hi):
print(it.key) # 4, 6
it.next()
def
rbegin(self) -> 'ReverseIterator[K, K]':
915 def rbegin(self) -> ReverseIterator[K, K]: 916 """ 917 Return a reverse STL-like iterator to the element with the largest key. 918 919 Example:: 920 921 s = TreeSet([1, 2, 3]) 922 it = s.rbegin() 923 while not it.equals(s.rend()): 924 print(it.key) # 3, 2, 1 925 it.next() 926 927 """ 928 return self._t.rbegin()
Return a reverse STL-like iterator to the element with the largest key.
Example::
s = TreeSet([1, 2, 3])
it = s.rbegin()
while not it.equals(s.rend()):
print(it.key) # 3, 2, 1
it.next()
def
rend(self) -> 'ReverseIterator[K, K]':
930 def rend(self) -> ReverseIterator[K, K]: 931 """ 932 Return a reverse STL-like iterator before the element with the smallest key. 933 934 Example:: 935 936 s = TreeSet([1, 2, 3]) 937 it = s.rbegin() 938 while not it.equals(s.rend()): 939 print(it.key) 940 it.next() 941 942 """ 943 return self._t.rend()
Return a reverse STL-like iterator before the element with the smallest key.
Example::
s = TreeSet([1, 2, 3])
it = s.rbegin()
while not it.equals(s.rend()):
print(it.key)
it.next()
def
upper_bound(self, key: 'K') -> 'TreeIterator[K, K]':
945 def upper_bound(self, key: K) -> TreeIterator[K, K]: 946 """ 947 Return an STL-like iterator to the first element with key > *key*, or end(). 948 949 Example:: 950 951 s = TreeSet([2, 4, 6, 8]) 952 lo = s.lower_bound(3) # iterator to 4 953 hi = s.upper_bound(6) # iterator to 8 954 it = lo 955 while not it.equals(hi): 956 print(it.key) # 4, 6 957 it.next() 958 959 """ 960 return self._t.upper_bound(key)
Return an STL-like iterator to the first element with key > key, or end().
Example::
s = TreeSet([2, 4, 6, 8])
lo = s.lower_bound(3) # iterator to 4
hi = s.upper_bound(6) # iterator to 8
it = lo
while not it.equals(hi):
print(it.key) # 4, 6
it.next()
def
first(self) -> 'K | None':
962 def first(self) -> K | None: 963 """ 964 Return the smallest element, or None when the set is empty. 965 966 Example:: 967 968 s = TreeSet([1, 2, 3]) 969 s.first() # 1 970 TreeSet().first() # None 971 972 """ 973 result = self._t.first() 974 return result
Return the smallest element, or None when the set is empty.
Example::
s = TreeSet([1, 2, 3])
s.first() # 1
TreeSet().first() # None
def
last(self) -> 'K | None':
976 def last(self) -> K | None: 977 """ 978 Return the largest element, or None when the set is empty. 979 980 Example:: 981 982 s = TreeSet([1, 2, 3]) 983 s.last() # 3 984 TreeSet().last() # None 985 986 """ 987 result = self._t.last() 988 return result
Return the largest element, or None when the set is empty.
Example::
s = TreeSet([1, 2, 3])
s.last() # 3
TreeSet().last() # None