mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
220 lines
6.4 KiB
Swift
220 lines
6.4 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 2021 - 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 {
|
|
/// Initializes a new, empty bit set.
|
|
///
|
|
/// This is equivalent to initializing with an empty array literal.
|
|
/// For example:
|
|
///
|
|
/// let set1 = BitSet()
|
|
/// print(set1.isEmpty) // true
|
|
///
|
|
/// let set2: BitSet = []
|
|
/// print(set2.isEmpty) // true
|
|
///
|
|
/// - Complexity: O(1)
|
|
public init() {
|
|
self.init(_rawStorage: [])
|
|
}
|
|
|
|
@usableFromInline
|
|
init(_words: [_Word]) {
|
|
self._storage = _words
|
|
_shrink()
|
|
_checkInvariants()
|
|
}
|
|
|
|
/// Initialize a new bit set from the raw bits of the supplied sequence of
|
|
/// words. (The term "words" is used here to mean a sequence of `UInt`
|
|
/// values, as in the `words` property of `BinaryInteger`.)
|
|
///
|
|
/// The resulting bit set will contain precisely those integers that
|
|
/// correspond to `true` bits within `words`. Bits are counted from least
|
|
/// to most significant within each word.
|
|
///
|
|
/// let bits = BitSet(words: [5, 2])
|
|
/// // bits is [0, 2, UInt.bitWidth + 1]
|
|
///
|
|
/// - Complexity: O(`words.count`)
|
|
@inlinable
|
|
public init(words: some Sequence<UInt>) {
|
|
self.init(_words: words.map { _Word($0) })
|
|
}
|
|
|
|
/// Initialize a new bit set from the raw bits of the supplied integer value.
|
|
///
|
|
/// The resulting bit set will contain precisely those integers that
|
|
/// correspond to `true` bits within `x`. Bits are counted from least
|
|
/// to most significant.
|
|
///
|
|
/// let bits = BitSet(bitPattern: 42)
|
|
/// // bits is [1, 3, 5]
|
|
///
|
|
/// - Complexity: O(`x.bitWidth`)
|
|
@inlinable
|
|
public init(bitPattern x: some BinaryInteger) {
|
|
self.init(words: x.words)
|
|
}
|
|
|
|
/// Initialize a new bit set from the storage bits of the given bit array.
|
|
/// The resulting bit set will contain exactly those integers that address
|
|
/// `true` elements in the array.
|
|
///
|
|
/// Note that this conversion is lossy -- it discards the precise length of
|
|
/// the input array.
|
|
///
|
|
/// - Complexity: O(`array.count`)
|
|
public init(_ array: BitArray) {
|
|
self.init(_words: array._storage)
|
|
}
|
|
|
|
/// Create a new bit set containing the elements of a sequence.
|
|
///
|
|
/// - Parameters:
|
|
/// - elements: The sequence of elements to turn into a bit set.
|
|
///
|
|
/// - Complexity: O(*n*), where *n* is the number of elements in the sequence.
|
|
@inlinable
|
|
public init(
|
|
_ elements: __owned some Sequence<Int>
|
|
) {
|
|
if let elements = _specialize(elements, for: BitSet.self) {
|
|
self = elements
|
|
return
|
|
}
|
|
if let elements = _specialize(elements, for: BitSet.Counted.self) {
|
|
self = elements._bits
|
|
return
|
|
}
|
|
self.init()
|
|
for value in elements {
|
|
self.insert(value)
|
|
}
|
|
}
|
|
|
|
/// Create a new bit set containing all the nonnegative elements of a
|
|
/// sequence of integers.
|
|
///
|
|
/// Items in `elements` that are negative are silently ignored.
|
|
///
|
|
/// - Parameters:
|
|
/// - elements: The sequence of elements to turn into a bit set.
|
|
///
|
|
/// - Complexity: O(*n*), where *n* is the number of elements in the sequence.
|
|
@inlinable
|
|
internal init(
|
|
_validMembersOf elements: __owned some Sequence<Int>
|
|
) {
|
|
if let elements = _specialize(elements, for: BitSet.self) {
|
|
self = elements
|
|
return
|
|
}
|
|
if let elements = _specialize(elements, for: BitSet.Counted.self) {
|
|
self = elements._bits
|
|
return
|
|
}
|
|
if let elements = _specialize(elements, for: Range<Int>.self) {
|
|
let r = elements
|
|
self.init(_range: r._clampedToUInt())
|
|
return
|
|
}
|
|
self.init()
|
|
for value in elements {
|
|
guard let value = UInt(exactly: value) else { continue }
|
|
self._insert(value)
|
|
}
|
|
}
|
|
}
|
|
|
|
extension BitSet {
|
|
/// Create a new bit set containing the elements of a range of integers.
|
|
///
|
|
/// - Parameters:
|
|
/// - range: The range to turn into a bit set. The range must not contain
|
|
/// negative values.
|
|
///
|
|
/// - Complexity: O(`range.upperBound`)
|
|
public init(_ range: Range<Int>) {
|
|
guard let range = range._toUInt() else {
|
|
preconditionFailure("BitSet can only hold nonnegative integers")
|
|
}
|
|
self.init(_range: range)
|
|
}
|
|
|
|
@usableFromInline
|
|
internal init(_range range: Range<UInt>) {
|
|
_storage = []
|
|
let lower = _UnsafeHandle.Index(range.lowerBound)
|
|
let upper = _UnsafeHandle.Index(range.upperBound)
|
|
if lower.word > 0 {
|
|
_storage.append(contentsOf: repeatElement(.empty, count: lower.word))
|
|
}
|
|
if lower.word == upper.word {
|
|
_storage.append(_Word(from: lower.bit, to: upper.bit))
|
|
} else {
|
|
_storage.append(_Word(upTo: lower.bit).complement())
|
|
let filledWords = upper.word &- lower.word
|
|
if filledWords > 0 {
|
|
_storage.append(
|
|
contentsOf: repeatElement(.allBits, count: filledWords &- 1))
|
|
}
|
|
_storage.append(_Word(upTo: upper.bit))
|
|
}
|
|
_shrink()
|
|
_checkInvariants()
|
|
}
|
|
}
|
|
|
|
extension BitSet {
|
|
internal init(
|
|
_combining handles: (_UnsafeHandle, _UnsafeHandle),
|
|
includingTail: Bool,
|
|
using function: (_Word, _Word) -> _Word
|
|
) {
|
|
let w1 = handles.0._words
|
|
let w2 = handles.1._words
|
|
let capacity = (
|
|
includingTail
|
|
? Swift.max(w1.count, w2.count)
|
|
: Swift.min(w1.count, w2.count))
|
|
_storage = Array(unsafeUninitializedCapacity: capacity) { buffer, count in
|
|
let sharedCount = Swift.min(w1.count, w2.count)
|
|
for w in 0 ..< sharedCount {
|
|
buffer.initializeElement(at: w, to: function(w1[w], w2[w]))
|
|
}
|
|
if includingTail {
|
|
if w1.count < w2.count {
|
|
for w in w1.count ..< w2.count {
|
|
buffer.initializeElement(at: w, to: function(_Word.empty, w2[w]))
|
|
}
|
|
} else {
|
|
for w in w2.count ..< w1.count {
|
|
buffer.initializeElement(at: w, to: function(w1[w], _Word.empty))
|
|
}
|
|
}
|
|
}
|
|
// Adjust the word count based on results.
|
|
count = capacity
|
|
while count > 0, buffer[count - 1].isEmpty {
|
|
count -= 1
|
|
}
|
|
}
|
|
_checkInvariants()
|
|
}
|
|
}
|