SortedBag

public struct SortedBag<Element: Comparable>: SetAlgebra

A sorted collection of comparable elements; also known as a multiset. SortedBag is like a SortedSet except it can contain multiple members that are equal to each other. Lookup, insertion and removal of any element has logarithmic complexity.

SortedBag stores duplicate elements in their entirety; it doesn’t just count multiplicities. This is an important feature when equal elements can be distinguished by identity comparison or some other means. (If you’re OK with just counting duplicates, use a Map or a Dictionary with the multiplicity as the value.)

SortedBag is a struct with copy-on-write value semantics, like Swift’s standard collection types. It uses an in-memory b-tree for element storage, whose individual nodes may be shared with other sorted sets or bags. Mutating a bag whose storage is (partially or completely) shared requires copying of only O(log(count)) elements. (Thus, mutation of shared SortedBags may be cheaper than ordinary Sets, which need to copy all elements.)

Set operations on sorted bags (such as taking the union, intersection or difference) can take as little as O(log(n)) time if the elements in the input bags aren’t too interleaved.

See also

SortedSet

Initializers

  • Create an empty bag.

    Declaration

    Swift

    public init()
    Show on GitHub

  • Create a bag that holds the same members as the specified sorted set.

    Complexity: O(1); the new bag simply refers to the same storage as the set.

    Declaration

    Swift

    public init(_ set: SortedSet<Element>)
    Show on GitHub

  • Create a bag from a finite sequence of items. The sequence need not be sorted. If the sequence contains duplicate items, all of them are kept, in the same order.

    Complexity

    O(n * log(n)), where n is the number of items in the sequence.

    Declaration

    Swift

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

  • Create a bag from a sorted finite sequence of items. If the sequence contains duplicate items, all of them are kept.

    Complexity

    O(n), where n is the number of items in the sequence.

    Declaration

    Swift

    public init<S: Sequence>(sortedElements elements: S) where S.Iterator.Element == Element
    Show on GitHub

  • Create a bag with the specified list of items. If the array literal contains duplicate items, all of them are kept.

    Declaration

    Swift

    public init(arrayLiteral elements: Element...)
    Show on GitHub

CollectionType

  • Returns the element at the given index.

    Requires

    index originated from an unmutated copy of this set.

    Complexity

    O(1)

    Declaration

    Swift

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

  • Return the subbag consisting of elements in the given range of indexes.

    Requires

    The indices in range originated from an unmutated copy of this bag.

    Complexity

    O(log(count))

    Declaration

    Swift

    public subscript(range: Range<Index>) -> SortedBag<Element>
    Show on GitHub

  • The index of the first element when non-empty. Otherwise the same as endIndex.

    Complexity

    O(log(count))

    Declaration

    Swift

    public var startIndex: Index
    Show on GitHub

  • The past-the-end element index; the successor of the last valid subscript argument.

    Complexity

    O(1)

    Declaration

    Swift

    public var endIndex: Index
    Show on GitHub

  • The number of elements in this bag.

    Declaration

    Swift

    public var count: Int
    Show on GitHub

  • True iff this collection has no elements.

    Declaration

    Swift

    public var isEmpty: Bool
    Show on GitHub

  • Return an iterator over all elements in this map, in ascending key order.

    Declaration

    Swift

    public func makeIterator() -> Iterator
    Show on GitHub

  • Returns the successor of the given index.

    Requires

    index is a valid index of this bag 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 bag 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 bag 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 bag 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 at the specified distance from the given index.

    Requires

    index must be a valid index of this set. 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 set.

    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 set. 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 bag.

    Declaration

    Swift

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

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

    Requires

    index and limit must be valid indices in this bag. 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 bag.

    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 in this bag. 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 bag.

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

    Complexity

    O(1)

    Declaration

    Swift

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

Offset-based access

  • Returns the subbag containing elements in the specified range of offsets from the start of the bag.

    Complexity

    O(log(count))

    Declaration

    Swift

    public subscript(offsetRange: Range<Int>) -> SortedBag<Element>
    Show on GitHub

  • Returns the element at offset from the start of the bag.

    Complexity

    O(log(count))

    Declaration

    Swift

    public subscript(offset: Int) -> Element
    Show on GitHub

  • If member is in this bag, return the offset of its first instance. Otherwise, return nil.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func offset(of member: Element) -> Int?
    Show on GitHub

  • Returns the offset of the element at index.

    Complexity

    O(log(count))

    Declaration

    Swift

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

  • Returns the index of the element at offset.

    Requires

    offset >= 0 && offset < count

    Complexity

    O(log(count))

    Declaration

    Swift

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

