Safe Haskell | None |
---|

- data SplayTree a where
- class Monoid (Measure a) => Measured a where
- empty :: SplayTree a
- (|>) :: Measured a => SplayTree a -> a -> SplayTree a
- (<|) :: Measured a => a -> SplayTree a -> SplayTree a
- (><) :: Measured a => SplayTree a -> SplayTree a -> SplayTree a
- null :: SplayTree a -> Bool
- singleton :: Measured a => a -> SplayTree a
- size :: SplayTree a -> Int
- split :: Measured a => (Measure a -> Bool) -> SplayTree a -> (SplayTree a, SplayTree a)
- query :: (Measured a, Measure a ~ Measure (SplayTree a)) => (Measure a -> Bool) -> SplayTree a -> Maybe (a, SplayTree a)
- memberSplay :: (Measured a, Ord (Measure a), Eq a) => a -> SplayTree a -> (Bool, SplayTree a)
- rootElem :: SplayTree a -> Maybe a
- delete :: (Measured a, Ord (Measure a), Eq a) => a -> SplayTree a -> SplayTree a
- insert :: (Measured a, Ord (Measure a), Eq a) => a -> SplayTree a -> SplayTree a
- difference :: (Measured a, Ord (Measure a), Eq a) => SplayTree a -> SplayTree a -> SplayTree a
- intersection :: (Measured a, Ord (Measure a), Eq a) => SplayTree a -> SplayTree a -> SplayTree a
- balance :: Measured a => SplayTree a -> SplayTree a
- deepL :: Measured a => SplayTree a -> SplayTree a
- deepR :: Measured a => SplayTree a -> SplayTree a
- fromList :: Measured a => [a] -> SplayTree a
- fromListBalance :: Measured a => [a] -> SplayTree a
- fmap' :: Measured b => (a -> b) -> SplayTree a -> SplayTree b
- traverse' :: (Measured b, Applicative f) => (a -> f b) -> SplayTree a -> f (SplayTree b)

# Documentation

split :: Measured a => (Measure a -> Bool) -> SplayTree a -> (SplayTree a, SplayTree a)Source

Split a tree at the point where the predicate on the measure changes from False to True.

query :: (Measured a, Measure a ~ Measure (SplayTree a)) => (Measure a -> Bool) -> SplayTree a -> Maybe (a, SplayTree a)Source

find the first point where the predicate returns True. Returns a tree splayed with that node at the top.

rootElem :: SplayTree a -> Maybe aSource

Return the root element, if the tree is not empty.

This, combined with `memberSplay`

, can be used to create many lookup
functions

difference :: (Measured a, Ord (Measure a), Eq a) => SplayTree a -> SplayTree a -> SplayTree aSource

intersection :: (Measured a, Ord (Measure a), Eq a) => SplayTree a -> SplayTree a -> SplayTree aSource

balance :: Measured a => SplayTree a -> SplayTree aSource

rebalance a splay tree. The order of elements does not change.

fromList :: Measured a => [a] -> SplayTree aSource

*O(n)*. Create a Tree from a finite list of elements.

fromListBalance :: Measured a => [a] -> SplayTree aSource

*O(n)*. Create a Tree from a finite list of elements.

After the tree is created, it is balanced. This is useful with sorted data, which would otherwise create a completely unbalanced tree.