Function Concat

pkg/util/bitarray/bitarray.go:398–441

Concat concatenates two bit arrays.

(lhs, rhs BitArray)

// Concat concatenates two bit arrays.
func Concat(lhs, rhs BitArray) BitArray {
	if lhs.lastBitsUsed == 0 {
		return rhs
	}
	if rhs.lastBitsUsed == 0 {
		return lhs
	}
	words := make([]word, (lhs.nonEmptyBitLen()+rhs.nonEmptyBitLen()+numBitsPerWord-1)/numBitsPerWord)

	// The first bits come from the lhs unchanged.
	copy(words, lhs.words)
	var lastBitsUsed uint8
	if lhs.lastBitsUsed == numBitsPerWord {
		// Fast path. Just concatenate.
		copy(words[len(lhs.words):], rhs.words)
		lastBitsUsed = rhs.lastBitsUsed
	} else {
		// We need to shift all the words in the RHS
		// by the lastBitsUsed of the LHS.
		rhsShift := lhs.lastBitsUsed
		targetWordIdx := len(lhs.words) - 1
		trailingBits := words[targetWordIdx]
		for _, w := range rhs.words {
			headingBits := w >> rhsShift
			combinedBits := trailingBits | headingBits
			words[targetWordIdx] = combinedBits
			targetWordIdx++
			trailingBits = w << (numBitsPerWord - rhsShift)
		}
		lastBitsUsed = lhs.lastBitsUsed + rhs.lastBitsUsed
		if lastBitsUsed > numBitsPerWord {
			// Some bits from the RHS didn't fill a
			// word, we need to fit them in the last word.
			words[targetWordIdx] = trailingBits
		}

		// Compute the final thing.
		lastBitsUsed %= numBitsPerWord
		if lastBitsUsed == 0 {
			lastBitsUsed = numBitsPerWord
		}
	}
	return BitArray{words: words, lastBitsUsed: lastBitsUsed}
}

// Not computes the complement of a bit array.
func Not(d BitArray) BitArray {