BTree

public struct BTree<Key: Comparable, Value>

B-trees are search trees that provide an ordered key-value store with excellent performance characteristics.

Definition

  • Initialize a new B-tree with no elements.

    Parameter

    Parameter order: The maximum number of children for tree nodes.

    Declaration

    Swift

    public init(order: Int = Node.defaultOrder)

    Parameters

    order

    The maximum number of children for tree nodes.
    Show on GitHub

  • The order of this tree, i.e., the maximum number of children for tree nodes.

    Declaration

    Swift

    public var order: Int
    Show on GitHub

  • The depth of this tree. Depth starts at 0 for a tree that has a single root node.

    Declaration

    Swift

    public var depth: Int
    Show on GitHub

Sequence

  • Returns true iff this tree has no elements.

    Declaration

    Swift

    public var isEmpty: Bool
    Show on GitHub

  • Returns an iterator over the elements of this B-tree. Elements are sorted by key.

    Declaration

    Swift

    public func makeIterator() -> Iterator
    Show on GitHub

  • Returns an iterator starting at a specific index.

    Declaration

    Swift

    public func makeIterator(from index: Index) -> Iterator
    Show on GitHub

  • Returns an iterator starting at a specific offset.

    Declaration

    Swift

    public func makeIterator(fromOffset offset: Int) -> Iterator
    Show on GitHub

  • Returns an iterator starting at the element with the specified key. If the tree contains no such element, the generator is positioned on the first element with a larger key. If there are multiple elements with the same key, selector indicates which matching element to find.

    Declaration

    Swift

    public func makeIterator(from key: Key, choosing selector: BTreeKeySelector = .any) -> Iterator
    Show on GitHub

  • Call body on each element in self in the same order as a for-in loop.

    Declaration

    Swift

    public func forEach(_ body: (Element) throws -> ()) rethrows
    Show on GitHub

  • A version of forEach that allows body to interrupt iteration by returning false.

    Returns

    true iff body returned true for all elements in the tree.

    Declaration

    Swift

    public func forEach(_ body: (Element) throws -> Bool) rethrows -> Bool

    Return Value

    true iff body returned true for all elements in the tree.

    Show on GitHub

CollectionType

  • Returns the element at index.

    Complexity

    O(1)

    Declaration

    Swift

    public subscript(index: Index) -> Element
    Show on GitHub

  • Returns a tree consisting of elements in the specified range of indexes.

    Complexity

    O(log(count))

    Declaration

    Swift

    public subscript(range: Range<Index>) -> BTree<Key, Value>
    Show on GitHub

  • The index of the first element of this tree. Elements are sorted by key.

    Complexity

    O(log(count))

    Declaration

    Swift

    public var startIndex: Index
    Show on GitHub

  • The index after the last element of this tree. (Equals startIndex when the tree is empty.)

    Complexity

    O(1)

    Declaration

    Swift

    public var endIndex: Index
    Show on GitHub

  • The number of elements in this tree.

    Declaration

    Swift

    public var count: Int
    Show on GitHub

  • Returns the successor of the given index.

    Requires

    index is a valid index of this tree and it is not equal to endIndex.

    Complexity

    Amortized O(1).

    Declaration

    Swift

    public func index(after index: Index) -> Index
    Show on GitHub

  • Replaces the given index with its successor.

    Requires

    index is a valid index of this tree and it is not equal to endIndex.

    Complexity

    Amortized O(1).

    Declaration

    Swift

    public func formIndex(after index: inout Index)
    Show on GitHub

  • Returns the predecessor of the given index.

    Requires

    index is a valid index of this tree and it is not equal to startIndex.

    Complexity

    Amortized O(1).

    Declaration

    Swift

    public func index(before index: Index) -> Index
    Show on GitHub

  • Replaces the given index with its predecessor.

    Requires

    index is a valid index of this tree and it is not equal to startIndex.

    Complexity

    Amortized O(1).

    Declaration

    Swift

    public func formIndex(before index: inout Index)
    Show on GitHub

  • Returns an index that is the specified distance from the given index.

    Requires

    index must be a valid index of this tree. If n is positive, it must not exceed the distance from index to endIndex. If n is negative, it must not be less than the distance from index to startIndex.

    Complexity

    O(log(count)) where count is the number of elements in the tree.

    Declaration

    Swift

    public func index(_ i: Index, offsetBy n: Int) -> Index
    Show on GitHub

  • Offsets the given index by the specified distance.

    Requires

    index must be a valid index of this tree. If n is positive, it must not exceed the distance from index to endIndex. If n is negative, it must not be less than the distance from index to startIndex.

    Complexity

    O(log(count)) where count is the number of elements in the tree.

    Declaration

    Swift

    public func formIndex(_ i: inout Index, offsetBy n: Int)
    Show on GitHub

  • Returns an index that is the specified distance from the given index, unless that distance is beyond a given limiting index.

    Requires

    index and limit must be valid indices of this tree. The operation must not advance the index beyond endIndex or before startIndex.

    Complexity

    O(log(count)) where count is the number of elements in the tree.

    Declaration

    Swift

    public func index(_ i: Index, offsetBy n: Int, limitedBy limit: Index) -> Index?
    Show on GitHub

  • Offsets the given index by the specified distance, or so that it equals the given limiting index.

    Requires

    index and limit must be valid indices of this tree. The operation must not advance the index beyond endIndex or before startIndex.

    Complexity

    O(log(count)) where count is the number of elements in the tree.

    Declaration

    Swift

    public func formIndex(_ i: inout Index, offsetBy n: Int, limitedBy limit: Index) -> Bool
    Show on GitHub

  • Returns the distance between two indices.

    Requires

    start and end must be valid indices in this tree.

    Complexity

    O(1)

    Declaration

    Swift

    public func distance(from start: Index, to end: Index) -> Int
    Show on GitHub

