// unions array b into bitmap a, mutating a in place. The n value
// of a will need to be repaired after the fact.
490971
func unionBitmapArrayInPlace(a, b *Container) {
	a.unmapBitmap()
	bitmap := a.bitmap()
	for _, v := range b.array() {
		bitmap[v>>6] |= (uint64(1) << (v % 64))
	}
}
306618
func (s *SeriesIDSet) Merge(others ...*SeriesIDSet) {
	bms := make([]*roaring.Bitmap, 0, len(others)+1)

	s.RLock()
	bms = append(bms, s.bitmap) // Add ourself.

	// Add other bitsets.
	for _, other := range others {
		other.RLock()
		defer other.RUnlock() // Hold until we have merged all the bitmaps
		bms = append(bms, other.bitmap)
	}

	result := roaring.FastOr(bms...)
	s.RUnlock()

	s.Lock()
	s.bitmap = result
	s.Unlock()
}
281979
func (r Rect) Union(other Rect) Rect {
	return Rect{r.X.Union(other.X), r.Y.Union(other.Y)}
}
1197542
func Union(a, b [][]byte) [][]byte {
	n := len(b)
	if len(a) > len(b) {
		n = len(a)
	}
	other := make([][]byte, 0, n)

	for {
		if len(a) > 0 && len(b) > 0 {
			if cmp := bytes.Compare(a[0], b[0]); cmp == 0 {
				other, a, b = append(other, a[0]), a[1:], b[1:]
			} else if cmp == -1 {
				other, a = append(other, a[0]), a[1:]
			} else {
				other, b = append(other, b[0]), b[1:]
			}
		} else if len(a) > 0 {
			other, a = append(other, a[0]), a[1:]
		} else if len(b) > 0 {
			other, b = append(other, b[0]), b[1:]
		} else {
			return other
		}
	}
}
612740
func insertionSort(data []int, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && data[j] < data[j-1]; j-- {
			data[j], data[j-1] = data[j-1], data[j]
		}
	}
}
365032
func (rb *Bitmap) Xor(x2 *Bitmap) {
	pos1 := 0
	pos2 := 0
	length1 := rb.highlowcontainer.size()
	length2 := x2.highlowcontainer.size()
	for {
		if (pos1 < length1) && (pos2 < length2) {
			s1 := rb.highlowcontainer.getKeyAtIndex(pos1)
			s2 := x2.highlowcontainer.getKeyAtIndex(pos2)
			if s1 < s2 {
				pos1 = rb.highlowcontainer.advanceUntil(s2, pos1)
				if pos1 == length1 {
					break
				}
			} else if s1 > s2 {
				c := x2.highlowcontainer.getWritableContainerAtIndex(pos2)
				rb.highlowcontainer.insertNewKeyValueAt(pos1, x2.highlowcontainer.getKeyAtIndex(pos2), c)
				length1++
				pos1++
				pos2++
			} else {
				// TODO: couple be computed in-place for reduced memory usage
				c := rb.highlowcontainer.getContainerAtIndex(pos1).xor(x2.highlowcontainer.getContainerAtIndex(pos2))
				if c.getCardinality() > 0 {
					rb.highlowcontainer.setContainerAtIndex(pos1, c)
					pos1++
				} else {
					rb.highlowcontainer.removeAtIndex(pos1)
					length1--
				}
				pos2++
			}
		} else {
			break
		}
	}
	if pos1 == length1 {
		rb.highlowcontainer.appendCopyMany(x2.highlowcontainer, pos2, length2)
	}
}
63529
func NewBitmap(bytes []byte) *Bitmap {
	var numBytes = len(bytes)
	var storeSize = sizeRequired(numBytes, bytesPerBlock)
	var s = make([]Block, 0, storeSize)

	var buf Block
	var hasPartialBuf bool
	var lastM = bytesPerBlock - 1
	for i, b := range bytes {
		var m = i % bytesPerBlock
		buf |= Block(b) << uint(bitsPerBlock-(m+1)*bitsPerByte)
		if lastM == m {
			s = append(s, buf)
			buf = 0
			hasPartialBuf = false
		} else {
			hasPartialBuf = true
		}
	}
	if hasPartialBuf {
		s = append(s, buf)
	}
	return &Bitmap{size: numBytes * bitsPerByte, store: s}
}
977569
func (rb *Bitmap) Or(x2 *Bitmap) {
	pos1 := 0
	pos2 := 0
	length1 := rb.highlowcontainer.size()
	length2 := x2.highlowcontainer.size()
main:
	for (pos1 < length1) && (pos2 < length2) {
		s1 := rb.highlowcontainer.getKeyAtIndex(pos1)
		s2 := x2.highlowcontainer.getKeyAtIndex(pos2)

		for {
			if s1 < s2 {
				pos1++
				if pos1 == length1 {
					break main
				}
				s1 = rb.highlowcontainer.getKeyAtIndex(pos1)
			} else if s1 > s2 {
				rb.highlowcontainer.insertNewKeyValueAt(pos1, s2, x2.highlowcontainer.getContainerAtIndex(pos2).clone())
				pos1++
				length1++
				pos2++
				if pos2 == length2 {
					break main
				}
				s2 = x2.highlowcontainer.getKeyAtIndex(pos2)
			} else {
				rb.highlowcontainer.replaceKeyAndContainerAtIndex(pos1, s1, rb.highlowcontainer.getWritableContainerAtIndex(pos1).ior(x2.highlowcontainer.getContainerAtIndex(pos2)), false)
				pos1++
				pos2++
				if (pos1 == length1) || (pos2 == length2) {
					break main
				}
				s1 = rb.highlowcontainer.getKeyAtIndex(pos1)
				s2 = x2.highlowcontainer.getKeyAtIndex(pos2)
			}
		}
	}
	if pos1 == length1 {
		rb.highlowcontainer.appendCopyMany(x2.highlowcontainer, pos2, length2)
	}
}
1053429
func UnionStringArr(arr [][]string) []string {
	// create a temporary map to hold the contents of the arrays
	tempMap := make(map[string]uint8)

	// write the contents of the arrays as keys to the map. The map values don't matter
	for idx1 := range arr {
		for idx2 := range arr[idx1] {
			tempMap[arr[idx1][idx2]] = 0
		}
	}

	// the map keys are now unique instances of all of the array contents
	tempArray := make([]string, 0)
	for key := range tempMap {
		tempArray = append(tempArray, key)
	}

	return tempArray
}
373564
func unionArrayRun(a, b *Container) *Container {
	statsHit("union/ArrayRun")
	if b.n == maxContainerVal+1 {
		return b.Clone()
	}
	output := NewContainerRun(nil)
	aa, rb := a.array(), b.runs()
	na, nb := len(aa), len(rb)
	var vb interval16
	var va uint16
	for i, j := 0, 0; i < na || j < nb; {
		if i < na {
			va = aa[i]
		}
		if j < nb {
			vb = rb[j]
		}
		if i < na && (j >= nb || va < vb.start) {
			output.n += output.runAppendInterval(interval16{start: va, last: va})
			i++
		} else {
			output.n += output.runAppendInterval(vb)
			j++
		}
	}
	if output.n < ArrayMaxSize {
		output.runToArray()
	} else if len(output.runs()) > runMaxSize {
		output.runToBitmap()
	}
	return output
}
627874
func (s1 Byte) Union(s2 Byte) Byte {
	result := NewByte()
	for key := range s1 {
		result.Insert(key)
	}
	for key := range s2 {
		result.Insert(key)
	}
	return result
}
807295
func (a *BooleanArray) Merge(b *BooleanArray) {
	if a.Len() == 0 {
		*a = *b
		return
	}

	if b.Len() == 0 {
		return
	}

	// Normally, both a and b should not contain duplicates.  Due to a bug in older versions, it's
	// possible stored blocks might contain duplicate values.  Remove them if they exists before
	// merging.
	// a = a.Deduplicate()
	// b = b.Deduplicate()

	if a.MaxTime() < b.MinTime() {
		a.Timestamps = append(a.Timestamps, b.Timestamps...)
		a.Values = append(a.Values, b.Values...)
		return
	}

	if b.MaxTime() < a.MinTime() {
		var tmp BooleanArray
		tmp.Timestamps = append(b.Timestamps, a.Timestamps...)
		tmp.Values = append(b.Values, a.Values...)
		*a = tmp
		return
	}

	out := NewBooleanArrayLen(a.Len() + b.Len())
	i, j, k := 0, 0, 0
	for i < len(a.Timestamps) && j < len(b.Timestamps) {
		if a.Timestamps[i] < b.Timestamps[j] {
			out.Timestamps[k] = a.Timestamps[i]
			out.Values[k] = a.Values[i]
			i++
		} else if a.Timestamps[i] == b.Timestamps[j] {
			out.Timestamps[k] = b.Timestamps[j]
			out.Values[k] = b.Values[j]
			i++
			j++
		} else {
			out.Timestamps[k] = b.Timestamps[j]
			out.Values[k] = b.Values[j]
			j++
		}
		k++
	}

	if i < len(a.Timestamps) {
		n := copy(out.Timestamps[k:], a.Timestamps[i:])
		copy(out.Values[k:], a.Values[i:])
		k += n
	} else if j < len(b.Timestamps) {
		n := copy(out.Timestamps[k:], b.Timestamps[j:])
		copy(out.Values[k:], b.Values[j:])
		k += n
	}

	a.Timestamps = out.Timestamps[:k]
	a.Values = out.Values[:k]
}
264528
func (b Bound) Union(other Bound) Bound {
	if other.IsEmpty() {
		return b
	}

	b = b.Extend(other.Min)
	b = b.Extend(other.Max)
	b = b.Extend(other.LeftTop())
	b = b.Extend(other.RightBottom())

	return b
}
147886
func Intersect(a, b [][]byte) [][]byte {
	n := len(b)
	if len(a) > len(b) {
		n = len(a)
	}
	other := make([][]byte, 0, n)

	for len(a) > 0 && len(b) > 0 {
		if cmp := bytes.Compare(a[0], b[0]); cmp == 0 {
			other, a, b = append(other, a[0]), a[1:], b[1:]
		} else if cmp == -1 {
			a = a[1:]
		} else {
			b = b[1:]
		}
	}
	return other
}
16117
func (b *Bitmap) Add(a ...uint64) (changed bool, err error) {
	changed = false
	for _, v := range a {
		// Create an add operation.
		op := &op{typ: opTypeAdd, value: v}

		// Write operation to op log.
		if err := b.writeOp(op); err != nil {
			return false, err
		}

		// Apply to the in-memory bitmap.
		if b.DirectAdd(v) {
			changed = true
		}
	}

	return changed, nil
}
796704
func UnionString(args ...[]string) []string {
	// create a temporary map to hold the contents of the arrays
	tempMap := make(map[string]uint8)

	// write the contents of the arrays as keys to the map. The map values don't matter
	for _, arg := range args {
		for idx := range arg {
			tempMap[arg[idx]] = 0
		}
	}

	// the map keys are now unique instances of all of the array contents
	tempArray := make([]string, 0)
	for key := range tempMap {
		tempArray = append(tempArray, key)
	}

	return tempArray
}
664251
func (rb *Bitmap) Clone() *Bitmap {
	ptr := new(Bitmap)
	ptr.highlowcontainer = *rb.highlowcontainer.clone()
	return ptr
}