Algorithms

  • Call body on each element in self in ascending order.

    Declaration

    Swift

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

  • Return an Array containing the results of mapping transform over self.

    Declaration

    Swift

    public func map<T>(_ transform: (Element) throws -> T) rethrows -> [T]
    Show on GitHub

  • Return an Array containing the concatenated results of mapping transform over self.

    Declaration

    Swift

    public func flatMap<S : Sequence>(_ transform: (Element) throws -> S) rethrows -> [S.Iterator.Element]
    Show on GitHub

  • Return an Array containing the non-nil results of mapping transform over self.

    Declaration

    Swift

    public func flatMap<T>(_ transform: (Element) throws -> T?) rethrows -> [T]
    Show on GitHub

  • Return an Array containing the elements of self, in ascending order, that satisfy the predicate includeElement.

    Declaration

    Swift

    public func filter(_ includeElement: (Element) throws -> Bool) rethrows -> [Element]
    Show on GitHub

  • Return the result of repeatedly calling combine with an accumulated value initialized to initial and each element of self, in turn. I.e., return combine(combine(...combine(combine(initial, self[0]), self[1]),...self[count-2]), self[count-1]).

    Declaration

    Swift

    public func reduce<T>(_ initialResult: T, _ nextPartialResult: (T, Element) throws -> T) rethrows -> T
    Show on GitHub

Extractions

  • Return (the first instance of) the smallest element in the bag, or nil if the bag is empty.

    Complexity

    O(log(count))

    Declaration

    Swift

    public var first: Element?
    Show on GitHub

  • Return (the last instance of) the largest element in the bag, or nil if the bag is empty.

    Complexity

    O(log(count))

    Declaration

    Swift

    public var last: Element?
    Show on GitHub

  • Return the smallest element in the bag, or nil if the bag is empty. This is the same as first.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func min() -> Element?
    Show on GitHub

  • Return the largest element in the set, or nil if the set is empty. This is the same as last.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func max() -> Element?
    Show on GitHub

  • If this bag is empty, the result is an empty bag.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func dropFirst() -> SortedBag
    Show on GitHub

  • Return a copy of this bag with the n smallest elements removed. If n exceeds the number of elements in the bag, the result is an empty bag.

    Complexity

    O(log(count))

    Declaration

    Swift

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

  • Return a copy of this bag with the largest element removed. If this bag is empty, the result is an empty bag.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func dropLast() -> SortedBag
    Show on GitHub

  • Return a copy of this bag with the n largest elements removed. If n exceeds the number of elements in the bag, the result is an empty bag.

    Complexity

    O(log(count))

    Declaration

    Swift

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

  • Returns a subbag, up to maxLength in size, containing the smallest elements in this bag.

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

    Complexity

    O(log(count))

    Declaration

    Swift

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

  • Returns a subbag containing all members of this bag at or before the specified index.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func prefix(through index: Index) -> SortedBag
    Show on GitHub

  • Returns a subset containing all members of this bag less than or equal to the specified element (which may or may not be a member of this bag).

    Complexity

    O(log(count))

    Declaration

    Swift

    public func prefix(through element: Element) -> SortedBag
    Show on GitHub

  • Returns a subbag containing all members of this bag before the specified index.

    Complexity

    O(log(count))

    Declaration

    Swift

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

  • Returns a subbag containing all members of this bag less than the specified element (which may or may not be a member of this bag).

    Complexity

    O(log(count))

    Declaration

    Swift

    public func prefix(upTo end: Element) -> SortedBag
    Show on GitHub

  • Returns a subbag, up to maxLength in size, containing the largest elements in this bag.

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

    Complexity

    O(log(count))

    Declaration

    Swift

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

  • Returns a subbag containing all members of this bag at or after the specified index.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func suffix(from index: Index) -> SortedBag
    Show on GitHub

  • Returns a subset containing all members of this bag greater than or equal to the specified element (which may or may not be a member of this bag).

    Complexity

    O(log(count))

    Declaration

    Swift

    public func suffix(from element: Element) -> SortedBag
    Show on GitHub

