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

Stability | stable |

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

This module defines useful functions for searching AVL trees and writing information to a particular element. The functions defined here may alter the content of a tree (values of tree elements) but not the structure of a tree (no insertion or deletion).

- writeL :: e -> AVL e -> AVL e
- tryWriteL :: e -> AVL e -> Maybe (AVL e)
- writeR :: AVL e -> e -> AVL e
- tryWriteR :: AVL e -> e -> Maybe (AVL e)
- genWrite :: (e -> COrdering e) -> AVL e -> AVL e
- genWriteFast :: (e -> COrdering e) -> AVL e -> AVL e
- genTryWrite :: (e -> COrdering e) -> AVL e -> Maybe (AVL e)
- genWriteMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> AVL e
- genTryWriteMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> Maybe (AVL e)

## Writing to extreme left or right.

I'm not sure these are likely to be much use in practice, but they're simple enough to implement so are included for the sake of completeness.

writeL :: e -> AVL e -> AVL eSource

Replace the left most element of a tree with the supplied new element. This function raises an error if applied to an empty tree.

Complexity: O(log n)

writeR :: AVL e -> e -> AVL eSource

Replace the right most element of a tree with the supplied new element. This function raises an error if applied to an empty tree.

Complexity: O(log n)

# Writing to *sorted* trees.

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

A general purpose function to perform a search of a tree, using the supplied selector.
If the search succeeds the found element is replaced by the value (`e`

) of the `(`

constructor returned by the selector. If the search fails this function returns the original tree.
`Eq`

e)

Complexity: O(log n)

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

Functionally identical to `genWrite`

, but returns an identical tree (one with all the nodes on
the path duplicated) if the search fails. This should probably only be used if you know the
search will succeed and will return an element which is different from that already present.

Complexity: O(log n)

genTryWriteMaybe :: (e -> COrdering (Maybe e)) -> AVL e -> Maybe (AVL e)Source

Similar to `genTryWrite`

, but also returns the original tree if the search succeeds but
the selector returns `(`

. (This version is intended to help reduce heap burn
rate if it's likely that no modification of the value is needed.)
`Eq`

`Nothing`

)

Complexity: O(log n)