BTreeCursor

public final class BTreeCursor<Key: Comparable, Value>

A stateful editing interface for efficiently inserting/removing/updating a range of elements in a B-tree.

Creating a cursor over a tree takes exclusive ownership of it; the tree is in a transient invalid state while the cursor is active. (In particular, element counts are not finalized until the cursor is deactivated.)

The cursor always focuses on a particular spot on the tree: either a particular element, or the empty spot after the last element. There are methods to move the cursor to the next or previous element, to modify the currently focused element, to insert a new element before the current position, and to remove the currently focused element from the tree.

Note that the cursor does not verify that keys you insert/modify uphold tree invariants – it is your responsibility to guarantee keys remain in ascending order while you’re working with the cursor.

Creating a cursor takes O(log(n)) steps; once the cursor has been created, the complexity of most manipulations is amortized O(1). For example, appending k new elements without a cursor takes O(k * log(n)) steps; using a cursor to do the same only takes O(log(n) + k).

  • The number of elements in the tree currently being edited.

    Declaration

    Swift

    public var count: Int
    Show on GitHub

  • The offset of the currently focused element in the tree.

    Complexity

    O(1) for the getter, O(log(count)) for the setter.

    Declaration

    Swift

    public var offset: Int
    Show on GitHub

Simple properties

  • Return true iff the cursor is focused on the initial element.

    Declaration

    Swift

    public var isAtStart: Bool
    Show on GitHub

  • Return true iff the cursor is focused on the spot beyond the last element.

    Declaration

    Swift

    public var isAtEnd: Bool
    Show on GitHub

Navigation

  • Position the cursor on the next element in the B-tree.

    Requires

    !isAtEnd

    Complexity

    Amortized O(1)

    Declaration

    Swift

    public func moveForward()
    Show on GitHub

  • Position this cursor on the previous element in the B-tree.

    Requires

    !isAtStart

    Complexity

    Amortized O(1)

    Declaration

    Swift

    public func moveBackward()
    Show on GitHub

  • Position this cursor on the start of the B-tree.

    Complexity

    O(log(offset))

    Declaration

    Swift

    public func moveToStart()
    Show on GitHub

  • Position this cursor on the end of the B-tree, i.e., at the offset after the last element.

    Complexity

    O(log(count - offset))

    Declaration

    Swift

    public func moveToEnd()
    Show on GitHub

  • Move this cursor to the specified offset in the B-tree.

    Complexity

    O(log(distance)), where distance is the absolute difference between the desired and current offsets.

    Declaration

    Swift

    public func move(toOffset offset: Int)
    Show on GitHub

  • Move this cursor to an element with the specified key. If there are no such elements, the cursor is moved to the first element after key (or at the end of tree). If there are multiple such elements, selector specifies which one to find.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func move(to key: Key, choosing selector: BTreeKeySelector = .any)
    Show on GitHub

Editing

  • Get or replace the currently focused element.

    Warning

    Changing the key is potentially dangerous; it is the caller’s responsibility to ensure that keys remain in ascending order. This is not verified at runtime.

    Complexity

    O(1)

    Declaration

    Swift

    public var element: Element
    Show on GitHub
  • key

    Get or set the key of the currently focused element.

    Warning

    Changing the key is potentially dangerous; it is the caller’s responsibility to ensure that keys remain in ascending order. This is not verified at runtime.

    Complexity

    O(1)

    Declaration

    Swift

    public var key: Key
    Show on GitHub

  • Get or set the value of the currently focused element.

    Complexity

    O(1)

    Declaration

    Swift

    public var value: Value
    Show on GitHub

  • Update the value stored at the cursor’s current position and return the previous value. This method does not change the cursor’s position.

    Complexity

    O(1)

    Declaration

    Swift

    public func setValue(_ value: Value) -> Value
    Show on GitHub

  • Insert a new element after the cursor’s current position, and position the cursor on the new element.

    Complexity

    amortized O(1)

    Declaration

    Swift

    public func insertAfter(_ element: Element)
    Show on GitHub

  • Insert a new element at the cursor’s current offset, and leave the cursor positioned on the original element.

    Complexity

    amortized O(1)

    Declaration

    Swift

    public func insert(_ element: Element)
    Show on GitHub

  • Insert the contents of tree before the currently focused element, keeping the cursor’s position on it.

    Complexity

    O(log(count + tree.count))

    Declaration

    Swift

    public func insert(_ tree: Tree)
    Show on GitHub

  • Insert all elements in a sequence before the currently focused element, keeping the cursor’s position on it.

    Requires

    self.isValid and elements is sorted by key.

    Complexity

    O(log(count) + c), where c is the number of elements in the sequence.

    Declaration

    Swift

    public func insert<S: Sequence>(_ elements: S) where S.Iterator.Element == Element
    Show on GitHub

  • Remove and return the element at the cursor’s current position, and position the cursor on its successor.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func remove() -> Element
    Show on GitHub

  • Remove n elements starting at the cursor’s current position, and position the cursor on the successor of the last element that was removed.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func remove(_ n: Int)
    Show on GitHub

  • Remove all elements.

    Complexity

    O(log(count)) if nodes of this tree are shared with other trees; O(count) otherwise.

    Declaration

    Swift

    public func removeAll()
    Show on GitHub

  • Remove all elements before (and if inclusive is true, including) the current position, and position the cursor at the start of the remaining tree.

    Complexity

    O(log(count)) if nodes of this tree are shared with other trees; O(count) otherwise.

    Declaration

    Swift

    public func removeAllBefore(includingCurrent inclusive: Bool)
    Show on GitHub

  • Remove all elements before (and if inclusive is true, including) the current position, and position the cursor on the end of the remaining tree.

    Complexity

    O(log(count)) if nodes of this tree are shared with other trees; O(count) otherwise.

    Declaration

    Swift

    public func removeAllAfter(includingCurrent inclusive: Bool)
    Show on GitHub

  • Extract n elements starting at the cursor’s current position, and position the cursor on the successor of the last element that was removed.

    Returns

    The extracted elements as a new B-tree.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func extract(_ n: Int) -> Tree

    Return Value

    The extracted elements as a new B-tree.

    Show on GitHub