====== Tree traversal ======
Next topic: [[documentation:guide:permutations_and_permutation_groups]]
----
Each [[documentation:ref:tensor]] in Redberry is a container of its child tensors, so any complicated expression becomes a hierarchical tree of such containers. Iteration over direct child elements of a tensor described in [[documentation:guide:tensors_and_indices]]. Besides, there are special tools for iteration and modification over a whole tree.
====Traversing expression tree====
There are two basic ways to perform a depth-first search on expression tree:
def t = 'a + Sin[x + y]'.t
def elements = []
t.parentAfterChild { a -> elements << a }
println elements
> [a, x, y, x+y, Sin[x+y], a+Sin[x+y]]
elements = []
t.parentBeforeChild { a -> elements << a }
println elements
> [a+Sin[y+x], a, Sin[y+x], y+x, y, x]
This example illustrates steps of parent-after-child and parent-before-child iteration modes.
Consider another example:
def allSymbols = { expr ->
def r = [] //result
expr.parentAfterChild { e ->
if (e.class == SimpleTensor && e.indices.size() == 0)
r << e
}
r
}
def t = 'f_ij*(x*t^i + k^i*a)*c*x'.t
println allSymbols(t)
> [x, c, a, x]
A function ''allSymbols(expr)'' takes an expression and returns a list of all symbols (without any indices) that contained in ''expr''. If one need to take only unique symbols one can do
println allSymbols(t) as Set
> [x, c, a]
====Modifying expression tree====
Modification of expression tree can be performed in the same way. As an example,
lets consider a naive implementation of a substitution transformation:
def subs = { expr, substitution ->
expr.transformParentAfterChild { element ->
def mapping = (substitution[0] % element).first
//if mapping exists apply it and return
if (mapping) mapping >> substitution[1]
else element
}
}
def t = 'z_m*Cos[x_m*y^m - x_n*(z^n + t^n)] + t_m'.t
println subs(t, 'z_a + t_a = y_a'.t)
> y_m
Here, the function ''subs(expr, s)'' applies substitution rule ''s'' to the expression ''expr''. Method ''.transformParentAfterChild(function)'' applies ''function'' to each part of expression (starting from deepest children nodes) and returns the result.
The key aspect of parent-after-child modification, is that if child node is changed, than its parent node will be reduced to [[documentation:guide:standard_form_of_mathematical_expressions|standard form]] before it will be shown. In the above example the first modification will be performed on the sum ''z^n + t^n'', which will be replaced with ''y^n''. After this modification, the whole branch of the expression tree, which contains this term, will be permanently reduced to the standard form. So, when iteration will reach the argument of cosine, which will be ''x_m*y^m - x_n*y^n'', it will be reduced to zero. On the next step the cosine receives zero as an argument and reduces to 1. On the last step of the iteration, it finally becomes possible to replace obtained ''z_m + t_m'' with ''y_m''.
It should be noted that when modifying expression using tree traversal, Rebderry will automatically take care about correct dummy indices relabelling when necessary.
====See also====
* Related guides: [[documentation:guide:tensors_and_indices]], [[documentation:guide:mappings_of_indices]]
* JavaDocs: [[http://api.redberry.cc/redberry/1.1.9/java-api/cc/redberry/core/tensor/iterator/package-summary.html| Tree iterators]], [[http://api.redberry.cc/redberry/1.1.9/java-api/cc/redberry/core/transformations/substitutions/SubstitutionIterator.html| SubstitutionIterator]]
* Source code: [[https://bitbucket.org/redberry/redberry/src/tip/core/src/main/java/cc/redberry/core/tensor/iterator|Tree iterators]], [[https://bitbucket.org/redberry/redberry/src/tip/core/src/main/java/cc/redberry/core/transformations/substitutions/SubstitutionIterator.java|SubstitutionIterator.java]]