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

Portability portable stable http://homepages.nildram.co.uk/~ahey/em.png

Data.Tree.AVL.Split

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 `Data.Tree.AVL.Types.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)Source

Split an AVL tree from the Left. The `Int` argument n (n >= 0) specifies the split point. This function raises an error if n is negative.

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)Source

Split an AVL tree from the Right. The `Int` argument n (n >= 0) specifies the split point. This function raises an error if n is negative.

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)Source

This is a simplified version of `splitAtL` which does not return the remaining tree. The `Int` argument n (n >= 0) specifies the number of elements to take (from the left). This function raises an error if n is negative.

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)Source

This is a simplified version of `splitAtR` which does not return the remaining tree. The `Int` argument n (n >= 0) specifies the number of elements to take (from the right). This function raises an error if n is negative.

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)Source

This is a simplified version of `splitAtL` which returns the remaining tree only (rightmost elements). This function raises an error if n is negative.

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)Source

This is a simplified version of `splitAtR` which returns the remaining tree only (leftmost elements). This function raises an error if n is negative.

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 `Data.Tree.AVL.Types.size` for no reason other than to exploit this optimisation (because this is O(s) anyway).

rotateL :: AVL e -> AVL eSource

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 eSource

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)Source

Similar to `rotateL`, but returns the rotated element. This function raises an error if applied to an empty tree.

Complexity: O(log n)

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

Similar to `rotateR`, but returns the rotated element. This function raises an error if applied to an empty tree.

Complexity: O(log n)

rotateByL :: AVL e -> Int -> AVL eSource

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 eSource

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)Source

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)Source

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 eSource

This is a simplified version of `spanL` which does not return the remaining tree The result is the leftmost consecutive sequence of elements which satisfy the supplied predicate (which may be empty).

Complexity: O(n), where n is the size of the result.

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

This is a simplified version of `spanL` which does not return the tree containing the elements which satisfy the supplied predicate. The result is a tree whose leftmost element is the first to fail the predicate, starting from the left (which may be empty).

Complexity: O(n), where n is the number of elements dropped.

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

This is a simplified version of `spanR` which does not return the remaining tree The result is the rightmost consecutive sequence of elements which satisfy the supplied predicate (which may be empty).

Complexity: O(n), where n is the size of the result.

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

This is a simplified version of `spanR` which does not return the tree containing the elements which satisfy the supplied predicate. The result is a tree whose rightmost element is the first to fail the predicate, starting from the right (which may be empty).

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 `genTakeLT` function is a tree containing all those elements which are less than the notional search key. That is, all those elements for which the supplied selector returns GT (not LT as you might expect). I know that seems backwards, but it's consistent if you think about it.

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

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)Source

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)Source

Similar to `genForkL` and `genForkR`, but returns any equal element found (instead of incorporating it into the left or right tree results respectively).

Complexity: O(log n)

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

This is a simplified version of `genForkL` which returns a sorted tree containing only those elements which are less than or equal to according to the supplied selector. This function also has the synonym `genDropGT`.

Complexity: O(log n)

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

A synonym for `genTakeLE`.

Complexity: O(log n)

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

This is a simplified version of `genForkR` which returns a sorted tree containing only those elements which are less than according to the supplied selector. This function also has the synonym `genDropGE`.

Complexity: O(log n)

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

A synonym for `genTakeLT`.

Complexity: O(log n)

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

This is a simplified version of `genForkL` which returns a sorted tree containing only those elements which are greater according to the supplied selector. This function also has the synonym `genDropLE`.

Complexity: O(log n)

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

A synonym for `genTakeGT`.

Complexity: O(log n)

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

This is a simplified version of `genForkR` which returns a sorted tree containing only those elements which are greater or equal to according to the supplied selector. This function also has the synonym `genDropLT`.

Complexity: O(log n)

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

A synonym for `genTakeGE`.

Complexity: O(log n)