Function Flip

roaring.go:2113–2164

Flip negates the bits in the given range (i.e., [rangeStart,rangeEnd)), any integer present in this range and in the bitmap is removed, and any integer present in the range and not in the bitmap is added, a new bitmap is returned leaving the current bitmap unchanged. The function uses 64-bit parame

(bm *Bitmap, rangeStart, rangeEnd uint64)

// The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range
// while uint64(0x100000000) cannot be represented as a 32-bit value.
func Flip(bm *Bitmap, rangeStart, rangeEnd uint64) *Bitmap {
	if rangeStart >= rangeEnd {
		return bm.Clone()
	}

	if rangeStart > MaxUint32 {
		panic("rangeStart > MaxUint32")
	}
	if rangeEnd-1 > MaxUint32 {
		panic("rangeEnd-1 > MaxUint32")
	}

	answer := NewBitmap()
	hbStart := uint32(highbits(uint32(rangeStart)))
	lbStart := uint32(lowbits(uint32(rangeStart)))
	hbLast := uint32(highbits(uint32(rangeEnd - 1)))
	lbLast := uint32(lowbits(uint32(rangeEnd - 1)))

	// copy the containers before the active area
	answer.highlowcontainer.appendCopiesUntil(bm.highlowcontainer, uint16(hbStart))

	var max uint32 = maxLowBit
	for hb := hbStart; hb <= hbLast; hb++ {
		var containerStart uint32
		if hb == hbStart {
			containerStart = lbStart
		}
		containerLast := max
		if hb == hbLast {
			containerLast = lbLast
		}

		i := bm.highlowcontainer.getIndex(uint16(hb))
		j := answer.highlowcontainer.getIndex(uint16(hb))

		if i >= 0 {
			c := bm.highlowcontainer.getContainerAtIndex(i).not(int(containerStart), int(containerLast)+1)
			if !c.isEmpty() {
				answer.highlowcontainer.insertNewKeyValueAt(-j-1, uint16(hb), c)
			}

		} else { // *think* the range of ones must never be
			// empty.
			answer.highlowcontainer.insertNewKeyValueAt(-j-1, uint16(hb),
				rangeOfOnes(int(containerStart), int(containerLast)))
		}
	}
	// copy the containers after the active area.
	answer.highlowcontainer.appendCopiesAfter(bm.highlowcontainer, uint16(hbLast))

	return answer
}

// SetCopyOnWrite sets this bitmap to use copy-on-write so that copies are fast and memory conscious
// if the parameter is true, otherwise we leave the default where hard copies are made