mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
`maskingShiftLeft(by:)`, `maskingShiftRight(by:)` and `resizingShiftLeft(by:)` handle a negative amount by negating it and shifting the other way, so `Int.min` trapped with an arithmetic overflow. All three have a defined result for it: an amount of at least `count` clears or removes every value, which is what `Int.min + 1` already did. Clamp the magnitude of a negative amount to `Int.max` in these three. `resizingShiftRight(by:)` is left alone: a negative amount inserts values there, and no array can hold as many as `Int.min` asks for. The masking shifts had no tests. Add tests for both of them over word-crossing counts and amounts on either side of `count`, for their doc examples, and for the extreme amounts. Co-Authored-By: Claude Fable 5.2 <noreply@anthropic.com>
182 lines
6.2 KiB
Swift
182 lines
6.2 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
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
extension BitArray {
|
|
/// Returns the magnitude of a negative shift amount.
|
|
///
|
|
/// `Int.min` has no positive counterpart, so it is clamped to `Int.max`.
|
|
/// This only suits shifts that discard values: those treat every amount
|
|
/// that is at least `count` the same way.
|
|
@inline(__always)
|
|
internal static func _magnitude(ofNegativeShift amount: Int) -> Int {
|
|
assert(amount < 0)
|
|
return Int(clamping: amount.magnitude)
|
|
}
|
|
}
|
|
|
|
extension BitArray {
|
|
/// Shift the bits in this array by the specified number of places to the
|
|
/// left (towards the end of the array), by inserting `amount` false values
|
|
/// at the beginning.
|
|
///
|
|
/// If `amount` is negative, this is equivalent to shifting `-amount`
|
|
/// places to the right.
|
|
///
|
|
/// var bits: BitArray = "1110110"
|
|
/// bits.resizingShiftLeft(by: 2)
|
|
/// // bits is now 111011000
|
|
/// bits.resizingShiftLeft(by: -4)
|
|
/// // bits is now 11101
|
|
/// bits.resizingShiftLeft(by: 8)
|
|
/// // bits is now 1110100000000
|
|
public mutating func resizingShiftLeft(by amount: Int) {
|
|
guard amount != 0 else { return }
|
|
if amount > 0 {
|
|
_resizingShiftLeft(by: amount)
|
|
} else {
|
|
_resizingShiftRight(by: Self._magnitude(ofNegativeShift: amount))
|
|
}
|
|
}
|
|
|
|
/// Shift the bits in this array by the specified number of places to the
|
|
/// right (towards the start of the array), by removing `amount` existing
|
|
/// values from the front of the array.
|
|
///
|
|
/// If `amount` is negative, then this is equivalent to shifting `-amount`
|
|
/// places to the left. If amount is greater than or equal to `count`,
|
|
/// then the resulting bit array will be empty.
|
|
///
|
|
/// var bits: BitArray = "1110110"
|
|
/// bits.resizingShiftRight(by: 2)
|
|
/// // bits is now 11101
|
|
/// bits.resizingShiftRight(by: -4)
|
|
/// // bits is now 111010000
|
|
/// bits.resizingShiftRight(by: 10)
|
|
/// // bits is now empty
|
|
///
|
|
/// If `amount` is between 0 and `count`, then this has the same effect as
|
|
/// `removeFirst(amount)`.
|
|
public mutating func resizingShiftRight(by amount: Int) {
|
|
guard amount != 0 else { return }
|
|
if amount > 0 {
|
|
_resizingShiftRight(by: amount)
|
|
} else {
|
|
// This direction inserts values, so `Int.min` cannot be clamped: no
|
|
// array can hold as many values as it asks for, and the negation traps.
|
|
_resizingShiftLeft(by: -amount)
|
|
}
|
|
}
|
|
|
|
internal mutating func _resizingShiftLeft(by amount: Int) {
|
|
assert(amount > 0)
|
|
_extend(by: amount, with: false)
|
|
maskingShiftLeft(by: amount)
|
|
}
|
|
|
|
internal mutating func _resizingShiftRight(by amount: Int) {
|
|
assert(amount > 0)
|
|
guard amount < count else {
|
|
self = .init()
|
|
return
|
|
}
|
|
self._copy(from: unsafe Range(uncheckedBounds: (amount, count)), to: 0)
|
|
self._removeLast(amount)
|
|
}
|
|
}
|
|
|
|
extension BitArray {
|
|
// FIXME: Add maskingShiftRight(by:in:) and maskingShiftLeft(by:in:) for shifting slices.
|
|
|
|
/// Shift the bits in this array by the specified number of places to the
|
|
/// left (towards the end of the array), without changing
|
|
/// its count.
|
|
///
|
|
/// Values that are shifted off the array are discarded. Values that are
|
|
/// shifted in are all set to false.
|
|
///
|
|
/// If `amount` is negative, this is equivalent to shifting `-amount`
|
|
/// places to the right. If `amount` is greater than or equal to `count`,
|
|
/// then all values are set to false.
|
|
///
|
|
/// var bits: BitArray = "1110110"
|
|
/// bits.maskingShiftLeft(by: 2)
|
|
/// // bits is now 1011000
|
|
/// bits.maskingShiftLeft(by: -4)
|
|
/// // bits is now 0000101
|
|
/// bits.maskingShiftLeft(by: 8)
|
|
/// // bits is now 0000000
|
|
public mutating func maskingShiftLeft(by amount: Int) {
|
|
guard amount != 0 else { return }
|
|
unsafe _update {
|
|
if amount > 0 {
|
|
unsafe $0._maskingShiftLeft(by: amount)
|
|
} else {
|
|
unsafe $0._maskingShiftRight(
|
|
by: BitArray._magnitude(ofNegativeShift: amount))
|
|
}
|
|
}
|
|
}
|
|
|
|
/// Shift the bits in this array by the specified number of places to the
|
|
/// right (towards the beginning of the array), without changing
|
|
/// its count.
|
|
///
|
|
/// Values that are shifted off the array are discarded. Values that are
|
|
/// shifted in are all set to false.
|
|
///
|
|
/// If `amount` is negative, this is equivalent to shifting `-amount`
|
|
/// places to the left. If `amount` is greater than or equal to `count`,
|
|
/// then all values are set to false.
|
|
///
|
|
/// var bits: BitArray = "1110110"
|
|
/// bits.maskingShiftRight(by: 2)
|
|
/// // bits is now 0011101
|
|
/// bits.maskingShiftRight(by: -3)
|
|
/// // bits is now 1101000
|
|
/// bits.maskingShiftRight(by: 8)
|
|
/// // bits is now 0000000
|
|
public mutating func maskingShiftRight(by amount: Int) {
|
|
guard amount != 0 else { return }
|
|
unsafe _update {
|
|
if amount > 0 {
|
|
unsafe $0._maskingShiftRight(by: amount)
|
|
} else {
|
|
unsafe $0._maskingShiftLeft(
|
|
by: BitArray._magnitude(ofNegativeShift: amount))
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
extension BitArray._UnsafeHandle {
|
|
internal mutating func _maskingShiftLeft(by amount: Int) {
|
|
assert(amount > 0)
|
|
let d = Swift.min(amount, self.count)
|
|
if d == amount {
|
|
let range = unsafe Range(uncheckedBounds: (0, self.count &- d))
|
|
unsafe self.copy(from: range, to: d)
|
|
}
|
|
unsafe self.clear(in: Range(uncheckedBounds: (0, d)))
|
|
}
|
|
|
|
internal mutating func _maskingShiftRight(by amount: Int) {
|
|
assert(amount > 0)
|
|
let d = Swift.min(amount, self.count)
|
|
if d == amount {
|
|
let range = unsafe Range(uncheckedBounds: (d, self.count))
|
|
unsafe self.copy(from: range, to: 0)
|
|
}
|
|
unsafe self.clear(in: Range(uncheckedBounds: (self.count &- d, self.count)))
|
|
}
|
|
}
|