{-# language DeriveFoldable #-}
{-# language FlexibleInstances #-}
{-# language FunctionalDependencies #-}
module Data.SplayTree where

import Data.Monoid
import qualified Data.Semigroup as Semigroup

infixr 5 <|
infixl 5 |>

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

data SplayTree v a
  = Leaf
  | Fork (SplayTree v a) a (SplayTree v a) !v -- ^ Cached measure of the whole node
  deriving (SplayTree v a -> SplayTree v a -> Bool
(SplayTree v a -> SplayTree v a -> Bool)
-> (SplayTree v a -> SplayTree v a -> Bool) -> Eq (SplayTree v a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall v a. (Eq a, Eq v) => SplayTree v a -> SplayTree v a -> Bool
/= :: SplayTree v a -> SplayTree v a -> Bool
$c/= :: forall v a. (Eq a, Eq v) => SplayTree v a -> SplayTree v a -> Bool
== :: SplayTree v a -> SplayTree v a -> Bool
$c== :: forall v a. (Eq a, Eq v) => SplayTree v a -> SplayTree v a -> Bool
Eq, Eq (SplayTree v a)
Eq (SplayTree v a)
-> (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)
-> (SplayTree v a -> SplayTree v a -> SplayTree v a)
-> (SplayTree v a -> SplayTree v a -> SplayTree v a)
-> Ord (SplayTree v a)
SplayTree v a -> SplayTree v a -> Bool
SplayTree v a -> SplayTree v a -> Ordering
SplayTree v a -> SplayTree v a -> SplayTree v a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall v a. (Ord a, Ord v) => Eq (SplayTree v a)
forall v a.
(Ord a, Ord v) =>
SplayTree v a -> SplayTree v a -> Bool
forall v a.
(Ord a, Ord v) =>
SplayTree v a -> SplayTree v a -> Ordering
forall v a.
(Ord a, Ord v) =>
SplayTree v a -> SplayTree v a -> SplayTree v a
min :: SplayTree v a -> SplayTree v a -> SplayTree v a
$cmin :: forall v a.
(Ord a, Ord v) =>
SplayTree v a -> SplayTree v a -> SplayTree v a
max :: SplayTree v a -> SplayTree v a -> SplayTree v a
$cmax :: forall v a.
(Ord a, Ord v) =>
SplayTree v a -> SplayTree v a -> SplayTree v a
>= :: SplayTree v a -> SplayTree v a -> Bool
$c>= :: forall v a.
(Ord a, Ord v) =>
SplayTree v a -> SplayTree v a -> Bool
> :: SplayTree v a -> SplayTree v a -> Bool
$c> :: forall v a.
(Ord a, Ord v) =>
SplayTree v a -> SplayTree v a -> Bool
<= :: SplayTree v a -> SplayTree v a -> Bool
$c<= :: forall v a.
(Ord a, Ord v) =>
SplayTree v a -> SplayTree v a -> Bool
< :: SplayTree v a -> SplayTree v a -> Bool
$c< :: forall v a.
(Ord a, Ord v) =>
SplayTree v a -> SplayTree v a -> Bool
compare :: SplayTree v a -> SplayTree v a -> Ordering
$ccompare :: forall v a.
(Ord a, Ord v) =>
SplayTree v a -> SplayTree v a -> Ordering
$cp1Ord :: forall v a. (Ord a, Ord v) => Eq (SplayTree v a)
Ord, Int -> SplayTree v a -> ShowS
[SplayTree v a] -> ShowS
SplayTree v a -> String
(Int -> SplayTree v a -> ShowS)
-> (SplayTree v a -> String)
-> ([SplayTree v a] -> ShowS)
-> Show (SplayTree v a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall v a. (Show a, Show v) => Int -> SplayTree v a -> ShowS
forall v a. (Show a, Show v) => [SplayTree v a] -> ShowS
forall v a. (Show a, Show v) => SplayTree v a -> String
showList :: [SplayTree v a] -> ShowS
$cshowList :: forall v a. (Show a, Show v) => [SplayTree v a] -> ShowS
show :: SplayTree v a -> String
$cshow :: forall v a. (Show a, Show v) => SplayTree v a -> String
showsPrec :: Int -> SplayTree v a -> ShowS
$cshowsPrec :: forall v a. (Show a, Show v) => Int -> SplayTree v a -> ShowS
Show, SplayTree v a -> Bool
(a -> m) -> SplayTree v a -> m
(a -> b -> b) -> b -> SplayTree v a -> b
(forall m. Monoid m => SplayTree v m -> m)
-> (forall m a. Monoid m => (a -> m) -> SplayTree v a -> m)
-> (forall m a. Monoid m => (a -> m) -> SplayTree v a -> m)
-> (forall a b. (a -> b -> b) -> b -> SplayTree v a -> b)
-> (forall a b. (a -> b -> b) -> b -> SplayTree v a -> b)
-> (forall b a. (b -> a -> b) -> b -> SplayTree v a -> b)
-> (forall b a. (b -> a -> b) -> b -> SplayTree v a -> b)
-> (forall a. (a -> a -> a) -> SplayTree v a -> a)
-> (forall a. (a -> a -> a) -> SplayTree v a -> a)
-> (forall a. SplayTree v a -> [a])
-> (forall a. SplayTree v a -> Bool)
-> (forall a. SplayTree v a -> Int)
-> (forall a. Eq a => a -> SplayTree v a -> Bool)
-> (forall a. Ord a => SplayTree v a -> a)
-> (forall a. Ord a => SplayTree v a -> a)
-> (forall a. Num a => SplayTree v a -> a)
-> (forall a. Num a => SplayTree v a -> a)
-> Foldable (SplayTree v)
forall a. Eq a => a -> SplayTree v a -> Bool
forall a. Num a => SplayTree v a -> a
forall a. Ord a => SplayTree v a -> a
forall m. Monoid m => SplayTree v m -> m
forall a. SplayTree v a -> Bool
forall a. SplayTree v a -> Int
forall a. SplayTree v a -> [a]
forall a. (a -> a -> a) -> SplayTree v a -> a
forall v a. Eq a => a -> SplayTree v a -> Bool
forall v a. Num a => SplayTree v a -> a
forall v a. Ord a => SplayTree v a -> a
forall m a. Monoid m => (a -> m) -> SplayTree v a -> m
forall v m. Monoid m => SplayTree v m -> m
forall v a. SplayTree v a -> Bool
forall v a. SplayTree v a -> Int
forall v a. SplayTree v a -> [a]
forall b a. (b -> a -> b) -> b -> SplayTree v a -> b
forall a b. (a -> b -> b) -> b -> SplayTree v a -> b
forall v a. (a -> a -> a) -> SplayTree v a -> a
forall v m a. Monoid m => (a -> m) -> SplayTree v a -> m
forall v b a. (b -> a -> b) -> b -> SplayTree v a -> b
forall v a b. (a -> b -> b) -> b -> SplayTree v a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: SplayTree v a -> a
$cproduct :: forall v a. Num a => SplayTree v a -> a
sum :: SplayTree v a -> a
$csum :: forall v a. Num a => SplayTree v a -> a
minimum :: SplayTree v a -> a
$cminimum :: forall v a. Ord a => SplayTree v a -> a
maximum :: SplayTree v a -> a
$cmaximum :: forall v a. Ord a => SplayTree v a -> a
elem :: a -> SplayTree v a -> Bool
$celem :: forall v a. Eq a => a -> SplayTree v a -> Bool
length :: SplayTree v a -> Int
$clength :: forall v a. SplayTree v a -> Int
null :: SplayTree v a -> Bool
$cnull :: forall v a. SplayTree v a -> Bool
toList :: SplayTree v a -> [a]
$ctoList :: forall v a. SplayTree v a -> [a]
foldl1 :: (a -> a -> a) -> SplayTree v a -> a
$cfoldl1 :: forall v a. (a -> a -> a) -> SplayTree v a -> a
foldr1 :: (a -> a -> a) -> SplayTree v a -> a
$cfoldr1 :: forall v a. (a -> a -> a) -> SplayTree v a -> a
foldl' :: (b -> a -> b) -> b -> SplayTree v a -> b
$cfoldl' :: forall v b a. (b -> a -> b) -> b -> SplayTree v a -> b
foldl :: (b -> a -> b) -> b -> SplayTree v a -> b
$cfoldl :: forall v b a. (b -> a -> b) -> b -> SplayTree v a -> b
foldr' :: (a -> b -> b) -> b -> SplayTree v a -> b
$cfoldr' :: forall v a b. (a -> b -> b) -> b -> SplayTree v a -> b
foldr :: (a -> b -> b) -> b -> SplayTree v a -> b
$cfoldr :: forall v a b. (a -> b -> b) -> b -> SplayTree v a -> b
foldMap' :: (a -> m) -> SplayTree v a -> m
$cfoldMap' :: forall v m a. Monoid m => (a -> m) -> SplayTree v a -> m
foldMap :: (a -> m) -> SplayTree v a -> m
$cfoldMap :: forall v m a. Monoid m => (a -> m) -> SplayTree v a -> m
fold :: SplayTree v m -> m
$cfold :: forall v m. Monoid m => SplayTree v m -> m
Foldable)

instance Measured v a => Measured v (SplayTree v a) where
  {-# INLINE measure #-}
  measure :: SplayTree v a -> v
measure SplayTree v a
Leaf = v
forall a. Monoid a => a
mempty
  measure (Fork SplayTree v a
_ a
_ SplayTree v a
_ v
v) = v
v

instance Measured v a => Semigroup.Semigroup (SplayTree v a) where
  {-# INLINE (<>) #-}
  SplayTree v a
Leaf <> :: SplayTree v a -> SplayTree v a -> SplayTree v a
<> SplayTree v a
t = SplayTree v a
t
  SplayTree v a
t <> SplayTree v a
Leaf = SplayTree v a
t
  Fork SplayTree v a
l1 a
a1 SplayTree v a
r1 v
lar1 <> Fork SplayTree v a
l2 a
a2 SplayTree v a
r2 v
lar2
    = SplayTree v a -> a -> SplayTree v a -> v -> SplayTree v a
forall v a.
SplayTree v a -> a -> SplayTree v a -> v -> SplayTree v a
Fork SplayTree v a
l1 a
a1 (SplayTree v a -> a -> SplayTree v a -> v -> SplayTree v a
forall v a.
SplayTree v a -> a -> SplayTree v a -> v -> SplayTree v a
Fork (SplayTree v a
r1 SplayTree v a -> SplayTree v a -> SplayTree v a
forall a. Semigroup a => a -> a -> a
<> SplayTree v a
l2) a
a2 SplayTree v a
r2 (SplayTree v a -> v
forall v a. Measured v a => a -> v
measure SplayTree v a
r1 v -> v -> v
forall a. Semigroup a => a -> a -> a
<> v
lar2)) (v
lar1 v -> v -> v
forall a. Semigroup a => a -> a -> a
<> v
lar2)

instance Measured v a => Monoid (SplayTree v a) where
  {-# INLINE mempty #-}
  mempty :: SplayTree v a
mempty = SplayTree v a
forall v a. SplayTree v a
Leaf
  {-# INLINE mappend #-}
  mappend :: SplayTree v a -> SplayTree v a -> SplayTree v a
mappend = SplayTree v a -> SplayTree v a -> SplayTree v a
forall a. Semigroup a => a -> a -> a
(Semigroup.<>)

-- | Is the splay tree empty?
--
-- @since 0.2.0.0
null :: SplayTree v a -> Bool
null :: SplayTree v a -> Bool
null SplayTree v a
Leaf = Bool
True
null Fork {} = Bool
False

-------------------------------------------------------------------------------
-- * Construction

{-# INLINE singleton #-}
singleton :: Measured v a => a -> SplayTree v a
singleton :: a -> SplayTree v a
singleton a
a = SplayTree v a -> a -> SplayTree v a -> v -> SplayTree v a
forall v a.
SplayTree v a -> a -> SplayTree v a -> v -> SplayTree v a
Fork SplayTree v a
forall v a. SplayTree v a
Leaf a
a SplayTree v a
forall v a. SplayTree v a
Leaf (v -> SplayTree v a) -> v -> SplayTree v a
forall a b. (a -> b) -> a -> b
$ a -> v
forall v a. Measured v a => a -> v
measure a
a

{-# INLINE (<|) #-}
(<|) :: Measured v a => a -> SplayTree v a -> SplayTree v a
<| :: a -> SplayTree v a -> SplayTree v a
(<|) = SplayTree v a -> a -> SplayTree v a -> SplayTree v a
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork SplayTree v a
forall v a. SplayTree v a
Leaf

{-# INLINE (|>) #-}
(|>) :: Measured v a => SplayTree v a -> a -> SplayTree v a
|> :: SplayTree v a -> a -> SplayTree v a
(|>) SplayTree v a
t a
a = SplayTree v a -> a -> SplayTree v a -> SplayTree v a
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork SplayTree v a
t a
a SplayTree v a
forall v a. SplayTree v a
Leaf

{-# INLINE fork #-}
fork :: Measured v a => SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork :: SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork SplayTree v a
l a
a SplayTree v a
r = SplayTree v a -> a -> SplayTree v a -> v -> SplayTree v a
forall v a.
SplayTree v a -> a -> SplayTree v a -> v -> SplayTree v a
Fork SplayTree v a
l a
a SplayTree v a
r (v -> SplayTree v a) -> v -> SplayTree v a
forall a b. (a -> b) -> a -> b
$ SplayTree v a -> v
forall v a. Measured v a => a -> v
measure SplayTree v a
l v -> v -> v
forall a. Semigroup a => a -> a -> a
<> a -> v
forall v a. Measured v a => a -> v
measure a
a v -> v -> v
forall a. Semigroup a => a -> a -> a
<> SplayTree v a -> v
forall v a. Measured v a => a -> v
measure SplayTree v a
r

-------------------------------------------------------------------------------
-- * Deconstruction

{-# INLINE uncons #-}
uncons :: Measured v a => SplayTree v a -> Maybe (a, SplayTree v a)
uncons :: SplayTree v a -> Maybe (a, SplayTree v a)
uncons SplayTree v a
Leaf = Maybe (a, SplayTree v a)
forall a. Maybe a
Nothing
uncons (Fork SplayTree v a
left a
el SplayTree v a
right v
_) = (a, SplayTree v a) -> Maybe (a, SplayTree v a)
forall a. a -> Maybe a
Just ((a, SplayTree v a) -> Maybe (a, SplayTree v a))
-> (a, SplayTree v a) -> Maybe (a, SplayTree v a)
forall a b. (a -> b) -> a -> b
$ SplayTree v a -> a -> SplayTree v a -> (a, SplayTree v a)
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> (a, SplayTree v a)
go SplayTree v a
left a
el SplayTree v a
right
  where
    go :: SplayTree v a -> a -> SplayTree v a -> (a, SplayTree v a)
go SplayTree v a
Leaf a
a SplayTree v a
r = (a
a, SplayTree v a
r)
    go (Fork SplayTree v a
l a
a SplayTree v a
m v
_) a
b SplayTree v a
r = SplayTree v a -> a -> SplayTree v a -> (a, SplayTree v a)
go SplayTree v a
l a
a (SplayTree v a -> a -> SplayTree v a -> SplayTree v a
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork SplayTree v a
m a
b SplayTree v a
r)

{-# INLINE unsnoc #-}
unsnoc :: Measured v a => SplayTree v a -> Maybe (SplayTree v a, a)
unsnoc :: SplayTree v a -> Maybe (SplayTree v a, a)
unsnoc SplayTree v a
Leaf = Maybe (SplayTree v a, a)
forall a. Maybe a
Nothing
unsnoc (Fork SplayTree v a
left a
el SplayTree v a
right v
_) = (SplayTree v a, a) -> Maybe (SplayTree v a, a)
forall a. a -> Maybe a
Just ((SplayTree v a, a) -> Maybe (SplayTree v a, a))
-> (SplayTree v a, a) -> Maybe (SplayTree v a, a)
forall a b. (a -> b) -> a -> b
$ SplayTree v a -> a -> SplayTree v a -> (SplayTree v a, a)
forall v t.
Measured v t =>
SplayTree v t -> t -> SplayTree v t -> (SplayTree v t, t)
go SplayTree v a
left a
el SplayTree v a
right
  where
    go :: SplayTree v t -> t -> SplayTree v t -> (SplayTree v t, t)
go SplayTree v t
l t
a SplayTree v t
Leaf = (SplayTree v t
l, t
a)
    go SplayTree v t
l t
a (Fork SplayTree v t
m t
b SplayTree v t
r v
_) = SplayTree v t -> t -> SplayTree v t -> (SplayTree v t, t)
go (SplayTree v t -> t -> SplayTree v t -> SplayTree v t
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork SplayTree v t
l t
a SplayTree v t
m) t
b SplayTree v t
r

data SplitResult v a
  = Outside
  | Inside (SplayTree v a) a (SplayTree v a)
  deriving (SplitResult v a -> SplitResult v a -> Bool
(SplitResult v a -> SplitResult v a -> Bool)
-> (SplitResult v a -> SplitResult v a -> Bool)
-> Eq (SplitResult v a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall v a.
(Eq a, Eq v) =>
SplitResult v a -> SplitResult v a -> Bool
/= :: SplitResult v a -> SplitResult v a -> Bool
$c/= :: forall v a.
(Eq a, Eq v) =>
SplitResult v a -> SplitResult v a -> Bool
== :: SplitResult v a -> SplitResult v a -> Bool
$c== :: forall v a.
(Eq a, Eq v) =>
SplitResult v a -> SplitResult v a -> Bool
Eq, Eq (SplitResult v a)
Eq (SplitResult v a)
-> (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)
-> (SplitResult v a -> SplitResult v a -> SplitResult v a)
-> (SplitResult v a -> SplitResult v a -> SplitResult v a)
-> Ord (SplitResult v a)
SplitResult v a -> SplitResult v a -> Bool
SplitResult v a -> SplitResult v a -> Ordering
SplitResult v a -> SplitResult v a -> SplitResult v a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall v a. (Ord a, Ord v) => Eq (SplitResult v a)
forall v a.
(Ord a, Ord v) =>
SplitResult v a -> SplitResult v a -> Bool
forall v a.
(Ord a, Ord v) =>
SplitResult v a -> SplitResult v a -> Ordering
forall v a.
(Ord a, Ord v) =>
SplitResult v a -> SplitResult v a -> SplitResult v a
min :: SplitResult v a -> SplitResult v a -> SplitResult v a
$cmin :: forall v a.
(Ord a, Ord v) =>
SplitResult v a -> SplitResult v a -> SplitResult v a
max :: SplitResult v a -> SplitResult v a -> SplitResult v a
$cmax :: forall v a.
(Ord a, Ord v) =>
SplitResult v a -> SplitResult v a -> SplitResult v a
>= :: SplitResult v a -> SplitResult v a -> Bool
$c>= :: forall v a.
(Ord a, Ord v) =>
SplitResult v a -> SplitResult v a -> Bool
> :: SplitResult v a -> SplitResult v a -> Bool
$c> :: forall v a.
(Ord a, Ord v) =>
SplitResult v a -> SplitResult v a -> Bool
<= :: SplitResult v a -> SplitResult v a -> Bool
$c<= :: forall v a.
(Ord a, Ord v) =>
SplitResult v a -> SplitResult v a -> Bool
< :: SplitResult v a -> SplitResult v a -> Bool
$c< :: forall v a.
(Ord a, Ord v) =>
SplitResult v a -> SplitResult v a -> Bool
compare :: SplitResult v a -> SplitResult v a -> Ordering
$ccompare :: forall v a.
(Ord a, Ord v) =>
SplitResult v a -> SplitResult v a -> Ordering
$cp1Ord :: forall v a. (Ord a, Ord v) => Eq (SplitResult v a)
Ord, Int -> SplitResult v a -> ShowS
[SplitResult v a] -> ShowS
SplitResult v a -> String
(Int -> SplitResult v a -> ShowS)
-> (SplitResult v a -> String)
-> ([SplitResult v a] -> ShowS)
-> Show (SplitResult v a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall v a. (Show a, Show v) => Int -> SplitResult v a -> ShowS
forall v a. (Show a, Show v) => [SplitResult v a] -> ShowS
forall v a. (Show a, Show v) => SplitResult v a -> String
showList :: [SplitResult v a] -> ShowS
$cshowList :: forall v a. (Show a, Show v) => [SplitResult v a] -> ShowS
show :: SplitResult v a -> String
$cshow :: forall v a. (Show a, Show v) => SplitResult v a -> String
showsPrec :: Int -> SplitResult v a -> ShowS
$cshowsPrec :: forall v a. (Show a, Show v) => Int -> SplitResult v a -> ShowS
Show)

{-# INLINE split #-}
split :: Measured v a => (v -> Bool) -> SplayTree v a -> SplitResult v a
split :: (v -> Bool) -> SplayTree v a -> SplitResult v a
split = v -> (v -> Bool) -> SplayTree v a -> SplitResult v a
forall v a.
Measured v a =>
v -> (v -> Bool) -> SplayTree v a -> SplitResult v a
go v
forall a. Monoid a => a
mempty
  where
    go :: v -> (v -> Bool) -> SplayTree v a -> SplitResult v a
go v
_ v -> Bool
_ SplayTree v a
Leaf = SplitResult v a
forall v a. SplitResult v a
Outside
    go v
v v -> Bool
f (Fork SplayTree v a
l a
a SplayTree v a
r v
_)
      | v -> Bool
f v
vl = case v -> (v -> Bool) -> SplayTree v a -> SplitResult v a
go v
v v -> Bool
f SplayTree v a
l of
        SplitResult v a
Outside -> SplitResult v a
forall v a. SplitResult v a
Outside
        Inside SplayTree v a
l' a
a' SplayTree v a
m -> SplayTree v a -> a -> SplayTree v a -> SplitResult v a
forall v a. SplayTree v a -> a -> SplayTree v a -> SplitResult v a
Inside SplayTree v a
l' a
a' (SplayTree v a -> SplitResult v a)
-> SplayTree v a -> SplitResult v a
forall a b. (a -> b) -> a -> b
$ SplayTree v a -> a -> SplayTree v a -> SplayTree v a
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork SplayTree v a
m a
a SplayTree v a
r
      | v -> Bool
f v
vla = SplayTree v a -> a -> SplayTree v a -> SplitResult v a
forall v a. SplayTree v a -> a -> SplayTree v a -> SplitResult v a
Inside SplayTree v a
l a
a SplayTree v a
r
      | Bool
otherwise = case v -> (v -> Bool) -> SplayTree v a -> SplitResult v a
go v
vla v -> Bool
f SplayTree v a
r of
        SplitResult v a
Outside -> SplitResult v a
forall v a. SplitResult v a
Outside
        Inside SplayTree v a
m a
a' SplayTree v a
r' -> SplayTree v a -> a -> SplayTree v a -> SplitResult v a
forall v a. SplayTree v a -> a -> SplayTree v a -> SplitResult v a
Inside (SplayTree v a -> a -> SplayTree v a -> SplayTree v a
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork SplayTree v a
l a
a SplayTree v a
m) a
a' SplayTree v a
r'
      where
        vl :: v
vl = v
v v -> v -> v
forall a. Semigroup a => a -> a -> a
<> SplayTree v a -> v
forall v a. Measured v a => a -> v
measure SplayTree v a
l
        vla :: v
vla = v
vl v -> v -> v
forall a. Semigroup a => a -> a -> a
<> a -> v
forall v a. Measured v a => a -> v
measure a
a

-------------------------------------------------------------------------------
-- * Maps

{-# INLINE map #-}
map
  :: (Measured v a, Measured w b)
  => (a -> b)
  -> SplayTree v a
  -> SplayTree w b
map :: (a -> b) -> SplayTree v a -> SplayTree w b
map a -> b
_ SplayTree v a
Leaf = SplayTree w b
forall v a. SplayTree v a
Leaf
map a -> b
f (Fork SplayTree v a
l a
a SplayTree v a
r v
_) = SplayTree w b -> b -> SplayTree w b -> SplayTree w b
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork ((a -> b) -> SplayTree v a -> SplayTree w b
forall v a w b.
(Measured v a, Measured w b) =>
(a -> b) -> SplayTree v a -> SplayTree w b
Data.SplayTree.map a -> b
f SplayTree v a
l) (a -> b
f a
a) ((a -> b) -> SplayTree v a -> SplayTree w b
forall v a w b.
(Measured v a, Measured w b) =>
(a -> b) -> SplayTree v a -> SplayTree w b
Data.SplayTree.map a -> b
f SplayTree v a
r)

{-# INLINE mapWithPos #-}
mapWithPos
  :: (Measured v a, Measured w b)
  => (v -> a -> b)
  -> SplayTree v a
  -> SplayTree w b
mapWithPos :: (v -> a -> b) -> SplayTree v a -> SplayTree w b
mapWithPos v -> a -> b
f = v -> SplayTree v a -> SplayTree w b
forall v. Measured v b => v -> SplayTree v a -> SplayTree v b
go v
forall a. Monoid a => a
mempty
  where
    go :: v -> SplayTree v a -> SplayTree v b
go v
_ SplayTree v a
Leaf = SplayTree v b
forall v a. SplayTree v a
Leaf
    go v
i (Fork SplayTree v a
l a
a SplayTree v a
r v
_) = SplayTree v b -> b -> SplayTree v b -> SplayTree v b
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork (v -> SplayTree v a -> SplayTree v b
go v
i SplayTree v a
l) (v -> a -> b
f v
il a
a) (v -> SplayTree v a -> SplayTree v b
go v
ila SplayTree v a
r)
      where
        il :: v
il = v
i v -> v -> v
forall a. Semigroup a => a -> a -> a
<> SplayTree v a -> v
forall v a. Measured v a => a -> v
measure SplayTree v a
l
        ila :: v
ila = v
il v -> v -> v
forall a. Semigroup a => a -> a -> a
<> a -> v
forall v a. Measured v a => a -> v
measure a
a

{-# INLINE mapWithContext #-}
mapWithContext
  :: (Measured v a, Measured w b)
  => (v -> a -> v -> b)
  -> SplayTree v a
  -> SplayTree w b
mapWithContext :: (v -> a -> v -> b) -> SplayTree v a -> SplayTree w b
mapWithContext v -> a -> v -> b
f SplayTree v a
t = v -> SplayTree v a -> v -> SplayTree w b
forall v. Measured v b => v -> SplayTree v a -> v -> SplayTree v b
go v
forall a. Monoid a => a
mempty SplayTree v a
t v
forall a. Monoid a => a
mempty
  where
    go :: v -> SplayTree v a -> v -> SplayTree v b
go v
_ SplayTree v a
Leaf v
_ = SplayTree v b
forall v a. SplayTree v a
Leaf
    go v
i (Fork SplayTree v a
l a
a SplayTree v a
r v
_) v
j = SplayTree v b -> b -> SplayTree v b -> SplayTree v b
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork (v -> SplayTree v a -> v -> SplayTree v b
go v
i SplayTree v a
l v
arj) (v -> a -> v -> b
f v
il a
a v
rj) (v -> SplayTree v a -> v -> SplayTree v b
go v
ila SplayTree v a
r v
j)
      where
        ma :: v
ma = a -> v
forall v a. Measured v a => a -> v
measure a
a
        il :: v
il = v
i v -> v -> v
forall a. Semigroup a => a -> a -> a
<> SplayTree v a -> v
forall v a. Measured v a => a -> v
measure SplayTree v a
l
        ila :: v
ila = v
il v -> v -> v
forall a. Semigroup a => a -> a -> a
<> v
ma
        rj :: v
rj = SplayTree v a -> v
forall v a. Measured v a => a -> v
measure SplayTree v a
r v -> v -> v
forall a. Semigroup a => a -> a -> a
<> v
j
        arj :: v
arj = v
ma

-------------------------------------------------------------------------------
-- * Traversals

{-# INLINE traverse #-}
traverse
  :: (Measured v a, Measured w b, Applicative f)
  => (a -> f b)
  -> SplayTree v a
  -> f (SplayTree w b)
traverse :: (a -> f b) -> SplayTree v a -> f (SplayTree w b)
traverse a -> f b
_ SplayTree v a
Leaf = SplayTree w b -> f (SplayTree w b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure SplayTree w b
forall v a. SplayTree v a
Leaf
traverse a -> f b
f (Fork SplayTree v a
l a
a SplayTree v a
r v
_)
  = SplayTree w b -> b -> SplayTree w b -> SplayTree w b
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork
  (SplayTree w b -> b -> SplayTree w b -> SplayTree w b)
-> f (SplayTree w b) -> f (b -> SplayTree w b -> SplayTree w b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> SplayTree v a -> f (SplayTree w b)
forall v a w b (f :: * -> *).
(Measured v a, Measured w b, Applicative f) =>
(a -> f b) -> SplayTree v a -> f (SplayTree w b)
Data.SplayTree.traverse a -> f b
f SplayTree v a
l
  f (b -> SplayTree w b -> SplayTree w b)
-> f b -> f (SplayTree w b -> SplayTree w b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> a -> f b
f a
a
  f (SplayTree w b -> SplayTree w b)
-> f (SplayTree w b) -> f (SplayTree w b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (a -> f b) -> SplayTree v a -> f (SplayTree w b)
forall v a w b (f :: * -> *).
(Measured v a, Measured w b, Applicative f) =>
(a -> f b) -> SplayTree v a -> f (SplayTree w b)
Data.SplayTree.traverse a -> f b
f SplayTree v a
r

{-# INLINE traverseWithPos #-}
traverseWithPos
  :: (Measured v a, Measured w b, Applicative f)
  => (v -> a -> f b)
  -> SplayTree v a
  -> f (SplayTree w b)
traverseWithPos :: (v -> a -> f b) -> SplayTree v a -> f (SplayTree w b)
traverseWithPos v -> a -> f b
f = v -> SplayTree v a -> f (SplayTree w b)
forall v. Measured v b => v -> SplayTree v a -> f (SplayTree v b)
go v
forall a. Monoid a => a
mempty
  where
    go :: v -> SplayTree v a -> f (SplayTree v b)
go v
_ SplayTree v a
Leaf = SplayTree v b -> f (SplayTree v b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure SplayTree v b
forall v a. SplayTree v a
Leaf
    go v
i (Fork SplayTree v a
l a
a SplayTree v a
r v
_)
      = SplayTree v b -> b -> SplayTree v b -> SplayTree v b
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork (SplayTree v b -> b -> SplayTree v b -> SplayTree v b)
-> f (SplayTree v b) -> f (b -> SplayTree v b -> SplayTree v b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> v -> SplayTree v a -> f (SplayTree v b)
go v
i SplayTree v a
l f (b -> SplayTree v b -> SplayTree v b)
-> f b -> f (SplayTree v b -> SplayTree v b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> v -> a -> f b
f v
il a
a f (SplayTree v b -> SplayTree v b)
-> f (SplayTree v b) -> f (SplayTree v b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> v -> SplayTree v a -> f (SplayTree v b)
go v
ila SplayTree v a
r
      where
        il :: v
il = v
i v -> v -> v
forall a. Semigroup a => a -> a -> a
<> SplayTree v a -> v
forall v a. Measured v a => a -> v
measure SplayTree v a
l
        ila :: v
ila = v
il v -> v -> v
forall a. Semigroup a => a -> a -> a
<> a -> v
forall v a. Measured v a => a -> v
measure a
a

{-# INLINE traverseWithContext #-}
traverseWithContext
  :: (Measured v a, Measured w b, Applicative f)
  => (v -> a -> v -> f b)
  -> SplayTree v a
  -> f (SplayTree w b)
traverseWithContext :: (v -> a -> v -> f b) -> SplayTree v a -> f (SplayTree w b)
traverseWithContext v -> a -> v -> f b
f SplayTree v a
t = v -> SplayTree v a -> v -> f (SplayTree w b)
forall v.
Measured v b =>
v -> SplayTree v a -> v -> f (SplayTree v b)
go v
forall a. Monoid a => a
mempty SplayTree v a
t v
forall a. Monoid a => a
mempty
  where
    go :: v -> SplayTree v a -> v -> f (SplayTree v b)
go v
_ SplayTree v a
Leaf v
_ = SplayTree v b -> f (SplayTree v b)
forall (f :: * -> *) a. Applicative f => a -> f a
pure SplayTree v b
forall v a. SplayTree v a
Leaf
    go v
i (Fork SplayTree v a
l a
a SplayTree v a
r v
_) v
j
      = SplayTree v b -> b -> SplayTree v b -> SplayTree v b
forall v a.
Measured v a =>
SplayTree v a -> a -> SplayTree v a -> SplayTree v a
fork (SplayTree v b -> b -> SplayTree v b -> SplayTree v b)
-> f (SplayTree v b) -> f (b -> SplayTree v b -> SplayTree v b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> v -> SplayTree v a -> v -> f (SplayTree v b)
go v
i SplayTree v a
l v
arj f (b -> SplayTree v b -> SplayTree v b)
-> f b -> f (SplayTree v b -> SplayTree v b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> v -> a -> v -> f b
f v
il a
a v
rj f (SplayTree v b -> SplayTree v b)
-> f (SplayTree v b) -> f (SplayTree v b)
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> v -> SplayTree v a -> v -> f (SplayTree v b)
go v
ila SplayTree v a
r v
j
      where
        ma :: v
ma = a -> v
forall v a. Measured v a => a -> v
measure a
a
        il :: v
il = v
i v -> v -> v
forall a. Semigroup a => a -> a -> a
<> SplayTree v a -> v
forall v a. Measured v a => a -> v
measure SplayTree v a
l
        ila :: v
ila = v
il v -> v -> v
forall a. Semigroup a => a -> a -> a
<> v
ma
        rj :: v
rj = SplayTree v a -> v
forall v a. Measured v a => a -> v
measure SplayTree v a
r v -> v -> v
forall a. Semigroup a => a -> a -> a
<> v
j
        arj :: v
arj = v
ma