Function andSparseWithSparseBitArray

bitarray/and.go:19–71

(sba, other *sparseBitArray)

package bitarray

func andSparseWithSparseBitArray(sba, other *sparseBitArray) BitArray {
	max := maxInt64(int64(len(sba.indices)), int64(len(other.indices)))
	indices := make(uintSlice, 0, max)
	blocks := make(blocks, 0, max)

	selfIndex := 0
	otherIndex := 0
	var resultBlock block

	// move through the array and compare the blocks if they happen to
	// intersect
	for {
		if selfIndex == len(sba.indices) || otherIndex == len(other.indices) {
			// One of the arrays has been exhausted. We don't need
			// to compare anything else for a bitwise and; the
			// operation is complete.
			break
		}

		selfValue := sba.indices[selfIndex]
		otherValue := other.indices[otherIndex]

		switch {
		case otherValue < selfValue:
			// The `sba` bitarray has a block with a index position
			// greater than us. We want to compare with that block
			// if possible, so move our `other` index closer to that
			// block's index.
			otherIndex++

		case otherValue > selfValue:
			// This is the exact logical inverse of the above case.
			selfIndex++

		default:
			// Here, our indices match for both `sba` and `other`.
			// Time to do the bitwise AND operation and add a block
			// to our result list if the block has values in it.
			resultBlock = sba.blocks[selfIndex].and(other.blocks[otherIndex])
			if resultBlock > 0 {
				indices = append(indices, selfValue)
				blocks = append(blocks, resultBlock)
			}
			selfIndex++
			otherIndex++
		}
	}

	return &sparseBitArray{
		indices: indices,
		blocks:  blocks,
	}
}

func andSparseWithDenseBitArray(sba *sparseBitArray, other *bitArray) BitArray {
	if other.IsEmpty() {