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

Stability | stable |

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

This module defines useful functions for searching AVL trees and reading information from a particular element. The functions defined here do not alter either the content or the structure of a tree.

- assertReadL :: AVL e -> e
- tryReadL :: AVL e -> Maybe e
- assertReadR :: AVL e -> e
- tryReadR :: AVL e -> Maybe e
- genAssertRead :: AVL e -> (e -> COrdering a) -> a
- genTryRead :: AVL e -> (e -> COrdering a) -> Maybe a
- genTryReadMaybe :: AVL e -> (e -> COrdering (Maybe a)) -> Maybe a
- genDefaultRead :: a -> AVL e -> (e -> COrdering a) -> a
- genContains :: AVL e -> (e -> Ordering) -> Bool

# Reading from extreme left or right.

assertReadL :: AVL e -> eSource

Read the leftmost element from a *non-empty* tree. Raises an error if the tree is empty.
If the tree is sorted this will return the least element.

Complexity: O(log n)

tryReadL :: AVL e -> Maybe eSource

Similar to `assertReadL`

but returns `Nothing`

if the tree is empty.

Complexity: O(log n)

assertReadR :: AVL e -> eSource

Read the rightmost element from a *non-empty* tree. Raises an error if the tree is empty.
If the tree is sorted this will return the greatest element.

Complexity: O(log n)

tryReadR :: AVL e -> Maybe eSource

Similar to `assertReadR`

but returns `Nothing`

if the tree is empty.

Complexity: O(log n)

# Reading from *sorted* trees.

genAssertRead :: AVL e -> (e -> COrdering a) -> aSource

General purpose function to perform a search of a sorted tree, using the supplied selector. This function raises a error if the search fails.

Complexity: O(log n)

genTryRead :: AVL e -> (e -> COrdering a) -> Maybe aSource

General purpose function to perform a search of a sorted tree, using the supplied selector.
This function is similar to `genAssertRead`

, but returns `Nothing`

if the search failed.

Complexity: O(log n)

genDefaultRead :: a -> AVL e -> (e -> COrdering a) -> aSource

General purpose function to perform a search of a sorted tree, using the supplied selector.
This function is similar to `genAssertRead`

, but returns a the default value (first argument) if
the search fails.

Complexity: O(log n)

# Simple searches of *sorted* trees.

genContains :: AVL e -> (e -> Ordering) -> BoolSource

General purpose function to perform a search of a sorted tree, using the supplied selector. Returns True if matching element is found.

Complexity: O(log n)