mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
201 lines
6.6 KiB
Swift
201 lines
6.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
|
|
|
|
#if false
|
|
// FIXME: Bitwise operators disabled for now. I have two concerns:
|
|
// 1. We need to support bitwise operations over slices of bit arrays, not just
|
|
// whole arrays.
|
|
// 2. We need to put in-place mutations as the primary operation, and they
|
|
// need to avoid copy-on-write copies unless absolutely necessary.
|
|
//
|
|
// It seems unlikely that the operator syntax will survive these points.
|
|
// We have five (5!) separate cases:
|
|
//
|
|
// foo |= bar
|
|
// foo[i ..< j] |= bar
|
|
// foo |= bar[u ..< v]
|
|
// foo[i ..< j] |= bar[u ..< v]
|
|
// foo[i ..< j] |= foo[k ..< l]
|
|
//
|
|
// The last one where the array is ORed with itself is particularly problematic
|
|
// -- like memcpy, these operations can easily support overlapping inputs, but
|
|
// it doesn't seem likely we can implement that with this nice slicing syntax,
|
|
// unless we are okay with forcing a CoW copy. (Which we aren't.)
|
|
//
|
|
// Even ignoring that, I would not like to end up with four overloads for each
|
|
// operator, especially not for such niche operations. So we'll entirely disable
|
|
// these for now, to prevent any shipping API from interfering with an eventual
|
|
// redesign. (This is an active area of experimentation, as it will potentially
|
|
// also affect our non-copyable container design.)
|
|
|
|
extension BitArray {
|
|
/// Stores the result of performing a bitwise OR operation on two
|
|
/// equal-sized bit arrays in the left-hand-side variable.
|
|
///
|
|
/// - Parameter left: A bit array.
|
|
/// - Parameter right: Another bit array of the same size.
|
|
/// - Complexity: O(left.count)
|
|
public static func |=(left: inout Self, right: Self) {
|
|
precondition(left.count == right.count)
|
|
left._update { target in
|
|
right._read { source in
|
|
for i in 0 ..< target._words.count {
|
|
target._mutableWords[i].formUnion(source._words[i])
|
|
}
|
|
}
|
|
}
|
|
left._checkInvariants()
|
|
}
|
|
|
|
/// Returns the result of performing a bitwise OR operation on two
|
|
/// equal-sized bit arrays.
|
|
///
|
|
/// - Parameter left: A bit array.
|
|
/// - Parameter right: Another bit array of the same size.
|
|
/// - Returns: The bitwise OR of `left` and `right`.
|
|
/// - Complexity: O(left.count)
|
|
public static func |(left: Self, right: Self) -> Self {
|
|
precondition(left.count == right.count)
|
|
var result = left
|
|
result |= right
|
|
return result
|
|
}
|
|
|
|
/// Stores the result of performing a bitwise AND operation on two given
|
|
/// equal-sized bit arrays in the left-hand-side variable.
|
|
///
|
|
/// - Parameter left: A bit array.
|
|
/// - Parameter right: Another bit array of the same size.
|
|
/// - Complexity: O(left.count)
|
|
public static func &=(left: inout Self, right: Self) {
|
|
precondition(left.count == right.count)
|
|
left._update { target in
|
|
right._read { source in
|
|
for i in 0 ..< target._words.count {
|
|
target._mutableWords[i].formIntersection(source._words[i])
|
|
}
|
|
}
|
|
}
|
|
left._checkInvariants()
|
|
}
|
|
|
|
/// Returns the result of performing a bitwise AND operation on two
|
|
/// equal-sized bit arrays.
|
|
///
|
|
/// - Parameter left: A bit array.
|
|
/// - Parameter right: Another bit array of the same size.
|
|
/// - Returns: The bitwise AND of `left` and `right`.
|
|
/// - Complexity: O(left.count)
|
|
public static func &(left: Self, right: Self) -> Self {
|
|
precondition(left.count == right.count)
|
|
var result = left
|
|
result &= right
|
|
return result
|
|
}
|
|
|
|
/// Stores the result of performing a bitwise XOR operation on two given
|
|
/// equal-sized bit arrays in the left-hand-side variable.
|
|
///
|
|
/// - Parameter left: A bit array.
|
|
/// - Parameter right: Another bit array of the same size.
|
|
/// - Complexity: O(left.count)
|
|
public static func ^=(left: inout Self, right: Self) {
|
|
precondition(left.count == right.count)
|
|
left._update { target in
|
|
right._read { source in
|
|
for i in 0 ..< target._words.count {
|
|
target._mutableWords[i].formSymmetricDifference(source._words[i])
|
|
}
|
|
}
|
|
}
|
|
left._checkInvariants()
|
|
}
|
|
|
|
/// Returns the result of performing a bitwise XOR operation on two
|
|
/// equal-sized bit arrays.
|
|
///
|
|
/// - Parameter left: A bit array.
|
|
/// - Parameter right: Another bit array of the same size.
|
|
/// - Returns: The bitwise XOR of `left` and `right`.
|
|
/// - Complexity: O(left.count)
|
|
public static func ^(left: Self, right: Self) -> Self {
|
|
precondition(left.count == right.count)
|
|
var result = left
|
|
result ^= right
|
|
return result
|
|
}
|
|
}
|
|
|
|
extension BitArray {
|
|
/// Returns the complement of the given bit array.
|
|
///
|
|
/// - Parameter value: A bit array.
|
|
/// - Returns: A bit array constructed by flipping each bit in `value`.
|
|
/// flipped.
|
|
/// - Complexity: O(value.count)
|
|
public static prefix func ~(value: Self) -> Self {
|
|
var result = value
|
|
result.toggleAll()
|
|
return result
|
|
}
|
|
}
|
|
#endif
|
|
|
|
extension BitArray {
|
|
public mutating func toggleAll() {
|
|
unsafe _update { handle in
|
|
let w = unsafe handle._mutableWords
|
|
for i in unsafe 0 ..< handle._words.count {
|
|
unsafe w[i].formComplement()
|
|
}
|
|
let p = handle.end
|
|
if p.bit > 0 {
|
|
unsafe w[p.word].subtract(_Word(upTo: p.bit).complement())
|
|
}
|
|
}
|
|
_checkInvariants()
|
|
}
|
|
|
|
public mutating func toggleAll(in range: Range<Int>) {
|
|
precondition(range.upperBound <= count, "Range out of bounds")
|
|
guard !range.isEmpty else { return }
|
|
unsafe _update { handle in
|
|
let words = unsafe handle._mutableWords
|
|
let start = _BitPosition(range.lowerBound)
|
|
let end = _BitPosition(range.upperBound)
|
|
if start.word == end.word {
|
|
let bits = _Word(from: start.bit, to: end.bit)
|
|
unsafe words[start.word].formSymmetricDifference(bits)
|
|
return
|
|
}
|
|
unsafe words[start.word].formSymmetricDifference(
|
|
_Word(upTo: start.bit).complement())
|
|
for i in stride(from: start.word + 1, to: end.word, by: 1) {
|
|
unsafe words[i].formComplement()
|
|
}
|
|
if end.bit > 0 {
|
|
unsafe words[end.word].formSymmetricDifference(_Word(upTo: end.bit))
|
|
}
|
|
}
|
|
}
|
|
|
|
@inlinable
|
|
public mutating func toggleAll(in range: some RangeExpression<Int>) {
|
|
toggleAll(in: range.relative(to: self))
|
|
}
|
|
}
|