module Data.Heap.Spray (Spray, spraySort) where
import Data.Heap.Class

data Spray a = Empty | Branch (Spray a) a (Spray a)
  deriving (ReadPrec [Spray a]
ReadPrec (Spray a)
Int -> ReadS (Spray a)
ReadS [Spray a]
(Int -> ReadS (Spray a))
-> ReadS [Spray a]
-> ReadPrec (Spray a)
-> ReadPrec [Spray a]
-> Read (Spray a)
forall a. Read a => ReadPrec [Spray a]
forall a. Read a => ReadPrec (Spray a)
forall a. Read a => Int -> ReadS (Spray a)
forall a. Read a => ReadS [Spray a]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [Spray a]
$creadListPrec :: forall a. Read a => ReadPrec [Spray a]
readPrec :: ReadPrec (Spray a)
$creadPrec :: forall a. Read a => ReadPrec (Spray a)
readList :: ReadS [Spray a]
$creadList :: forall a. Read a => ReadS [Spray a]
readsPrec :: Int -> ReadS (Spray a)
$creadsPrec :: forall a. Read a => Int -> ReadS (Spray a)
Read, Int -> Spray a -> ShowS
[Spray a] -> ShowS
Spray a -> String
(Int -> Spray a -> ShowS)
-> (Spray a -> String) -> ([Spray a] -> ShowS) -> Show (Spray a)
forall a. Show a => Int -> Spray a -> ShowS
forall a. Show a => [Spray a] -> ShowS
forall a. Show a => Spray a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Spray a] -> ShowS
$cshowList :: forall a. Show a => [Spray a] -> ShowS
show :: Spray a -> String
$cshow :: forall a. Show a => Spray a -> String
showsPrec :: Int -> Spray a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Spray a -> ShowS
Show, Spray a -> Spray a -> Bool
(Spray a -> Spray a -> Bool)
-> (Spray a -> Spray a -> Bool) -> Eq (Spray a)
forall a. Eq a => Spray a -> Spray a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Spray a -> Spray a -> Bool
$c/= :: forall a. Eq a => Spray a -> Spray a -> Bool
== :: Spray a -> Spray a -> Bool
$c== :: forall a. Eq a => Spray a -> Spray a -> Bool
Eq, Eq (Spray a)
Eq (Spray a)
-> (Spray a -> Spray a -> Ordering)
-> (Spray a -> Spray a -> Bool)
-> (Spray a -> Spray a -> Bool)
-> (Spray a -> Spray a -> Bool)
-> (Spray a -> Spray a -> Bool)
-> (Spray a -> Spray a -> Spray a)
-> (Spray a -> Spray a -> Spray a)
-> Ord (Spray a)
Spray a -> Spray a -> Bool
Spray a -> Spray a -> Ordering
Spray a -> Spray a -> Spray 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 a. Ord a => Eq (Spray a)
forall a. Ord a => Spray a -> Spray a -> Bool
forall a. Ord a => Spray a -> Spray a -> Ordering
forall a. Ord a => Spray a -> Spray a -> Spray a
min :: Spray a -> Spray a -> Spray a
$cmin :: forall a. Ord a => Spray a -> Spray a -> Spray a
max :: Spray a -> Spray a -> Spray a
$cmax :: forall a. Ord a => Spray a -> Spray a -> Spray a
>= :: Spray a -> Spray a -> Bool
$c>= :: forall a. Ord a => Spray a -> Spray a -> Bool
> :: Spray a -> Spray a -> Bool
$c> :: forall a. Ord a => Spray a -> Spray a -> Bool
<= :: Spray a -> Spray a -> Bool
$c<= :: forall a. Ord a => Spray a -> Spray a -> Bool
< :: Spray a -> Spray a -> Bool
$c< :: forall a. Ord a => Spray a -> Spray a -> Bool
compare :: Spray a -> Spray a -> Ordering
$ccompare :: forall a. Ord a => Spray a -> Spray a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (Spray a)
Ord)

instance Heap Spray where
  empty :: Spray a
