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

Stability | stable |

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

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.

- set2AVL :: Set a -> AVL a
- avl2Set :: AVL a -> Set a
- map2AVL :: Map key val -> AVL (key, val)
- avl2Map :: AVL (key, val) -> Map key val
- module Data.Tree.AVL.Types
- module Data.Tree.AVL.Size
- module Data.Tree.AVL.Read
- module Data.Tree.AVL.Write
- module Data.Tree.AVL.Push
- module Data.Tree.AVL.Delete
- module Data.Tree.AVL.List
- module Data.Tree.AVL.Join
- module Data.Tree.AVL.Split
- module Data.Tree.AVL.Set
- module Data.Tree.AVL.Zipper

# 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.

module Data.Tree.AVL.Types

module Data.Tree.AVL.Size

module Data.Tree.AVL.Read

module Data.Tree.AVL.Write

module Data.Tree.AVL.Push

module Data.Tree.AVL.Delete

module Data.Tree.AVL.List

module Data.Tree.AVL.Join

module Data.Tree.AVL.Split

module Data.Tree.AVL.Set

module Data.Tree.AVL.Zipper