HeapZip

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

Signature of HeapZip

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

SIGNATURE HeapZip[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 Heap[from1, <] ONLY heap
       Heap[from2, <] ONLY heap
       Heap[to, <]    ONLY heap

Parameter

from1 and from2 are the element types of the two heaps to be merged to a heap of type to or the result types of the two heaps obtained by splitting a heap 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 heaps are not structural isomorphic. Two heaps 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) ** heap[from1, <] ** heap[from2, <] ->
                                                               heap[to, <]

Splitting

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

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

next node: Heap,
prev node: HeapMapEnv,
up to node: Subsystem Heaps