Lookups

  • Returns the first element in this tree, or nil if the tree is empty.

    Complexity

    O(log(count))

    Declaration

    Swift

    public var first: Element?
    Show on GitHub

  • Returns the last element in this tree, or nil if the tree is empty.

    Complexity

    O(log(count))

    Declaration

    Swift

    public var last: Element?
    Show on GitHub

  • Returns the element at offset.

    Requires

    offset >= 0 && offset < count

    Complexity

    O(log(count))

    Declaration

    Swift

    public func element(atOffset offset: Int) -> Element
    Show on GitHub

  • Returns the value of an element of this tree with the specified key, or nil if there is no such element. If there are multiple elements with the same key, selector indicates which matching element to find.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func value(of key: Key, choosing selector: BTreeKeySelector = .any) -> Value?
    Show on GitHub

  • Returns an index to an element in this tree with the specified key, or nil if there is no such element. If there are multiple elements with the same key, selector indicates which matching element to find.

    This method never returns endIndex.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func index(forKey key: Key, choosing selector: BTreeKeySelector = .any) -> Index?
    Show on GitHub

  • Returns an index that points to the position where a new element with the specified key would be inserted into this tree. This is useful for finding the nearest element above or below key.

    The returned index may be endIndex if the tree is empty or key is greater than or equal to the key of the largest element.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func index(forInserting key: Key, at selector: BTreeKeySelector = .any) -> Index
    Show on GitHub

  • Returns the offset of the first element in this tree with the specified key, or nil if there is no such element. If there are multiple elements with the same key, selector indicates which matching element to find.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func offset(forKey key: Key, choosing selector: BTreeKeySelector = .any) -> Int?
    Show on GitHub

  • Returns the offset of the element at index.

    Complexity

    O(1)

    Declaration

    Swift

    public func offset(of index: Index) -> Int
    Show on GitHub

  • Returns the index of the element at offset.

    Requires

    offset >= 0 && offset <= count

    Complexity

    O(log(count))

    Declaration

    Swift

    public func index(ofOffset offset: Int) -> Index
    Show on GitHub

Editing

  • Set the value at offset, and return the value originally stored there.

    Requires

    offset < count

    Note

    When you need to perform multiple modifications on the same tree, BTreeCursor provides an alternative interface that’s often more efficient.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func setValue(atOffset offset: Int, to value: Value) -> Value
    Show on GitHub

