tpl_binNodeGenerators.H File Reference

Lazy (coroutine-based) traversals of binary trees. More...

#include <ah-generator.H>
#include <tpl_arrayStack.H>
#include <tpl_binNode.H>
#include <tpl_binNodeUtils.H>

Include dependency graph for tpl_binNodeGenerators.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Functions
template<class Node >
Aleph::Generator< Node * >	Aleph::lazy_in_order (Node *root)
	Lazily traverse a binary tree in-order (left, node, right).
template<class Node >
Aleph::Generator< Node * >	Aleph::lazy_pre_order (Node *root)
	Lazily traverse a binary tree pre-order (node, left, right).
template<class Node >
Aleph::Generator< Node * >	Aleph::lazy_post_order (Node *root)
	Lazily traverse a binary tree post-order (left, right, node).

Detailed Description

Lazy (coroutine-based) traversals of binary trees.

Lazy counterparts of the eager visitor-based traversals in tpl_binNodeUtils.H (for_each_in_order, for_each_preorder, for_each_postorder): instead of invoking a callback on every node, lazy_in_order/lazy_pre_order/lazy_post_order return an Aleph::Generator<Node *> that yields one node at a time, driven by the caller (range-for, early break, composing with other generators…). The lazy wrappers are iterative internally: they keep one coroutine frame and use Aleph's explicit stack-based traversal machinery.

The eager visitor-based traversals are not replaced — they remain the right tool when the full tree must be visited and no early exit is expected (a hand-written recursive call is cheaper than a coroutine resume). Reach for the lazy versions when you may stop early, when you want to interleave traversal with other lazy computation (Aleph:: Generator composition), or when materializing the traversal into a container is wasteful.

for (Node *n : lazy_in_order(root))
  {
    if (KEY(n) == target)
      break;             // stops the traversal outright; no wasted work
    process(n);
  }

Note

Traversal state: the generator itself has one coroutine frame. Tree depth is represented by explicit Aleph stack state (the same idea used by BinNodeInfixIterator/BinNodePrefixIterator), not by recursive nested generators or the process call stack.

See also

tpl_binNodeUtils.H Eager visitor-based traversals.

ah-generator.H Aleph::Generator<T>, the underlying lazy sequence type.

Author

Leandro Rabindranath Leon

Definition in file tpl_binNodeGenerators.H.