| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Data.BalBST
Contents
- 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
Constructors
| Nav | |
Fields
| |
ordNav :: Ord a => TreeNavigator a a Source #
ordNavBy :: Ord b => (a -> b) -> TreeNavigator b a Source #
A balanced binary search tree
Constructors
| BalBST | |
Fields
| |
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)\)
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.
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
Constructors
| 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)\)