Insertion

  • Insert the specified element into the tree at offset.

    Requires

    The key of the supplied element does not violate the B-tree’s ordering requirement. (This is only verified in non-optimized builds.)

    Note

    When you need to perform multiple modifications on the same tree, BTreeCursor provides an alternative interface that’s often more efficient.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func insert(_ element: Element, atOffset offset: Int)
    Show on GitHub

  • Insert element into the tree as a new element. If the tree already contains elements with the same key, selector specifies where to put the new element.

    Note

    When you need to perform multiple modifications on the same tree, BTreeCursor provides an alternative interface that’s often more efficient.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func insert(_ element: Element, at selector: BTreeKeySelector = .any)
    Show on GitHub

  • Insert element into the tree, replacing an element with the same key if there is one. If the tree already contains multiple elements with the same key, selector specifies which one to replace.

    Note

    When you need to perform multiple modifications on the same tree, BTreeCursor provides an alternative interface that’s often more efficient.

    Returns

    The element previously stored in the tree at the specified key.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func insertOrReplace(_ element: Element, at selector: BTreeKeySelector = .any) -> Element?

    Return Value

    The element previously stored in the tree at the specified key.

    Show on GitHub

  • Find and return an element that has the same key as element if there is one, or insert element in the tree and return nil.

    If the tree already contains multiple elements with the same key, selector specifies which one to return.

    Note

    When you need to perform multiple modifications on the same tree, BTreeCursor provides an alternative interface that’s often more efficient.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func insertOrFind(_ element: Element, at selector: BTreeKeySelector = .any) -> Element?
    Show on GitHub

Removal

  • Remove and return the first element.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func removeFirst() -> Element
    Show on GitHub

  • Remove and return the last element.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func removeLast() -> Element
    Show on GitHub

  • Remove and return the first element, or return nil if the tree is empty.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func popFirst() -> Element?
    Show on GitHub

  • Remove and return the first element, or return nil if the tree is empty.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func popLast() -> Element?
    Show on GitHub

  • Remove the first n elements from this tree.

    Complexity

    O(log(count) + n)

    Declaration

    Swift

    public mutating func removeFirst(_ n: Int)
    Show on GitHub

  • Remove the last n elements from this tree.

    Complexity

    O(log(count) + n)

    Declaration

    Swift

    public mutating func removeLast(_ n: Int)
    Show on GitHub

  • Remove and return the element at the specified offset.

    Note

    When you need to perform multiple modifications on the same tree, BTreeCursor provides an alternative interface that’s often more efficient.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func remove(atOffset offset: Int) -> Element
    Show on GitHub

  • Remove an element with the specified key, if it exists. If there are multiple elements with the same key, selector indicates which matching element to remove.

    Returns

    The removed element, or nil if there was no element with key in the tree.

    Note

    When you need to perform multiple modifications on the same tree, BTreeCursor provides an alternative interface that’s often more efficient.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func remove(_ key: Key, at selector: BTreeKeySelector = .any) -> Element?

    Return Value

    The removed element, or nil if there was no element with key in the tree.

    Show on GitHub

  • Remove and return the element referenced by the given index.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func remove(at index: Index) -> Element
    Show on GitHub

  • Remove all elements from this tree.

    Declaration

    Swift

    public mutating func removeAll()
    Show on GitHub