Conversion to string

Queries

  • Return true if the bag contains element.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func contains(_ element: Element) -> Bool
    Show on GitHub

  • Returns the multiplicity of member in this bag, i.e. the number of instances of member contained in the bag. Returns 0 if member is not an element.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func count(of member: Element) -> Int
    Show on GitHub

  • Returns the index of the first instance of a given member, or nil if the member is not present in the bag.

    Complexity

    O(log(count))

    Declaration

    Swift

    public func index(of member: Element) -> BTreeIndex<Element, Void>?
    Show on GitHub

  • Returns the index of the lowest member of this bag that is strictly greater than element, or nil if there is no such element.

    This function never returns endIndex. (If it returns non-nil, the returned index can be used to subscript the bag.)

    Complexity

    O(log(count))

    Declaration

    Swift

    public func indexOfFirstElement(after element: Element) -> BTreeIndex<Element, Void>?
    Show on GitHub

  • Returns the index of the lowest member of this bag that is greater than or equal to element, or nil if there is no such element.

    This function never returns endIndex. (If it returns non-nil, the returned index can be used to subscript the bag.)

    Complexity

    O(log(count))

    Declaration

    Swift

    public func indexOfFirstElement(notBefore element: Element) -> BTreeIndex<Element, Void>?
    Show on GitHub

  • Returns the index of the highest member of this bag that is strictly less than element, or nil if there is no such element.

    This function never returns endIndex. (If it returns non-nil, the returned index can be used to subscript the bag.)

    Complexity

    O(log(count))

    Declaration

    Swift

    public func indexOfLastElement(before element: Element) -> BTreeIndex<Element, Void>?
    Show on GitHub

  • Returns the index of the highest member of this bag that is less than or equal to element, or nil if there is no such element.

    This function never returns endIndex. (If it returns non-nil, the returned index can be used to subscript the bag.)

    Complexity

    O(log(count))

    Declaration

    Swift

    public func indexOfLastElement(notAfter element: Element) -> BTreeIndex<Element, Void>?
    Show on GitHub

Set comparions

  • Return true iff self and other contain the same number of instances of all the same elements.

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

    Complexity

    O(count)

    Declaration

    Swift

    public func elementsEqual(_ other: SortedBag<Element>) -> Bool
    Show on GitHub

  • Returns true iff a contains the exact same elements as b, including multiplicities.

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

    Complexity

    O(count)

    Declaration

    Swift

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

  • Returns true iff no members in this bag are also included in other.

    The elements of the two input bags may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input bags may be skipped instead of elementwise processing, which can drastically improve performance.

    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 isDisjoint(with other: SortedBag<Element>) -> Bool
    Show on GitHub

  • Returns true iff all members in this bag are also included in other.

    The elements of the two input bags may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input bags may be skipped instead of elementwise processing, which can drastically improve performance.

    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 isSubset(of other: SortedBag<Element>) -> Bool
    Show on GitHub

  • Returns true iff all members in this bag are also included in other, but the two bags aren’t equal.

    The elements of the two input bags may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input bags may be skipped instead of elementwise processing, which can drastically improve performance.

    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 isStrictSubset(of other: SortedBag<Element>) -> Bool
    Show on GitHub

  • Returns true iff all members in other are also included in this bag.

    The elements of the two input bags may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input bags may be skipped instead of elementwise processing, which can drastically improve performance.

    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 isSuperset(of other: SortedBag<Element>) -> Bool
    Show on GitHub

  • Returns true iff all members in other are also included in this bag, but the two bags aren’t equal.

    The elements of the two input bags may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input bags may be skipped instead of elementwise processing, which can drastically improve performance.

    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 isStrictSuperset(of other: SortedBag<Element>) -> Bool
    Show on GitHub

