Data.SplayTree

Documentation

data SplayTree a where

Constructors

Tip :: SplayTree a

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

Instances

Typeable1 SplayTree

Foldable SplayTree

Eq a => Eq (SplayTree a)

Ord a => Ord (SplayTree a)

(Show a, Show (Measure a)) => Show (SplayTree a)

Measured a => Monoid (SplayTree a)

(NFData a, NFData (Measure a)) => NFData (SplayTree a)

Measured a => Measured (SplayTree a)

class Monoid (Measure a) => Measured a where

Associated Types

type Measure a :: *

Methods

measure :: a -> Measure a

Instances

Measured a => Measured (SplayTree a)

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

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

Append two trees.

null :: SplayTree a -> Bool

Is the tree empty?

singleton :: Measured a => a -> SplayTree a

size :: SplayTree a -> Int

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

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)

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)

rootElem :: SplayTree a -> Maybe a

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

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

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

descend to the deepest left-hand branch

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

descend to the deepest right-hand branch

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

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

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

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 b

Like fmap, but with a more restrictive type.

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

Like traverse, but with a more restrictive type.