Apply a function to every element of a tree. The map function handles an additional parameter called environment. You may either handle both subtrees simultaneously, or you can traverse the the tree in some given order.
If the result is no valid tree, the tree is rearranged so that it fulfills the tree condition. Hence, every function is total.
List of Import References :
See BOOL
See BSTree
See DENOTATION
See Nat
See Option
See Pair
See Seq
See Tree
SIGNATURE BSTreeMapEnv[env,from, < : from ** from -> bool,
$Date: 2010-09-30 18:24:17 +0200 (Do, 30. Sep 2010) $ ($Revision: 616 $)
to, < : to ** to -> bool]
IMPORT BSTree[from, <] ONLY bstree[from, <]
BSTree[to, <] ONLY bstree[to, <]
env is the data type of the additional parameter,
from is the original data type of the elements of the tree,
to is the new data type of the elements.
SORT env from to FUN < : from ** from -> bool FUN < : to ** to -> bool
Top-Down Direction First, from the current environment, and the root value, two new environments are computed for the left and right child respectively and a new value for the current node. The initial environment is used for computing the value of the root node.
FUN *_V : (env ** from -> env ** env ** to) **
env ** bstree[from, <] -> bstree[to, <]
Bottom-Up Direction First, the children are processed. The environments from the left and right subtree together with the current value are fed into the function which then returns a new environment and a new value. The initial environment is returned for the empty tree. The environment returned is the result from the root.
FUN *_^ : (env ** env ** from -> env ** to) **
env ** bstree[from, <] -> env ** bstree[to, <]
These functions visit the the nodes in preorder, inorder or postorder, always using the environment from the previous computation.
FUN *_pre *_in *_post:
(env ** from -> env ** to) ** env ** bstree[from, <] ->
env ** bstree[to, <]
next node: BSTreeZip,
prev node: BSTreeMap,
up to node: Subsystem Balanced Search Trees