// computeCellsIntersected computes the index cells intersected by the current
// edge that are descendants of pcell and adds them to this queries set of cells.
968146
func (c *CrossingEdgeQuery) computeCellsIntersected(pcell *PaddedCell, edgeBound r2.Rect) {

	c.iter.seek(pcell.id.RangeMin())
	if c.iter.Done() || c.iter.CellID() > pcell.id.RangeMax() {
		// The index does not contain pcell or any of its descendants.
		return
	}
	if c.iter.CellID() == pcell.id {
		// The index contains this cell exactly.
		c.cells = append(c.cells, c.iter.IndexCell())
		return
	}

	// Otherwise, split the edge among the four children of pcell.
	center := pcell.Middle().Lo()

	if edgeBound.X.Hi < center.X {
		// Edge is entirely contained in the two left children.
		c.clipVAxis(edgeBound, center.Y, 0, pcell)
		return
	} else if edgeBound.X.Lo >= center.X {
		// Edge is entirely contained in the two right children.
		c.clipVAxis(edgeBound, center.Y, 1, pcell)
		return
	}

	childBounds := c.splitUBound(edgeBound, center.X)
	if edgeBound.Y.Hi < center.Y {
		// Edge is entirely contained in the two lower children.
		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 0, 0), childBounds[0])
		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 1, 0), childBounds[1])
	} else if edgeBound.Y.Lo >= center.Y {
		// Edge is entirely contained in the two upper children.
		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 0, 1), childBounds[0])
		c.computeCellsIntersected(PaddedCellFromParentIJ(pcell, 1, 1), childBounds[1])
	} else {
		// The edge bound spans all four children. The edge itself intersects
		// at most three children (since no padding is being used).
		c.clipVAxis(childBounds[0], center.Y, 0, pcell)
		c.clipVAxis(childBounds[1], center.Y, 1, pcell)
	}
}
1241227
func (r Rect) InteriorIntersects(other Rect) bool {
	return r.X.InteriorIntersects(other.X) && r.Y.InteriorIntersects(other.Y)
}
1156389
func (c Cap) CellUnionBound() []CellID {
	// TODO(roberts): The covering could be made quite a bit tighter by mapping
	// the cap to a rectangle in (i,j)-space and finding a covering for that.

	// Find the maximum level such that the cap contains at most one cell vertex
	// and such that CellID.AppendVertexNeighbors() can be called.
	level := MinWidthMetric.MaxLevel(c.Radius().Radians()) - 1

	// If level < 0, more than three face cells are required.
	if level < 0 {
		cellIDs := make([]CellID, 6)
		for face := 0; face < 6; face++ {
			cellIDs[face] = CellIDFromFace(face)
		}
		return cellIDs
	}
	// The covering consists of the 4 cells at the given level that share the
	// cell vertex that is closest to the cap center.
	return cellIDFromPoint(c.center).VertexNeighbors(level)
}
1334232
func sortedEdges(edges map[*node]*edgeInfo) edgeList {
	el := make(edgeList, 0, len(edges))
	for _, w := range edges {
		el = append(el, w)
	}

	sort.Sort(el)
	return el
}
150641
func compute(X, Y mat.Matrix) *mat.Dense {
	var ret mat.Dense
	ret.Mul(X, Y)
	return &ret
}
290963
func (c *convergence) actualLRPsWithMissingCells(logger lager.Logger, cellSet models.CellSet) {
	logger = logger.Session("actual-lrps-with-missing-cells")

	var ordinaryKeysWithMissingCells []*models.ActualLRPKeyWithSchedulingInfo

	rows, err := c.selectLRPsWithMissingCells(logger, c.db, cellSet)
	if err != nil {
		logger.Error("failed-query", err)
		return
	}

	missingCellSet := make(map[string]struct{})
	for rows.Next() {
		var index int32
		var cellID string
		var presence models.ActualLRP_Presence
		schedulingInfo, err := c.fetchDesiredLRPSchedulingInfoAndMore(logger, rows, &index, &cellID, &presence)
		if err == nil && presence == models.ActualLRP_Ordinary {
			ordinaryKeysWithMissingCells = append(ordinaryKeysWithMissingCells, &models.ActualLRPKeyWithSchedulingInfo{
				Key: &models.ActualLRPKey{
					ProcessGuid: schedulingInfo.ProcessGuid,
					Domain:      schedulingInfo.Domain,
					Index:       index,
				},
				SchedulingInfo: schedulingInfo,
			})
		}
		missingCellSet[cellID] = struct{}{}
	}

	if rows.Err() != nil {
		logger.Error("failed-getting-next-row", rows.Err())
	}

	for key, _ := range missingCellSet {
		c.missingCellIds = append(c.missingCellIds, key)
	}

	if len(c.missingCellIds) > 0 {
		logger.Info("detected-missing-cells", lager.Data{"cell_ids": c.missingCellIds})
	}

	c.ordinaryKeysWithMissingCells = ordinaryKeysWithMissingCells
}
871171
func (cu *CellUnion) IntersectsCell(c Cell) bool {
	return cu.IntersectsCellID(c.id)
}
507869
func rayIntersect(p, s, e orb.Point) (intersects, on bool) {
	if s[0] > e[0] {
		s, e = e, s
	}

	if p[0] == s[0] {
		if p[1] == s[1] {
			// p == start
			return false, true
		} else if s[0] == e[0] {
			// vertical segment (s -> e)
			// return true if within the line, check to see if start or end is greater.
			if s[1] > e[1] && s[1] >= p[1] && p[1] >= e[1] {
				return false, true
			}

			if e[1] > s[1] && e[1] >= p[1] && p[1] >= s[1] {
				return false, true
			}
		}

		// Move the y coordinate to deal with degenerate case
		p[0] = math.Nextafter(p[0], math.Inf(1))
	} else if p[0] == e[0] {
		if p[1] == e[1] {
			// matching the end point
			return false, true
		}

		p[0] = math.Nextafter(p[0], math.Inf(1))
	}

	if p[0] < s[0] || p[0] > e[0] {
		return false, false
	}

	if s[1] > e[1] {
		if p[1] > s[1] {
			return false, false
		} else if p[1] < e[1] {
			return true, false
		}
	} else {
		if p[1] > e[1] {
			return false, false
		} else if p[1] < s[1] {
			return true, false
		}
	}

	rs := (p[1] - s[1]) / (p[0] - s[0])
	ds := (e[1] - s[1]) / (e[0] - s[0])

	if rs == ds {
		return false, true
	}

	return rs <= ds, false
}
253106
func computeAverageGiniIndex(s map[string]map[string]int) float64 {

	// Figure out the total number of things in this map
	total := 0
	for i := range s {
		for j := range s[i] {
			total += s[i][j]
		}
	}

	sum := 0.0
	for i := range s {
		subtotal := 0.0
		for j := range s[i] {
			subtotal += float64(s[i][j])
		}
		cf := subtotal / float64(total)
		cf *= computeGini(s[i])
		sum += cf
	}
	return sum
}
346888
func CellUnionFromDifference(x, y CellUnion) CellUnion {
	// TODO(roberts): This is approximately O(N*log(N)), but could probably
	// use similar techniques as CellUnionFromIntersectionWithCellID to be more efficient.

	var cu CellUnion
	for _, xid := range x {
		cu.cellUnionDifferenceInternal(xid, &y)
	}

	// The output is generated in sorted order, and there should not be any
	// cells that can be merged (provided that both inputs were normalized).
	return cu
}
327718
func IsIntersecting(rect1 engo.AABB, rect2 engo.AABB) bool {
	if rect1.Max.X > rect2.Min.X && rect1.Min.X < rect2.Max.X && rect1.Max.Y > rect2.Min.Y && rect1.Min.Y < rect2.Max.Y {
		return true
	}

	return false
}
1352006
func (r Rect) IntersectsCell(c Cell) bool {
	// First we eliminate the cases where one region completely contains the
	// other. Once these are disposed of, then the regions will intersect
	// if and only if their boundaries intersect.
	if r.IsEmpty() {
		return false
	}
	if r.ContainsPoint(Point{c.id.rawPoint()}) {
		return true
	}
	if c.ContainsPoint(PointFromLatLng(r.Center())) {
		return true
	}

	// Quick rejection test (not required for correctness).
	if !r.Intersects(c.RectBound()) {
		return false
	}

	// Precompute the cell vertices as points and latitude-longitudes. We also
	// check whether the Cell contains any corner of the rectangle, or
	// vice-versa, since the edge-crossing tests only check the edge interiors.
	vertices := [4]Point{}
	latlngs := [4]LatLng{}

	for i := range vertices {
		vertices[i] = c.Vertex(i)
		latlngs[i] = LatLngFromPoint(vertices[i])
		if r.ContainsLatLng(latlngs[i]) {
			return true
		}
		if c.ContainsPoint(PointFromLatLng(r.Vertex(i))) {
			return true
		}
	}

	// Now check whether the boundaries intersect. Unfortunately, a
	// latitude-longitude rectangle does not have straight edges: two edges
	// are curved, and at least one of them is concave.
	for i := range vertices {
		edgeLng := s1.IntervalFromEndpoints(latlngs[i].Lng.Radians(), latlngs[(i+1)&3].Lng.Radians())
		if !r.Lng.Intersects(edgeLng) {
			continue
		}

		a := vertices[i]
		b := vertices[(i+1)&3]
		if edgeLng.Contains(r.Lng.Lo) && intersectsLngEdge(a, b, r.Lat, s1.Angle(r.Lng.Lo)) {
			return true
		}
		if edgeLng.Contains(r.Lng.Hi) && intersectsLngEdge(a, b, r.Lat, s1.Angle(r.Lng.Hi)) {
			return true
		}
		if intersectsLatEdge(a, b, s1.Angle(r.Lat.Lo), r.Lng) {
			return true
		}
		if intersectsLatEdge(a, b, s1.Angle(r.Lat.Hi), r.Lng) {
			return true
		}
	}
	return false
}
404957
func (c *tabletStatsCache) cellsInTopology(keyspace string) []string {
	keyspaces := c.keyspacesLocked(keyspace)
	cells := make(map[string]bool)
	// Going through all shards in each keyspace to get all existing cells
	for _, ks := range keyspaces {
		shardsPerKeyspace := c.statuses[ks]
		for s := range shardsPerKeyspace {
			cellsInKeyspace := c.statuses[ks][s]
			for cl := range cellsInKeyspace {
				cells[cl] = true
			}
		}
	}
	var cellList []string
	for cell := range cells {
		cellList = append(cellList, cell)
	}
	sort.Strings(cellList)
	return cellList
}
902740
func deriveIntersect(this, that []int) []int {
	intersect := make([]int, 0, deriveMin(len(this), len(that)))
	for i, v := range this {
		if deriveContains(that, v) {
			intersect = append(intersect, this[i])
		}
	}
	return intersect
}
323832
func (l *loopCrosser) edgeCrossesCell(bClipped *clippedShape) bool {
	// Test the current edge of A against all edges of bClipped
	bNumEdges := bClipped.numEdges()
	for j := 0; j < bNumEdges; j++ {
		bj := bClipped.edges[j]
		if bj != l.bjPrev+1 {
			l.crosser.RestartAt(l.b.Vertex(bj))
		}
		l.bjPrev = bj
		if crossing := l.crosser.ChainCrossingSign(l.b.Vertex(bj + 1)); crossing == DoNotCross {
			continue
		} else if crossing == Cross {
			return true
		}

		// We only need to check each shared vertex once, so we only
		// consider the case where l.aVertex(l.aj+1) == l.b.Vertex(bj+1).
		if l.a.Vertex(l.aj+1) == l.b.Vertex(bj+1) {
			if l.swapped {
				if l.relation.wedgesCross(l.b.Vertex(bj), l.b.Vertex(bj+1), l.b.Vertex(bj+2), l.a.Vertex(l.aj), l.a.Vertex(l.aj+2)) {
					return true
				}
			} else {
				if l.relation.wedgesCross(l.a.Vertex(l.aj), l.a.Vertex(l.aj+1), l.a.Vertex(l.aj+2), l.b.Vertex(bj), l.b.Vertex(bj+2)) {
					return true
				}
			}
		}
	}

	return false
}
206851
func (ci CellID) Intersects(oci CellID) bool {
	return uint64(oci.RangeMin()) <= uint64(ci.RangeMax()) && uint64(oci.RangeMax()) >= uint64(ci.RangeMin())
}
1312916
func indexInSlice(slice []*html.Node, node *html.Node) int {
	if node != nil {
		for i, n := range slice {
			if n == node {
				return i
			}
		}
	}
	return -1
}