// intersectBitmapRun returns an array container if either container's
// cardinality is <= ArrayMaxSize. Otherwise it returns a bitmap container.
437102
func intersectBitmapRun(a, b *Container) *Container {
	statsHit("intersect/BitmapRun")
	var output *Container
	runs := b.runs()
	if b.n <= ArrayMaxSize || a.n <= ArrayMaxSize {
		// output is array container
		array := make([]uint16, 0, b.n)
		for _, iv := range runs {
			for i := iv.start; i <= iv.last; i++ {
				if a.bitmapContains(i) {
					array = append(array, i)
				}
				// If the run ends the container, break to avoid an infinite loop.
				if i == 65535 {
					break
				}
			}
		}

		output = NewContainerArray(array)
	} else {
		// right now this iterates through the runs and sets integers in the
		// bitmap that are in the runs. alternately, we could zero out ranges in
		// the bitmap which are between runs.
		output = NewContainerBitmap(0, nil)
		bitmap := output.bitmap()
		aBitmap := a.bitmap()
		for j := 0; j < len(runs); j++ {
			vb := runs[j]
			i := vb.start >> 6 // index into a
			vastart := i << 6
			valast := vastart + 63
			for valast >= vb.start && vastart <= vb.last && i < bitmapN {
				if vastart >= vb.start && valast <= vb.last { // a within b
					bitmap[i] = aBitmap[i]
					output.n += int32(popcount(aBitmap[i]))
				} else if vb.start >= vastart && vb.last <= valast { // b within a
					var mask uint64 = ((1 << (vb.last - vb.start + 1)) - 1) << (vb.start - vastart)
					bits := aBitmap[i] & mask
					bitmap[i] |= bits
					output.n += int32(popcount(bits))
				} else if vastart < vb.start { // a overlaps front of b
					offset := 64 - (1 + valast - vb.start)
					bits := (aBitmap[i] >> offset) << offset
					bitmap[i] |= bits
					output.n += int32(popcount(bits))
				} else if vb.start < vastart { // b overlaps front of a
					offset := 64 - (1 + vb.last - vastart)
					bits := (aBitmap[i] << offset) >> offset
					bitmap[i] |= bits
					output.n += int32(popcount(bits))
				}
				// update loop vars
				i++
				vastart = i << 6
				valast = vastart + 63
			}
		}
	}
	return output
}
714782
func (members Members) Intersect(otherMembers Members) Members {
	var res Members
	m := otherMembers.ByID()
	for _, member := range members {
		if _, exists := m[string(member.PKIid)]; exists {
			res = append(res, member)
		}
	}
	return res
}
1029870
func differenceRunBitmap(a, b *Container) *Container {
	statsHit("difference/RunBitmap")
	ra := a.runs()
	// If a is full, difference is the flip of b.
	if len(ra) > 0 && ra[0].start == 0 && ra[0].last == 65535 {
		return flipBitmap(b)
	}
	output := NewContainerRun(nil)
	runs := output.runs()
	if len(ra) == 0 {
		return NewContainerRun(nil)
	}
	output.n = a.n
	for _, inputRun := range ra {
		run := inputRun
		add := true
		for bit := inputRun.start; bit <= inputRun.last; bit++ {
			if b.bitmapContains(bit) {
				output.n--
				if run.start == bit {
					if bit == 65535 { //overflow
						add = false
					}

					run.start++
				} else if bit == run.last {
					run.last--
				} else {
					run.last = bit - 1
					if run.last >= run.start {
						runs = append(runs, run)
					}
					run.start = bit + 1
					run.last = inputRun.last
				}
				if run.start > run.last {
					break
				}
			}

			if bit == 65535 { //overflow
				break
			}
		}
		if run.start <= run.last {
			if add {
				runs = append(runs, run)
			}
		}
	}

	output.setRuns(runs)
	if output.n < ArrayMaxSize && int32(len(runs)) > output.n/2 {
		output.runToArray()
	} else if len(runs) > runMaxSize {
		output.runToBitmap()
	}
	return output
}
479889
func (c *Container) bitmapXorRange(i, j uint64) {
	x := i >> 6
	y := (j - 1) >> 6
	var X uint64 = maxBitmap << (i % 64)
	var Y uint64 = maxBitmap >> (63 - ((j - 1) % 64))
	bitmap := c.bitmap()
	if x == y {
		cnt := popcount(bitmap[x])
		bitmap[x] ^= (X & Y) //// flip
		c.n += int32(popcount(bitmap[x]) - cnt)
	} else {
		cnt := popcount(bitmap[x])
		bitmap[x] ^= X
		c.n += int32(popcount(bitmap[x]) - cnt)
		for i := x + 1; i < y; i++ {
			cnt = popcount(bitmap[i])
			bitmap[i] ^= maxBitmap
			c.n += int32(popcount(bitmap[i]) - cnt)
		}
		cnt = popcount(bitmap[y])
		bitmap[y] ^= Y
		c.n += int32(popcount(bitmap[y]) - cnt)
	}
}
1192770
func (b *Bound) Intersects(bound *Bound) bool {

	if (b.ne[0] < bound.sw[0]) ||
		(b.sw[0] > bound.ne[0]) ||
		(b.ne[1] < bound.sw[1]) ||
		(b.sw[1] > bound.ne[1]) {
		return false
	}

	return true
}
99997
func ParAnd(parallelism int, bitmaps ...*Bitmap) *Bitmap {
	bitmapCount := len(bitmaps)
	if bitmapCount == 0 {
		return NewBitmap()
	} else if bitmapCount == 1 {
		return bitmaps[0].Clone()
	}

	if parallelism == 0 {
		parallelism = defaultWorkerCount
	}

	h := newBitmapContainerHeap(bitmaps...)

	bitmapChan := make(chan *Bitmap)
	inputChan := make(chan multipleContainers, 128)
	resultChan := make(chan keyedContainer, 32)
	expectedKeysChan := make(chan int)

	andFunc := func() {
		// Assumes only structs with >=2 containers are passed
		for input := range inputChan {
			c := input.containers[0].and(input.containers[1])
			for _, next := range input.containers[2:] {
				if c.getCardinality() == 0 {
					break
				}
				c = c.iand(next)
			}

			// Send a nil explicitly if the result of the intersection is an empty container
			if c.getCardinality() == 0 {
				c = nil
			}

			kx := keyedContainer{
				input.key,
				c,
				input.idx,
			}
			resultChan <- kx
		}
	}

	go appenderRoutine(bitmapChan, resultChan, expectedKeysChan)

	for i := 0; i < parallelism; i++ {
		go andFunc()
	}

	idx := 0
	for h.Len() > 0 {
		ck := h.Next(make([]container, 0, 4))
		if len(ck.containers) == bitmapCount {
			ck.idx = idx
			inputChan <- ck
			idx++
		}
	}
	expectedKeysChan <- idx

	bitmap := <-bitmapChan

	close(inputChan)
	close(resultChan)
	close(expectedKeysChan)

	return bitmap
}
848842
func intersect(box orb.Bound, edge int, a, b orb.Point) orb.Point {
	if edge&8 != 0 {
		// top
		return orb.Point{a[0] + (b[0]-a[0])*(box.Max[1]-a[1])/(b[1]-a[1]), box.Max[1]}
	} else if edge&4 != 0 {
		// bottom
		return orb.Point{a[0] + (b[0]-a[0])*(box.Min[1]-a[1])/(b[1]-a[1]), box.Min[1]}
	} else if edge&2 != 0 {
		// right
		return orb.Point{box.Max[0], a[1] + (b[1]-a[1])*(box.Max[0]-a[0])/(b[0]-a[0])}
	} else if edge&1 != 0 {
		// left
		return orb.Point{box.Min[0], a[1] + (b[1]-a[1])*(box.Min[0]-a[0])/(b[0]-a[0])}
	}

	panic("no edge??")
}
1013295
func (p *PGeometry) Intersects(other *Geometry) (bool, error) {
	return p.predicate("intersects", cGEOSPreparedIntersects, other)
}
1168505
func PostingsIteratorFromBitmap(bm *roaring.Bitmap,
	includeFreqNorm, includeLocs bool) (*PostingsIterator, error) {
	return &PostingsIterator{
		ActualBM:        bm,
		Actual:          bm.Iterator(),
		includeFreqNorm: includeFreqNorm,
		includeLocs:     includeLocs,
	}, nil
}
955114
func (a *Rect) Intersect(b *Rect) (Rect, bool) {
	var result Rect

	if a == nil || b == nil {
		return result, false
	}

	// Special case for empty rects
	if a.Empty() || b.Empty() {
		result.W = 0
		result.H = 0
		return result, false
	}

	aMin := a.X
	aMax := aMin + a.W
	bMin := b.X
	bMax := bMin + b.W
	if bMin > aMin {
		aMin = bMin
	}
	result.X = aMin
	if bMax < aMax {
		aMax = bMax
	}
	result.W = aMax - aMin

	aMin = a.Y
	aMax = aMin + a.H
	bMin = b.Y
	bMax = bMin + b.H
	if bMin > aMin {
		aMin = bMin
	}
	result.Y = aMin
	if bMax < aMax {
		aMax = bMax
	}
	result.H = aMax - aMin

	return result, !result.Empty()
}
402328
func IntersectUint64Arr(arr [][]uint64) []uint64 {
	// create a map to count all the instances of the strings
	arrLength := len(arr)
	tempMap := make(map[uint64]int)
	for idx1 := range arr {
		tempArr := DistinctUint64(arr[idx1])
		for idx2 := range tempArr {
			// how many times have we encountered this elem?
			if _, ok := tempMap[tempArr[idx2]]; ok {
				tempMap[tempArr[idx2]]++
			} else {
				tempMap[tempArr[idx2]] = 1
			}
		}
	}

	// find the keys equal to the length of the input args
	tempArray := make([]uint64, 0)
	for key, val := range tempMap {
		if val == arrLength {
			tempArray = append(tempArray, key)
		}
	}

	return tempArray
}
1216431
func ToBitmapBytes(bit C.MMBitmapRef) []byte {
	var len C.size_t
	ptr := C.saveMMBitmapAsBytes(bit, &len)
	if int(len) < 0 {
		return nil
	}

	bs := C.GoBytes(unsafe.Pointer(ptr), C.int(len))
	C.free(unsafe.Pointer(ptr))
	return bs
}
552232
func ReadBitmap(bitmap C.MMBitmapRef) bool {
	abool := C.bitmap_ready(bitmap)
	gbool := bool(abool)
	return gbool
}
84192
func (c *Container) setBitmap(bitmap []uint64) {
	if roaringParanoia {
		if c.typ != containerBitmap {
			panic("attempt to write non-bitmap's bitmap")
		}
	}
	h := (*reflect.SliceHeader)(unsafe.Pointer(&bitmap))
	c.pointer, c.len, c.cap = (*uint16)(unsafe.Pointer(h.Data)), int32(h.Len), int32(h.Cap)
	runtime.KeepAlive(&bitmap)
}
985740
func unionBitmapBitmapInPlace(a, b *Container) {

	a.unmapBitmap()

	// local variables added to prevent BCE checks in loop
	// see https://go101.org/article/bounds-check-elimination.html
	var (
		ab = a.bitmap()[:bitmapN]
		bb = b.bitmap()[:bitmapN]
	)
	// Manually unroll loop to make it a little faster.
	// TODO(rartoul): Can probably make this a few x faster using
	// SIMD instructions.
	for i := 0; i < bitmapN; i += 4 {
		ab[i] |= bb[i]
		ab[i+1] |= bb[i+1]
		ab[i+2] |= bb[i+2]
		ab[i+3] |= bb[i+3]
	}
}
1066293
func (c *Container) bitmapToArray() {
	statsHit("bitmapToArray")
	bitmap := c.bitmap()
	c.setBitmap(nil)
	c.typ = containerArray
	c.mapped = false

	// return early if empty
	if c.n == 0 {
		c.setArray(nil)
		return
	}
	n := int32(0)

	array := make([]uint16, c.n)
	for i, word := range bitmap {
		for word != 0 {
			t := word & -word
			if roaringParanoia {
				if n >= c.n {
					panic("bitmap has more bits set than container.n")
				}
			}
			array[n] = uint16((i*64 + int(popcount(t-1))))
			n++
			word ^= t
		}
	}
	if roaringParanoia {
		if n != c.n {
			panic("bitmap has fewer bits set than container.n")
		}
	}
	c.setArray(array)
}
1074755
func (r Rect) Intersects(other Rect) bool {
	return r.Lat.Intersects(other.Lat) && r.Lng.Intersects(other.Lng)
}