mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
256 lines
7.6 KiB
Swift
256 lines
7.6 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 {
|
|
@usableFromInline
|
|
internal typealias _UnsafeHandle = _UnsafeBitSet
|
|
}
|
|
|
|
extension _UnsafeBitSet {
|
|
@inline(__always)
|
|
internal func _isReachable(_ index: Index) -> Bool {
|
|
unsafe index == endIndex || contains(index.value)
|
|
}
|
|
}
|
|
|
|
extension _UnsafeBitSet {
|
|
internal func _emptySuffix() -> Int {
|
|
var i = wordCount - 1
|
|
while i >= 0, unsafe _words[i].isEmpty {
|
|
i -= 1
|
|
}
|
|
return wordCount - 1 - i
|
|
}
|
|
}
|
|
|
|
extension _UnsafeBitSet {
|
|
@inlinable
|
|
internal mutating func combineSharedPrefix(
|
|
with other: Self,
|
|
using function: (inout _Word, _Word) -> Void
|
|
) {
|
|
ensureMutable()
|
|
let c = Swift.min(self.wordCount, other.wordCount)
|
|
for w in 0 ..< c {
|
|
unsafe function(&self._mutableWords[w], other._words[w])
|
|
}
|
|
}
|
|
}
|
|
|
|
extension _UnsafeBitSet {
|
|
@_effects(releasenone)
|
|
internal mutating func formUnion(_ range: Range<UInt>) {
|
|
ensureMutable()
|
|
let l = Index(range.lowerBound)
|
|
let u = Index(range.upperBound)
|
|
assert(u.value <= capacity)
|
|
|
|
if l.word == u.word {
|
|
guard l.word < wordCount else { return }
|
|
let w = _Word(from: l.bit, to: u.bit)
|
|
unsafe _mutableWords[l.word].formUnion(w)
|
|
return
|
|
}
|
|
unsafe _mutableWords[l.word].formUnion(_Word(upTo: l.bit).complement())
|
|
for w in l.word + 1 ..< u.word {
|
|
unsafe _mutableWords[w] = .allBits
|
|
}
|
|
if u.word < wordCount {
|
|
unsafe _mutableWords[u.word].formUnion(_Word(upTo: u.bit))
|
|
}
|
|
}
|
|
|
|
@_effects(releasenone)
|
|
internal mutating func formIntersection(_ range: Range<UInt>) {
|
|
ensureMutable()
|
|
let l = Index(Swift.min(range.lowerBound, capacity))
|
|
let u = Index(Swift.min(range.upperBound, capacity))
|
|
|
|
for w in 0 ..< l.word {
|
|
unsafe _mutableWords[w] = .empty
|
|
}
|
|
|
|
if l.word == u.word {
|
|
guard l.word < wordCount else { return }
|
|
|
|
let w = _Word(from: l.bit, to: u.bit)
|
|
unsafe _mutableWords[l.word].formIntersection(w)
|
|
return
|
|
}
|
|
|
|
unsafe _mutableWords[l.word].formIntersection(_Word(upTo: l.bit).complement())
|
|
if u.word < wordCount {
|
|
unsafe _mutableWords[u.word].formIntersection(_Word(upTo: u.bit))
|
|
unsafe _mutableWords[(u.word + 1)...].update(repeating: .empty)
|
|
}
|
|
}
|
|
|
|
@_effects(releasenone)
|
|
internal mutating func formSymmetricDifference(_ range: Range<UInt>) {
|
|
ensureMutable()
|
|
let l = Index(range.lowerBound)
|
|
let u = Index(range.upperBound)
|
|
assert(u.value <= capacity)
|
|
|
|
if l.word == u.word {
|
|
guard l.word < wordCount else { return }
|
|
let w = _Word(from: l.bit, to: u.bit)
|
|
unsafe _mutableWords[l.word].formSymmetricDifference(w)
|
|
return
|
|
}
|
|
unsafe _mutableWords[l.word]
|
|
.formSymmetricDifference(_Word(upTo: l.bit).complement())
|
|
for w in l.word + 1 ..< u.word {
|
|
unsafe _mutableWords[w].formComplement()
|
|
}
|
|
if u.word < wordCount {
|
|
unsafe _mutableWords[u.word].formSymmetricDifference(_Word(upTo: u.bit))
|
|
}
|
|
}
|
|
|
|
@_effects(releasenone)
|
|
internal mutating func subtract(_ range: Range<UInt>) {
|
|
ensureMutable()
|
|
let l = Index(Swift.min(range.lowerBound, capacity))
|
|
let u = Index(Swift.min(range.upperBound, capacity))
|
|
|
|
if l.word == u.word {
|
|
guard l.word < wordCount else { return }
|
|
let w = _Word(from: l.bit, to: u.bit)
|
|
unsafe _mutableWords[l.word].subtract(w)
|
|
return
|
|
}
|
|
|
|
unsafe _mutableWords[l.word].subtract(_Word(upTo: l.bit).complement())
|
|
unsafe _mutableWords[(l.word + 1) ..< u.word].update(repeating: .empty)
|
|
if u.word < wordCount {
|
|
unsafe _mutableWords[u.word].subtract(_Word(upTo: u.bit))
|
|
}
|
|
}
|
|
|
|
@_effects(releasenone)
|
|
internal func isDisjoint(with range: Range<UInt>) -> Bool {
|
|
if unsafe self.isEmpty { return true }
|
|
let lower = Index(Swift.min(range.lowerBound, capacity))
|
|
let upper = Index(Swift.min(range.upperBound, capacity))
|
|
if lower == upper { return true }
|
|
|
|
if lower.word == upper.word {
|
|
guard lower.word < wordCount else { return true }
|
|
let w = _Word(from: lower.bit, to: upper.bit)
|
|
return unsafe _words[lower.word].intersection(w).isEmpty
|
|
}
|
|
|
|
let lw = _Word(upTo: lower.bit).complement()
|
|
guard unsafe _words[lower.word].intersection(lw).isEmpty else { return false }
|
|
|
|
for i in lower.word + 1 ..< upper.word {
|
|
guard unsafe _words[i].isEmpty else { return false }
|
|
}
|
|
if upper.word < wordCount {
|
|
let uw = _Word(upTo: upper.bit)
|
|
guard unsafe _words[upper.word].intersection(uw).isEmpty else { return false }
|
|
}
|
|
return true
|
|
}
|
|
|
|
@_effects(releasenone)
|
|
internal func isSubset(of range: Range<UInt>) -> Bool {
|
|
guard !range.isEmpty else { return unsafe isEmpty }
|
|
guard unsafe !_words.isEmpty else { return true }
|
|
let r = range.clamped(to: 0 ..< UInt(capacity))
|
|
|
|
let lower = Index(r.lowerBound)
|
|
let upper = Index(r.upperBound)
|
|
|
|
for w in 0 ..< lower.word {
|
|
guard unsafe _words[w].isEmpty else { return false }
|
|
}
|
|
|
|
guard lower.word < wordCount else { return true }
|
|
|
|
let lw = _Word(upTo: lower.bit)
|
|
guard unsafe _words[lower.word].intersection(lw).isEmpty else { return false }
|
|
|
|
guard upper.word < wordCount else { return true }
|
|
|
|
let hw = _Word(upTo: upper.bit).complement()
|
|
guard unsafe _words[upper.word].intersection(hw).isEmpty else { return false }
|
|
|
|
for w in upper.word + 1 ..< wordCount {
|
|
guard unsafe _words[w].isEmpty else { return false }
|
|
}
|
|
return true
|
|
}
|
|
|
|
@_effects(releasenone)
|
|
internal func isSuperset(of range: Range<UInt>) -> Bool {
|
|
guard !range.isEmpty else { return true }
|
|
let r = range.clamped(to: 0 ..< UInt(capacity))
|
|
guard r == range else { return false }
|
|
|
|
let lower = Index(range.lowerBound)
|
|
let upper = Index(range.upperBound)
|
|
|
|
if lower.word == upper.word {
|
|
let w = _Word(from: lower.bit, to: upper.bit)
|
|
return unsafe _words[lower.word].intersection(w) == w
|
|
}
|
|
let lw = _Word(upTo: lower.bit).complement()
|
|
guard unsafe _words[lower.word].intersection(lw) == lw else { return false }
|
|
|
|
for w in lower.word + 1 ..< upper.word {
|
|
guard unsafe _words[w].isFull else { return false }
|
|
}
|
|
|
|
guard upper.word < wordCount else { return true }
|
|
let uw = _Word(upTo: upper.bit)
|
|
return unsafe _words[upper.word].intersection(uw) == uw
|
|
}
|
|
|
|
@_effects(releasenone)
|
|
internal func isEqualSet(to range: Range<UInt>) -> Bool {
|
|
if range.isEmpty { return unsafe self.isEmpty }
|
|
let r = range.clamped(to: 0 ..< UInt(capacity))
|
|
guard r == range else { return false }
|
|
|
|
let lower = Index(range.lowerBound).split
|
|
let upper = Index(range.upperBound).endSplit
|
|
|
|
guard upper.word == wordCount &- 1 else { return false }
|
|
|
|
for w in 0 ..< lower.word {
|
|
guard unsafe _words[w].isEmpty else { return false }
|
|
}
|
|
|
|
if lower.word == upper.word {
|
|
let w = _Word(from: lower.bit, to: upper.bit)
|
|
return unsafe _words[lower.word] == w
|
|
}
|
|
let lw = _Word(upTo: lower.bit).complement()
|
|
guard unsafe _words[lower.word] == lw else { return false }
|
|
|
|
for w in lower.word + 1 ..< upper.word {
|
|
guard unsafe _words[w].isFull else { return false }
|
|
}
|
|
|
|
let uw = _Word(upTo: upper.bit)
|
|
return unsafe _words[upper.word] == uw
|
|
}
|
|
}
|
|
|