Data.Tree.AVL.Internals.HAVL
 Portability portable Stability stable Maintainer http://homepages.nildram.co.uk/~ahey/em.png
Description
HAVL data type and related utilities
Synopsis
 data HAVL e = HAVL (AVL e) !Int# emptyHAVL :: HAVL e toHAVL :: AVL e -> HAVL e isEmptyHAVL :: HAVL e -> Bool isNonEmptyHAVL :: HAVL e -> Bool spliceHAVL :: HAVL e -> e -> HAVL e -> HAVL e joinHAVL :: HAVL e -> HAVL e -> HAVL e pushLHAVL :: e -> HAVL e -> HAVL e pushRHAVL :: HAVL e -> e -> HAVL e
Documentation
data HAVL e
An HAVL represents an AVL tree of known height.
Constructors
 HAVL (AVL e) !Int#
emptyHAVL :: HAVL e
Empty HAVL (height is 0).
toHAVL :: AVL e -> HAVL e
Converts an AVL to HAVL
isEmptyHAVL :: HAVL e -> Bool

Returns True if the AVL component of an HAVL tree is empty. Note that height component is ignored, so it's OK to use this function in cases where the height is relative.

Complexity: O(1)

isNonEmptyHAVL :: HAVL e -> Bool

Returns True if the AVL component of an HAVL tree is non-empty. Note that height component is ignored, so it's OK to use this function in cases where the height is relative.

Complexity: O(1)

spliceHAVL :: HAVL e -> e -> HAVL e -> HAVL e

Splice two HAVL trees using the supplied bridging element. That is, the bridging element appears in the middle of the resulting HAVL tree. The elements of the first tree argument are to the left of the bridging element and the elements of the second tree are to the right of the bridging element.

This function does not require that the AVL heights are absolutely correct, only that the difference in supplied heights is equal to the difference in actual heights. So it's OK if the input heights both have the same unknown constant offset. (The output height will also have the same constant offset in this case.)

Complexity: O(d), where d is the absolute difference in tree heights.

joinHAVL :: HAVL e -> HAVL e -> HAVL e

Join two HAVL trees. It's OK if heights are relative (I.E. if they share same fixed offset).

Complexity: O(d), where d is the absolute difference in tree heights.

pushLHAVL :: e -> HAVL e -> HAVL e
A version of pushL for HAVL trees. It's OK if height is relative, with fixed offset. In this case the height of the result will have the same fixed offset.
pushRHAVL :: HAVL e -> e -> HAVL e
A version of pushR for HAVL trees. It's OK if height is relative, with fixed offset. In this case the height of the result will have the same fixed offset.