mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
1363 lines
42 KiB
Swift
1363 lines
42 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 2022 - 2026 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
// SPDX-License-Identifier: Apache-2.0 WITH Swift-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#if !COLLECTIONS_SINGLE_MODULE
|
|
import InternalCollectionsUtilities
|
|
#endif
|
|
|
|
extension BitSet {
|
|
public struct Counted {
|
|
@usableFromInline
|
|
internal var _bits: BitSet
|
|
@usableFromInline
|
|
internal var _count: Int
|
|
|
|
internal init(_bits: BitSet, count: Int) {
|
|
self._bits = _bits
|
|
self._count = count
|
|
_checkInvariants()
|
|
}
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted: Sendable {}
|
|
|
|
extension BitSet.Counted {
|
|
#if COLLECTIONS_INTERNAL_CHECKS
|
|
@inline(never)
|
|
@_effects(releasenone)
|
|
public func _checkInvariants() {
|
|
_bits._checkInvariants()
|
|
precondition(_count == _bits.count)
|
|
}
|
|
#else
|
|
@inline(__always) @inlinable
|
|
public func _checkInvariants() {}
|
|
#endif // COLLECTIONS_INTERNAL_CHECKS
|
|
}
|
|
|
|
extension BitSet.Counted: _UniqueCollection {}
|
|
|
|
extension BitSet.Counted {
|
|
public init() {
|
|
self.init(BitSet())
|
|
}
|
|
|
|
@inlinable
|
|
public init(words: some Sequence<UInt>) {
|
|
self.init(BitSet(words: words))
|
|
}
|
|
|
|
@inlinable
|
|
public init(bitPattern x: some BinaryInteger) {
|
|
self.init(words: x.words)
|
|
}
|
|
|
|
public init(_ array: BitArray) {
|
|
self.init(BitSet(array))
|
|
}
|
|
|
|
@inlinable
|
|
public init(_ elements: __owned some Sequence<Int>) {
|
|
self.init(BitSet(elements))
|
|
}
|
|
|
|
public init(_ range: Range<Int>) {
|
|
self.init(BitSet(range))
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
public init(_ bits: BitSet) {
|
|
self.init(_bits: bits, count: bits.count)
|
|
}
|
|
|
|
public var uncounted: BitSet {
|
|
get { _bits }
|
|
@inline(__always) // https://github.com/apple/swift-collections/issues/164
|
|
_modify {
|
|
defer {
|
|
_count = _bits.count
|
|
}
|
|
yield &_bits
|
|
}
|
|
}
|
|
}
|
|
|
|
extension BitSet {
|
|
public init(_ bits: BitSet.Counted) {
|
|
self = bits._bits
|
|
}
|
|
|
|
public var counted: BitSet.Counted {
|
|
get {
|
|
BitSet.Counted(_bits: self, count: self.count)
|
|
}
|
|
@inline(__always) // https://github.com/apple/swift-collections/issues/164
|
|
_modify {
|
|
var value = BitSet.Counted(self)
|
|
self = []
|
|
defer { self = value._bits }
|
|
yield &value
|
|
}
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted: Sequence {
|
|
public typealias Iterator = BitSet.Iterator
|
|
|
|
public var underestimatedCount: Int {
|
|
_count
|
|
}
|
|
|
|
public func makeIterator() -> BitSet.Iterator {
|
|
_bits.makeIterator()
|
|
}
|
|
|
|
public func _customContainsEquatableElement(
|
|
_ element: Int
|
|
) -> Bool? {
|
|
_bits._customContainsEquatableElement(element)
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted: BidirectionalCollection {
|
|
public typealias Index = BitSet.Index
|
|
|
|
public var isEmpty: Bool { _count == 0 }
|
|
|
|
public var count: Int { _count }
|
|
|
|
public var startIndex: Index { _bits.startIndex }
|
|
public var endIndex: Index { _bits.endIndex }
|
|
|
|
public subscript(position: Index) -> Int {
|
|
_bits[position]
|
|
}
|
|
|
|
public func index(after index: Index) -> Index {
|
|
_bits.index(after: index)
|
|
}
|
|
|
|
public func index(before index: Index) -> Index {
|
|
_bits.index(before: index)
|
|
}
|
|
|
|
public func distance(from start: Index, to end: Index) -> Int {
|
|
_bits.distance(from: start, to: end)
|
|
}
|
|
|
|
public func index(_ index: Index, offsetBy distance: Int) -> Index {
|
|
_bits.index(index, offsetBy: distance)
|
|
}
|
|
|
|
public func index(
|
|
_ i: Index, offsetBy distance: Int, limitedBy limit: Index
|
|
) -> Index? {
|
|
_bits.index(i, offsetBy: distance, limitedBy: limit)
|
|
}
|
|
|
|
public func _customIndexOfEquatableElement(_ element: Int) -> Index?? {
|
|
_bits._customIndexOfEquatableElement(element)
|
|
}
|
|
|
|
public func _customLastIndexOfEquatableElement(_ element: Int) -> Index?? {
|
|
_bits._customLastIndexOfEquatableElement(element)
|
|
}
|
|
}
|
|
|
|
|
|
#if !$Embedded
|
|
extension BitSet.Counted: Codable {
|
|
public func encode(to encoder: Encoder) throws {
|
|
try _bits.encode(to: encoder)
|
|
}
|
|
|
|
public init(from decoder: Decoder) throws {
|
|
self.init(try BitSet(from: decoder))
|
|
}
|
|
}
|
|
#endif
|
|
|
|
#if !$Embedded
|
|
extension BitSet.Counted: CustomStringConvertible {
|
|
// A textual representation of this instance.
|
|
public var description: String {
|
|
_bits.description
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted: CustomDebugStringConvertible {
|
|
/// A textual representation of this instance, suitable for debugging.
|
|
public var debugDescription: String {
|
|
description
|
|
}
|
|
}
|
|
#endif
|
|
|
|
#if !$Embedded
|
|
extension BitSet.Counted: CustomReflectable {
|
|
public var customMirror: Mirror {
|
|
_bits.customMirror
|
|
}
|
|
}
|
|
#endif
|
|
|
|
extension BitSet.Counted: Equatable {
|
|
public static func ==(left: Self, right: Self) -> Bool {
|
|
guard left._count == right._count else { return false }
|
|
return left._bits == right._bits
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted: Hashable {
|
|
public func hash(into hasher: inout Hasher) {
|
|
hasher.combine(_bits)
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted: ExpressibleByArrayLiteral {
|
|
@inlinable
|
|
public init(arrayLiteral elements: Int...) {
|
|
let bits = BitSet(elements)
|
|
self.init(bits)
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted { // Extras
|
|
public init(reservingCapacity maximumValue: Int) {
|
|
self.init(_bits: BitSet(reservingCapacity: maximumValue), count: 0)
|
|
}
|
|
|
|
public mutating func reserveCapacity(_ maximumValue: Int) {
|
|
_bits.reserveCapacity(maximumValue)
|
|
}
|
|
|
|
public subscript(member member: Int) -> Bool {
|
|
get { contains(member) }
|
|
set {
|
|
if newValue {
|
|
insert(member)
|
|
} else {
|
|
remove(member)
|
|
}
|
|
}
|
|
}
|
|
|
|
public subscript(members bounds: Range<Int>) -> Slice<BitSet> {
|
|
_bits[members: bounds]
|
|
}
|
|
|
|
public subscript(members bounds: some RangeExpression<Int>) -> Slice<BitSet> {
|
|
_bits[members: bounds]
|
|
}
|
|
|
|
public mutating func remove(at index: Index) -> Int {
|
|
defer { self._count &-= 1 }
|
|
return _bits.remove(at: index)
|
|
}
|
|
|
|
public func filter(
|
|
_ isIncluded: (Element) throws -> Bool
|
|
) rethrows -> Self {
|
|
BitSet.Counted(try _bits.filter(isIncluded))
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted: _SortedCollection {
|
|
/// Returns the current set (already sorted).
|
|
///
|
|
/// - Complexity: O(1)
|
|
public func sorted() -> BitSet.Counted { self }
|
|
|
|
/// Returns the minimum element in this set.
|
|
///
|
|
/// Bit sets are sorted, so the minimum element is always at the first
|
|
/// position in the set.
|
|
///
|
|
/// - Returns: The bit set's minimum element. If the sequence has no
|
|
/// elements, returns `nil`.
|
|
///
|
|
/// - Complexity: O(1)
|
|
@warn_unqualified_access
|
|
public func min() -> Element? {
|
|
first
|
|
}
|
|
|
|
/// Returns the maximum element in this set.
|
|
///
|
|
/// Bit sets are sorted, so the maximum element is always at the last
|
|
/// position in the set.
|
|
///
|
|
/// - Returns: The bit set's maximum element. If the sequence has no
|
|
/// elements, returns `nil`.
|
|
///
|
|
/// - Complexity: O(1)
|
|
@warn_unqualified_access
|
|
public func max() -> Element? {
|
|
last
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
public static func random(upTo limit: Int) -> BitSet.Counted {
|
|
BitSet.Counted(BitSet.random(upTo: limit))
|
|
}
|
|
|
|
public static func random(
|
|
upTo limit: Int,
|
|
using rng: inout some RandomNumberGenerator
|
|
) -> BitSet.Counted {
|
|
BitSet.Counted(BitSet.random(upTo: limit, using: &rng))
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted: SetAlgebra {
|
|
public func contains(_ member: Int) -> Bool {
|
|
_bits.contains(member)
|
|
}
|
|
|
|
@discardableResult
|
|
public mutating func insert(
|
|
_ newMember: Int
|
|
) -> (inserted: Bool, memberAfterInsert: Int) {
|
|
let r = _bits.insert(newMember)
|
|
if r.inserted { _count += 1 }
|
|
return r
|
|
}
|
|
|
|
@discardableResult
|
|
public mutating func update(with newMember: Int) -> Int? {
|
|
_bits.update(with: newMember)
|
|
}
|
|
|
|
@discardableResult
|
|
public mutating func remove(_ member: Int) -> Int? {
|
|
let old = _bits.remove(member)
|
|
if old != nil { _count -= 1 }
|
|
return old
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Returns a new set with the elements of both this and the given set.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet.Counted = [0, 2, 4, 6]
|
|
/// set.union(other) // [0, 1, 2, 3, 4, 6]
|
|
///
|
|
/// - Parameter other: The set of elements to insert.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public func union(_ other: BitSet.Counted) -> BitSet.Counted {
|
|
_bits.union(other).counted
|
|
}
|
|
|
|
/// Returns a new set with the elements of both this and the given set.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet = [0, 2, 4, 6]
|
|
/// set.union(other) // [0, 1, 2, 3, 4, 6]
|
|
///
|
|
/// - Parameter other: The set of elements to insert.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public func union(_ other: BitSet) -> BitSet.Counted {
|
|
_bits.union(other).counted
|
|
}
|
|
|
|
/// Returns a new set with the elements of both this set and the given
|
|
/// range of integers.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// set.union(3 ..< 7) // [1, 2, 3, 4, 5, 6]
|
|
///
|
|
/// - Parameter other: A range of nonnegative integers.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public func union(_ other: Range<Int>) -> BitSet.Counted {
|
|
_bits.union(other).counted
|
|
}
|
|
|
|
/// Returns a new set with the elements of both this set and the given
|
|
/// sequence of integers.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other = [6, 4, 2, 0, 2, 0]
|
|
/// set.union(other) // [0, 1, 2, 3, 4, 6]
|
|
///
|
|
/// - Parameter other: A sequence of nonnegative integers.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in either
|
|
/// input, and *k* is the complexity of iterating over all elements in
|
|
/// `other`.
|
|
@inlinable
|
|
public func union(
|
|
_ other: __owned some Sequence<Int>
|
|
) -> Self {
|
|
_bits.union(other).counted
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Returns a new bit set with the elements that are common to both this set
|
|
/// and the given set.
|
|
///
|
|
/// let a: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let b: BitSet.Counted = [6, 4, 2, 0]
|
|
/// let c = a.intersection(b)
|
|
/// // c is now [2, 4]
|
|
///
|
|
/// - Parameter other: A bit set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either set.
|
|
public func intersection(_ other: BitSet.Counted) -> BitSet.Counted {
|
|
_bits.intersection(other).counted
|
|
}
|
|
|
|
/// Returns a new bit set with the elements that are common to both this set
|
|
/// and the given set.
|
|
///
|
|
/// let a: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let b: BitSet = [6, 4, 2, 0]
|
|
/// let c = a.intersection(b)
|
|
/// // c is now [2, 4]
|
|
///
|
|
/// - Parameter other: A bit set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either set.
|
|
public func intersection(_ other: BitSet) -> BitSet.Counted {
|
|
_bits.intersection(other).counted
|
|
}
|
|
|
|
/// Returns a new bit set with the elements that are common to both this set
|
|
/// and the given range of integers.
|
|
///
|
|
/// let a: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let c = a.intersection(-10 ..< 3)
|
|
/// // c is now [3, 4]
|
|
///
|
|
/// - Parameter other: A range of integers.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in `self`,
|
|
/// and *k* is the complexity of iterating over all elements in `other`.
|
|
public func intersection(_ other: Range<Int>) -> BitSet.Counted {
|
|
_bits.intersection(other).counted
|
|
}
|
|
|
|
/// Returns a new bit set with the elements that are common to both this set
|
|
/// and the given sequence.
|
|
///
|
|
/// let a: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let b = [6, 4, 2, 0]
|
|
/// let c = a.intersection(b)
|
|
/// // c is now [2, 4]
|
|
///
|
|
/// - Parameter other: A sequence of integer values.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in `self`,
|
|
/// and *k* is the complexity of iterating over all elements in `other`.
|
|
@inlinable
|
|
public func intersection(
|
|
_ other: __owned some Sequence<Int>
|
|
) -> Self {
|
|
_bits.intersection(other).counted
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Returns a new bit set with the elements that are either in this set or in
|
|
/// `other`, but not in both.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet.Counted = [6, 4, 2, 0]
|
|
/// set.symmetricDifference(other) // [0, 1, 3, 6]
|
|
///
|
|
/// - Parameter other: Another set.
|
|
///
|
|
/// - Returns: A new set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either set.
|
|
public func symmetricDifference(_ other: BitSet.Counted) -> BitSet.Counted {
|
|
_bits.symmetricDifference(other).counted
|
|
}
|
|
|
|
/// Returns a new bit set with the elements that are either in this set or in
|
|
/// `other`, but not in both.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet = [6, 4, 2, 0]
|
|
/// set.symmetricDifference(other) // [0, 1, 3, 6]
|
|
///
|
|
/// - Parameter other: Another set.
|
|
///
|
|
/// - Returns: A new set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either set.
|
|
public func symmetricDifference(_ other: BitSet) -> BitSet.Counted {
|
|
_bits.symmetricDifference(other).counted
|
|
}
|
|
|
|
/// Returns a new bit set with the elements that are either in this set or in
|
|
/// `other`, but not in both.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// set.formSymmetricDifference(3 ..< 7) // [1, 2, 5, 6]
|
|
///
|
|
/// - Parameter other: A range of nonnegative integers.
|
|
///
|
|
/// - Returns: A new set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public func symmetricDifference(_ other: Range<Int>) -> BitSet.Counted {
|
|
_bits.symmetricDifference(other).counted
|
|
}
|
|
|
|
/// Returns a new bit set with the elements that are either in this set or in
|
|
/// `other`, but not in both.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other = [6, 4, 2, 0, 2, 0]
|
|
/// set.formSymmetricDifference(other) // [0, 1, 3, 6]
|
|
///
|
|
/// - Parameter other: A sequence of nonnegative integers.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in either
|
|
/// input, and *k* is the complexity of iterating over all elements in
|
|
/// `other`.
|
|
@inlinable
|
|
public func symmetricDifference(
|
|
_ other: __owned some Sequence<Int>
|
|
) -> Self {
|
|
_bits.symmetricDifference(other).counted
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Returns a new set containing the elements of this set that do not occur
|
|
/// in the given other set.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet.Counted = [0, 2, 4, 6]
|
|
/// set.subtracting(other) // [1, 3]
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: A new set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public func subtracting(_ other: BitSet.Counted) -> BitSet.Counted {
|
|
_bits.subtracting(other).counted
|
|
}
|
|
|
|
/// Returns a new set containing the elements of this set that do not occur
|
|
/// in the given other set.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet = [0, 2, 4, 6]
|
|
/// set.subtracting(other) // [1, 3]
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: A new set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public func subtracting(_ other: BitSet) -> BitSet.Counted {
|
|
_bits.subtracting(other).counted
|
|
}
|
|
|
|
/// Returns a new set containing the elements of this set that do not occur
|
|
/// in the given range of integers.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// set.subtracting(-10 ..< 3) // [3, 4]
|
|
///
|
|
/// - Parameter other: A range of arbitrary integers.
|
|
///
|
|
/// - Returns: A new set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in self.
|
|
public func subtracting(_ other: Range<Int>) -> BitSet.Counted {
|
|
_bits.subtracting(other).counted
|
|
}
|
|
|
|
/// Returns a new set containing the elements of this set that do not occur
|
|
/// in the given sequence of integers.
|
|
///
|
|
/// let set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other = [6, 4, 2, 0, -2, -4]
|
|
/// set.subtracting(other) // [1, 3]
|
|
///
|
|
/// - Parameter other: A sequence of arbitrary integers.
|
|
///
|
|
/// - Returns: A new set.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in `self`,
|
|
/// and *k* is the complexity of iterating over all elements in `other`.
|
|
@inlinable
|
|
public func subtracting(
|
|
_ other: __owned some Sequence<Int>
|
|
) -> Self {
|
|
_bits.subtracting(other).counted
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Adds the elements of the given set to this set.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet.Counted = [0, 2, 4, 6]
|
|
/// set.formUnion(other)
|
|
/// // `set` is now `[0, 1, 2, 3, 4, 6]`
|
|
///
|
|
/// - Parameter other: The set of elements to insert.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public mutating func formUnion(_ other: BitSet.Counted) {
|
|
_bits.formUnion(other._bits)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Adds the elements of the given set to this set.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet = [0, 2, 4, 6]
|
|
/// set.formUnion(other)
|
|
/// // `set` is now `[0, 1, 2, 3, 4, 6]`
|
|
///
|
|
/// - Parameter other: The set of elements to insert.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public mutating func formUnion(_ other: BitSet) {
|
|
_bits.formUnion(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Adds the elements of the given range of integers to this set.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// set.formUnion(3 ..< 7)
|
|
/// // `set` is now `[1, 2, 3, 4, 5, 6]`
|
|
///
|
|
/// - Parameter other: A range of nonnegative integers.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public mutating func formUnion(_ other: Range<Int>) {
|
|
_bits.formUnion(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Adds the elements of the given sequence to this set.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other = [6, 4, 2, 0, 2, 0]
|
|
/// set.formUnion(other)
|
|
/// // `set` is now `[0, 1, 2, 3, 4, 6]`
|
|
///
|
|
/// - Parameter other: A sequence of nonnegative integers.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in either
|
|
/// input, and *k* is the complexity of iterating over all elements in
|
|
/// `other`.
|
|
@inlinable
|
|
public mutating func formUnion(
|
|
_ other: __owned some Sequence<Int>
|
|
) {
|
|
_bits.formUnion(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Removes the elements of this set that aren't also in the given one.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet.Counted = [0, 2, 4, 6]
|
|
/// set.formIntersection(other)
|
|
/// // set is now [2, 4]
|
|
///
|
|
/// - Parameter other: A bit set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either set.
|
|
public mutating func formIntersection(_ other: BitSet.Counted) {
|
|
_bits.formIntersection(other._bits)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Removes the elements of this set that aren't also in the given one.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet = [0, 2, 4, 6]
|
|
/// set.formIntersection(other)
|
|
/// // set is now [2, 4]
|
|
///
|
|
/// - Parameter other: A bit set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either set.
|
|
public mutating func formIntersection(_ other: BitSet) {
|
|
_bits.formIntersection(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Removes the elements of this set that aren't also in the given range.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// set.formIntersection(-10 ..< 3)
|
|
/// // set is now [3, 4]
|
|
///
|
|
/// - Parameter other: A range of integers.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `self`.
|
|
public mutating func formIntersection(_ other: Range<Int>) {
|
|
_bits.formIntersection(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Removes the elements of this set that aren't also in the given sequence.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: Set<Int> = [6, 4, 2, 0]
|
|
/// set.formIntersection(other)
|
|
/// // set is now [2, 4]
|
|
///
|
|
/// - Parameter other: A sequence of integers.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in `self`,
|
|
/// and *k* is the complexity of iterating over all elements in `other`.
|
|
@inlinable
|
|
public mutating func formIntersection(
|
|
_ other: __owned some Sequence<Int>
|
|
) {
|
|
_bits.formIntersection(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Replace this set with the elements contained in this set or the given
|
|
/// set, but not both.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet.Counted = [0, 2, 4, 6]
|
|
/// set.formSymmetricDifference(other)
|
|
/// // set is now [0, 1, 3, 6]
|
|
///
|
|
/// - Parameter other: Another set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either set.
|
|
public mutating func formSymmetricDifference(_ other: BitSet.Counted) {
|
|
_bits.formSymmetricDifference(other._bits)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Replace this set with the elements contained in this set or the given
|
|
/// set, but not both.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet = [0, 2, 4, 6]
|
|
/// set.formSymmetricDifference(other)
|
|
/// // set is now [0, 1, 3, 6]
|
|
///
|
|
/// - Parameter other: Another set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either set.
|
|
public mutating func formSymmetricDifference(_ other: BitSet) {
|
|
_bits.formSymmetricDifference(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Replace this set with the elements contained in this set or the given
|
|
/// range of integers, but not both.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// set.formSymmetricDifference(3 ..< 7)
|
|
/// // set is now [1, 2, 5, 6]
|
|
///
|
|
/// - Parameter other: A range of nonnegative integers.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public mutating func formSymmetricDifference(_ other: Range<Int>) {
|
|
_bits.formSymmetricDifference(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Replace this set with the elements contained in this set or the given
|
|
/// sequence, but not both.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other = [6, 4, 2, 0, 2, 0]
|
|
/// set.formSymmetricDifference(other)
|
|
/// // set is now [0, 1, 3, 6]
|
|
///
|
|
/// - Parameter other: A sequence of nonnegative integers.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in either
|
|
/// input, and *k* is the complexity of iterating over all elements in
|
|
/// `other`.
|
|
@inlinable
|
|
public mutating func formSymmetricDifference(
|
|
_ other: __owned some Sequence<Int>
|
|
) {
|
|
_bits.formSymmetricDifference(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Removes the elements of the given bit set from this set.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet.Counted = [0, 2, 4, 6]
|
|
/// set.subtract(other)
|
|
/// // set is now [1, 3]
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public mutating func subtract(_ other: BitSet.Counted) {
|
|
_bits.subtract(other._bits)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Removes the elements of the given bit set from this set.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other: BitSet = [0, 2, 4, 6]
|
|
/// set.subtract(other)
|
|
/// // set is now [1, 3]
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public mutating func subtract(_ other: BitSet) {
|
|
_bits.subtract(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Removes the elements of the given range of integers from this set.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// set.subtract(-10 ..< 3)
|
|
/// // set is now [3, 4]
|
|
///
|
|
/// - Parameter other: A range of arbitrary integers.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in self.
|
|
public mutating func subtract(_ other: Range<Int>) {
|
|
_bits.subtract(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Removes the elements of the given sequence of integers from this set.
|
|
///
|
|
/// var set: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let other = [6, 4, 2, 0, -2, -4]
|
|
/// set.subtract(other)
|
|
/// // set is now [1, 3]
|
|
///
|
|
/// - Parameter other: A sequence of arbitrary integers.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in `self`,
|
|
/// and *k* is the complexity of iterating over all elements in `other`.
|
|
@inlinable
|
|
public mutating func subtract(
|
|
_ other: __owned some Sequence<Int>
|
|
) {
|
|
_bits.subtract(other)
|
|
_count = _bits.count
|
|
_checkInvariants()
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Returns a Boolean value indicating whether two bit sets are equal. Two
|
|
/// bit sets are considered equal if they contain the same elements.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is value of the largest member of
|
|
/// either set.
|
|
public func isEqualSet(to other: BitSet.Counted) -> Bool {
|
|
guard self.count == other.count else { return false }
|
|
return self._bits.isEqualSet(to: other._bits)
|
|
}
|
|
|
|
/// Returns a Boolean value indicating whether a bit set is equal to a counted
|
|
/// bit set, i.e., whether they contain the same values.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is value of the largest member of
|
|
/// either set.
|
|
public func isEqualSet(to other: BitSet) -> Bool {
|
|
self._bits.isEqualSet(to: other)
|
|
}
|
|
|
|
/// Returns a Boolean value indicating whether a bit set is equal to a range
|
|
/// of integers, i.e., whether they contain the same values.
|
|
///
|
|
/// - Complexity: O(min(*max*, `other.upperBound`), where *max* is the largest
|
|
/// member of `self`.
|
|
public func isEqualSet(to other: Range<Int>) -> Bool {
|
|
guard self.count == other.count else { return false }
|
|
return _bits.isEqualSet(to: other)
|
|
}
|
|
|
|
/// Returns a Boolean value indicating whether this bit set contains the same
|
|
/// elements as the given `other` sequence.
|
|
///
|
|
/// Duplicate items in `other` do not prevent it from comparing equal to
|
|
/// `self`.
|
|
///
|
|
/// let bits: BitSet = [0, 1, 5, 6]
|
|
/// let other = [5, 5, 0, 1, 1, 6, 5, 0, 1, 6, 6, 5]
|
|
///
|
|
/// bits.isEqualSet(to: other) // true
|
|
///
|
|
/// - Complexity: O(*n*), where *n* is the number of items in `other`.
|
|
@inlinable
|
|
public func isEqualSet(to other: some Sequence<Int>) -> Bool {
|
|
guard self.count >= other.underestimatedCount else { return false }
|
|
return _bits.isEqualSet(to: other)
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Returns a Boolean value that indicates whether this set is a subset of
|
|
/// the given set.
|
|
///
|
|
/// Set *A* is a subset of another set *B* if every member of *A* is also a
|
|
/// member of *B*.
|
|
///
|
|
/// let a: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let b: BitSet.Counted = [1, 2, 4]
|
|
/// let c: BitSet.Counted = [0, 1]
|
|
/// a.isSubset(of: a) // true
|
|
/// b.isSubset(of: a) // true
|
|
/// c.isSubset(of: a) // false
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: `true` if the set is a subset of `other`; otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `self`.
|
|
public func isSubset(of other: BitSet.Counted) -> Bool {
|
|
if self.count > other.count { return false }
|
|
return self._bits.isSubset(of: other._bits)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this set is a subset of
|
|
/// the given set.
|
|
///
|
|
/// Set *A* is a subset of another set *B* if every member of *A* is also a
|
|
/// member of *B*.
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: `true` if the set is a subset of `other`; otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `self`.
|
|
public func isSubset(of other: BitSet) -> Bool {
|
|
self._bits.isSubset(of: other)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this set is a subset of
|
|
/// the given range of integers.
|
|
///
|
|
/// Set *A* is a subset of another set *B* if every member of *A* is also a
|
|
/// member of *B*.
|
|
///
|
|
/// let b: BitSet.Counted = [0, 1, 2]
|
|
/// let c: BitSet.Counted = [2, 3, 4]
|
|
/// b.isSubset(of: -10 ..< 4) // true
|
|
/// c.isSubset(of: -10 ..< 4) // false
|
|
///
|
|
/// - Parameter other: An arbitrary range of integers.
|
|
///
|
|
/// - Returns: `true` if the set is a subset of `other`; otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `self`.
|
|
public func isSubset(of other: Range<Int>) -> Bool {
|
|
_bits.isSubset(of: other)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this set is a subset of
|
|
/// the values in a given sequence of integers.
|
|
///
|
|
/// Set *A* is a subset of another set *B* if every member of *A* is also a
|
|
/// member of *B*.
|
|
///
|
|
/// let a = [1, 2, 3, 4, -10]
|
|
/// let b: BitSet.Counted = [1, 2, 4]
|
|
/// let c: BitSet.Counted = [0, 1]
|
|
/// b.isSubset(of: a) // true
|
|
/// c.isSubset(of: a) // false
|
|
///
|
|
/// - Parameter other: A sequence of arbitrary integers.
|
|
///
|
|
/// - Returns: `true` if the set is a subset of `other`; otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in `self`,
|
|
/// and *k* is the complexity of iterating over all elements in `other`.
|
|
@inlinable
|
|
public func isSubset(of other: some Sequence<Int>) -> Bool {
|
|
_bits.isSubset(of: other)
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Returns a Boolean value that indicates whether this set is a superset of
|
|
/// the given set.
|
|
///
|
|
/// Set *A* is a superset of another set *B* if every member of *B* is also a
|
|
/// member of *A*.
|
|
///
|
|
/// let a: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let b: BitSet.Counted = [1, 2, 4]
|
|
/// let c: BitSet.Counted = [0, 1]
|
|
/// a.isSuperset(of: a) // true
|
|
/// a.isSuperset(of: b) // true
|
|
/// a.isSuperset(of: c) // false
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: `true` if the set is a superset of `other`; otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `other`.
|
|
public func isSuperset(of other: BitSet.Counted) -> Bool {
|
|
other.isSubset(of: self)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this set is a superset of
|
|
/// the given set.
|
|
///
|
|
/// Set *A* is a superset of another set *B* if every member of *B* is also a
|
|
/// member of *A*.
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: `true` if the set is a superset of `other`; otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `other`.
|
|
public func isSuperset(of other: BitSet) -> Bool {
|
|
other.isSubset(of: self)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this set is a superset of
|
|
/// a given range of integers.
|
|
///
|
|
/// Set *A* is a superset of another set *B* if every member of *B* is also a
|
|
/// member of *A*.
|
|
///
|
|
/// let a: BitSet = [0, 1, 2, 3, 4, 10]
|
|
/// a.isSuperset(of: 0 ..< 4) // true
|
|
/// a.isSuperset(of: -10 ..< 4) // false
|
|
///
|
|
/// - Parameter other: An arbitrary range of integers.
|
|
///
|
|
/// - Returns: `true` if the set is a superset of `other`; otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(`range.count`)
|
|
public func isSuperset(of other: Range<Int>) -> Bool {
|
|
_bits.isSuperset(of: other)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this set is a superset of
|
|
/// the values in a given sequence of integers.
|
|
///
|
|
/// Set *A* is a superset of another set *B* if every member of *B* is also a
|
|
/// member of *A*.
|
|
///
|
|
/// let a = [1, 2, 3]
|
|
/// let b: BitSet = [0, 1, 2, 3, 4]
|
|
/// let c: BitSet = [0, 1, 2]
|
|
/// b.isSuperset(of: a) // true
|
|
/// c.isSuperset(of: a) // false
|
|
///
|
|
/// - Parameter other: A sequence of arbitrary integers, some of whose members
|
|
/// may appear more than once. (Duplicate items are ignored.)
|
|
///
|
|
/// - Returns: `true` if the set is a superset of `other`; otherwise, `false`.
|
|
///
|
|
/// - Complexity: The same as the complexity of iterating over all elements
|
|
/// in `other`.
|
|
@inlinable
|
|
public func isSuperset(of other: some Sequence<Int>) -> Bool {
|
|
_bits.isSuperset(of: other)
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Returns a Boolean value that indicates whether this bit set is a strict
|
|
/// subset of the given set.
|
|
///
|
|
/// Set *A* is a strict subset of another set *B* if every member of *A* is
|
|
/// also a member of *B* and *B* contains at least one element that is not a
|
|
/// member of *A*.
|
|
///
|
|
/// let a: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let b: BitSet.Counted = [1, 2, 4]
|
|
/// let c: BitSet.Counted = [0, 1]
|
|
/// a.isStrictSubset(of: a) // false
|
|
/// b.isStrictSubset(of: a) // true
|
|
/// c.isStrictSubset(of: a) // false
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: `true` if the set is a strict subset of `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `self`.
|
|
public func isStrictSubset(of other: BitSet.Counted) -> Bool {
|
|
guard self.count < other.count else { return false }
|
|
return _bits.isStrictSubset(of: other._bits)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this bit set is a strict
|
|
/// subset of the given set.
|
|
///
|
|
/// Set *A* is a strict subset of another set *B* if every member of *A* is
|
|
/// also a member of *B* and *B* contains at least one element that is not a
|
|
/// member of *A*.
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: `true` if the set is a strict subset of `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `self`.
|
|
public func isStrictSubset(of other: BitSet) -> Bool {
|
|
_bits.isStrictSubset(of: other)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this set is a strict
|
|
/// subset of the given set.
|
|
///
|
|
/// Set *A* is a strict subset of another set *B* if every member of *A* is
|
|
/// also a member of *B* and *B* contains at least one element that is not a
|
|
/// member of *A*.
|
|
///
|
|
/// let b: BitSet.Counted = [0, 1, 2]
|
|
/// let c: BitSet.Counted = [2, 3, 4]
|
|
/// b.isStrictSubset(of: -10 ..< 4) // true
|
|
/// c.isStrictSubset(of: -10 ..< 4) // false
|
|
///
|
|
/// - Parameter other: An arbitrary range of integers.
|
|
///
|
|
/// - Returns: `true` if the set is a strict subset of `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `self`.
|
|
public func isStrictSubset(of other: Range<Int>) -> Bool {
|
|
guard self.count < other.count else { return false }
|
|
return _bits.isStrictSubset(of: other)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this bit set is a strict
|
|
/// subset of the values in a given sequence of integers.
|
|
///
|
|
/// Set *A* is a strict subset of another set *B* if every member of *A* is
|
|
/// also a member of *B* and *B* contains at least one element that is not a
|
|
/// member of *A*.
|
|
///
|
|
/// let a = [1, 2, 3, 4, -10]
|
|
/// let b: BitSet.Counted = [1, 2, 4]
|
|
/// let c: BitSet.Counted = [0, 1]
|
|
/// b.isStrictSubset(of: a) // true
|
|
/// c.isStrictSubset(of: a) // false
|
|
///
|
|
/// - Parameter other: A sequence of arbitrary integers.
|
|
///
|
|
/// - Returns: `true` if the set is a strict subset of `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in `self`,
|
|
/// and *k* is the complexity of iterating over all elements in `other`.
|
|
@inlinable
|
|
public func isStrictSubset(of other: some Sequence<Int>) -> Bool {
|
|
_bits.isStrictSubset(of: other)
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Returns a Boolean value that indicates whether this set is a strict
|
|
/// superset of another set.
|
|
///
|
|
/// Set *A* is a strict superset of another set *B* if every member of *B* is
|
|
/// also a member of *A* and *A* contains at least one element that is *not*
|
|
/// a member of *B*.
|
|
///
|
|
/// let a: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let b: BitSet.Counted = [1, 2, 4]
|
|
/// let c: BitSet.Counted = [0, 1]
|
|
/// a.isStrictSuperset(of: a) // false
|
|
/// a.isStrictSuperset(of: b) // true
|
|
/// a.isStrictSuperset(of: c) // false
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: `true` if the set is a strict superset of `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `other`.
|
|
public func isStrictSuperset(of other: BitSet.Counted) -> Bool {
|
|
other.isStrictSubset(of: self)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this set is a strict
|
|
/// superset of another set.
|
|
///
|
|
/// Set *A* is a strict superset of another set *B* if every member of *B* is
|
|
/// also a member of *A* and *A* contains at least one element that is *not*
|
|
/// a member of *B*.
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: `true` if the set is a strict superset of `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `other`.
|
|
public func isStrictSuperset(of other: BitSet) -> Bool {
|
|
other.isStrictSubset(of: self)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this set is a strict
|
|
/// superset of a given range of integers.
|
|
///
|
|
/// Set *A* is a strict superset of another set *B* if every member of *B* is
|
|
/// also a member of *A* and *A* contains at least one element that is *not*
|
|
/// a member of *B*.
|
|
///
|
|
/// let a: BitSet.Counted = [0, 1, 2, 3, 4, 10]
|
|
/// a.isStrictSuperset(of: 0 ..< 4) // true
|
|
/// a.isStrictSuperset(of: -10 ..< 4) // false
|
|
///
|
|
/// - Parameter other: An arbitrary range of integers.
|
|
///
|
|
/// - Returns: `true` if the set is a strict superset of `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(`range.count`)
|
|
public func isStrictSuperset(of other: Range<Int>) -> Bool {
|
|
_bits.isStrictSuperset(of: other)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether this set is a strict
|
|
/// superset of the values in a given sequence of integers.
|
|
///
|
|
/// Set *A* is a strict superset of another set *B* if every member of *B* is
|
|
/// also a member of *A* and *A* contains at least one element that is *not*
|
|
/// a member of *B*.
|
|
///
|
|
/// let a = [1, 2, 3]
|
|
/// let b: BitSet.Counted = [0, 1, 2, 3, 4]
|
|
/// let c: BitSet.Counted = [0, 1, 2]
|
|
/// b.isStrictSuperset(of: a) // true
|
|
/// c.isStrictSuperset(of: a) // false
|
|
///
|
|
/// - Parameter other: A sequence of arbitrary integers, some of whose members
|
|
/// may appear more than once. (Duplicate items are ignored.)
|
|
///
|
|
/// - Returns: `true` if the set is a strict superset of `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in `other`,
|
|
/// and *k* is the complexity of iterating over all elements in `other`.
|
|
@inlinable
|
|
public func isStrictSuperset(of other: some Sequence<Int>) -> Bool {
|
|
_bits.isStrictSuperset(of: other)
|
|
}
|
|
}
|
|
|
|
extension BitSet.Counted {
|
|
/// Returns a Boolean value that indicates whether the set has no members in
|
|
/// common with the given set.
|
|
///
|
|
/// let a: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let b: BitSet.Counted = [5, 6]
|
|
/// a.isDisjoint(with: b) // true
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: `true` if `self` has no elements in common with `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public func isDisjoint(with other: BitSet.Counted) -> Bool {
|
|
_bits.isDisjoint(with: other._bits)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether the set has no members in
|
|
/// common with the given set.
|
|
///
|
|
/// let a: BitSet.Counted = [1, 2, 3, 4]
|
|
/// let b: BitSet = [5, 6]
|
|
/// a.isDisjoint(with: b) // true
|
|
///
|
|
/// - Parameter other: Another bit set.
|
|
///
|
|
/// - Returns: `true` if `self` has no elements in common with `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in either input.
|
|
public func isDisjoint(with other: BitSet) -> Bool {
|
|
_bits.isDisjoint(with: other)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether the set has no members in
|
|
/// common with the given range of integers.
|
|
///
|
|
/// let a: BitSet = [1, 2, 3, 4]
|
|
/// a.isDisjoint(with: -10 ..< 0) // true
|
|
///
|
|
/// - Parameter other: A range of arbitrary integers.
|
|
///
|
|
/// - Returns: `true` if `self` has no elements in common with `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*), where *max* is the largest item in `self`.
|
|
public func isDisjoint(with other: Range<Int>) -> Bool {
|
|
_bits.isDisjoint(with: other)
|
|
}
|
|
|
|
/// Returns a Boolean value that indicates whether the set has no members in
|
|
/// common with the given sequence of integers.
|
|
///
|
|
/// let a: BitSet = [1, 2, 3, 4]
|
|
/// let b: BitSet = [5, 6, -10, 42]
|
|
/// a.isDisjoint(with: b) // true
|
|
///
|
|
/// - Parameter other: A sequence of arbitrary integers.
|
|
///
|
|
/// - Returns: `true` if `self` has no elements in common with `other`;
|
|
/// otherwise, `false`.
|
|
///
|
|
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in `self`,
|
|
/// and *k* is the complexity of iterating over all elements in `other`.
|
|
@inlinable
|
|
public func isDisjoint(with other: some Sequence<Int>) -> Bool {
|
|
_bits.isDisjoint(with: other)
|
|
}
|
|
}
|