Subtree extraction

  • Returns a subtree containing the initial maxLength elements in this tree.

    If maxLength exceeds self.count, the result contains all the elements of self.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func prefix(_ maxLength: Int) -> BTree
    Show on GitHub

  • Returns a subtree containing all but the last n elements. If n exceeds the number of elements in the tree, the result is an empty tree.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func dropLast(_ n: Int) -> BTree
    Show on GitHub

  • Returns a subtree containing all elements before the specified index.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func prefix(upTo end: Index) -> BTree
    Show on GitHub

  • Returns a subtree containing all elements whose key is less than key.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func prefix(upTo end: Key) -> BTree
    Show on GitHub

  • Returns a subtree containing all elements at or before the specified index.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func prefix(through stop: Index) -> BTree
    Show on GitHub

  • Returns a subtree containing all elements whose key is less than or equal to key.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func prefix(through stop: Key) -> BTree
    Show on GitHub

  • Returns a tree containing the final maxLength elements in this tree.

    If maxLength exceeds self.count, the result contains all the elements of self.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func suffix(_ maxLength: Int) -> BTree
    Show on GitHub

  • Returns a subtree containing all but the first n elements. If n exceeds the number of elements in the tree, the result is an empty tree.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func dropFirst(_ n: Int) -> BTree
    Show on GitHub

  • Returns a subtree containing all elements at or after the specified index.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func suffix(from start: Index) -> BTree
    Show on GitHub

  • Returns a subtree containing all elements whose key is greater than or equal to key.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func suffix(from start: Key) -> BTree
    Show on GitHub

  • Return a subtree consisting of elements in the specified range of indexes.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func subtree(with range: Range<Index>) -> BTree<Key, Value>
    Show on GitHub

  • Return a subtree consisting of elements in the specified range of offsets.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func subtree(withOffsets offsets: Range<Int>) -> BTree<Key, Value>
    Show on GitHub

  • Return a subtree consisting of all elements with keys greater than or equal to start but less than end.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func subtree(from start: Key, to end: Key) -> BTree<Key, Value>
    Show on GitHub

  • Return a submap consisting of all elements with keys greater than or equal to start but less than or equal to end.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func subtree(from start: Key, through stop: Key) -> BTree<Key, Value>
    Show on GitHub