empty = Spray a
forall a. Spray a
Empty
  {-# INLINE empty #-}

  null :: Spray a -> Bool
null Spray a
Empty = Bool
True
  null Spray a
_     = Bool
False
  {-# INLINE null #-}

  insert :: a -> Spray a -> Spray a
insert a
x Spray a
t =
    let (Spray a
small, Spray a
big) = a -> Spray a -> (Spray a, Spray a)
forall a. Ord a => a -> Spray a -> (Spray a, Spray a)
partite a
x Spray a
t
    in Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch Spray a
small a
x Spray a
big
  {-# INLINE insert #-}

  findMin :: Spray a -> Maybe a
findMin (Branch Spray a
Empty a
x Spray a
_) = a -> Maybe a
forall a. a -> Maybe a
Just a
x
  findMin (Branch Spray a
l a
_ Spray a
_)     = Spray a -> Maybe a
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> Maybe a
findMin Spray a
l
  findMin Spray a
Empty              = Maybe a
forall a. Maybe a
Nothing

  deleteMin :: Spray a -> Maybe (Spray a)
deleteMin (Branch Spray a
Empty a
_ Spray a
b)              = Spray a -> Maybe (Spray a)
forall a. a -> Maybe a
Just Spray a
b
  deleteMin (Branch (Branch Spray a
Empty a
_ Spray a
b) a
y Spray a
c) = Spray a -> Maybe (Spray a)
forall a. a -> Maybe a
Just (Spray a -> Maybe (Spray a)) -> Spray a -> Maybe (Spray a)
forall a b. (a -> b) -> a -> b
$ Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch Spray a
b a
y Spray a
c
  deleteMin (Branch (Branch Spray a
a a
x Spray a
b) a
y Spray a
c) =
    (\Spray a
l -> Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch Spray a
l a
x (Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch Spray a
b a
y Spray a
c)) (Spray a -> Spray a) -> Maybe (Spray a) -> Maybe (Spray a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Spray a -> Maybe (Spray a)
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> Maybe (f a)
deleteMin Spray a
a
  deleteMin Spray a
Empty = Maybe (Spray a)
forall a. Maybe a
Nothing

  merge :: Spray a -> Spray a -> Spray a
merge Spray a
Empty Spray a
t = Spray a
t
  merge (Branch Spray a
a a
x Spray a
b) Spray a
t =
    let (Spray a
ta, Spray a
tb) = a -> Spray a -> (Spray a, Spray a)
forall a. Ord a => a -> Spray a -> (Spray a, Spray a)
partite a
x Spray a
t
    in Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch (Spray a -> Spray a -> Spray a
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> f a -> f a
merge Spray a
ta Spray a
a) a
x (Spray a -> Spray a -> Spray a
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> f a -> f a
merge Spray a
tb Spray a
b)

  toList :: Spray a -> [a]
toList = (([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ []) (([a] -> [a]) -> [a]) -> (Spray a -> [a] -> [a]) -> Spray a -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Spray a -> [a] -> [a]
forall a. Spray a -> [a] -> [a]
go where
    go :: Spray a -> [a] -> [a]
go Spray a
Empty          = [a] -> [a]
forall a. a -> a
id
    go (Branch Spray a
l a
x Spray a
r) = Spray a -> [a] -> [a]
go Spray a
l ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a
xa -> [a] -> [a]
forall a. a -> [a] -> [a]
:) ([a] -> [a]) -> ([a] -> [a]) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Spray a -> [a] -> [a]
go Spray a
r
  {-# INLINE toList #-}

partite :: Ord a => a -> Spray a -> (Spray a, Spray a)
partite :: a -> Spray a -> (Spray a, Spray a)
partite a
_ Spray a
Empty = (Spray a
forall a. Spray a
Empty, Spray a
forall a. Spray a
Empty)
partite a
p t :: Spray a
t@(Branch Spray a
a a
x Spray a
b)
  | a
x a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
p =
    case Spray a
b of
      Spray a
Empty -> (Spray a
t, Spray a
forall a. Spray a
Empty)
      Branch Spray a
b1 a
y Spray a
b2
        | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
p  ->
          let (Spray a
small, Spray a
big) = a -> Spray a -> (Spray a, Spray a)
forall a. Ord a => a -> Spray a -> (Spray a, Spray a)
partite a
p Spray a
b2
          in (Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch (Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch Spray a
a a
x Spray a
b1) a
y Spray a
small, Spray a
big)
        | Bool
otherwise ->
          let (Spray a
small, Spray a
big) = a -> Spray a -> (Spray a, Spray a)
forall a. Ord a => a -> Spray a -> (Spray a, Spray a)
partite a
p Spray a
b1
          in (Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch Spray a
a a
x Spray a
small, Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch Spray a
big a
y Spray a
b2)

  | Bool
otherwise =
    case Spray a
a of
      Spray a
Empty -> (Spray a
forall a. Spray a
Empty, Spray a
t)
      Branch Spray a
a1 a
y Spray a
a2
        | a
y a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
p ->
          let (Spray a
small, Spray a
big) = a -> Spray a -> (Spray a, Spray a)
forall a. Ord a => a -> Spray a -> (Spray a, Spray a)
partite a
p Spray a
a2
          in (Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch Spray a
a1 a
y Spray a
small, Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch Spray a
big a
x Spray a
b)
        | Bool
otherwise ->
          let (Spray a
small, Spray a
big) = a -> Spray a -> (Spray a, Spray a)
forall a. Ord a => a -> Spray a -> (Spray a, Spray a)
partite a
p Spray a
a1
          in (Spray a
small, Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch Spray a
big a
y (Spray a -> a -> Spray a -> Spray a
forall a. Spray a -> a -> Spray a -> Spray a
Branch Spray a
a2 a
x Spray a
b))

spraySort :: Ord a => [a] -> [a]
spraySort :: [a] -> [a]
spraySort = Spray a -> [a]
forall (f :: * -> *) a. (Heap f, Ord a) => f a -> [a]
toList (Spray a -> [a]) -> ([a] -> Spray a) -> [a] -> [a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Spray a -> Spray a) -> Spray a -> [a] -> Spray a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> Spray a -> Spray a
forall (f :: * -> *) a. (Heap f, Ord a) => a -> f a -> f a
insert Spray a
forall a. Spray a
Empty