A seekable cursor for a BTree. If you are going to use a cursor on a mutable BTree, you should use it in a ``with`` block so that any mutations of the BTree automatically park the cursor.
| 379 | |
| 380 | |
| 381 | class Cursor(Generic[KT, ET]): |
| 382 | """A seekable cursor for a BTree. |
| 383 | |
| 384 | If you are going to use a cursor on a mutable BTree, you should use it |
| 385 | in a ``with`` block so that any mutations of the BTree automatically park |
| 386 | the cursor. |
| 387 | """ |
| 388 | |
| 389 | def __init__(self, btree: "BTree[KT, ET]"): |
| 390 | self.btree = btree |
| 391 | self.current_node: _Node | None = None |
| 392 | # The current index is the element index within the current node, or |
| 393 | # if there is no current node then it is 0 on the left boundary and 1 |
| 394 | # on the right boundary. |
| 395 | self.current_index: int = 0 |
| 396 | self.recurse = False |
| 397 | self.increasing = True |
| 398 | self.parents: list[tuple[_Node, int]] = [] |
| 399 | self.parked = False |
| 400 | self.parking_key: KT | None = None |
| 401 | self.parking_key_read = False |
| 402 | |
| 403 | def _seek_least(self) -> None: |
| 404 | # seek to the least value in the subtree beneath the current index of the |
| 405 | # current node |
| 406 | assert self.current_node is not None |
| 407 | while not self.current_node.is_leaf: |
| 408 | self.parents.append((self.current_node, self.current_index)) |
| 409 | self.current_node = self.current_node.children[self.current_index] |
| 410 | assert self.current_node is not None |
| 411 | self.current_index = 0 |
| 412 | |
| 413 | def _seek_greatest(self) -> None: |
| 414 | # seek to the greatest value in the subtree beneath the current index of the |
| 415 | # current node |
| 416 | assert self.current_node is not None |
| 417 | while not self.current_node.is_leaf: |
| 418 | self.parents.append((self.current_node, self.current_index)) |
| 419 | self.current_node = self.current_node.children[self.current_index] |
| 420 | assert self.current_node is not None |
| 421 | self.current_index = len(self.current_node.elts) |
| 422 | |
| 423 | def park(self): |
| 424 | """Park the cursor. |
| 425 | |
| 426 | A cursor must be "parked" before mutating the BTree to avoid undefined behavior. |
| 427 | Cursors created in a ``with`` block register with their BTree and will park |
| 428 | automatically. Note that a parked cursor may not observe some changes made when |
| 429 | it is parked; for example a cursor being iterated with next() will not see items |
| 430 | inserted before its current position. |
| 431 | """ |
| 432 | if not self.parked: |
| 433 | self.parked = True |
| 434 | |
| 435 | def _maybe_unpark(self): |
| 436 | if self.parked: |
| 437 | if self.parking_key is not None: |
| 438 | # remember our increasing hint, as seeking might change it |
no outgoing calls
no test coverage detected
searching dependent graphs…