Split sublists with length greater than double the load-factor. Updates the index when the sublist length is less than double the load level. This requires incrementing the nodes in a traversal from the leaf node to the root. For an example traversal see ``SortedList
(self, pos)
| 1820 | |
| 1821 | |
| 1822 | def _expand(self, pos): |
| 1823 | """Split sublists with length greater than double the load-factor. |
| 1824 | |
| 1825 | Updates the index when the sublist length is less than double the load |
| 1826 | level. This requires incrementing the nodes in a traversal from the |
| 1827 | leaf node to the root. For an example traversal see |
| 1828 | ``SortedList._loc``. |
| 1829 | |
| 1830 | """ |
| 1831 | _lists = self._lists |
| 1832 | _keys = self._keys |
| 1833 | _index = self._index |
| 1834 | |
| 1835 | if len(_keys[pos]) > (self._load << 1): |
| 1836 | _maxes = self._maxes |
| 1837 | _load = self._load |
| 1838 | |
| 1839 | _lists_pos = _lists[pos] |
| 1840 | _keys_pos = _keys[pos] |
| 1841 | half = _lists_pos[_load:] |
| 1842 | half_keys = _keys_pos[_load:] |
| 1843 | del _lists_pos[_load:] |
| 1844 | del _keys_pos[_load:] |
| 1845 | _maxes[pos] = _keys_pos[-1] |
| 1846 | |
| 1847 | _lists.insert(pos + 1, half) |
| 1848 | _keys.insert(pos + 1, half_keys) |
| 1849 | _maxes.insert(pos + 1, half_keys[-1]) |
| 1850 | |
| 1851 | del _index[:] |
| 1852 | else: |
| 1853 | if _index: |
| 1854 | child = self._offset + pos |
| 1855 | while child: |
| 1856 | _index[child] += 1 |
| 1857 | child = (child - 1) >> 1 |
| 1858 | _index[0] += 1 |
| 1859 | |
| 1860 | |
| 1861 | def update(self, iterable): |