Safe Haskell  None 

Language  Haskell2010 
Synopsis
 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
 lookupLE :: Ord k => k > BalBST k a > Maybe a
 insert :: a > BalBST k a > BalBST k a
 delete :: Eq a => a > BalBST k a > BalBST k a
 minView :: BalBST k a > Maybe (a, Tree k a)
 lookupMin :: BalBST k b > Maybe b
 maxView :: BalBST k a > Maybe (a, Tree k a)
 lookupMax :: BalBST k b > Maybe b
 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(n\log n)\)
lookup :: Eq a => a > BalBST k a > Maybe a Source #
Test if an element occurs in the BST. \(O(\log n)\)
delete :: Eq a => a > BalBST k a > BalBST k a Source #
Delete (one occurance of) an element. \(O(\log n)\)
minView :: BalBST k a > Maybe (a, Tree k a) Source #
Extract the minimum from the tree \(O(\log n)\)
maxView :: BalBST k a > Maybe (a, Tree k a) Source #
Extract the maximum from the tree \(O(\log n)\)
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(\log n)\)
joinWith :: TreeNavigator k a > Tree k a > Tree k a > Tree k a Source #
Joins two BSTs' with a specific Tree Navigator
\(O(\log n)\)
Splitting and extracting
A pair that is strict in its first argument and lazy in the second.
Instances
Functor (Pair a) Source #  
Foldable (Pair a) Source #  
Defined in Data.BalBST fold :: Monoid m => Pair a m > m # foldMap :: Monoid m => (a0 > m) > Pair a a0 > m # foldr :: (a0 > b > b) > b > Pair a a0 > b # foldr' :: (a0 > b > b) > b > Pair a a0 > b # foldl :: (b > a0 > b) > b > Pair a a0 > b # foldl' :: (b > a0 > b) > b > Pair a a0 > b # foldr1 :: (a0 > a0 > a0) > Pair a a0 > a0 # foldl1 :: (a0 > a0 > a0) > Pair a a0 > a0 # elem :: Eq a0 => a0 > Pair a a0 > Bool # maximum :: Ord a0 => Pair a a0 > a0 # minimum :: Ord a0 => Pair a a0 > a0 #  
Traversable (Pair a) Source #  
(Eq a, Eq b) => Eq (Pair a b) Source #  
(Show a, Show b) => Show (Pair a b) Source #  
extractPrefix :: BalBST k a > [Pair a (Tree k a)] Source #
Extract a prefix from the tree, i.e. a repeated minView
\(O(\log n +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(\log n +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(\log n)\)
splitMonotone :: (a > Bool) > BalBST k a > (BalBST k a, BalBST k a) Source #
split based on a monotonic predicate
\(O(\log n)\)
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(\log n)\)
unsafeMax :: Tree k a > a Source #
Get the maximum in the tree. Errors when the tree is empty
\(O(\log n)\)