Safe Haskell | None |
---|---|
Language | Haskell2010 |
- data TreeNavigator k a = Nav {
- goLeft :: a -> k -> Bool
- extractKey :: a -> a -> k
- ordNav :: Ord a => TreeNavigator a a
- ordNavBy :: Ord b => (a -> b) -> TreeNavigator b a
- data BalBST k a = BalBST {
- nav :: !(TreeNavigator k a)
- toTree :: !(Tree k a)
- data Color
- type Height = Int
- data Tree k a
- empty :: TreeNavigator k a -> BalBST k a
- fromList :: TreeNavigator k a -> [a] -> BalBST k a
- fromList' :: Ord a => [a] -> BalBST a a
- null :: BalBST k a -> Bool
- lookup :: Eq a => a -> BalBST k a -> Maybe a
- member :: Eq a => a -> BalBST k a -> Bool
- insert :: a -> BalBST k a -> BalBST k a
- minView :: BalBST k a -> Maybe (a, Tree k a)
- maxView :: BalBST k a -> Maybe (a, Tree k a)
- join :: BalBST k a -> BalBST k a -> BalBST k a
- joinWith :: TreeNavigator k a -> Tree k a -> Tree k a -> Tree k a
- data Pair a b = Pair {}
- collect :: b -> [Pair a b] -> Pair [a] b
- extractPrefix :: BalBST k a -> [Pair a (Tree k a)]
- extractSuffix :: BalBST k a -> [Pair a (Tree k a)]
- data Split a b = Split a !b a
- split :: Eq a => a -> BalBST k a -> Split (Tree k a) (Maybe a)
- splitMonotone :: (a -> Bool) -> BalBST k a -> (BalBST k a, BalBST k a)
- splitExtract :: (a -> Bool) -> (a -> Bool) -> BalBST k a -> Split (BalBST k a) ([a], [a])
- data T k a
- toRoseTree :: Tree k a -> Maybe (Tree (T k a))
- showTree :: (Show k, Show a) => BalBST k a -> String
- unsafeMin :: Tree k a -> a
- unsafeMax :: Tree k a -> a
- toList :: BalBST k a -> [a]
- toList' :: Tree k a -> [a]
- black :: Height -> Tree k a -> k -> Tree k a -> Tree k a
- red :: Height -> Tree k a -> k -> Tree k a -> Tree k a
- blacken :: Tree k a -> Tree k a
- balance :: Color -> Height -> Tree k a -> k -> Tree k a -> Tree k a
- mkNode :: Height -> Tree k a -> k -> Tree k a -> k -> Tree k a -> k -> Tree k a -> Tree k a
- height :: Tree k a -> Height
Documentation
data TreeNavigator k a Source #
Describes how to search in a tree
Nav | |
|
ordNav :: Ord a => TreeNavigator a a Source #
ordNavBy :: Ord b => (a -> b) -> TreeNavigator b a Source #
A balanced binary search tree
BalBST | |
|
empty :: TreeNavigator k a -> BalBST k a Source #
Creates an empty BST
fromList :: TreeNavigator k a -> [a] -> BalBST k a Source #
O(nlogn)
join :: BalBST k a -> BalBST k a -> BalBST k a Source #
Joins two BSTs. Assumes that the ranges are disjoint. It takes the left Tree nav
O(logn)
joinWith :: TreeNavigator k a -> Tree k a -> Tree k a -> Tree k a Source #
Joins two BSTs' with a specific Tree Navigator
O(logn)
Splitting and extracting
A pair that is strict in its first argument and lazy in the second.
extractPrefix :: BalBST k a -> [Pair a (Tree k a)] Source #
Extract a prefix from the tree, i.e. a repeated minView
O(logn+k), where k is the size of the extracted part
extractSuffix :: BalBST k a -> [Pair a (Tree k a)] Source #
Extract a suffix from the tree, i.e. a repeated minView
O(logn+k), where k is the size of the extracted part
Result of splititng a tree
Split a !b a |
split :: Eq a => a -> BalBST k a -> Split (Tree k a) (Maybe a) Source #
Splits the tree at x. Note that if x occurs more often, no guarantees are given which one is found.
O(logn)
splitMonotone :: (a -> Bool) -> BalBST k a -> (BalBST k a, BalBST k a) Source #
split based on a monotonic predicate
O(logn)
splitExtract :: (a -> Bool) -> (a -> Bool) -> BalBST k a -> Split (BalBST k a) ([a], [a]) Source #
Splits at a given monotone predicate p, and then selects everything that satisfies the predicate sel.
unsafeMin :: Tree k a -> a Source #
Get the minimum in the tree. Errors when the tree is empty
O(logn)
unsafeMax :: Tree k a -> a Source #
Get the maximum in the tree. Errors when the tree is empty
O(logn)