Add `value` to sorted list. Runtime complexity: `O(log(n))` -- approximate. >>> sl = SortedList() >>> sl.add(3) >>> sl.add(1) >>> sl.add(2) >>> sl SortedList([1, 2, 3]) :param value: value to add to sorted list
(self, value)
| 251 | |
| 252 | |
| 253 | def add(self, value): |
| 254 | """Add `value` to sorted list. |
| 255 | |
| 256 | Runtime complexity: `O(log(n))` -- approximate. |
| 257 | |
| 258 | >>> sl = SortedList() |
| 259 | >>> sl.add(3) |
| 260 | >>> sl.add(1) |
| 261 | >>> sl.add(2) |
| 262 | >>> sl |
| 263 | SortedList([1, 2, 3]) |
| 264 | |
| 265 | :param value: value to add to sorted list |
| 266 | |
| 267 | """ |
| 268 | _lists = self._lists |
| 269 | _maxes = self._maxes |
| 270 | |
| 271 | if _maxes: |
| 272 | pos = bisect_right(_maxes, value) |
| 273 | |
| 274 | if pos == len(_maxes): |
| 275 | pos -= 1 |
| 276 | _lists[pos].append(value) |
| 277 | _maxes[pos] = value |
| 278 | else: |
| 279 | insort(_lists[pos], value) |
| 280 | |
| 281 | self._expand(pos) |
| 282 | else: |
| 283 | _lists.append([value]) |
| 284 | _maxes.append(value) |
| 285 | |
| 286 | self._len += 1 |
| 287 | |
| 288 | |
| 289 | def _expand(self, pos): |