Safe Haskell	None
Language	Haskell2010

Data.BalBST

Contents

Helper stuff

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
- = Red
- | Black
type Height = Int
data Tree k a
- = Empty
- | Leaf !a
- | Node !Color !Height (Tree k a) !k (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 {
- fst' :: !a
- snd' :: b
}
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
- = Internal !Color !Height !k
- | Val !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 goLeft :: a -> k -> Bool extractKey :: a -> a -> k

Instances

Contravariant (TreeNavigator k) Source #
Instance details Defined in Data.BalBST Methods contramap :: (a -> b) -> TreeNavigator k b -> TreeNavigator k a # (>$) :: b -> TreeNavigator k b -> TreeNavigator k a #

ordNav :: Ord a => TreeNavigator a a Source #

ordNavBy :: Ord b => (a -> b) -> TreeNavigator b a Source #

data BalBST k a Source #

A balanced binary search tree

Constructors

BalBST
Fields nav :: !(TreeNavigator k a) toTree :: !(Tree k a)

Instances

(Show k, Show a) => Show (BalBST k a) Source #
Instance details Defined in Data.BalBST Methods showsPrec :: Int -> BalBST k a -> ShowS # show :: BalBST k a -> String # showList :: [BalBST k a] -> ShowS #

data Color Source #

Constructors

Red
Black

Instances

Eq Color Source #
Instance details Defined in Data.BalBST Methods (==) :: Color -> Color -> Bool # (/=) :: Color -> Color -> Bool #
Ord Color Source #
Instance details Defined in Data.BalBST Methods compare :: Color -> Color -> Ordering # (<) :: Color -> Color -> Bool # (<=) :: Color -> Color -> Bool # (>) :: Color -> Color -> Bool # (>=) :: Color -> Color -> Bool # max :: Color -> Color -> Color # min :: Color -> Color -> Color #
Read Color Source #
Instance details Defined in Data.BalBST Methods readsPrec :: Int -> ReadS Color # readList :: ReadS [Color] # readPrec :: ReadPrec Color # readListPrec :: ReadPrec [Color] #
Show Color Source #
Instance details Defined in Data.BalBST Methods showsPrec :: Int -> Color -> ShowS # show :: Color -> String # showList :: [Color] -> ShowS #

type Height = Int Source #

data Tree k a Source #

Constructors

Empty
Leaf !a
Node !Color !Height (Tree k a) !k (Tree k a)

Instances

(Eq a, Eq k) => Eq (Tree k a) Source #
Instance details Defined in Data.BalBST Methods (==) :: Tree k a -> Tree k a -> Bool # (/=) :: Tree k a -> Tree k a -> Bool #
(Show a, Show k) => Show (Tree k a) Source #
Instance details Defined in Data.BalBST Methods showsPrec :: Int -> Tree k a -> ShowS # show :: Tree k a -> String # showList :: [Tree k a] -> ShowS #

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

fromList' :: Ord a => [a] -> BalBST a a Source #

null :: BalBST k a -> Bool Source #

Check if the tree is empty

lookup :: Eq a => a -> BalBST k a -> Maybe a Source #

Test if an element occurs in the BST. $O(\log n)$

member :: Eq a => a -> BalBST k a -> Bool Source #

$O(\log n)$

lookupLE :: Ord k => k -> BalBST k a -> Maybe a Source #

Search for the Predecessor $O(\log n)$

insert :: a -> BalBST k a -> BalBST k a Source #

Insert an element 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)$

lookupMin :: BalBST k b -> Maybe b Source #

maxView :: BalBST k a -> Maybe (a, Tree k a) Source #

Extract the maximum from the tree $O(\log n)$

lookupMax :: BalBST k b -> Maybe b Source #

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

data Pair a b Source #

Splitting and extracting

A pair that is strict in its first argument and lazy in the second.

Constructors

Pair
Fields fst' :: !a snd' :: b

Instances

Functor (Pair a) Source #
Instance details Defined in Data.BalBST Methods fmap :: (a0 -> b) -> Pair a a0 -> Pair a b # (<$) :: a0 -> Pair a b -> Pair a a0 #
Foldable (Pair a) Source #
Instance details Defined in Data.BalBST Methods 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 # toList :: Pair a a0 -> [a0] # null :: Pair a a0 -> Bool # length :: Pair a a0 -> Int # elem :: Eq a0 => a0 -> Pair a a0 -> Bool # maximum :: Ord a0 => Pair a a0 -> a0 # minimum :: Ord a0 => Pair a a0 -> a0 # sum :: Num a0 => Pair a a0 -> a0 # product :: Num a0 => Pair a a0 -> a0 #
Traversable (Pair a) Source #
Instance details Defined in Data.BalBST Methods traverse :: Applicative f => (a0 -> f b) -> Pair a a0 -> f (Pair a b) # sequenceA :: Applicative f => Pair a (f a0) -> f (Pair a a0) # mapM :: Monad m => (a0 -> m b) -> Pair a a0 -> m (Pair a b) # sequence :: Monad m => Pair a (m a0) -> m (Pair a a0) #
(Eq a, Eq b) => Eq (Pair a b) Source #
Instance details Defined in Data.BalBST Methods (==) :: Pair a b -> Pair a b -> Bool # (/=) :: Pair a b -> Pair a b -> Bool #
(Show a, Show b) => Show (Pair a b) Source #
Instance details Defined in Data.BalBST Methods showsPrec :: Int -> Pair a b -> ShowS # show :: Pair a b -> String # showList :: [Pair a b] -> ShowS #

collect :: b -> [Pair a b] -> 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

data Split a b Source #

Result of splititng a tree

Constructors

Split a !b a

Instances

(Eq a, Eq b) => Eq (Split a b) Source #
Instance details Defined in Data.BalBST Methods (==) :: Split a b -> Split a b -> Bool # (/=) :: Split a b -> Split a b -> Bool #
(Show a, Show b) => Show (Split a b) Source #
Instance details Defined in Data.BalBST Methods showsPrec :: Int -> Split a b -> ShowS # show :: Split a b -> String # showList :: [Split a b] -> ShowS #

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.

data T k a Source #

Constructors

Internal !Color !Height !k
Val !a

Instances

(Eq k, Eq a) => Eq (T k a) Source #
Instance details Defined in Data.BalBST Methods (==) :: T k a -> T k a -> Bool # (/=) :: T k a -> T k a -> Bool #
(Ord k, Ord a) => Ord (T k a) Source #
Instance details Defined in Data.BalBST Methods compare :: T k a -> T k a -> Ordering # (<) :: T k a -> T k a -> Bool # (<=) :: T k a -> T k a -> Bool # (>) :: T k a -> T k a -> Bool # (>=) :: T k a -> T k a -> Bool # max :: T k a -> T k a -> T k a # min :: T k a -> T k a -> T k a #
(Show k, Show a) => Show (T k a) Source #
Instance details Defined in Data.BalBST Methods showsPrec :: Int -> T k a -> ShowS # show :: T k a -> String # showList :: [T k a] -> ShowS #