Method Add

runcontainer.go:1021–1099

Add adds a single value k to the set.

(k uint16)

// Add adds a single value k to the set.
func (rc *runContainer16) Add(k uint16) (wasNew bool) {
	// TODO comment from runContainer16.java:
	// it might be better and simpler to do return
	// toBitmapOrArrayContainer(getCardinality()).add(k)
	// but note that some unit tests use this method to build up test
	// runcontainers without calling runOptimize

	k64 := int(k)

	index, present, _ := rc.search(k64)
	if present {
		return // already there
	}
	wasNew = true

	n := len(rc.iv)
	if index == -1 {
		// we may need to extend the first run
		if n > 0 {
			if rc.iv[0].start == k+1 {
				rc.iv[0].start = k
				rc.iv[0].length++
				return
			}
		}
		// nope, k stands alone, starting the new first interval16.
		rc.iv = append([]interval16{newInterval16Range(k, k)}, rc.iv...)
		return
	}

	// are we off the end? handle both index == n and index == n-1:
	if index >= n-1 {
		if int(rc.iv[n-1].last())+1 == k64 {
			rc.iv[n-1].length++
			return
		}
		rc.iv = append(rc.iv, newInterval16Range(k, k))
		return
	}

	// INVAR: index and index+1 both exist, and k goes between them.
	//
	// Now: add k into the middle,
	// possibly fusing with index or index+1 interval16
	// and possibly resulting in fusing of two interval16s
	// that had a one integer gap.

	left := index
	right := index + 1

	// are we fusing left and right by adding k?
	if int(rc.iv[left].last())+1 == k64 && int(rc.iv[right].start) == k64+1 {
		// fuse into left
		rc.iv[left].length = rc.iv[right].last() - rc.iv[left].start
		// remove redundant right
		rc.iv = append(rc.iv[:left+1], rc.iv[right+1:]...)
		return
	}