Merging and set operations

  • Merge elements from two trees into a new tree, and return it.

    Parameter

    Parameter other: Any tree with the same order as self.

    Parameter

    Parameter strategy: When .groupingMatches, elements in self whose keys also appear in other are not included in the result. If neither input tree had duplicate keys on its own, the result won’t have any duplicates, either.

    When .countingMatches, all elements in both trees are kept in the result, including ones with duplicate keys. The result may have duplicate keys, even if the input trees only had unique-keyed elements.

    Returns

    A tree with elements from self with matching keys in other removed.

    Note

    The elements of the two input trees may interleave and overlap in any combination. However, if there are long runs of non-interleaved elements, parts of the input trees will be entirely skipped instead of elementwise processing. This may drastically improve performance.

    When strategy == .groupingMatches, this function also detects shared subtrees between the two trees, and links them directly into the result when possible. (Otherwise matching keys are individually processed.)

    Requires

    self.order == other.order

    Complexity

    Complexity:

    • O(min(self.count, other.count)) in general.
    • O(log(self.count + other.count)) if there are only a constant amount of interleaving element runs.

    Declaration

    Swift

    public func union(_ other: BTree, by strategy: BTreeMatchingStrategy) -> BTree

    Parameters

    other

    Any tree with the same order as self.
    strategy

    When .groupingMatches, elements in self whose keys also appear in other are not included in the result. If neither input tree had duplicate keys on its own, the result won’t have any duplicates, either.

    When .countingMatches, all elements in both trees are kept in the result, including ones with duplicate keys. The result may have duplicate keys, even if the input trees only had unique-keyed elements.

    Return Value

    A tree with elements from self with matching keys in other removed.

    Show on GitHub

  • Return a tree with the same elements as self except those with matching keys in other.

    Parameter

    Parameter other: Any tree with the same order as self.

    Parameter

    Parameter strategy: When .groupingMatches, all elements in self that have a matching key in other are removed.

    When .countingMatches, for each key in self, only as many matching elements are removed as the key’s multiplicity in other.

    Returns

    A tree with elements from self with matching keys in other removed.

    Note

    The elements of the two input trees may interleave and overlap in any combination. However, if there are long runs of non-interleaved elements, parts of the input trees will be entirely skipped or linked into the result instead of elementwise processing. This may drastically improve performance.

    This function also detects and skips over shared subtrees between the two trees. (Keys that appear in both trees otherwise require individual processing.)

    Requires

    self.order == other.order

    Complexity

    Complexity:

    • O(min(self.count, tree.count)) in general.
    • O(log(self.count + tree.count)) if there are only a constant amount of interleaving element runs.

    Declaration

    Swift

    public func subtracting(_ other: BTree, by strategy: BTreeMatchingStrategy) -> BTree

    Parameters

    other

    Any tree with the same order as self.
    strategy

    When .groupingMatches, all elements in self that have a matching key in other are removed.

    When .countingMatches, for each key in self, only as many matching elements are removed as the key’s multiplicity in other.

    Return Value

    A tree with elements from self with matching keys in other removed.

    Show on GitHub

  • Return a tree combining the elements of self and other except those whose keys can be matched in both trees.

    Parameter

    Parameter other: Any tree with the same order as self.

    Parameter

    Parameter strategy: When .groupingMatches, all elements in both trees are removed whose key appears in both trees, regardless of their multiplicities.

    When .countingMatches, for each key, only as many matching elements are removed as the minimum of the key’s multiplicities in the two trees, leaving extra occurences from the longer tree in the result.

    Returns

    A tree combining elements of self and other except those whose keys can be matched in both trees.

    Note

    The elements of the two input trees may interleave and overlap in any combination. However, if there are long runs of non-interleaved elements, parts of the input trees will be entirely linked into the result instead of elementwise processing. This may drastically improve performance.

    This function also detects and skips over shared subtrees between the two trees. (Keys that appear in both trees otherwise require individual processing.)

    Requires

    self.order == other.order

    Complexity

    Complexity:

    • O(min(self.count, other.count)) in general.
    • O(log(self.count + other.count)) if there are only a constant amount of interleaving element runs.

    Declaration

    Swift

    public func symmetricDifference(_ other: BTree, by strategy: BTreeMatchingStrategy) -> BTree

    Parameters

    other

    Any tree with the same order as self.
    strategy

    When .groupingMatches, all elements in both trees are removed whose key appears in both trees, regardless of their multiplicities.

    When .countingMatches, for each key, only as many matching elements are removed as the minimum of the key’s multiplicities in the two trees, leaving “extra” occurences from the “longer” tree in the result.

    Return Value

    A tree combining elements of self and other except those whose keys can be matched in both trees.

    Show on GitHub

  • Return a tree with those elements of other whose keys are also included in self.

    Parameter

    Parameter other: Any tree with the same order as self.

    Parameter

    Parameter strategy: When .groupingMatches, all elements in other are included that have matching keys in self, regardless of multiplicities.

    When .countingMatches, for each key, only as many matching elements from other are kept as the minimum of the key’s multiplicities in the two trees.

    Returns

    A tree combining elements of self and other except those whose keys can be matched in both trees.

    Note

    The elements of the two input trees may interleave and overlap in any combination. However, if there are long runs of non-interleaved elements, parts of the input trees will be entirely skipped instead of elementwise processing. This may drastically improve performance.

    This function also detects shared subtrees between the two trees, and links them directly into the result when possible. (Keys that appear in both trees otherwise require individual processing.)

    Requires

    self.order == other.order

    Complexity

    Complexity:

    • O(min(self.count, other.count)) in general.
    • O(log(self.count + other.count)) if there are only a constant amount of interleaving element runs.

    Declaration

    Swift

    public func intersection(_ other: BTree, by strategy: BTreeMatchingStrategy) -> BTree

    Parameters

    other

    Any tree with the same order as self.
    strategy

    When .groupingMatches, all elements in other are included that have matching keys in self, regardless of multiplicities.

    When .countingMatches, for each key, only as many matching elements from other are kept as the minimum of the key’s multiplicities in the two trees.

    Return Value

    A tree combining elements of self and other except those whose keys can be matched in both trees.

    Show on GitHub

  • Return a tree that contains all elements in self whose key is not in the supplied sorted sequence.

    Note

    The keys of self may interleave and overlap with sortedKeys in any combination. However, if there are long runs of non-interleaved keys, parts of self will be entirely skipped instead of elementwise processing. This may drastically improve performance.

    Requires

    sortedKeys is sorted in ascending order.

    Complexity

    O(n + self.count), where n is the number of keys in sortedKeys.

    Declaration

    Swift

    public func subtracting<S: Sequence>(sortedKeys: S, by strategy: BTreeMatchingStrategy) -> BTree where S.Iterator.Element == Key
    Show on GitHub

  • Return a tree that contains all elements in self whose key is in the supplied sorted sequence.

    Note

    The keys of self may interleave and overlap with sortedKeys in any combination. However, if there are long runs of non-interleaved keys, parts of self will be entirely skipped instead of elementwise processing. This may drastically improve performance.

    Requires

    sortedKeys is sorted in ascending order.

    Complexity

    O(n + self.count), where n is the number of keys in sortedKeys.

    Declaration

    Swift

    public func intersection<S: Sequence>(sortedKeys: S, by strategy: BTreeMatchingStrategy) -> BTree where S.Iterator.Element == Key
    Show on GitHub

