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