Insertion

  • Unconditionally insert a new member into the bag, adding another instance if the member was already present.

    The new member is inserted after its existing instances, if any. (This is important when equal members can be distinguished by identity comparison or some other means.)

    Note

    SetAlgebra requires insert to do nothing and return (false, member) if the set already contains a matching element. SortedBag ignores this requirement and always inserts a new copy of the specified element.

    Parameter

    Parameter newMember: An element to insert into the set.

    Returns

    (true, newMember) to satisfy the syntactic requirements of the SetAlgebra protocol.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func insert(_ newMember: Element) -> (inserted: Bool, memberAfterInsert: Element)

    Parameters

    newMember

    An element to insert into the set.

    Return Value

    (true, newMember) to satisfy the syntactic requirements of the SetAlgebra protocol.

    Show on GitHub

  • Unconditionally insert a new member into the bag, adding another instance if the member was already present.

    The new member is inserted before its existing instances, if any. (This is important when equal members can be distinguished by identity comparison or some other means.)

    Note

    SetAlgebra requires update to replace and return an existing member if the set already contains a matching element. SortedBag ignores this requirement and always inserts a new copy of the specified element.

    Parameter

    Parameter newMember: An element to insert into the set.

    Returns

    Always returns nil, to satisfy the syntactic requirements of the SetAlgebra protocol.

    Declaration

    Swift

    public mutating func update(with newMember: Element) -> Element?

    Parameters

    newMember

    An element to insert into the set.

    Return Value

    Always returns nil, to satisfy the syntactic requirements of the SetAlgebra protocol.

    Show on GitHub

Removal

  • Remove and return the first instance of member from the bag, or return nil if the bag contains no instances of member.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func remove(_ member: Element) -> Element?
    Show on GitHub

  • Remove all instances of member from the bag.

    Complexity

    O(log(count))

    Declaration

    Swift

    public mutating func removeAll(_ member: Element)
    Show on GitHub

  • Remove the member referenced by the given index.

    Complexity

    O(log(count))

    Declaration

    Swift

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

  • Remove the member at the given offset.

    Complexity

    O(log(count))

    Declaration

    Swift

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

  • Remove and return the smallest member in this bag, or return nil if the bag is empty.

    Complexity

    O(log(count))

    Declaration

    Swift

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

  • Remove and return the largest member in this bag, or return nil if the bag is empty.

    Complexity

    O(log(count))

    Declaration

    Swift

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

  • Remove all members from this bag.

    Declaration

    Swift

    public mutating func removeAll()
    Show on GitHub

Sorting

  • Return an Array containing the members of this bag, in ascending order.

    SortedSet already keeps its elements sorted, so this is equivalent to Array(self).

    Complexity

    O(count)

    Declaration

    Swift

    public func sorted() -> [Element]
    Show on GitHub

Set operations

  • Return a bag containing all members from both this bag and other. The result contains all elements of duplicate members from both bags.

    Elements from other follow matching elements from this in the result.

    The elements of the two input bags may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input bags will be simply linked into the result instead of copying, which can drastically improve performance.

    Complexity

    • O(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: SortedBag<Element>) -> SortedBag<Element>
    Show on GitHub

  • Add all members in other to this bag, also keeping all existing instances already in self.

    The elements of the two input bags may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input sets will be simply linked into the result instead of copying, which can drastically improve performance.

    Complexity

    • O(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 mutating func formUnion(_ other: SortedBag<Element>)
    Show on GitHub

  • Return a set consisting of all members in other that are also in this bag. For duplicate members, only as many instances from other are kept in the result that appear in self.

    The elements of the two input sets may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input sets will be simply linked into the result instead of copying, which can drastically improve performance.

    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: SortedBag<Element>) -> SortedBag<Element>
    Show on GitHub

  • Remove all members from this bag that are not also included in other. For duplicate members, only as many instances from self are kept that appear in other.

    The elements of the two input sets may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input sets will be simply linked into the result instead of copying, which can drastically improve performance.

    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 mutating func formIntersection(_ other: SortedBag<Element>)
    Show on GitHub

  • Return a bag containing those members of this bag that aren’t also included in other. For duplicate members whose multiplicity exceeds that of matching members in other, the extra members are kept in the result.

    The elements of the two input bags may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input bags will be simply linked into the result instead of copying, which can drastically improve performance.

    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 subtracting(_ other: SortedBag) -> SortedBag
    Show on GitHub

  • Remove all members from this bag that are also included in other. For duplicate members whose multiplicity exceeds that of matching members in other, the extra members aren’t removed.

    The elements of the two input bags may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input bags will be simply linked into the result instead of copying, which can drastically improve performance.

    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 mutating func subtract(_ other: SortedBag)
    Show on GitHub

  • Return a bag consisting of members from self and other that aren’t in both bags at once. For members whose multiplicity is different in the two bags, the last d members from the bag with the greater multiplicity is kept in the result (where d is the absolute difference of multiplicities).

    The elements of the two input bags may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input bags will be simply linked into the result instead of copying, which can drastically improve performance.

    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: SortedBag<Element>) -> SortedBag<Element>
    Show on GitHub

  • Replace self with a set consisting of members from self and other that aren’t in both sets at once.

    The elements of the two input sets may be freely interleaved. However, if there are long runs of non-interleaved elements, parts of the input sets will be simply linked into the result instead of copying, which can drastically improve performance.

    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 mutating func formSymmetricDifference(_ other: SortedBag<Element>)
    Show on GitHub

