Haskell Hierarchical Libraries (collections package)ContentsIndex
Data.Tree.AVL.Read
Portabilityportable
Stabilitystable
Maintainerhttp://homepages.nildram.co.uk/~ahey/em.png
Contents
Reading from extreme left or right.
Reading from sorted trees.
Simple searches of sorted trees.
Description
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.
Synopsis
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 -> 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)

Produced by Haddock version 0.7