Data.Tree.AVL.Read

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.

Reading from extreme left or right.

assertReadL :: AVL e -> e

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 e

Similar to assertReadL but returns Nothing if the tree is empty.

Complexity: O(log n)

assertReadR :: AVL e -> e

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 e

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) -> a

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 a

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)

genTryReadMaybe :: AVL e -> (e -> COrdering (Maybe a)) -> Maybe a

This version returns the result of the selector (without adding a Just wrapper) if the search succeeds, or Nothing if it fails.

Complexity: O(log n)

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

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) -> Bool

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)