Portability | portable |
---|---|

Stability | stable |

Maintainer | http://homepages.nildram.co.uk/~ahey/em.png |

This module defines functions for searching AVL trees and pushing a new element in the tree (or modifying the value of an existing element). The functions defined here may alter the content of a tree (value of an existing tree element) and also the structure of a tree (by adding a new element).

# Pushing on extreme left or right.

pushL :: e -> AVL e -> AVL eSource

Push a new element in the leftmost position of an AVL tree. No comparison or searching is involved.

Complexity: O(log n)

pushR :: AVL e -> e -> AVL eSource

Push a new element in the rightmost position of an AVL tree. No comparison or searching is involved.

Complexity: O(log n)

# Pushing on *sorted* trees.

genPush :: (e -> COrdering e) -> e -> AVL e -> AVL eSource

General push. This function searches the AVL tree using the supplied selector. If a matching element
is found it's replaced by the value (`e`

) returned in the `(`

constructor returned by the selector.
If no match is found then the default element value is added at in the appropriate position in the tree.
`Eq`

e)

Note that for this to work properly requires that the selector behave as if it were comparing the (potentially) new default element with existing tree elements, even if it isn't.

Note also that this function is *non-strict* in it's second argument (the default value which
is inserted if the search fails or is discarded if the search succeeds). If you want
to force evaluation, but only if it's actually incorprated in the tree, then use `genPush'`

Complexity: O(log n)

genPush' :: (e -> COrdering e) -> e -> AVL e -> AVL eSource

Almost identical to `genPush`

, but this version forces evaluation of the default new element
(second argument) if no matching element is found. Note that it does *not* do this if
a matching element is found, because in this case the default new element is discarded
anyway. Note also that it does not force evaluation of any replacement value provided by the
selector (if it returns Eq). (You have to do that yourself if that's what you want.)

Complexity: O(log n)

genPushMaybe :: (e -> COrdering (Maybe e)) -> e -> AVL e -> AVL eSource

Similar to `genPush`

, but returns the original tree if the combining comparison returns
`(`

. So this function can be used reduce heap burn rate by avoiding duplication
of nodes on the insertion path. But it may also be marginally slower otherwise.
`Eq`

`Nothing`

)

Note that this function is *non-strict* in it's second argument (the default value which
is inserted in the search fails or is discarded if the search succeeds). If you want
to force evaluation, but only if it's actually incorprated in the tree, then use `genPushMaybe'`

Complexity: O(log n)

genPushMaybe' :: (e -> COrdering (Maybe e)) -> e -> AVL e -> AVL eSource

Almost identical to `genPushMaybe`

, but this version forces evaluation of the default new element
(second argument) if no matching element is found. Note that it does *not* do this if
a matching element is found, because in this case the default new element is discarded
anyway.

Complexity: O(log n)