func()

in s2/cell_index.go [409:493]
57 lines of code
9 McCabe index (conditional complexity)

func (c *CellIndex) Build() {
	// To build the cell tree and leaf cell ranges, we maintain a stack of
	// (CellID, label) pairs that contain the current leaf cell. This struct
	// represents an instruction to push or pop a (cellID, label) pair.
	//
	// If label >= 0, the (cellID, label) pair is pushed on the stack.
	// If CellID == SentinelCellID, a pair is popped from the stack.
	// Otherwise the stack is unchanged but a rangeNode is still emitted.

	// delta represents an entry in a stack of (CellID, label) pairs used in the
	// construction of the CellIndex structure.
	type delta struct {
		startID CellID
		cellID  CellID
		label   int32
	}

	deltas := make([]delta, 0, 2*len(c.cellTree)+2)

	// Create two deltas for each (cellID, label) pair: one to add the pair to
	// the stack (at the start of its leaf cell range), and one to remove it from
	// the stack (at the end of its leaf cell range).
	for _, node := range c.cellTree {
		deltas = append(deltas, delta{
			startID: node.cellID.RangeMin(),
			cellID:  node.cellID,
			label:   node.label,
		})
		deltas = append(deltas, delta{
			startID: node.cellID.RangeMax().Next(),
			cellID:  SentinelCellID,
			label:   -1,
		})
	}

	// We also create two special deltas to ensure that a RangeNode is emitted at
	// the beginning and end of the CellID range.
	deltas = append(deltas, delta{
		startID: CellIDFromFace(0).ChildBeginAtLevel(maxLevel),
		cellID:  CellID(0),
		label:   -1,
	})
	deltas = append(deltas, delta{
		startID: CellIDFromFace(5).ChildEndAtLevel(maxLevel),
		cellID:  CellID(0),
		label:   -1,
	})

	sort.Slice(deltas, func(i, j int) bool {
		// deltas are sorted first by startID, then in reverse order by cellID,
		// and then by label. This is necessary to ensure that (1) larger cells
		// are pushed on the stack before smaller cells, and (2) cells are popped
		// off the stack before any new cells are added.

		if si, sj := deltas[i].startID, deltas[j].startID; si != sj {
			return si < sj
		}
		if si, sj := deltas[i].cellID, deltas[j].cellID; si != sj {
			return si > sj
		}
		return deltas[i].label < deltas[j].label
	})

	// Now walk through the deltas to build the leaf cell ranges and cell tree
	// (which is essentially a permanent form of the "stack" described above).
	c.cellTree = nil
	c.rangeNodes = nil
	contents := int32(-1)
	for i := 0; i < len(deltas); {
		startID := deltas[i].startID
		// Process all the deltas associated with the current startID.
		for ; i < len(deltas) && deltas[i].startID == startID; i++ {
			if deltas[i].label >= 0 {
				c.cellTree = append(c.cellTree, cellIndexNode{
					cellID: deltas[i].cellID,
					label:  deltas[i].label,
					parent: contents})
				contents = int32(len(c.cellTree) - 1)
			} else if deltas[i].cellID == SentinelCellID {
				contents = c.cellTree[contents].parent
			}
		}
		c.rangeNodes = append(c.rangeNodes, rangeNode{startID, contents})
	}
}