Cursors

  • Call body with a cursor at offset in this tree.

    Warning

    Do not rely on anything about self (the BTree that is the target of this method) during the execution of body: it will not appear to have the correct value. Instead, use only the supplied cursor to manipulate the tree.

    Declaration

    Swift

    public mutating func withCursor<R>(atOffset offset: Int, body: (Cursor) throws -> R) rethrows -> R
    Show on GitHub

  • Call body with a cursor at the start of this tree.

    Warning

    Do not rely on anything about self (the BTree that is the target of this method) during the execution of body: it will not appear to have the correct value. Instead, use only the supplied cursor to manipulate the tree.

    Declaration

    Swift

    public mutating func withCursorAtStart<R>(_ body: (Cursor) throws -> R) rethrows -> R
    Show on GitHub

  • Call body with a cursor at the end of this tree.

    Warning

    Do not rely on anything about self (the BTree that is the target of this method) during the execution of body: it will not appear to have the correct value. Instead, use only the supplied cursor to manipulate the tree.

    Declaration

    Swift

    public mutating func withCursorAtEnd<R>(_ body: (Cursor) throws -> R) rethrows -> R
    Show on GitHub

  • Call body with a cursor positioned on key in this tree. If there are multiple elements with the same key, selector indicates which matching element to find.

    Warning

    Do not rely on anything about self (the BTree that is the target of this method) during the execution of body: it will not appear to have the correct value. Instead, use only the supplied cursor to manipulate the tree.

    Declaration

    Swift

    public mutating func withCursor<R>(onKey key: Key, choosing selector: BTreeKeySelector = .any, body: (Cursor) throws -> R) rethrows -> R
    Show on GitHub

  • Call body with a cursor positioned on index in this tree.

    Warning

    Do not rely on anything about self (the BTree that is the target of this method) during the execution of body: it will not appear to have the correct value. Instead, use only the supplied cursor to manipulate the tree.

    Declaration

    Swift

    public mutating func withCursor<R>(at index: Index, body: (Cursor) throws -> R) rethrows -> R
    Show on GitHub

