BSTreeZip

Merge two structural isomorphic trees to a single one by combining the elements pointwise. Or, split a tree up into two structural isomorphic trees by a splitting function

Signature of BSTreeZip

List of Import References :
See BOOL
See BSTree
See DENOTATION
See Nat
See Option
See Pair
See Seq
See Tree

SIGNATURE BSTreeZip[from1, < : from1 ** from1 -> bool, 

$Date: 2010-09-30 18:24:17 +0200 (Do, 30. Sep 2010) $ ($Revision: 616 $)

                  from2, < : from2 ** from2 -> bool,
                  to,    < : to    ** to    -> bool] 

IMPORT BSTree[from1, <] ONLY bstree[from1, <]
       BSTree[from2, <] ONLY bstree[from2, <]
       BSTree[to, <]    ONLY bstree[to, <]

Parameter

from1 and from2 are the element types of the two trees to be merged to a tree of type to or the result types of the two trees obtained by splitting a tree of type to.

SORT from1 from2 to
FUN < : from1 ** from1 -> bool
FUN < : from2 ** from2 -> bool
FUN < : to    ** to    -> bool

Merging

zip combines the corresponding values of the nodes by the argument function. zip aborts, if the trees are not structural isomorphic. Two trees are structural isomorphic, if both are empty or both are non emptyand their left and right children are structural isomorphic.

FUN zip: (from1 ** from2 -> to) ** bstree[from1, <] ** bstree[from2, <] ->
                                                               bstree[to, <]

Splitting

unzip produces two (structural isomorphic) trees by splitting the values of the nodes with the function.

FUN unzip: (to -> from1 ** from2) ** bstree[to, <] -> 
                                bstree[from1, <] ** bstree[from2, <]

next node: BSTree,
prev node: BSTreeMapEnv,
up to node: Subsystem Balanced Search Trees