Perform a left or right rotation if node A is imbalanced. Returns the new root index.
(iA int)
| 497 | // Perform a left or right rotation if node A is imbalanced. |
| 498 | // Returns the new root index. |
| 499 | func (tree *B2DynamicTree) Balance(iA int) int { |
| 500 | B2Assert(iA != B2_nullNode) |
| 501 | |
| 502 | A := &tree.M_nodes[iA] |
| 503 | if A.IsLeaf() || A.Height < 2 { |
| 504 | return iA |
| 505 | } |
| 506 | |
| 507 | iB := A.Child1 |
| 508 | iC := A.Child2 |
| 509 | B2Assert(0 <= iB && iB < tree.M_nodeCapacity) |
| 510 | B2Assert(0 <= iC && iC < tree.M_nodeCapacity) |
| 511 | |
| 512 | B := &tree.M_nodes[iB] |
| 513 | C := &tree.M_nodes[iC] |
| 514 | |
| 515 | balance := C.Height - B.Height |
| 516 | |
| 517 | // Rotate C up |
| 518 | if balance > 1 { |
| 519 | iF := C.Child1 |
| 520 | iG := C.Child2 |
| 521 | B2Assert(0 <= iF && iF < tree.M_nodeCapacity) |
| 522 | B2Assert(0 <= iG && iG < tree.M_nodeCapacity) |
| 523 | F := &tree.M_nodes[iF] |
| 524 | G := &tree.M_nodes[iG] |
| 525 | |
| 526 | // Swap A and C |
| 527 | C.Child1 = iA |
| 528 | C.Parent = A.Parent |
| 529 | A.Parent = iC |
| 530 | |
| 531 | // A's old parent should point to C |
| 532 | if C.Parent != B2_nullNode { |
| 533 | if tree.M_nodes[C.Parent].Child1 == iA { |
| 534 | tree.M_nodes[C.Parent].Child1 = iC |
| 535 | } else { |
| 536 | B2Assert(tree.M_nodes[C.Parent].Child2 == iA) |
| 537 | tree.M_nodes[C.Parent].Child2 = iC |
| 538 | } |
| 539 | } else { |
| 540 | tree.M_root = iC |
| 541 | } |
| 542 | |
| 543 | // Rotate |
| 544 | if F.Height > G.Height { |
| 545 | C.Child2 = iF |
| 546 | A.Child2 = iG |
| 547 | G.Parent = iA |
| 548 | A.Aabb.CombineTwoInPlace(B.Aabb, G.Aabb) |
| 549 | C.Aabb.CombineTwoInPlace(A.Aabb, F.Aabb) |
| 550 | |
| 551 | A.Height = 1 + MaxInt(B.Height, G.Height) |
| 552 | C.Height = 1 + MaxInt(A.Height, F.Height) |
| 553 | } else { |
| 554 | C.Child2 = iG |
| 555 | A.Child2 = iF |
| 556 | F.Parent = iA |
no test coverage detected