collections-0.3.1: Useful standard collections types and related functions.

Portabilityportable
Stabilitystable
Maintainerhttp://homepages.nildram.co.uk/~ahey/em.png

Data.Tree.AVL

Contents

Description

Many of the functions defined by this package make use of generalised comparison functions which return a variant of the Prelude Ordering data type: Data.COrdering.COrdering. These are refered to as "combining comparisons". (This is because they combine "equal" values in some manner defined by the user.)

The idea is that using this simple mechanism you can define many practical and useful variations of tree (or general set) operations from a few generic primitives, something that would not be so easy using plain Ordering comparisons (overloaded or otherwise).

Functions which involve searching a tree really only require a single argument function which takes the current tree element value as argument and returns an Ordering or Data.COrdering.COrdering to direct the next stage of the search down the left or right sub-trees (or stop at the current element). For documentation purposes, these functions are called "selectors" throughout this library. Typically a selector will be obtained by partially applying the appropriate combining comparison with the value or key being searched for. For example..

 mySelector :: Int -> Ordering               Tree elements are Ints
 or..
 mySelector :: (key,val) -> COrdering val    Tree elements are (key,val) pairs

Please read the notes in the Data.Tree.AVL.Types module documentation too.

Synopsis

Conversion utilities.

set2AVL :: Set a -> AVL aSource

Convert a Data.Set.Set (from the base package Data.Set module) to a sorted AVL tree. Elements and element ordering are preserved (ascending order is left to right).

Complexity: O(n)

avl2Set :: AVL a -> Set aSource

Convert a sorted AVL tree to a Data.Set.Set (from the base package Data.Set module). Elements and element ordering are preserved.

Complexity: O(n)

map2AVL :: Map key val -> AVL (key, val)Source

Convert a Data.Map.Map (from the base package Data.Map module) to a sorted (by key) AVL tree. Elements and element ordering are preserved (ascending order is left to right).

Complexity: O(n)

avl2Map :: AVL (key, val) -> Map key valSource

Convert a sorted (by key) AVL tree to a Data.Map.Map (from the base package Data.Map module). Elements and element ordering are preserved.

Complexity: O(n)

Modules.