Comparison

  • Return true iff self and other contain equivalent elements, using isEquivalent as the equivalence test.

    This method skips over shared subtrees when possible; this can drastically improve performance when the two trees are divergent mutations originating from the same value.

    Requires

    isEquivalent is an equivalence relation.

    Complexity

    O(count)

    Declaration

    Swift

    public func elementsEqual(_ other: BTree, by isEquivalent: (Element, Element) throws -> Bool) rethrows -> Bool
    Show on GitHub

  • Return true iff self and other contain equal elements.

    This method skips over shared subtrees when possible; this can drastically improve performance when the two trees are divergent mutations originating from the same value.

    Complexity

    O(count)

    Declaration

    Swift

    public func elementsEqual(_ other: BTree) -> Bool
    Show on GitHub

  • Return true iff a and b contain equal elements.

    This method skips over shared subtrees when possible; this can drastically improve performance when the two trees are divergent mutations originating from the same value.

    Complexity

    O(count)

    Declaration

    Swift

    public static func == (a: BTree, b: BTree) -> Bool
    Show on GitHub

  • Return true iff a and b do not contain equal elements.

    This method skips over shared subtrees when possible; this can drastically improve performance when the two trees are divergent mutations originating from the same value.

    Complexity

    O(count)

    Declaration

    Swift

    public static func != (a: BTree, b: BTree) -> Bool
    Show on GitHub

  • Returns true iff this tree has no elements whose keys are also in tree.

    Complexity

    • O(min(self.count, tree.count)) in general.
    • O(log(self.count + tree.count)) if there are only a constant amount of interleaving element runs.

    Declaration

    Swift

    public func isDisjoint(with tree: BTree) -> Bool
    Show on GitHub

  • Returns true iff all keys in self are also in tree.

    Complexity

    • O(min(self.count, tree.count)) in general.
    • O(log(self.count + tree.count)) if there are only a constant amount of interleaving element runs.

    Declaration

    Swift

    public func isSubset(of tree: BTree, by strategy: BTreeMatchingStrategy) -> Bool
    Show on GitHub

  • Returns true iff all keys in self are also in tree, but tree contains at least one key that isn’t in self.

    Complexity

    • O(min(self.count, tree.count)) in general.
    • O(log(self.count + tree.count)) if there are only a constant amount of interleaving element runs.

    Declaration

    Swift

    public func isStrictSubset(of tree: BTree, by strategy: BTreeMatchingStrategy) -> Bool
    Show on GitHub

  • Returns true iff all keys in tree are also in self.

    Complexity

    • O(min(self.count, tree.count)) in general.
    • O(log(self.count + tree.count)) if there are only a constant amount of interleaving element runs.

    Declaration

    Swift

    public func isSuperset(of tree: BTree, by strategy: BTreeMatchingStrategy) -> Bool
    Show on GitHub

  • Returns true iff all keys in tree are also in self, but self contains at least one key that isn’t in tree.

    Complexity

    • O(min(self.count, tree.count)) in general.
    • O(log(self.count + tree.count)) if there are only a constant amount of interleaving element runs.

    Declaration

    Swift

    public func isStrictSuperset(of tree: BTree, by strategy: BTreeMatchingStrategy) -> Bool
    Show on GitHub

Bulk loading initializers

  • Create a new B-tree from elements of an unsorted sequence, using a stable sort algorithm.

    Parameter

    Parameter elements: An unsorted sequence of arbitrary length.

    Parameter

    Parameter order: The desired B-tree order. If not specified (recommended), the default order is used.

    Complexity

    O(count * log(count))

    See also

    init(sortedElements:order:fillFactor:) for a (faster) variant that can be used if the sequence is already sorted.

    Declaration

    Swift

    public init<S: Sequence>(_ elements: S, dropDuplicates: Bool = false, order: Int = Node.defaultOrder)
        where S.Iterator.Element == Element

    Parameters

    elements

    An unsorted sequence of arbitrary length.
    order

    The desired B-tree order. If not specified (recommended), the default order is used.
    Show on GitHub

  • Create a new B-tree from elements of a sequence sorted by key.

    Parameter

    Parameter sortedElements: A sequence of arbitrary length, sorted by key.

    Parameter

    Parameter order: The desired B-tree order. If not specified (recommended), the default order is used.

    Parameter

    Parameter fillFactor: The desired fill factor in each node of the new tree. Must be between 0.5 and 1.0. If not specified, a value of 1.0 is used, i.e., nodes will be loaded with as many elements as possible.

    Complexity

    O(count)

    See also

    init(elements:order:fillFactor:) for a (slower) unsorted variant.

    Declaration

    Swift

    public init<S: Sequence>(sortedElements elements: S, dropDuplicates: Bool = false, order: Int = Node.defaultOrder, fillFactor: Double = 1) where S.Iterator.Element == Element

    Parameters

    sortedElements

    A sequence of arbitrary length, sorted by key.
    order

    The desired B-tree order. If not specified (recommended), the default order is used.
    fillFactor

    The desired fill factor in each node of the new tree. Must be between 0.5 and 1.0. If not specified, a value of 1.0 is used, i.e., nodes will be loaded with as many elements as possible.
    Show on GitHub