hgeometry-0.6.0.0: Geometric Algorithms, Data structures, and Data types.

Safe HaskellNone
LanguageHaskell2010

Data.BalBST

Contents

Synopsis

Documentation

data TreeNavigator k a Source #

Describes how to search in a tree

Constructors

Nav 

Fields

Instances

Contravariant (TreeNavigator k) Source # 

Methods

contramap :: (a -> b) -> TreeNavigator k b -> TreeNavigator k a #

(>$) :: b -> TreeNavigator k b -> TreeNavigator k a #

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

data BalBST k a Source #

A balanced binary search tree

Constructors

BalBST 

Fields

Instances

(Show k, Show a) => Show (BalBST k a) Source # 

Methods

showsPrec :: Int -> BalBST k a -> ShowS #

show :: BalBST k a -> String #

showList :: [BalBST k a] -> ShowS #

data Tree k a Source #

Constructors

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

Instances

(Eq k, Eq a) => Eq (Tree k a) Source # 

Methods

(==) :: Tree k a -> Tree k a -> Bool #

(/=) :: Tree k a -> Tree k a -> Bool #

(Show k, Show a) => Show (Tree k a) Source # 

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

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

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

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

Instances

Functor (Pair a) Source # 

Methods

fmap :: (a -> b) -> Pair a a -> Pair a b #

(<$) :: a -> Pair a b -> Pair a a #

Foldable (Pair a) Source # 

Methods

fold :: Monoid m => Pair a m -> m #

foldMap :: Monoid m => (a -> m) -> Pair a a -> m #

foldr :: (a -> b -> b) -> b -> Pair a a -> b #

foldr' :: (a -> b -> b) -> b -> Pair a a -> b #

foldl :: (b -> a -> b) -> b -> Pair a a -> b #

foldl' :: (b -> a -> b) -> b -> Pair a a -> b #

foldr1 :: (a -> a -> a) -> Pair a a -> a #

foldl1 :: (a -> a -> a) -> Pair a a -> a #

toList :: Pair a a -> [a] #

null :: Pair a a -> Bool #

length :: Pair a a -> Int #

elem :: Eq a => a -> Pair a a -> Bool #

maximum :: Ord a => Pair a a -> a #

minimum :: Ord a => Pair a a -> a #

sum :: Num a => Pair a a -> a #

product :: Num a => Pair a a -> a #

Traversable (Pair a) Source # 

Methods

traverse :: Applicative f => (a -> f b) -> Pair a a -> f (Pair a b) #

sequenceA :: Applicative f => Pair a (f a) -> f (Pair a a) #

mapM :: Monad m => (a -> m b) -> Pair a a -> m (Pair a b) #

sequence :: Monad m => Pair a (m a) -> m (Pair a a) #

(Eq b, Eq a) => Eq (Pair a b) Source # 

Methods

(==) :: Pair a b -> Pair a b -> Bool #

(/=) :: Pair a b -> Pair a b -> Bool #

(Show b, Show a) => Show (Pair a b) Source # 

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 b, Eq a) => Eq (Split a b) Source # 

Methods

(==) :: Split a b -> Split a b -> Bool #

(/=) :: Split a b -> Split a b -> Bool #

(Show b, Show a) => Show (Split a b) Source # 

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 a, Eq k) => Eq (T k a) Source # 

Methods

(==) :: T k a -> T k a -> Bool #

(/=) :: T k a -> T k a -> Bool #

(Ord a, Ord k) => Ord (T k a) Source # 

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 a, Show k) => Show (T k a) Source # 

Methods

showsPrec :: Int -> T k a -> ShowS #

show :: T k a -> String #

showList :: [T k a] -> ShowS #

toRoseTree :: Tree k a -> Maybe (Tree (T k a)) Source #

showTree :: (Show k, Show a) => BalBST k a -> String Source #

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

toList :: BalBST k a -> [a] Source #

Extract all elements in the tree

\(O(n)\)

toList' :: Tree k a -> [a] Source #

Extract all elements in the tree

\(O(n)\)

Helper stuff

black :: Height -> Tree k a -> k -> Tree k a -> Tree k a Source #

red :: Height -> Tree k a -> k -> Tree k a -> Tree k a Source #

blacken :: Tree k a -> Tree k a Source #

balance :: Color -> Height -> Tree k a -> k -> Tree k a -> Tree k a Source #

rebalance the tree

mkNode :: Height -> Tree k a -> k -> Tree k a -> k -> Tree k a -> k -> Tree k a -> Tree k a Source #