splaytree-0.1.5: Provides an annotated splay tree

Safe HaskellNone

Data.SplayTree

Synopsis

Documentation

data SplayTree a whereSource

Constructors

Tip :: SplayTree a 
Branch :: Measure a -> SplayTree a -> !a -> SplayTree a -> SplayTree a 

class Monoid (Measure a) => Measured a whereSource

Associated Types

type Measure a :: *Source

Methods

measure :: a -> Measure aSource

Instances

Measured a => Measured (SplayTree a) 
(Num a, Ord a) => Measured (Range a) 

(><) :: Measured a => SplayTree a -> SplayTree a -> SplayTree aSource

Append two trees.

null :: SplayTree a -> BoolSource

Is the tree empty?

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.

memberSplay :: (Measured a, Ord (Measure a), Eq a) => a -> SplayTree a -> (Bool, SplayTree a)Source

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

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

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

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

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

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

descend to the deepest left-hand branch

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

descend to the deepest right-hand branch

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.

fmap' :: Measured b => (a -> b) -> SplayTree a -> SplayTree bSource

Like fmap, but with a more restrictive type.

traverse' :: (Measured b, Applicative f) => (a -> f b) -> SplayTree a -> f (SplayTree b)Source

Like traverse, but with a more restrictive type.