Files
swift-collections/Sources/BitCollections/BitArray/BitArray+ChunkedBitsIterators.swift

103 lines
2.9 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
internal struct _ChunkedBitsForwardIterator {
internal typealias _BitPosition = _UnsafeBitSet.Index
internal let words: UnsafeBufferPointer<_Word>
internal let end: _BitPosition
internal var position: _BitPosition
internal init(
words: UnsafeBufferPointer<_Word>,
range: Range<Int>
) {
assert(range.lowerBound >= 0)
assert(range.upperBound <= words.count * _Word.capacity)
self.words = words
self.end = _BitPosition(range.upperBound)
self.position = _BitPosition(range.lowerBound)
}
mutating func next() -> (bits: _Word, count: UInt)? {
guard position < end else { return nil }
let (w, b) = position.split
if w == end.word {
position = end
return (
bits: words[w]
.intersection(_Word(upTo: end.bit))
.shiftedDown(by: b),
count: end.bit - b)
}
let c = _Word._capacity - b
position.value += c
return (bits: words[w].shiftedDown(by: b), count: c)
}
}
internal struct _ChunkedBitsBackwardIterator {
internal typealias _BitPosition = _UnsafeBitSet.Index
internal let words: UnsafeBufferPointer<_Word>
internal let start: _BitPosition
internal var position: _BitPosition
internal init(
words: UnsafeBufferPointer<_Word>,
range: Range<Int>
) {
assert(range.lowerBound >= 0)
assert(range.upperBound <= words.count * _Word.capacity)
self.words = words
self.start = _BitPosition(range.lowerBound)
self.position = _BitPosition(range.upperBound)
}
internal mutating func next() -> (bits: _Word, count: UInt)? {
guard position > start else { return nil }
let (w, b) = position.endSplit
if w == start.word {
position = start
return (
bits: words[w]
.intersection(_Word(upTo: b))
.shiftedDown(by: start.bit),
count: b - start.bit)
}
let c = b
position.value -= c
return (bits: words[w].intersection(_Word(upTo: b)), count: c)
}
}
extension IteratorProtocol where Element == Bool {
mutating func _nextChunk(
maximumCount: UInt = _Word._capacity
) -> (bits: _Word, count: UInt) {
assert(maximumCount <= _Word.capacity)
var bits = _Word.empty
var c: UInt = 0
while let v = next() {
if v { bits.insert(c) }
c += 1
if c == maximumCount { break }
}
return (bits, c)
}
}