Haskell Hierarchical Libraries (collections package)ContentsIndex
Data.Tree.AVL.Internals.BinPath
Portabilityportable
Stabilitystable
Maintainerhttp://homepages.nildram.co.uk/~ahey/em.png
Description
This module provides a cheap but extremely limited and dangerous alternative to using the Zipper, hence it's for INTERNAL USE ONLY. A BinPath provides a way of finding a particular element in an AVL tree again without doing any comparisons. But a BinPath is ONLY VALID IF THE TREE SHAPE DOES NOT CHANGE.
Synopsis
data BinPath a
= FullBP !Int# a
| EmptyBP !Int#
genFindPath :: (e -> Ordering) -> AVL e -> Int#
genOpenPath :: (e -> Ordering) -> AVL e -> BinPath e
genOpenPathWith :: (e -> COrdering a) -> AVL e -> BinPath a
readPath :: Int# -> AVL e -> e
writePath :: Int# -> e -> AVL e -> AVL e
insertPath :: Int# -> e -> AVL e -> AVL e
sel :: Int# -> Ordering
goL :: Int# -> Int#
goR :: Int# -> Int#
Documentation
data BinPath a
Int fields are search depth and path bits respecively. The path bits consist of a a string of depth bits, left justified. MSB of 0 means go left, MSB of 1 means go right.
Constructors
FullBP !Int# a
EmptyBP !Int#
genFindPath :: (e -> Ordering) -> AVL e -> Int#

Find the path to a AVL tree element, returns -1 (invalid path) if element not found

Complexity: O(log n)

genOpenPath :: (e -> Ordering) -> AVL e -> BinPath e

Get the BinPath of an element using the supplied selector.

Complexity: O(log n)

genOpenPathWith :: (e -> COrdering a) -> AVL e -> BinPath a

Get the BinPath of an element using the supplied (combining) selector.

Complexity: O(log n)

readPath :: Int# -> AVL e -> e

Read a tree element. Assumes the path bits were extracted from FullBP constructor. Raises an error if the path leads to an empty tree.

Complexity: O(log n)

writePath :: Int# -> e -> AVL e -> AVL e

Overwrite a tree element. Assumes the path bits were extracted from FullBP constructor. Raises an error if the path leads to an empty tree.

N.B This operation does not change tree shape (no insertion occurs).

Complexity: O(log n)

insertPath :: Int# -> e -> AVL e -> AVL e

Inserts a new tree element. Assumes the path bits were extracted from a EmptyBP constructor. This function replaces the first Empty node it encounters with the supplied value, regardless of the current path bits (which are not checked). DO NOT USE THIS FOR REPLACING ELEMENTS ALREADY PRESENT IN THE TREE (use writePath for this).

Complexity: O(log n)

sel :: Int# -> Ordering
goL :: Int# -> Int#
goR :: Int# -> Int#
Produced by Haddock version 0.7