Add `value` to sorted-key list. Runtime complexity: `O(log(n))` -- approximate. >>> from operator import neg >>> skl = SortedKeyList(key=neg) >>> skl.add(3) >>> skl.add(1) >>> skl.add(2) >>> skl SortedKeyList([3, 2, 1], key=<built-in
(self, value)
| 1776 | |
| 1777 | |
| 1778 | def add(self, value): |
| 1779 | """Add `value` to sorted-key list. |
| 1780 | |
| 1781 | Runtime complexity: `O(log(n))` -- approximate. |
| 1782 | |
| 1783 | >>> from operator import neg |
| 1784 | >>> skl = SortedKeyList(key=neg) |
| 1785 | >>> skl.add(3) |
| 1786 | >>> skl.add(1) |
| 1787 | >>> skl.add(2) |
| 1788 | >>> skl |
| 1789 | SortedKeyList([3, 2, 1], key=<built-in function neg>) |
| 1790 | |
| 1791 | :param value: value to add to sorted-key list |
| 1792 | |
| 1793 | """ |
| 1794 | _lists = self._lists |
| 1795 | _keys = self._keys |
| 1796 | _maxes = self._maxes |
| 1797 | |
| 1798 | key = self._key(value) |
| 1799 | |
| 1800 | if _maxes: |
| 1801 | pos = bisect_right(_maxes, key) |
| 1802 | |
| 1803 | if pos == len(_maxes): |
| 1804 | pos -= 1 |
| 1805 | _lists[pos].append(value) |
| 1806 | _keys[pos].append(key) |
| 1807 | _maxes[pos] = key |
| 1808 | else: |
| 1809 | idx = bisect_right(_keys[pos], key) |
| 1810 | _lists[pos].insert(idx, value) |
| 1811 | _keys[pos].insert(idx, key) |
| 1812 | |
| 1813 | self._expand(pos) |
| 1814 | else: |
| 1815 | _lists.append([value]) |
| 1816 | _keys.append([key]) |
| 1817 | _maxes.append(key) |
| 1818 | |
| 1819 | self._len += 1 |
| 1820 | |
| 1821 | |
| 1822 | def _expand(self, pos): |