Adding Stitching Methods to a Type
After establishing the basics of my packed-Boolean container type in Part 1, I’m going to add some methods I didn’t have in the prototype written in the Swift playground.
In the prototype, I wrote all the methods needed to satify Collection and its derived protocols (BidirectionalCollection, RandomAccessCollection, MutableCollection, and RangeReplaceableCollection). Most were easy. The general method to jump between index spans was hard because I couldn’t reuse the code for the single-step-forward/backward methods (and the general method is too heavy to reuse the other way). The hardest was replaceSubrange(_:, with:), the method that deals with changing the length of the array by adding/removing (and re-assigning) elements. Since the Boolean elements are packed within UInt elements, moving stuff involves bit-masks and shifting. The logic was hard to wrap around in my head, but I think I got it (mostly?) right.
When rethinking this code for the public type, I realized the operations of replaceSubrange(_:, with:), can be broken down in terms of splitting a container in two and/or joining two containers together. (The split/join doesn’t have to be between equal-length parts.) I would lose some efficiency since I’ll no longer be assigning elements in parts of the finished container that don’t need length adjustment, but the overall code should be easier to understand and debug. The replaceSubrange(_:, with:) would work like:
- Split off the prefix I’m keeping.
- Split off the suffix I’m keeping.
- Create another array for the incoming elements.
- Join the prefix and new array together.
- Join the prefix/new and suffix parts together. (The part of the old array between the prefix and suffix is thrown away.)
Before working on the joining and splitting methods, I need to identify which element of the word array holds the remnant bits, and how many words I’m storing before the remnant one:
extension BitArray { var remnantWordIndex: WordArray.Index? {
return remnantCount != 0 ? bits.index(before: bits.endIndex) : nil
} var wholeWordCount: WordArray.IndexDistance {
return bits.distance(from: bits.startIndex, to: remnantWordIndex ?? bits.endIndex)
} //...
}
I will start with inspecting and mutating the head of the container, in terms of the number of stored bits (not words). Since the words are stored the same way as reading them from a higher-order-bits-first external array, I can reuse the code from the master initializer (after a sanity check):
{
//... func head(bitCount: Int) -> BitArray {
let (bq, br) = bitCount.quotientAndRemainder(dividingBy: Word.bitWidth)
precondition((bq, br) <= (wholeWordCount, remnantCount)) return BitArray(coreWords: bits, bitCount: bitCount, bitIterationDirection: .hi2lo)
} //...
}
(I renamed the first parameter for the master initializer, because I’ll use the old signature when making a public Sequence-of-words initializer.)
Adding or removing elements from the beginning of the array is much harder. For removal, I break down the number of elements to eliminate into whole words and a remnant count. I remove the whole words. For the remnant, I have to shift the retained bits to the high-order positions and fill in the low postitions with the high-order bits from the following word. This has to cascade to all the following words. Then I have to calcuate the new remnant marker and remove the last word if it held a remnant but enough bits were shifted up to eliminate its need.
{
//... mutating func truncateHead(bitCount: Int) {
let (bq, br) = bitCount.quotientAndRemainder(dividingBy: Word.bitWidth)
precondition(bitCount >= 0)
precondition((bq, br) <= (wholeWordCount, remnantCount)) bits.removeFirst(bq) var pushedOutBits: Word = 0
for i in bits.indices.reversed() {
pushedOutBits = bits[i].pushLowOrderBits(fromHighOrderBitsOf: pushedOutBits, count: br)
} let hadRemnant = remnantCount != 0
remnantCount -= br
if remnantCount <= 0 {
if hadRemnant {
let extraneousWord = bits.removeLast()
assert(extraneousWord == 0)
} else {
assert((remnantCount < 0) == (br > 0))
}
if remnantCount < 0 {
remnantCount += Word.bitWidth
}
}
} //...
}
For insertion, I figure out if the incoming and receiving arrays’ remnants would add up to a new word, and insert a zero-value word at the end. Then I would shift in the remnant of the incoming array to the high-order-bit end of the first receiver word, and shift down the pushed-out bits to the following word, down to the new word. Then the incoming array’s whole words can be prepended and the remnant count recalculated.
{
//... mutating func prependHead(_ head: BitArray) {
guard !head.bits.isEmpty else { return }
guard !bits.isEmpty else {
bits.replaceSubrange(bits.startIndex..., with: head.bits)
remnantCount = head.remnantCount
return
} if let hrwi = head.remnantWordIndex {
assert(head.remnantCount > 0)
if remnantCount == 0 || head.remnantCount + remnantCount > Word.bitWidth {
bits.append(0)
} var pushedOutBits = head.bits[hrwi] >> (Word.bitWidth - head.remnantCount)
for i in bits.indices {
pushedOutBits = bits[i].pushHighOrderBits(fromLowOrderBitsOf: pushedOutBits, count: head.remnantCount)
}
remnantCount += head.remnantCount
remnantCount %= Word.bitWidth
} else {
assert(head.remnantCount == 0)
} bits.insert(contentsOf: head.bits.prefix(head.wholeWordCount), at: bits.startIndex)
} //...
}
For the operations on the tail end, the inspection and insertion methods can be written in terms of using the head versions on copies. The removal method has to be new: find where the new remnant word will be and remove all words after that, then zero-out all the bits after the remnant prefix length.
{
//... func tail(bitCount: Int) -> BitArray {
let count = wholeWordCount * Word.bitWidth + remnantCount
var copy = self
copy.truncateHead(bitCount: count - bitCount)
return copy
} mutating func truncateTail(bitCount: Int) {
let count = wholeWordCount * Word.bitWidth + remnantCount
precondition(0...count ~= bitCount) let headCount = count - bitCount
let (hq, hr) = headCount.quotientAndRemainder(dividingBy: Word.bitWidth)
var truncationIndex = bits.index(bits.startIndex, offsetBy: hq)
if hr != 0 {
assert(truncationIndex < bits.endIndex)
bits[truncationIndex] &= Word.highOrderBitsMask(count: hr)
truncationIndex = bits.index(after: truncationIndex)
}
bits.removeSubrange(truncationIndex...)
remnantCount = hr
} mutating func appendTail(_ tail: BitArray) {
var copy = tail
copy.prependHead(self)
bits.replaceSubrange(bits.startIndex..., with: copy.bits)
remnantCount = copy.remnantCount
}}
Hopefully, the way I carried out appendTail(_:) means that the internal word array and its capacity to store new words is kept.
Shifting in bits into a word from another word, and keeping the ejected bits for the next round, are carried out in more custom extensions to the System Library integer types:
extension BinaryInteger { //... @discardableResult
mutating func replaceBits(with source: Self, forOnly mask: Self) -> Self {
defer {
self &= ~mask
self |= source & mask
} return self & mask
}}extension FixedWidthInteger { //... mutating func pushLowOrderBits(fromHighOrderBitsOf source: Self, count: Int) -> Self {
switch count {
case bitWidth:
defer { self = source }
return self
case 1..<bitWidth:
defer {
self <<= count
replaceBits(with: source >> (bitWidth - count), forOnly: Self.lowOrderBitsMask(count: count))
}
return self & Self.highOrderBitsMask(count: count)
case 0:
return 0
default:
preconditionFailure("Illegal replacing bit-width used")
}
} mutating func pushHighOrderBits(fromLowOrderBitsOf source: Self, count: Int) -> Self {
switch count {
case bitWidth:
defer { self = source }
return self
case 1..<bitWidth:
defer {
self >>= count
replaceBits(with: source << (bitWidth - count), forOnly: Self.highOrderBitsMask(count: count))
}
return self & Self.lowOrderBitsMask(count: count)
case 0:
return 0
default:
preconditionFailure("Illegal replacing bit-width used")
}
}}
The @discardableResult attribute allows a properly-returning function to be used optionally like a Void-returning function; for using the function just for its side effects without caring about the proper result. (The printf and scanf functions from C are examples of functions that are more like procedures with a return result that is only occasionally useful.) There wasn’t a need to add a result to replaceBits(with: forOnly:); I just over-engineered it to allow the user to keep the old value around for a switch-back.
