Method PreviousValue

roaring.go:2235–2281

PreviousValue returns the previous largest value in the bitmap, or -1 if none is present. This function should not be used inside a performance-sensitive loop: prefer iterators if performance is a concern.

(target uint32)

// a performance-sensitive loop: prefer iterators if
// performance is a concern.
func (rb *Bitmap) PreviousValue(target uint32) int64 {
	if rb.IsEmpty() {
		return -1
	}

	originalKey := highbits(target)
	query := lowbits(target)
	var prevValue int64
	prevValue = -1
	containerIndex := rb.highlowcontainer.advanceUntil(originalKey, -1)

	if containerIndex == rb.highlowcontainer.size() {
		return int64(rb.Maximum())
	}

	if rb.highlowcontainer.getKeyAtIndex(containerIndex) > originalKey {
		// target absent, key of first container after target too high
		containerIndex--
	}

	for containerIndex != -1 && prevValue == -1 {
		containerKey := rb.highlowcontainer.getKeyAtIndex(containerIndex)
		container := rb.highlowcontainer.getContainer(containerKey)
		// if containerKey > originalKey then we are past the container which mapped to the original key
		// in that case we can just return the minimum from that container
		var responseBit int
		if containerKey < originalKey {
			bit, err := container.safeMaximum()

			if err == nil {
				responseBit = -1
			}
			responseBit = int(bit)
		} else {
			responseBit = container.previousValue(query)
		}

		if responseBit == -1 {
			prevValue = -1
		} else {
			prevValue = int64(combineLoHi32(uint32(responseBit), uint32(containerKey)))
		}
		containerIndex--
	}

	return prevValue
}

// NextAbsentValue returns the next largest missing value in the bitmap, or -1
// if none is present. This function should not be used inside