BTree

public struct BTree<Key: Comparable, Value>

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

  • 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.

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

    Declaration

    Swift

    public var order: Int
  • The depth of this tree. Depth starts at 0 for a tree that has a single root node.

    Declaration

    Swift

    public var depth: Int
  • Returns true iff this tree has no elements.

    Declaration

    Swift

    public var isEmpty: Bool
  • Returns an iterator over the elements of this B-tree. Elements are sorted by key.

    Declaration

    Swift

    public func makeIterator() -> Iterator
  • Returns an iterator starting at a specific index.

    Declaration

    Swift

    public func makeIterator(from index: Index) -> Iterator
  • Returns an iterator starting at a specific offset.

    Declaration

    Swift

    public func makeIterator(fromOffset offset: Int) -> Iterator
  • 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
  • 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
  • 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.

  • Returns the element at index.

    Complexity

    O(1)

    Declaration

    Swift

    public subscript(index: Index) -> Element
  • 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>
  • The index of the first element of this tree. Elements are sorted by key.

    Complexity

    O(log(count))

    Declaration

    Swift

    public var startIndex: Index
  • 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
  • The number of elements in this tree.

    Declaration

    Swift

    public var count: Int
  • 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
  • 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)
  • 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
  • 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)
  • 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
  • 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)
  • 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?
  • 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
  • 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
  • Returns the first element in this tree, or nil if the tree is empty.

    Complexity

    O(log(count))

    Declaration

    Swift

    public var first: Element?
  • Returns the last element in this tree, or nil if the tree is empty.

    Complexity

    O(log(count))

    Declaration

    Swift

    public var last: Element?
  • Returns the element at offset.

    Requires

    offset >= 0 && offset < count

    Complexity

    O(log(count))

    Declaration

    Swift

    public func element(atOffset offset: Int) -> Element
  • 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?
  • 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?
  • 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
  • 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?
  • Returns the offset of the element at index.

    Complexity

    O(1)

    Declaration

    Swift

    public func offset(of index: Index) -> Int
  • 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
  • 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
  • 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)
  • 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)
  • 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.

  • 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?
  • Remove and return the first element.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func removeFirst() -> Element
  • Remove and return the last element.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func removeLast() -> Element
  • 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?
  • 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?
  • Remove the first n elements from this tree.

    Complexity

    O(log(count) + n)

    Declaration

    Swift

    public mutating func removeFirst(_ n: Int)
  • Remove the last n elements from this tree.

    Complexity

    O(log(count) + n)

    Declaration

    Swift

    public mutating func removeLast(_ n: Int)
  • 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
  • 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.

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

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func remove(at index: Index) -> Element
  • Remove all elements from this tree.

    Declaration

    Swift

    public mutating func removeAll()
  • 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
  • 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
  • Returns a subtree containing all elements before the specified index.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func prefix(upTo end: Index) -> BTree
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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>
  • 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>
  • 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>
  • 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>
  • 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.

  • 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.

  • 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.

  • 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.

  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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.

  • 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.