// Intersects checks whether two bitmap intersects, bitmaps are not modified
762300
func (rb *Bitmap) Intersects(x2 *Bitmap) bool {
	pos1 := 0
	pos2 := 0
	length1 := rb.highlowcontainer.size()
	length2 := x2.highlowcontainer.size()

main:
	for {
		if pos1 < length1 && pos2 < length2 {
			s1 := rb.highlowcontainer.getKeyAtIndex(pos1)
			s2 := x2.highlowcontainer.getKeyAtIndex(pos2)
			for {
				if s1 == s2 {
					c1 := rb.highlowcontainer.getContainerAtIndex(pos1)
					c2 := x2.highlowcontainer.getContainerAtIndex(pos2)
					if c1.intersects(c2) {
						return true
					}
					pos1++
					pos2++
					if (pos1 == length1) || (pos2 == length2) {
						break main
					}
					s1 = rb.highlowcontainer.getKeyAtIndex(pos1)
					s2 = x2.highlowcontainer.getKeyAtIndex(pos2)
				} else if s1 < s2 {
					pos1 = rb.highlowcontainer.advanceUntil(s2, pos1)
					if pos1 == length1 {
						break main
					}
					s1 = rb.highlowcontainer.getKeyAtIndex(pos1)
				} else { //s1 > s2
					pos2 = x2.highlowcontainer.advanceUntil(s1, pos2)
					if pos2 == length2 {
						break main
					}
					s2 = x2.highlowcontainer.getKeyAtIndex(pos2)
				}
			}
		} else {
			break
		}
	}
	return false
}
20044
func (ns *Namespace) Intersect(l1, l2 interface{}) (interface{}, error) {
	if l1 == nil || l2 == nil {
		return make([]interface{}, 0), nil
	}

	var ins *intersector

	l1v := reflect.ValueOf(l1)
	l2v := reflect.ValueOf(l2)

	switch l1v.Kind() {
	case reflect.Array, reflect.Slice:
		ins = &intersector{r: reflect.MakeSlice(l1v.Type(), 0, 0), seen: make(map[interface{}]bool)}
		switch l2v.Kind() {
		case reflect.Array, reflect.Slice:
			for i := 0; i < l1v.Len(); i++ {
				l1vv := l1v.Index(i)
				if !l1vv.Type().Comparable() {
					return make([]interface{}, 0), errors.New("intersect does not support slices or arrays of uncomparable types")
				}

				for j := 0; j < l2v.Len(); j++ {
					l2vv := l2v.Index(j)
					if !l2vv.Type().Comparable() {
						return make([]interface{}, 0), errors.New("intersect does not support slices or arrays of uncomparable types")
					}

					ins.handleValuePair(l1vv, l2vv)
				}
			}
			return ins.r.Interface(), nil
		default:
			return nil, errors.New("can't iterate over " + reflect.ValueOf(l2).Type().String())
		}
	default:
		return nil, errors.New("can't iterate over " + reflect.ValueOf(l1).Type().String())
	}
}
1098897
func (bitmap *bitmap) Compare(other *bitmap, prefixLen int) int {
	if prefixLen > bitmap.Size || prefixLen > other.Size {
		panic("index out of range")
	}

	div, mod := prefixLen>>3, prefixLen&0x07
	res := bytes.Compare(bitmap.data[:div], other.data[:div])
	if res != 0 {
		return res
	}

	for i := div << 3; i < (div<<3)+mod; i++ {
		bit1, bit2 := bitmap.Bit(i), other.Bit(i)
		if bit1 > bit2 {
			return 1
		} else if bit1 < bit2 {
			return -1
		}
	}

	return 0
}
275653
func (me *Dataset) Intersect(other *Dataset) *Dataset {
	ret := me.compoundFromSelf()
	ret.clauses.Compounds = append(ret.clauses.Compounds, Intersect(other.compoundFromSelf()))
	return ret
}
1097313
func Intersect(x interface{}, y interface{}) interface{} {
	if !IsCollection(x) {
		panic("First parameter must be a collection")
	}
	if !IsCollection(y) {
		panic("Second parameter must be a collection")
	}

	hash := map[interface{}]struct{}{}

	xValue := reflect.ValueOf(x)
	xType := xValue.Type()

	yValue := reflect.ValueOf(y)
	yType := yValue.Type()

	if NotEqual(xType, yType) {
		panic("Parameters must have the same type")
	}

	zType := reflect.SliceOf(xType.Elem())
	zSlice := reflect.MakeSlice(zType, 0, 0)

	for i := 0; i < xValue.Len(); i++ {
		v := xValue.Index(i).Interface()
		hash[v] = struct{}{}
	}

	for i := 0; i < yValue.Len(); i++ {
		v := yValue.Index(i).Interface()
		_, ok := hash[v]
		if ok {
			zSlice = reflect.Append(zSlice, yValue.Index(i))
		}
	}

	return zSlice.Interface()
}
49082
func (c Cap) IntersectsCell(cell Cell) bool {
	// If the cap contains any cell vertex, return true.
	var vertices [4]Point
	for k := 0; k < 4; k++ {
		vertices[k] = cell.Vertex(k)
		if c.ContainsPoint(vertices[k]) {
			return true
		}
	}
	return c.intersects(cell, vertices)
}
613259
func (actionSet ActionSet) Intersection(sset ActionSet) ActionSet {
	nset := NewActionSet()
	for k := range actionSet {
		if _, ok := sset[k]; ok {
			nset.Add(k)
		}
	}

	return nset
}
1012605
func (vu versionUnifier) intersect(id ProjectIdentifier, c1, c2 Constraint) Constraint {
	rc := c1.Intersect(c2)
	if rc != none {
		return rc
	}

	vu.mtr.push("b-intersect")
	// This approach is slightly wasteful, but just SO much less verbose, and
	// more easily understood.
	var uc1, uc2 Constraint
	if v1, ok := c1.(Version); ok {
		uc1 = vu.createTypeUnion(id, v1)
	} else {
		uc1 = c1
	}

	if v2, ok := c2.(Version); ok {
		uc2 = vu.createTypeUnion(id, v2)
	} else {
		uc2 = c2
	}

	vu.mtr.pop()
	return uc1.Intersect(uc2)
}
336509
func (s *mockServer) intersect(f messageInterceptor) {
	s.interceptorFuncs = append(s.interceptorFuncs, f)
}
1314052
func (g1 *Virtual) Intersect(g2 *Virtual) *Virtual {
	n := min(g1.order, g2.order)
	switch n {
	case 0:
		return null
	case 1:
		return singleton()
	}

	var res *Virtual
	if g1.order == g2.order {
		res = generic0(n, func(v, w int) bool {
			return g1.edge(v, w) && g2.edge(v, w)
		})
	} else {
		res = generic0(n, func(v, w int) bool {
			return v < n && w < n && g1.edge(v, w) && g2.edge(v, w)
		})
	}

	res.visit = func(v int, a int, do func(w int, c int64) bool) (aborted bool) {
		w, n := findBoth(v, a, g1, g2)
		for n != 0 {
			for u := w; u < w+n; u++ {
				if do(u, 0) {
					return true
				}
			}
			w, n = findBoth(v, w+n, g1, g2)
		}
		return
	}
	return res
}
1070955
func (p *Path) Intersects(geometry interface{}) bool {
	var result bool

	switch g := geometry.(type) {
	case Line:
		result = p.IntersectsLine(&g)
	case *Line:
		result = p.IntersectsLine(g)
	case Path:
		result = p.IntersectsPath(&g)
	case *Path:
		result = p.IntersectsPath(g)
	default:
		panic("can only determine intersection with lines and paths")
	}

	return result
}
339339
func (s Set) Intersect(other Set) Set {
	smallLen := len(s)
	if lo := len(other); lo < smallLen {
		smallLen = lo
	}
	ret := make(Set, smallLen)
	for k := range s {
		if _, ok := other[k]; ok {
			ret[k] = struct{}{}
		}
	}
	return ret
}
208099
func (i Interval) Intersects(oi Interval) bool {
	if i.Lo <= oi.Lo {
		return oi.Lo <= i.Hi && oi.Lo <= oi.Hi // oi.Lo ∈ i and oi is not empty
	}
	return i.Lo <= oi.Hi && i.Lo <= i.Hi // i.Lo ∈ oi and i is not empty
}
419923
func (p *Path) Intersection(geometry interface{}) ([]*Point, [][2]int) {
	var points []*Point
	var segments [][2]int

	switch g := geometry.(type) {
	case Line:
		points, segments = p.IntersectionLine(&g)
	case *Line:
		points, segments = p.IntersectionLine(g)
	case Path:
		points, segments = p.IntersectionPath(&g)
	case *Path:
		points, segments = p.IntersectionPath(g)
	default:
		panic("can only determine intersection with lines and paths")
	}

	return points, segments
}
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]
	}
}
564705
func Intersection(a []corev1.ResourceName, b []corev1.ResourceName) []corev1.ResourceName {
	result := make([]corev1.ResourceName, 0, len(a))
	for _, item := range a {
		if Contains(result, item) {
			continue
		}
		if !Contains(b, item) {
			continue
		}
		result = append(result, item)
	}
	sort.Slice(result, func(i, j int) bool { return result[i] < result[j] })
	return result
}
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
}