mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
109 lines
3.0 KiB
Swift
109 lines
3.0 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
|
|
|
|
@unsafe
|
|
internal struct _ChunkedBitsForwardIterator {
|
|
internal typealias _BitPosition = _UnsafeBitSet.Index
|
|
|
|
internal let words: UnsafeBufferPointer<_Word>
|
|
@safe
|
|
internal let end: _BitPosition
|
|
@safe
|
|
internal var position: _BitPosition
|
|
|
|
internal init(
|
|
words: UnsafeBufferPointer<_Word>,
|
|
range: Range<Int>
|
|
) {
|
|
assert(range.lowerBound >= 0)
|
|
assert(range.upperBound <= words.count * _Word.capacity)
|
|
unsafe 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 unsafe (
|
|
bits: words[w]
|
|
.intersection(_Word(upTo: end.bit))
|
|
.shiftedDown(by: b),
|
|
count: end.bit - b)
|
|
}
|
|
let c = _Word._capacity - b
|
|
position.value += c
|
|
return unsafe (bits: words[w].shiftedDown(by: b), count: c)
|
|
}
|
|
}
|
|
|
|
@unsafe
|
|
internal struct _ChunkedBitsBackwardIterator {
|
|
internal typealias _BitPosition = _UnsafeBitSet.Index
|
|
|
|
internal let words: UnsafeBufferPointer<_Word>
|
|
@safe
|
|
internal let start: _BitPosition
|
|
@safe
|
|
internal var position: _BitPosition
|
|
|
|
internal init(
|
|
words: UnsafeBufferPointer<_Word>,
|
|
range: Range<Int>
|
|
) {
|
|
assert(range.lowerBound >= 0)
|
|
assert(range.upperBound <= words.count * _Word.capacity)
|
|
unsafe 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 unsafe (
|
|
bits: words[w]
|
|
.intersection(_Word(upTo: b))
|
|
.shiftedDown(by: start.bit),
|
|
count: b - start.bit)
|
|
}
|
|
let c = b
|
|
position.value -= c
|
|
return unsafe (bits: words[w].intersection(_Word(upTo: b)), count: c)
|
|
}
|
|
}
|
|
|
|
extension IteratorProtocol where Element == Bool {
|
|
mutating func _nextChunk(
|
|
maxCount: UInt = _Word._capacity
|
|
) -> (bits: _Word, count: UInt) {
|
|
assert(maxCount <= _Word.capacity)
|
|
var bits = _Word.empty
|
|
var c: UInt = 0
|
|
while let v = next() {
|
|
if v { bits.insert(c) }
|
|
c += 1
|
|
if c == maxCount { break }
|
|
}
|
|
return (bits, c)
|
|
}
|
|
}
|