Interactions with ranges

  • Return the count of elements in this bag that are in range.

    Complexity

    O(log(self.count))

    Declaration

    Swift

    public func count(elementsIn range: Range<Element>) -> Int
    Show on GitHub

  • Return the count of elements in this bag that are in range.

    Complexity

    O(log(self.count))

    Declaration

    Swift

    public func count(elementsIn range: ClosedRange<Element>) -> Int
    Show on GitHub

  • Return a bag consisting of all members in self that are also in range.

    Complexity

    O(log(self.count))

    Declaration

    Swift

    public func intersection(elementsIn range: Range<Element>) -> SortedBag<Element>
    Show on GitHub

  • Return a bag consisting of all members in self that are also in range.

    Complexity

    O(log(self.count))

    Declaration

    Swift

    public func intersection(elementsIn range: ClosedRange<Element>) -> SortedBag<Element>
    Show on GitHub

  • Remove all members from this bag that are not included in range.

    Complexity

    O(log(self.count))

    Declaration

    Swift

    public mutating func formIntersection(elementsIn range: Range<Element>)
    Show on GitHub

  • Remove all members from this bag that are not included in range.

    Complexity

    O(log(self.count))

    Declaration

    Swift

    public mutating func formIntersection(elementsIn range: ClosedRange<Element>)
    Show on GitHub

  • Remove all elements in range from this bag.

    Complexity

    O(log(self.count))

    Declaration

    Swift

    public mutating func subtract(elementsIn range: Range<Element>)
    Show on GitHub

  • Remove all elements in range from this bag.

    Complexity

    O(log(self.count))

    Declaration

    Swift

    public mutating func subtract(elementsIn range: ClosedRange<Element>)
    Show on GitHub

  • Return a bag containing those members of this bag that aren’t also included in range.

    Complexity

    O(log(self.count))

    Declaration

    Swift

    public mutating func subtracting(elementsIn range: Range<Element>) -> SortedBag<Element>
    Show on GitHub

  • Return a bag containing those members of this bag that aren’t also included in range.

    Complexity

    O(log(self.count))

    Declaration

    Swift

    public mutating func subtracting(elementsIn range: ClosedRange<Element>) -> SortedBag<Element>
    Show on GitHub

Shifting

  • Shift the value of all elements starting at start by delta. For a positive delta, this shifts elements to the right, creating an empty gap in start ..< start + delta. For a negative delta, this shifts elements to the left, removing any elements in the range start + delta ..< start that were previously in the bag.

    Complexity

    O(self.count). The elements are modified in place.

    Declaration

    Swift

    public mutating func shift(startingAt start: Element, by delta: Element.Stride)
    Show on GitHub

  • Shift the value of all elements starting at index start by delta.

    This variant does not ever remove elements from the bag; if delta is negative, its absolute value must not be greater than the difference between the element at start and the element previous to it (if any).

    Requires

    `start == self.startIndex || self[self.index(before: startIndex)] <= self[index] + delta

    Complexity

    O(self.count). The elements are modified in place.

    Declaration

    Swift

    public mutating func shift(startingAt start: Index, by delta: Element.Stride)
    Show on GitHub