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

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

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

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

Functions for splitting AVL trees. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

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

Taking fixed size lumps of tree. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Bear in mind that the tree size (s) is not stored in the AVL data structure, but if it is
already known for other reasons then for (n > s/2) using the appropriate complementary
function with argument (s-n) will be faster.
But it's probably not worth invoking size for no reason other than to
exploit this optimisation (because this is O(s) anyway).
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

splitAtL :: Int -> AVL e -> Either Int (AVL e, AVL e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Split an AVL tree from the Left. The If the tree size is greater than n the result is (Right (l,r)) where l contains the leftmost n elements and r contains the remaining rightmost elements (r will be non-empty). If the tree size is less than or equal to n then the result is (Left s), where s is tree size. An empty tree will always yield a result of (Left 0). Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

splitAtR :: Int -> AVL e -> Either Int (AVL e, AVL e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Split an AVL tree from the Right. The If the tree size is greater than n the result is (Right (l,r)) where r contains the rightmost n elements and l contains the remaining leftmost elements (l will be non-empty). If the tree size is less than or equal to n then the result is (Left s), where s is tree size. An empty tree will always yield a result of (Left 0). Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

takeL :: Int -> AVL e -> Either Int (AVL e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

This is a simplified version of If the tree size is greater than n the result is (Right l) where l contains the leftmost n elements. If the tree size is less than or equal to n then the result is (Left s), where s is tree size. An empty tree will always yield a result of (Left 0). Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

takeR :: Int -> AVL e -> Either Int (AVL e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

This is a simplified version of If the tree size is greater than n the result is (Right r) where r contains the rightmost n elements. If the tree size is less than or equal to n then the result is (Left s), where s is tree size. An empty tree will always yield a result of (Left 0). Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

dropL :: Int -> AVL e -> Either Int (AVL e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

This is a simplified version of If the tree size is greater than n the result is (Right r) where r contains the remaining elements (r will be non-empty). If the tree size is less than or equal to n then the result is (Left s), where s is tree size. An empty tree will always yield a result of (Left 0). Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

dropR :: Int -> AVL e -> Either Int (AVL e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

This is a simplified version of If the tree size is greater than n the result is (Right l) where l contains the remaining elements (l will be non-empty). If the tree size is less than or equal to n then the result is (Left s), where s is tree size. An empty tree will always yield a result of (Left 0). Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Rotations. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Bear in mind that the tree size (s) is not stored in the AVL data structure, but if it is
already known for other reasons then for (n > s/2) using the appropriate complementary
function with argument (s-n) will be faster.
But it's probably not worth invoking size for no reason other than to exploit this optimisation
(because this is O(s) anyway).
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

rotateL :: AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Rotate an AVL tree one place left. This function pops the leftmost element and pushes into the rightmost position. An empty tree yields an empty tree. Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

rotateR :: AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Rotate an AVL tree one place right. This function pops the rightmost element and pushes into the leftmost position. An empty tree yields an empty tree. Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

popRotateL :: AVL e -> (e, AVL e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

popRotateR :: AVL e -> (AVL e, e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

rotateByL :: AVL e -> Int -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Rotate an AVL tree left by n places. If s is the size of the tree then ordinarily n should be in the range [0..s-1]. However, this function will deliver a correct result for any n (n<0 or n>=s), the actual rotation being given by (n `mod` s) in such cases. The result of rotating an empty tree is an empty tree. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

rotateByR :: AVL e -> Int -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Rotate an AVL tree right by n places. If s is the size of the tree then ordinarily n should be in the range [0..s-1]. However, this function will deliver a correct result for any n (n<0 or n>=s), the actual rotation being given by (n `mod` s) in such cases. The result of rotating an empty tree is an empty tree. Complexity: O(n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Taking lumps of tree according to a supplied predicate. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

Span an AVL tree from the left, using the supplied predicate. This function returns a pair of trees (l,r), where l contains the leftmost consecutive elements which satisfy the predicate. The leftmost element of r (if any) is the first to fail the predicate. Either of the resulting trees may be empty. Element ordering is preserved. Complexity: O(n), where n is the size of l. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

Span an AVL tree from the right, using the supplied predicate. This function returns a pair of trees (l,r), where r contains the rightmost consecutive elements which satisfy the predicate. The rightmost element of l (if any) is the first to fail the predicate. Either of the resulting trees may be empty. Element ordering is preserved. Complexity: O(n), where n is the size of r. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

This is a simplified version of Complexity: O(n), where n is the size of the result. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

This is a simplified version of Complexity: O(n), where n is the number of elements dropped. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

This is a simplified version of Complexity: O(n), where n is the size of the result. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

This is a simplified version of Complexity: O(n), where n is the number of elements dropped. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Taking lumps of sorted trees.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Prepare to get confused. All these functions adhere to the same Ordering convention as is used for searches. That is, if the supplied selector returns LT that means the search key is less than the current tree element. Or put another way, the current tree element is greater than the search key. So (for example) the result of the | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genForkL :: (e -> Ordering) -> AVL e -> (AVL e, AVL e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Divide a sorted AVL tree into left and right sorted trees (l,r), such that l contains all the elements less than or equal to according to the supplied selector and r contains all the elements greater than according to the supplied selector. Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genForkR :: (e -> Ordering) -> AVL e -> (AVL e, AVL e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Divide a sorted AVL tree into left and right sorted trees (l,r), such that l contains all the elements less than supplied selector and r contains all the elements greater than or equal to the supplied selector. Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genFork :: (e -> COrdering a) -> AVL e -> (AVL e, Maybe a, AVL e) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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

genTakeLE :: (e -> Ordering) -> AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

This is a simplified version of Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genDropGT :: (e -> Ordering) -> AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

A synonym for Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genTakeLT :: (e -> Ordering) -> AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

This is a simplified version of Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genDropGE :: (e -> Ordering) -> AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

A synonym for Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genTakeGT :: (e -> Ordering) -> AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

This is a simplified version of Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genDropLE :: (e -> Ordering) -> AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

A synonym for Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genTakeGE :: (e -> Ordering) -> AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

This is a simplified version of Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

genDropLT :: (e -> Ordering) -> AVL e -> AVL e | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

A synonym for Complexity: O(log n) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Produced by Haddock version 0.7 |