// Return the cartesian extent of a merged cell range from its origin
// cell (the closest merged cell to the to left of the sheet.
177508
func (mc *xlsxMergeCells) getExtent(cellRef string) (int, int, error) {
	if mc == nil {
		return 0, 0, nil
	}
	for _, cell := range mc.Cells {
		if strings.HasPrefix(cell.Ref, cellRef+cellRangeChar) {
			parts := strings.Split(cell.Ref, cellRangeChar)
			startx, starty, err := GetCoordsFromCellIDString(parts[0])
			if err != nil {
				return -1, -1, err
			}
			endx, endy, err := GetCoordsFromCellIDString(parts[1])
			if err != nil {
				return -2, -2, err
			}
			return endx - startx, endy - starty, nil
		}
	}
	return 0, 0, nil
}
635811
func (c *Cell) Merge(hcells, vcells int) {
	c.HMerge = hcells
	c.VMerge = vcells
}
986879
func (s *ShapeIndex) makeIndexCell(p *PaddedCell, edges []*clippedEdge, t *tracker) bool {
	// If the cell is empty, no index cell is needed. (In most cases this
	// situation is detected before we get to this point, but this can happen
	// when all shapes in a cell are removed.)
	if len(edges) == 0 && len(t.shapeIDs) == 0 {
		return true
	}

	// Count the number of edges that have not reached their maximum level yet.
	// Return false if there are too many such edges.
	count := 0
	for _, ce := range edges {
		if p.Level() < ce.faceEdge.maxLevel {
			count++
		}

		if count > s.maxEdgesPerCell {
			return false
		}
	}

	// Possible optimization: Continue subdividing as long as exactly one child
	// of the padded cell intersects the given edges. This can be done by finding
	// the bounding box of all the edges and calling ShrinkToFit:
	//
	// cellID = p.ShrinkToFit(RectBound(edges));
	//
	// Currently this is not beneficial; it slows down construction by 4-25%
	// (mainly computing the union of the bounding rectangles) and also slows
	// down queries (since more recursive clipping is required to get down to
	// the level of a spatial index cell). But it may be worth trying again
	// once containsCenter is computed and all algorithms are modified to
	// take advantage of it.

	// We update the InteriorTracker as follows. For every Cell in the index
	// we construct two edges: one edge from entry vertex of the cell to its
	// center, and one from the cell center to its exit vertex. Here entry
	// and exit refer the CellID ordering, i.e. the order in which points
	// are encountered along the 2 space-filling curve. The exit vertex then
	// becomes the entry vertex for the next cell in the index, unless there are
	// one or more empty intervening cells, in which case the InteriorTracker
	// state is unchanged because the intervening cells have no edges.

	// Shift the InteriorTracker focus point to the center of the current cell.
	if t.isActive && len(edges) != 0 {
		if !t.atCellID(p.id) {
			t.moveTo(p.EntryVertex())
		}
		t.drawTo(p.Center())
		s.testAllEdges(edges, t)
	}

	// Allocate and fill a new index cell. To get the total number of shapes we
	// need to merge the shapes associated with the intersecting edges together
	// with the shapes that happen to contain the cell center.
	cshapeIDs := t.shapeIDs
	numShapes := s.countShapes(edges, cshapeIDs)
	cell := NewShapeIndexCell(numShapes)

	// To fill the index cell we merge the two sources of shapes: edge shapes
	// (those that have at least one edge that intersects this cell), and
	// containing shapes (those that contain the cell center). We keep track
	// of the index of the next intersecting edge and the next containing shape
	// as we go along. Both sets of shape ids are already sorted.
	eNext := 0
	cNextIdx := 0
	for i := 0; i < numShapes; i++ {
		var clipped *clippedShape
		// advance to next value base + i
		eshapeID := int32(s.Len())
		cshapeID := int32(eshapeID) // Sentinels

		if eNext != len(edges) {
			eshapeID = edges[eNext].faceEdge.shapeID
		}
		if cNextIdx < len(cshapeIDs) {
			cshapeID = cshapeIDs[cNextIdx]
		}
		eBegin := eNext
		if cshapeID < eshapeID {
			// The entire cell is in the shape interior.
			clipped = newClippedShape(cshapeID, 0)
			clipped.containsCenter = true
			cNextIdx++
		} else {
			// Count the number of edges for this shape and allocate space for them.
			for eNext < len(edges) && edges[eNext].faceEdge.shapeID == eshapeID {
				eNext++
			}
			clipped = newClippedShape(eshapeID, eNext-eBegin)
			for e := eBegin; e < eNext; e++ {
				clipped.edges[e-eBegin] = edges[e].faceEdge.edgeID
			}
			if cshapeID == eshapeID {
				clipped.containsCenter = true
				cNextIdx++
			}
		}
		cell.shapes[i] = clipped
	}

	// Add this cell to the map.
	s.cellMap[p.id] = cell
	s.cells = append(s.cells, p.id)

	// Shift the tracker focus point to the exit vertex of this cell.
	if t.isActive && len(edges) != 0 {
		t.drawTo(p.ExitVertex())
		s.testAllEdges(edges, t)
		t.setNextCellID(p.id.Next())
	}
	return true
}
1072952
func GetCellIDStringFromCoords(x, y int) string {
	return GetCellIDStringFromCoordsWithFixed(x, y, false, false)
}
265696
func (p *Polygon) ContainsCell(cell Cell) bool {
	it := p.index.Iterator()
	relation := it.LocateCellID(cell.ID())

	// If "cell" is disjoint from all index cells, it is not contained.
	// Similarly, if "cell" is subdivided into one or more index cells then it
	// is not contained, since index cells are subdivided only if they (nearly)
	// intersect a sufficient number of edges.  (But note that if "cell" itself
	// is an index cell then it may be contained, since it could be a cell with
	// no edges in the loop interior.)
	if relation != Indexed {
		return false
	}

	// Otherwise check if any edges intersect "cell".
	if p.boundaryApproxIntersects(it, cell) {
		return false
	}

	// Otherwise check if the loop contains the center of "cell".
	return p.iteratorContainsPoint(it, cell.Center())
}
1138974
func (f *File) getColWidth(sheet string, col int) int {
	xlsx, _ := f.workSheetReader(sheet)
	if xlsx.Cols != nil {
		var width float64
		for _, v := range xlsx.Cols.Col {
			if v.Min <= col && col <= v.Max {
				width = v.Width
			}
		}
		if width != 0 {
			return int(convertColWidthToPixels(width))
		}
	}
	// Optimisation for when the column widths haven't changed.
	return int(defaultColWidthPixels)
}
165244
func GetCoordsFromCellIDString(cellIDString string) (x, y int, error error) {
	var letterPart string = strings.Map(letterOnlyMapF, cellIDString)
	y, error = strconv.Atoi(strings.Map(intOnlyMapF, cellIDString))
	if error != nil {
		return x, y, error
	}
	y -= 1 // Zero based
	x = ColLettersToIndex(letterPart)
	return x, y, error
}
786618
func maxRange(root, left, right *Node) Comparable {
	end := root.Elem.End()
	if left != nil && left.Range.End().Compare(end) > 0 {
		end = left.Range.End()
	}
	if right != nil && right.Range.End().Compare(end) > 0 {
		end = right.Range.End()
	}
	return end
}
1258030
func (td *MergingDigest) CDF(value float64) float64 {
	td.mergeAllTemps()

	if len(td.mainCentroids) == 0 {
		return math.NaN()
	}
	if value <= td.min {
		return 0
	}
	if value >= td.max {
		return 1
	}

	weightSoFar := 0.0
	lowerBound := td.min
	for i, c := range td.mainCentroids {
		upperBound := td.centroidUpperBound(i)
		if value < upperBound {
			// the value falls inside the bounds of this centroid
			// based on the assumed uniform distribution, we calculate how much
			// of this centroid's weight is below the value
			weightSoFar += c.Weight * (value - lowerBound) / (upperBound - lowerBound)
			return weightSoFar / td.mainWeight
		}

		// the value is above this centroid, so sum the weight and carry on
		weightSoFar += c.Weight
		lowerBound = upperBound
	}

	// should never be reached, since the final loop comparison is value < td.max
	return math.NaN()
}
277201
func (c Cell) CapBound() Cap {
	// We use the cell center in (u,v)-space as the cap axis.  This vector is very close
	// to GetCenter() and faster to compute.  Neither one of these vectors yields the
	// bounding cap with minimal surface area, but they are both pretty close.
	cap := CapFromPoint(Point{faceUVToXYZ(int(c.face), c.uv.Center().X, c.uv.Center().Y).Normalize()})
	for k := 0; k < 4; k++ {
		cap = cap.AddPoint(c.Vertex(k))
	}
	return cap
}
1206063
func MergeRows(ms []Row) Row {
	res := make(map[string]*Cell)
	for _, om := range ms {
		for k, v := range om {
			if k != "" {
				res[k] = v
			}
		}
	}
	return res
}
824877
func (ll LatLng) Distance(ll2 LatLng) s1.Angle {
	// Haversine formula, as used in C++ S2LatLng::GetDistance.
	lat1, lat2 := ll.Lat.Radians(), ll2.Lat.Radians()
	lng1, lng2 := ll.Lng.Radians(), ll2.Lng.Radians()
	dlat := math.Sin(0.5 * (lat2 - lat1))
	dlng := math.Sin(0.5 * (lng2 - lng1))
	x := dlat*dlat + dlng*dlng*math.Cos(lat1)*math.Cos(lat2)
	return s1.Angle(2*math.Atan2(math.Sqrt(x), math.Sqrt(math.Max(0, 1-x)))) * s1.Radian
}
87476
func (cu *CellUnion) ExactArea() float64 {
	var area float64
	for _, id := range *cu {
		area += CellFromCellID(id).ExactArea()
	}
	return area
}
905125
func getCellIDStringFromCoords(x, y int) string {
	letterPart := numericToLetters(x)
	numericPart := y + 1
	return fmt.Sprintf("%s%d", letterPart, numericPart)
}
1119483
func mergeAllRanges(r []matchRange) []matchRange {
	sort.Slice(r, func(i, j int) bool { return r[i].first < r[j].first })
	for i := 0; i < len(r)-1; i++ {
		for i+1 < len(r) && r[i+1].first <= r[i].last {
			if r[i+1].last > r[i].last {
				r[i].last = r[i+1].last
			}
			r = append(r[:i+1], r[i+2:]...)
		}
	}
	return r
}
1155520
func (ci CellID) boundST() r2.Rect {
	s := ci.sizeST(ci.Level())
	return r2.RectFromCenterSize(ci.centerST(), r2.Point{s, s})
}
43472
func (c *CrossingEdgeQuery) getCellsForEdge(a, b Point) {
	c.cells = nil

	segments := FaceSegments(a, b)
	for _, segment := range segments {
		c.a = segment.a
		c.b = segment.b

		// Optimization: rather than always starting the recursive subdivision at
		// the top level face cell, instead we start at the smallest S2CellId that
		// contains the edge (the edge root cell). This typically lets us skip
		// quite a few levels of recursion since most edges are short.
		edgeBound := r2.RectFromPoints(c.a, c.b)
		pcell := PaddedCellFromCellID(CellIDFromFace(segment.face), 0)
		edgeRoot := pcell.ShrinkToFit(edgeBound)

		// Now we need to determine how the edge root cell is related to the cells
		// in the spatial index (cellMap). There are three cases:
		//
		//  1. edgeRoot is an index cell or is contained within an index cell.
		//     In this case we only need to look at the contents of that cell.
		//  2. edgeRoot is subdivided into one or more index cells. In this case
		//     we recursively subdivide to find the cells intersected by AB.
		//  3. edgeRoot does not intersect any index cells. In this case there
		//     is nothing to do.
		relation := c.iter.LocateCellID(edgeRoot)
		if relation == Indexed {
			// edgeRoot is an index cell or is contained by an index cell (case 1).
			c.cells = append(c.cells, c.iter.IndexCell())
		} else if relation == Subdivided {
			// edgeRoot is subdivided into one or more index cells (case 2). We
			// find the cells intersected by AB using recursive subdivision.
			if !edgeRoot.isFace() {
				pcell = PaddedCellFromCellID(edgeRoot, 0)
			}
			c.computeCellsIntersected(pcell, edgeBound)
		}
	}
}