WalkDownPost iterates in a depth-first manner over the children, calling shouldContinue on each node to test if processing should proceed (if it returns [Break] then that branch of the tree is not further processed), and then calls the given function after all of a node's children have been iterated
(shouldContinue func(n Node) bool, fun func(n Node) bool)
| 555 | // time, so you should use a Mutex if there is a chance of multiple threads |
| 556 | // running at the same time. The nodes are processed in the current goroutine. |
| 557 | func (n *NodeBase) WalkDownPost(shouldContinue func(n Node) bool, fun func(n Node) bool) { |
| 558 | if n.This == nil { |
| 559 | return |
| 560 | } |
| 561 | tm := map[Node]int{} // traversal map |
| 562 | start := n.This |
| 563 | cur := start |
| 564 | tm[cur] = -1 |
| 565 | outer: |
| 566 | for { |
| 567 | cb := cur.AsTree() |
| 568 | if cb.This != nil && shouldContinue(cur) { // false return means stop |
| 569 | if cb.HasChildren() { |
| 570 | tm[cur] = 0 // 0 for no fields |
| 571 | nxt := cb.Child(0) |
| 572 | if nxt != nil && nxt.AsTree().This != nil { |
| 573 | cur = nxt.AsTree().This |
| 574 | tm[cur] = -1 |
| 575 | continue |
| 576 | } |
| 577 | } |
| 578 | } else { |
| 579 | tm[cur] = cb.NumChildren() |
| 580 | } |
| 581 | // if we get here, we're in the ascent branch -- move to the right and then up |
| 582 | for { |
| 583 | cb := cur.AsTree() // may have changed, so must get again |
| 584 | curChild := tm[cur] |
| 585 | if (curChild + 1) < cb.NumChildren() { |
| 586 | curChild++ |
| 587 | tm[cur] = curChild |
| 588 | nxt := cb.Child(curChild) |
| 589 | if nxt != nil && nxt.AsTree().This != nil { |
| 590 | cur = nxt.AsTree().This |
| 591 | tm[cur] = -1 |
| 592 | continue outer |
| 593 | } |
| 594 | continue |
| 595 | } |
| 596 | fun(cur) // now we call the function, last.. |
| 597 | // couldn't go right, move up.. |
| 598 | delete(tm, cur) |
| 599 | if cur == start { |
| 600 | break outer // done! |
| 601 | } |
| 602 | parent := cb.Parent |
| 603 | if parent == nil || parent == cur { // shouldn't happen |
| 604 | break outer |
| 605 | } |
| 606 | cur = parent |
| 607 | } |
| 608 | } |
| 609 | } |
| 610 | |
| 611 | // Note: it does not appear that there is a good |
| 612 | // recursive breadth-first-search strategy: |