| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Description | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

List related utilities for AVL trees. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Synopsis | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Converting AVL trees to Lists (fixed element order). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

These functions are lazy and allow normal lazy list processing style to be used (without necessarily converting the entire tree to a list in one gulp). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

asListL :: AVL e -> [e] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

List AVL tree contents in left to right order. The resulting list in ascending order if the tree is sorted. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

toListL :: AVL e -> [e] -> [e] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Join the AVL tree contents to an existing list in left to right order. This is a ++ free function which behaves as if defined thusly.. avl `toListL` as = (asListL avl) ++ as Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

asListR :: AVL e -> [e] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

List AVL tree contents in right to left order. The resulting list in descending order if the tree is sorted. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

toListR :: AVL e -> [e] -> [e] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Join the AVL tree contents to an existing list in right to left order. This is a ++ free function which behaves as if defined thusly.. avl `toListR` as = (asListR avl) ++ as Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Converting Lists to AVL trees (fixed element order). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

asTreeLenL :: Int -> [e] -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Convert a list of known length into an AVL tree, such that the head of the list becomes the leftmost tree element. The resulting tree is flat (and also sorted if the supplied list is sorted in ascending order). If the actual length of the list is not the same as the supplied length then an error will be raised. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

asTreeL :: [e] -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

As Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

asTreeLenR :: Int -> [e] -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Convert a list of known length into an AVL tree, such that the head of the list becomes the rightmost tree element. The resulting tree is flat (and also sorted if the supplied list is sorted in descending order). If the actual length of the list is not the same as the supplied length then an error will be raised. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

asTreeR :: [e] -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

As Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Converting unsorted Lists to sorted AVL trees. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genAsTree :: (e -> e -> COrdering e) -> [e] -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Invokes Complexity: O(n.(log n)) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Pushing unsorted Lists in sorted AVL trees. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genPushList :: (e -> e -> COrdering e) -> AVL e -> [e] -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Push the elements of an unsorted List in a sorted AVL tree using the supplied combining comparison. Complexity: O(n.(log (m+n))) where n is the list length, m is the tree size. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Some analogues of common List functions. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

reverseAVL :: AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Reverse an AVL tree (swaps and reverses left and right sub-trees). The resulting tree is the mirror image of the original. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

mapAVL :: (a -> b) -> AVL a -> AVL b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Apply a function to every element in an AVL tree. This function preserves the tree shape.
There is also a strict version of this function ( N.B. If the tree is sorted the result of this operation will only be sorted if the applied function preserves ordering (for some suitable ordering definition). Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

mapAVL' :: (a -> b) -> AVL a -> AVL b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Similar to Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

traverseAVL :: Applicative f => (a -> f b) -> AVL a -> f (AVL b) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

replicateAVL :: Int -> e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Construct a flat AVL tree of size n (n>=0), where all elements are identical. Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

filterViaList :: (e -> Bool) -> AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Remove all AVL tree elements which do not satisfy the supplied predicate. Element ordering is preserved. The resulting tree is flat. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

mapMaybeViaList :: (a -> Maybe b) -> AVL a -> AVL b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Remove all AVL tree elements for which the supplied function returns Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

partitionAVL :: (e -> Bool) -> AVL e -> (AVL e, AVL e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Partition an AVL tree using the supplied predicate. The first AVL tree in the resulting pair contains all elements for which the predicate is True, the second contains all those for which the predicate is False. Element ordering is preserved. Both of the resulting trees are flat. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Folds | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Note that unlike folds over lists (foldr and foldl), there is no
significant difference between left and right folds in AVL trees, other
than which side of the tree each starts with. Both involve tail and non-tail recursion.
Therefore this library provides strict and lazy versions of both.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldrAVL :: (e -> a -> a) -> a -> AVL e -> a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The AVL equivalent of It behaves as if defined.. foldrAVL f a avl = foldr f a (asListL avl) For example, the asListL = foldrAVL (:) [] Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldrAVL' :: (e -> a -> a) -> a -> AVL e -> a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The strict version of Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldr1AVL :: (e -> e -> e) -> AVL e -> e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The AVL equivalent of foldr1AVL f avl = foldr1 f (asListL avl) This function raises an error if the tree is empty. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldr1AVL' :: (e -> e -> e) -> AVL e -> e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The strict version of Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldr2AVL :: (e -> a -> a) -> (e -> a) -> AVL e -> a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

This fold is a hybrid between Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldr2AVL' :: (e -> a -> a) -> (e -> a) -> AVL e -> a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The strict version of Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldlAVL :: (a -> e -> a) -> a -> AVL e -> a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The AVL equivalent of foldlAVL f a avl = foldl f a (asListL avl) For example, the asListR = foldlAVL (flip (:)) [] Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldlAVL' :: (a -> e -> a) -> a -> AVL e -> a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The strict version of Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldl1AVL :: (e -> e -> e) -> AVL e -> e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The AVL equivalent of foldl1AVL f avl = foldl1 f (asListL avl) This function raises an error if the tree is empty. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldl1AVL' :: (e -> e -> e) -> AVL e -> e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The strict version of Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldl2AVL :: (a -> e -> a) -> (e -> a) -> AVL e -> a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

This fold is a hybrid between Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

foldl2AVL' :: (a -> e -> a) -> (e -> a) -> AVL e -> a | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The strict version of Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Tree flattening utilities. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

None of these functions preserve the tree shape (of course). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

flatten :: AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Flatten an AVL tree, preserving the ordering of the tree elements. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

flatReverse :: AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Similar to Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

flatMap :: (a -> b) -> AVL a -> AVL b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Similar to Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

flatMap' :: (a -> b) -> AVL a -> AVL b | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Same as Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Sorting. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Nothing to do with AVL trees really. But using AVL trees do give an O(n.(log n)) sort algorithm for free, so here it is. These functions all consume the entire input list to construct a sorted AVL tree and then read the elements out as a list (lazily). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genSortAscending :: (e -> e -> COrdering e) -> [e] -> [e] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Uses the supplied combining comparison to sort list elements into ascending order. Multiple occurences of the same element are eliminated (they are combined in some way). Complexity: O(n.(log n)) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genSortDescending :: (e -> e -> COrdering e) -> [e] -> [e] | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Uses the supplied combining comparison to sort list elements into descending order. Multiple occurences of the same element are eliminated (they are combined in some way). Complexity: O(n.(log n)) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Produced by Haddock version 0.7 |