Build builds the index for use. This method should only be called once.
()
| 404 | |
| 405 | // Build builds the index for use. This method should only be called once. |
| 406 | func (c *CellIndex) Build() { |
| 407 | // To build the cell tree and leaf cell ranges, we maintain a stack of |
| 408 | // (CellID, label) pairs that contain the current leaf cell. This struct |
| 409 | // represents an instruction to push or pop a (cellID, label) pair. |
| 410 | // |
| 411 | // If label >= 0, the (cellID, label) pair is pushed on the stack. |
| 412 | // If CellID == SentinelCellID, a pair is popped from the stack. |
| 413 | // Otherwise the stack is unchanged but a rangeNode is still emitted. |
| 414 | |
| 415 | // delta represents an entry in a stack of (CellID, label) pairs used in the |
| 416 | // construction of the CellIndex structure. |
| 417 | type delta struct { |
| 418 | startID CellID |
| 419 | cellID CellID |
| 420 | label int32 |
| 421 | } |
| 422 | |
| 423 | deltas := make([]delta, 0, 2*len(c.cellTree)+2) |
| 424 | |
| 425 | // Create two deltas for each (cellID, label) pair: one to add the pair to |
| 426 | // the stack (at the start of its leaf cell range), and one to remove it from |
| 427 | // the stack (at the end of its leaf cell range). |
| 428 | for _, node := range c.cellTree { |
| 429 | deltas = append(deltas, delta{ |
| 430 | startID: node.cellID.RangeMin(), |
| 431 | cellID: node.cellID, |
| 432 | label: node.label, |
| 433 | }) |
| 434 | deltas = append(deltas, delta{ |
| 435 | startID: node.cellID.RangeMax().Next(), |
| 436 | cellID: SentinelCellID, |
| 437 | label: -1, |
| 438 | }) |
| 439 | } |
| 440 | |
| 441 | // We also create two special deltas to ensure that a RangeNode is emitted at |
| 442 | // the beginning and end of the CellID range. |
| 443 | deltas = append(deltas, delta{ |
| 444 | startID: CellIDFromFace(0).ChildBeginAtLevel(MaxLevel), |
| 445 | cellID: CellID(0), |
| 446 | label: -1, |
| 447 | }) |
| 448 | deltas = append(deltas, delta{ |
| 449 | startID: CellIDFromFace(5).ChildEndAtLevel(MaxLevel), |
| 450 | cellID: CellID(0), |
| 451 | label: -1, |
| 452 | }) |
| 453 | |
| 454 | sort.Slice(deltas, func(i, j int) bool { |
| 455 | // deltas are sorted first by startID, then in reverse order by cellID, |
| 456 | // and then by label. This is necessary to ensure that (1) larger cells |
| 457 | // are pushed on the stack before smaller cells, and (2) cells are popped |
| 458 | // off the stack before any new cells are added. |
| 459 | |
| 460 | if si, sj := deltas[i].startID, deltas[j].startID; si != sj { |
| 461 | return si < sj |
| 462 | } |
| 463 | if si, sj := deltas[i].cellID, deltas[j].cellID; si != sj { |