# 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 `SortedBag`s may be cheaper than ordinary `Set`s, 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.

`SortedSet`
• ``` init() ```

Create an empty bag.

#### Declaration

Swift

``public init()``
• ``` init(_:) ```

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>)``
• ``` init(_:) ```

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``
• ``` init(sortedElements:) ```

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``
• ``` init(arrayLiteral:) ```

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...)``
• ``` subscript(_:) ```

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``
• ``` subscript(_:) ```

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>``
• ``` startIndex ```

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

Complexity

O(log(`count`))

#### Declaration

Swift

``public var startIndex: Index``
• ``` endIndex ```

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

Complexity

O(1)

#### Declaration

Swift

``public var endIndex: Index``
• ``` count ```

The number of elements in this bag.

#### Declaration

Swift

``public var count: Int``
• ``` isEmpty ```

True iff this collection has no elements.

#### Declaration

Swift

``public var isEmpty: Bool``
• ``` makeIterator() ```

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

#### Declaration

Swift

``public func makeIterator() -> Iterator``
• ``` index(after:) ```

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``
• ``` formIndex(after:) ```

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)``
• ``` index(before:) ```

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``
• ``` formIndex(before:) ```

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)``
• ``` index(_:offsetBy:) ```

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``
• ``` formIndex(_:offsetBy:) ```

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)``
• ``` index(_:offsetBy:limitedBy:) ```

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?``
• ``` formIndex(_:offsetBy:limitedBy:) ```

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``
• ``` distance(from:to:) ```

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``
• ``` subscript(_:) ```

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>``
• ``` subscript(_:) ```

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

Complexity

O(log(`count`))

#### Declaration

Swift

``public subscript(offset: Int) -> Element``
• ``` offset(of:) ```

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?``
• ``` index(ofOffset:) ```

Returns the offset of the element at `index`.

Complexity

O(log(`count`))

#### Declaration

Swift

``public func index(ofOffset offset: Int) -> Index``
• ``` offset(of:) ```

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``
• ``` forEach(_:) ```

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

#### Declaration

Swift

``public func forEach(_ body: (Element) throws -> Void) rethrows``
• ``` map(_:) ```

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

#### Declaration

Swift

``public func map<T>(_ transform: (Element) throws -> T) rethrows -> [T]``
• ``` flatMap(_:) ```

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]``
• ``` flatMap(_:) ```

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]``
• ``` filter(_:) ```

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]``
• ``` reduce(_:_:) ```

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), self),...self[count-2]), self[count-1])`.

#### Declaration

Swift

``public func reduce<T>(_ initialResult: T, _ nextPartialResult: (T, Element) throws -> T) rethrows -> T``
• ``` first ```

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?``
• ``` last ```

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?``
• ``` min() ```

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?``
• ``` max() ```

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?``
• ``` dropFirst() ```

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

Complexity

O(log(`count`))

#### Declaration

Swift

``public func dropFirst() -> SortedBag``
• ``` dropFirst(_:) ```

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``
• ``` dropLast() ```

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``
• ``` dropLast(_:) ```

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``
• ``` prefix(_:) ```

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``
• ``` prefix(through:) ```

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``
• ``` prefix(through:) ```

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``
• ``` prefix(upTo:) ```

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``
• ``` prefix(upTo:) ```

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``
• ``` suffix(_:) ```

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``
• ``` suffix(from:) ```

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``
• ``` suffix(from:) ```

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``
• ``` description ```

A textual representation of this bag.

#### Declaration

Swift

``public var description: String``
• ``` debugDescription ```

A textual representation of this bag, suitable for debugging.

#### Declaration

Swift

``public var debugDescription: String``
• ``` contains(_:) ```

Return true if the bag contains `element`.

Complexity

O(log(`count`))

#### Declaration

Swift

``public func contains(_ element: Element) -> Bool``
• ``` count(of:) ```

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``
• ``` index(of:) ```

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>?``
• ``` indexOfFirstElement(after:) ```

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>?``
• ``` indexOfFirstElement(notBefore:) ```

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>?``
• ``` indexOfLastElement(before:) ```

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>?``
• ``` indexOfLastElement(notAfter:) ```

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>?``
• ``` elementsEqual(_:) ```

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``
• ``` ==(_:_:) ```

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``
• ``` isDisjoint(with:) ```

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``
• ``` isSubset(of:) ```

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``
• ``` isStrictSubset(of:) ```

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``
• ``` isSuperset(of:) ```

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``
• ``` isStrictSuperset(of:) ```

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``
• ``` insert(_:) ```

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.

• ``` update(with:) ```

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.

• ``` remove(_:) ```

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?``
• ``` removeAll(_:) ```

Remove all instances of `member` from the bag.

Complexity

O(log(`count`))

#### Declaration

Swift

``public mutating func removeAll(_ member: Element)``
• ``` remove(at:) ```

Remove the member referenced by the given index.

Complexity

O(log(`count`))

#### Declaration

Swift

``public mutating func remove(at index: Index) -> Element``
• ``` remove(atOffset:) ```

Remove the member at the given offset.

Complexity

O(log(`count`))

#### Declaration

Swift

``public mutating func remove(atOffset offset: Int) -> Element``
• ``` popFirst() ```

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?``
• ``` popLast() ```

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?``
• ``` removeAll() ```

Remove all members from this bag.

#### Declaration

Swift

``public mutating func removeAll()``
• ``` sorted() ```

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]``
• ``` union(_:) ```

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>``
• ``` formUnion(_:) ```

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>)``
• ``` intersection(_:) ```

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>``
• ``` formIntersection(_:) ```

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>)``
• ``` subtracting(_:) ```

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``
• ``` subtract(_:) ```

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)``
• ``` symmetricDifference(_:) ```

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>``
• ``` formSymmetricDifference(_:) ```

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>)``
• ``` count(elementsIn:) ```

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``
• ``` count(elementsIn:) ```

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``
• ``` intersection(elementsIn:) ```

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>``
• ``` intersection(elementsIn:) ```

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>``
• ``` formIntersection(elementsIn:) ```

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>)``
• ``` formIntersection(elementsIn:) ```

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>)``
• ``` subtract(elementsIn:) ```

Remove all elements in `range` from this bag.

Complexity

O(log(`self.count`))

#### Declaration

Swift

``public mutating func subtract(elementsIn range: Range<Element>)``
• ``` subtract(elementsIn:) ```

Remove all elements in `range` from this bag.

Complexity

O(log(`self.count`))

#### Declaration

Swift

``public mutating func subtract(elementsIn range: ClosedRange<Element>)``
• ``` subtracting(elementsIn:) ```

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>``
• ``` subtracting(elementsIn:) ```

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>``
• ``` shift(startingAt:by:) ```

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)``
• ``` shift(startingAt:by:) ```

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)``