Data.SplayTree

Documentation

class Monoid v => Measured v a | a -> v where

Minimal complete definition

measure

Methods

measure :: a -> v

Instances

Measured Position Rope

Methods

measure :: Rope -> Position

Measured Position Chunk

Methods

measure :: Chunk -> Position

Measured v a => Measured v (SplayTree v a)

Methods

measure :: SplayTree v a -> v

data SplayTree v a

Constructors

Leaf

Fork (SplayTree v a) a (SplayTree v a) !v

Cached measure of the whole node

Instances

Measured v a => Measured v (SplayTree v a)

Methods

measure :: SplayTree v a -> v

Foldable (SplayTree v)

Methods

fold :: Monoid m => SplayTree v m -> m

foldMap :: Monoid m => (a -> m) -> SplayTree v a -> m

foldr :: (a -> b -> b) -> b -> SplayTree v a -> b

foldr' :: (a -> b -> b) -> b -> SplayTree v a -> b

foldl :: (b -> a -> b) -> b -> SplayTree v a -> b

foldl' :: (b -> a -> b) -> b -> SplayTree v a -> b

foldr1 :: (a -> a -> a) -> SplayTree v a -> a

foldl1 :: (a -> a -> a) -> SplayTree v a -> a

toList :: SplayTree v a -> [a]

null :: SplayTree v a -> Bool

length :: SplayTree v a -> Int

elem :: Eq a => a -> SplayTree v a -> Bool

maximum :: Ord a => SplayTree v a -> a

minimum :: Ord a => SplayTree v a -> a

sum :: Num a => SplayTree v a -> a

product :: Num a => SplayTree v a -> a

(Eq a, Eq v) => Eq (SplayTree v a)

Methods

(==) :: SplayTree v a -> SplayTree v a -> Bool

(/=) :: SplayTree v a -> SplayTree v a -> Bool

(Ord a, Ord v) => Ord (SplayTree v a)

Methods

compare :: SplayTree v a -> SplayTree v a -> Ordering

(<) :: SplayTree v a -> SplayTree v a -> Bool

(<=) :: SplayTree v a -> SplayTree v a -> Bool

(>) :: SplayTree v a -> SplayTree v a -> Bool

(>=) :: SplayTree v a -> SplayTree v a -> Bool

max :: SplayTree v a -> SplayTree v a -> SplayTree v a

min :: SplayTree v a -> SplayTree v a -> SplayTree v a

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

Methods

showsPrec :: Int -> SplayTree v a -> ShowS

show :: SplayTree v a -> String

showList :: [SplayTree v a] -> ShowS

Measured v a => Semigroup (SplayTree v a)

Methods

(<>) :: SplayTree v a -> SplayTree v a -> SplayTree v a

sconcat :: NonEmpty (SplayTree v a) -> SplayTree v a

stimes :: Integral b => b -> SplayTree v a -> SplayTree v a

Measured v a => Monoid (SplayTree v a)

Methods

mempty :: SplayTree v a

mappend :: SplayTree v a -> SplayTree v a -> SplayTree v a

mconcat :: [SplayTree v a] -> SplayTree v a

null :: SplayTree v a -> Bool

Is the splay tree empty?

Since: 0.2.0.0

Construction

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

(<|) :: Measured v a => a -> SplayTree v a -> SplayTree v a infixr 5

(|>) :: Measured v a => SplayTree v a -> a -> SplayTree v a infixl 5

fork :: Measured v a => SplayTree v a -> a -> SplayTree v a -> SplayTree v a

Deconstruction

uncons :: Measured v a => SplayTree v a -> Maybe (a, SplayTree v a)

unsnoc :: Measured v a => SplayTree v a -> Maybe (SplayTree v a, a)

data SplitResult v a

Constructors

Outside

Inside (SplayTree v a) a (SplayTree v a)

Instances

(Eq a, Eq v) => Eq (SplitResult v a)

Methods

(==) :: SplitResult v a -> SplitResult v a -> Bool

(/=) :: SplitResult v a -> SplitResult v a -> Bool

(Ord a, Ord v) => Ord (SplitResult v a)

Methods

compare :: SplitResult v a -> SplitResult v a -> Ordering

(<) :: SplitResult v a -> SplitResult v a -> Bool

(<=) :: SplitResult v a -> SplitResult v a -> Bool

(>) :: SplitResult v a -> SplitResult v a -> Bool

(>=) :: SplitResult v a -> SplitResult v a -> Bool

max :: SplitResult v a -> SplitResult v a -> SplitResult v a

min :: SplitResult v a -> SplitResult v a -> SplitResult v a

(Show a, Show v) => Show (SplitResult v a)

Methods

showsPrec :: Int -> SplitResult v a -> ShowS

show :: SplitResult v a -> String

showList :: [SplitResult v a] -> ShowS

split :: Measured v a => (v -> Bool) -> SplayTree v a -> SplitResult v a

Maps

map :: (Measured v a, Measured w b) => (a -> b) -> SplayTree v a -> SplayTree w b

mapWithPos :: (Measured v a, Measured w b) => (v -> a -> b) -> SplayTree v a -> SplayTree w b

mapWithContext :: (Measured v a, Measured w b) => (v -> a -> v -> b) -> SplayTree v a -> SplayTree w b

Traversals

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

traverseWithPos :: (Measured v a, Measured w b, Applicative f) => (v -> a -> f b) -> SplayTree v a -> f (SplayTree w b)

traverseWithContext :: (Measured v a, Measured w b, Applicative f) => (v -> a -> v -> f b) -> SplayTree v a -> f (SplayTree w b)