Apply a function to every element of a heap. The map function handles an additional parameter called environment. You may either handle both subheaps simultaneously, or you can traverse the the heap in some given order.
If the result is no valid heap, the tree is rearranged so that it fulfills the heap condition. Hence, every function is total.
List of Import References :
See BOOL
See DENOTATION
See Heap
See Nat
See Option
See Seq
See Tree
SIGNATURE HeapMapEnv[env,from, < : from ** from -> bool,
$Date: 2010-09-30 18:24:17 +0200 (Do, 30. Sep 2010) $ ($Revision: 616 $)
to, < : to ** to -> bool]
IMPORT Heap[from, <] ONLY heap
Heap[to, <] ONLY heap
env is the data type of the additional parameter,
from is the original data type of the elements of the heap,
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 ** heap[from, <] -> heap[to, <]
Bottom-Up Direction First, the children are processed. The environments from the left and right subheap 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 heap. The environment returned is the result from the root.
FUN *_^ : (env ** env ** from -> env ** to) **
env ** heap[from, <] -> env ** heap[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 ** heap[from, <] -> env ** heap[to, <]
next node: HeapZip,
prev node: HeapMap,
up to node: Subsystem Heaps