{-# LANGUAGE CPP #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE UnboxedTuples #-}

module My.Prelude where

import Control.Monad
import Control.Monad.Primitive
import Control.Monad.ST
import Control.Monad.State.Strict
import Data.Bits
import Data.Bool
import qualified Data.ByteString.Builder as B
import qualified Data.ByteString.Builder.Prim as BP
import qualified Data.ByteString.Builder.Prim.Internal as BP
import qualified Data.Foldable as F
#if MIN_VERSION_mtl(2,3,0)
import Data.Function (fix)
#endif
import Data.Functor.Identity
import Data.Primitive
import qualified Data.Vector as V
import qualified Data.Vector.Fusion.Bundle as Bundle
import qualified Data.Vector.Fusion.Bundle.Monadic as MBundle
import qualified Data.Vector.Fusion.Bundle.Size as Bundle
import qualified Data.Vector.Fusion.Stream.Monadic as MS
import Data.Vector.Fusion.Util
import qualified Data.Vector.Generic as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import Data.Word
import Foreign.Ptr
import Foreign.Storable
import GHC.Exts
import System.IO

import Data.PrimParser

-- * Stream utils
rep :: (Monad m) => Int -> (Int -> m ()) -> m ()
rep :: forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rep Int
n = ((Int -> m ()) -> Stream m Int -> m ())
-> Stream m Int -> (Int -> m ()) -> m ()
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Int -> m ()) -> Stream m Int -> m ()
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Stream m a -> m ()
MS.mapM_ (Int
0 Int -> Int -> Stream m Int
forall (m :: * -> *). Monad m => Int -> Int -> Stream m Int
..< Int
n)
{-# INLINE rep #-}

rep1 :: (Monad m) => Int -> (Int -> m ()) -> m ()
rep1 :: forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rep1 Int
n = ((Int -> m ()) -> Stream m Int -> m ())
-> Stream m Int -> (Int -> m ()) -> m ()
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Int -> m ()) -> Stream m Int -> m ()
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Stream m a -> m ()
MS.mapM_ (Int
1 Int -> Int -> Stream m Int
forall (m :: * -> *). Monad m => Int -> Int -> Stream m Int
..< Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
{-# INLINE rep1 #-}

rev :: (Monad m) => Int -> (Int -> m ()) -> m ()
rev :: forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev Int
n = ((Int -> m ()) -> Stream m Int -> m ())
-> Stream m Int -> (Int -> m ()) -> m ()
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Int -> m ()) -> Stream m Int -> m ()
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Stream m a -> m ()
MS.mapM_ (Int
n Int -> Int -> Stream m Int
forall (m :: * -> *). Monad m => Int -> Int -> Stream m Int
>.. Int
0)
{-# INLINE rev #-}

rev1 :: (Monad m) => Int -> (Int -> m ()) -> m ()
rev1 :: forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rev1 Int
n = ((Int -> m ()) -> Stream m Int -> m ())
-> Stream m Int -> (Int -> m ()) -> m ()
forall a b c. (a -> b -> c) -> b -> a -> c
flip (Int -> m ()) -> Stream m Int -> m ()
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Stream m a -> m ()
MS.mapM_ (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1 Int -> Int -> Stream m Int
forall (m :: * -> *). Monad m => Int -> Int -> Stream m Int
>.. Int
1)
{-# INLINE rev1 #-}

infix 4 ..<

{- |
>>> runIdentity $ MS.toList (0..<5)
[0,1,2,3,4]
-}
(..<) :: (Monad m) => Int -> Int -> MS.Stream m Int
..< :: forall (m :: * -> *). Monad m => Int -> Int -> Stream m Int
(..<) !Int
l !Int
r = (Int -> m (Step Int Int)) -> Int -> Stream m Int
forall (m :: * -> *) a s. (s -> m (Step s a)) -> s -> Stream m a
MS.Stream Int -> m (Step Int Int)
forall {m :: * -> *}. Monad m => Int -> m (Step Int Int)
step Int
l
  where
    step :: Int -> m (Step Int Int)
step Int
x
      | Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r = Step Int Int -> m (Step Int Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step Int Int -> m (Step Int Int))
-> Step Int Int -> m (Step Int Int)
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Step Int Int
forall a s. a -> s -> Step s a
MS.Yield Int
x (Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
      | Bool
otherwise = Step Int Int -> m (Step Int Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Step Int Int
forall s a. Step s a
MS.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] (..<) #-}

infix 4 >..

{- |
>>> runIdentity $ MS.toList (5>..0)
[4,3,2,1,0]
-}
(>..) :: (Monad m) => Int -> Int -> MS.Stream m Int
>.. :: forall (m :: * -> *). Monad m => Int -> Int -> Stream m Int
(>..) !Int
r !Int
l = (Int -> m (Step Int Int)) -> Int -> Stream m Int
forall (m :: * -> *) a s. (s -> m (Step s a)) -> s -> Stream m a
MS.Stream Int -> m (Step Int Int)
forall {m :: * -> *}. Monad m => Int -> m (Step Int Int)
step (Int
r Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
  where
    step :: Int -> m (Step Int Int)
step Int
x
      | Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
l = Step Int Int -> m (Step Int Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step Int Int -> m (Step Int Int))
-> Step Int Int -> m (Step Int Int)
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Step Int Int
forall a s. a -> s -> Step s a
MS.Yield Int
x (Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
      | Bool
otherwise = Step Int Int -> m (Step Int Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Step Int Int
forall s a. Step s a
MS.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] (>..) #-}

{- |
>>> runIdentity $ MS.toList (stride 0 10 3)
[0,3,6,9]
-}
stride :: (Monad m) => Int -> Int -> Int -> MS.Stream m Int
stride :: forall (m :: * -> *). Monad m => Int -> Int -> Int -> Stream m Int
stride !Int
l !Int
r !Int
d = (Int -> m (Step Int Int)) -> Int -> Stream m Int
forall (m :: * -> *) a s. (s -> m (Step s a)) -> s -> Stream m a
MS.Stream Int -> m (Step Int Int)
forall {m :: * -> *}. Monad m => Int -> m (Step Int Int)
step Int
l
  where
    step :: Int -> m (Step Int Int)
step Int
x
      | Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
r = Step Int Int -> m (Step Int Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step Int Int -> m (Step Int Int))
-> Step Int Int -> m (Step Int Int)
forall a b. (a -> b) -> a -> b
$ Int -> Int -> Step Int Int
forall a s. a -> s -> Step s a
MS.Yield Int
x (Int
x Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
d)
      | Bool
otherwise = Step Int Int -> m (Step Int Int)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Step Int Int
forall s a. Step s a
MS.Done
    {-# INLINE [0] step #-}
{-# INLINE [1] stride #-}

liftMS :: (Monad m) => MS.Stream Id a -> MS.Stream m a
liftMS :: forall (m :: * -> *) a. Monad m => Stream Id a -> Stream m a
liftMS = (forall z. Id z -> m z) -> Stream Id a -> Stream m a
forall (m :: * -> *) (m' :: * -> *) a.
(Monad m, Monad m') =>
(forall z. m z -> m' z) -> Stream m a -> Stream m' a
MS.trans (z -> m z
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (z -> m z) -> (Id z -> z) -> Id z -> m z
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Id z -> z
forall a. Id a -> a
unId)
{-# INLINE liftMS #-}

-- * Vector utils

asUVector :: U.Vector a -> U.Vector a
asUVector :: forall a. Vector a -> Vector a
asUVector = Vector a -> Vector a
forall a. a -> a
id
{-# INLINE asUVector #-}

asBVector :: V.Vector a -> V.Vector a
asBVector :: forall a. Vector a -> Vector a
asBVector = Vector a -> Vector a
forall a. a -> a
id
{-# INLINE asBVector #-}

{- |
>>> lowerBound (U.fromList "122333") '2'
1
>>> lowerBound (U.fromList "122333") '0'
0
>>> lowerBound (U.fromList "122333") '9'
6
-}
lowerBound :: (Ord a, G.Vector v a) => v a -> a -> Int
lowerBound :: forall a (v :: * -> *). (Ord a, Vector v a) => v a -> a -> Int
lowerBound !v a
vec !a
key = Int -> Int -> (Int -> Bool) -> Int
binarySearch Int
0 (v a -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v a
vec) ((a
key <=) (a -> Bool) -> (Int -> a) -> Int -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Int -> a
forall (v :: * -> *) a. Vector v a => v a -> Int -> a
G.unsafeIndex v a
vec)
{-# INLINE lowerBound #-}

{- |
>>> upperBound (U.fromList "122333") '2'
3
>>> upperBound (U.fromList "122333") '0'
0
>>> upperBound (U.fromList "122333") '9'
6
-}
upperBound :: (Ord a, G.Vector v a) => v a -> a -> Int
upperBound :: forall a (v :: * -> *). (Ord a, Vector v a) => v a -> a -> Int
upperBound !v a
vec !a
key = Int -> Int -> (Int -> Bool) -> Int
binarySearch Int
0 (v a -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v a
vec) ((a
key <) (a -> Bool) -> (Int -> a) -> Int -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Int -> a
forall (v :: * -> *) a. Vector v a => v a -> Int -> a
G.unsafeIndex v a
vec)
{-# INLINE upperBound #-}

{- |
>>> radixSort $ U.fromList [3,1,4,1,5,9]
[1,1,3,4,5,9]
>>> radixSort $ U.fromList [-3,-1,-4,1,5,9]
[1,5,9,-4,-3,-1]
-}
radixSort :: U.Vector Int -> U.Vector Int
radixSort :: Vector Int -> Vector Int
radixSort Vector Int
v0 = (Vector Int -> Int -> Vector Int)
-> Vector Int -> [Int] -> Vector Int
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' Vector Int -> Int -> Vector Int
step Vector Int
v0 [Int
0, Int
16, Int
32, Int
48]
  where
    step :: Vector Int -> Int -> Vector Int
step Vector Int
v Int
k = (forall s. ST s (MVector s Int)) -> Vector Int
forall a. Unbox a => (forall s. ST s (MVector s a)) -> Vector a
U.create ((forall s. ST s (MVector s Int)) -> Vector Int)
-> (forall s. ST s (MVector s Int)) -> Vector Int
forall a b. (a -> b) -> a -> b
$ do
      MVector s Int
pos <- Int -> ST s (MVector (PrimState (ST s)) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
UM.unsafeNew Int
0x10001
      MVector (PrimState (ST s)) Int -> Int -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> a -> m ()
UM.set MVector s Int
MVector (PrimState (ST s)) Int
pos Int
0
      Vector Int -> (Int -> ST s ()) -> ST s ()
forall (m :: * -> *) a b.
(Monad m, Unbox a) =>
Vector a -> (a -> m b) -> m ()
U.forM_ Vector Int
v ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
x -> do
        MVector (PrimState (ST s)) Int -> (Int -> Int) -> Int -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> (a -> a) -> Int -> m ()
UM.unsafeModify MVector s Int
MVector (PrimState (ST s)) Int
pos (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) ((Int
x Int -> Int -> Int
!>>>. Int
k) Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
0xffff Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
      Int -> (Int -> ST s ()) -> ST s ()
forall (m :: * -> *). Monad m => Int -> (Int -> m ()) -> m ()
rep Int
0xffff ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
i -> do
        Int
fi <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead MVector s Int
MVector (PrimState (ST s)) Int
pos Int
i
        MVector (PrimState (ST s)) Int -> (Int -> Int) -> Int -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> (a -> a) -> Int -> m ()
UM.unsafeModify MVector s Int
MVector (PrimState (ST s)) Int
pos (Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
fi) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
      MVector s Int
res <- Int -> ST s (MVector (PrimState (ST s)) Int)
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
Int -> m (MVector (PrimState m) a)
UM.unsafeNew (Int -> ST s (MVector (PrimState (ST s)) Int))
-> Int -> ST s (MVector (PrimState (ST s)) Int)
forall a b. (a -> b) -> a -> b
$ Vector Int -> Int
forall a. Unbox a => Vector a -> Int
U.length Vector Int
v
      Vector Int -> (Int -> ST s ()) -> ST s ()
forall (m :: * -> *) a b.
(Monad m, Unbox a) =>
Vector a -> (a -> m b) -> m ()
U.forM_ Vector Int
v ((Int -> ST s ()) -> ST s ()) -> (Int -> ST s ()) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \Int
x -> do
        let !masked :: Int
masked = (Int
x Int -> Int -> Int
!>>>. Int
k) Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
0xffff
        Int
i <- MVector (PrimState (ST s)) Int -> Int -> ST s Int
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> m a
UM.unsafeRead MVector s Int
MVector (PrimState (ST s)) Int
pos Int
masked
        MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> a -> m ()
UM.unsafeWrite MVector s Int
MVector (PrimState (ST s)) Int
pos Int
masked (Int -> ST s ()) -> Int -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1
        MVector (PrimState (ST s)) Int -> Int -> Int -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Unbox a) =>
MVector (PrimState m) a -> Int -> a -> m ()
UM.unsafeWrite MVector s Int
MVector (PrimState (ST s)) Int
res Int
i Int
x
      MVector s Int -> ST s (MVector s Int)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return MVector s Int
res
{-# INLINE radixSort #-}

{- |
>>> runLengthEncode $ U.fromList "abbccc"
[('a',1),('b',2),('c',3)]
>>> runLengthEncode $ U.fromList ""
[]
-}
runLengthEncode ::
  (Eq a, G.Vector v a, G.Vector v (a, Int)) =>
  v a ->
  v (a, Int)
runLengthEncode :: forall a (v :: * -> *).
(Eq a, Vector v a, Vector v (a, Int)) =>
v a -> v (a, Int)
runLengthEncode =
  Bundle v (a, Int) -> v (a, Int)
forall (v :: * -> *) a. Vector v a => Bundle v a -> v a
G.unstream
    (Bundle v (a, Int) -> v (a, Int))
-> (v a -> Bundle v (a, Int)) -> v a -> v (a, Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall (m :: * -> *). Monad m => Stream m a -> Stream m (a, Int))
-> (Size -> Size) -> Bundle v a -> Bundle v (a, Int)
forall a b (v :: * -> *).
(forall (m :: * -> *). Monad m => Stream m a -> Stream m b)
-> (Size -> Size) -> Bundle v a -> Bundle v b
Bundle.inplace Stream m a -> Stream m (a, Int)
forall a (m :: * -> *).
(Eq a, Monad m) =>
Stream m a -> Stream m (a, Int)
forall (m :: * -> *). Monad m => Stream m a -> Stream m (a, Int)
streamRLE Size -> Size
Bundle.toMax
    (Bundle v a -> Bundle v (a, Int))
-> (v a -> Bundle v a) -> v a -> Bundle v (a, Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle v a
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
G.stream
{-# INLINE runLengthEncode #-}

streamRLE :: (Eq a, Monad m) => MS.Stream m a -> MS.Stream m (a, Int)
streamRLE :: forall a (m :: * -> *).
(Eq a, Monad m) =>
Stream m a -> Stream m (a, Int)
streamRLE (MS.Stream s -> m (Step s a)
step s
s0) = ((Maybe (a, Int), s) -> m (Step (Maybe (a, Int), s) (a, Int)))
-> (Maybe (a, Int), s) -> Stream m (a, Int)
forall (m :: * -> *) a s. (s -> m (Step s a)) -> s -> Stream m a
MS.Stream (Maybe (a, Int), s) -> m (Step (Maybe (a, Int), s) (a, Int))
forall {b}.
Num b =>
(Maybe (a, b), s) -> m (Step (Maybe (a, b), s) (a, b))
step' (Maybe (a, Int)
forall a. Maybe a
Nothing, s
s0)
  where
    step' :: (Maybe (a, b), s) -> m (Step (Maybe (a, b), s) (a, b))
step' (Maybe (a, b)
Nothing, s
s) = do
      Step s a
r <- s -> m (Step s a)
step s
s
      case Step s a
r of
        MS.Yield a
x s
s' -> Step (Maybe (a, b), s) (a, b) -> m (Step (Maybe (a, b), s) (a, b))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (Maybe (a, b), s) (a, b)
 -> m (Step (Maybe (a, b), s) (a, b)))
-> Step (Maybe (a, b), s) (a, b)
-> m (Step (Maybe (a, b), s) (a, b))
forall a b. (a -> b) -> a -> b
$ (Maybe (a, b), s) -> Step (Maybe (a, b), s) (a, b)
forall s a. s -> Step s a
MS.Skip ((a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a
x, b
1), s
s')
        MS.Skip s
s' -> Step (Maybe (a, b), s) (a, b) -> m (Step (Maybe (a, b), s) (a, b))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (Maybe (a, b), s) (a, b)
 -> m (Step (Maybe (a, b), s) (a, b)))
-> Step (Maybe (a, b), s) (a, b)
-> m (Step (Maybe (a, b), s) (a, b))
forall a b. (a -> b) -> a -> b
$ (Maybe (a, b), s) -> Step (Maybe (a, b), s) (a, b)
forall s a. s -> Step s a
MS.Skip (Maybe (a, b)
forall a. Maybe a
Nothing, s
s')
        Step s a
MS.Done -> Step (Maybe (a, b), s) (a, b) -> m (Step (Maybe (a, b), s) (a, b))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Step (Maybe (a, b), s) (a, b)
forall s a. Step s a
MS.Done
    step' (Just (a
x, !b
i), s
s) = do
      Step s a
r <- s -> m (Step s a)
step s
s
      case Step s a
r of
        MS.Yield a
y s
s'
          | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
y -> Step (Maybe (a, b), s) (a, b) -> m (Step (Maybe (a, b), s) (a, b))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (Maybe (a, b), s) (a, b)
 -> m (Step (Maybe (a, b), s) (a, b)))
-> Step (Maybe (a, b), s) (a, b)
-> m (Step (Maybe (a, b), s) (a, b))
forall a b. (a -> b) -> a -> b
$ (Maybe (a, b), s) -> Step (Maybe (a, b), s) (a, b)
forall s a. s -> Step s a
MS.Skip ((a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a
x, b
i b -> b -> b
forall a. Num a => a -> a -> a
+ b
1), s
s')
          | Bool
otherwise -> Step (Maybe (a, b), s) (a, b) -> m (Step (Maybe (a, b), s) (a, b))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (Maybe (a, b), s) (a, b)
 -> m (Step (Maybe (a, b), s) (a, b)))
-> Step (Maybe (a, b), s) (a, b)
-> m (Step (Maybe (a, b), s) (a, b))
forall a b. (a -> b) -> a -> b
$ (a, b) -> (Maybe (a, b), s) -> Step (Maybe (a, b), s) (a, b)
forall a s. a -> s -> Step s a
MS.Yield (a
x, b
i) ((a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a
y, b
1), s
s')
        MS.Skip s
s' -> Step (Maybe (a, b), s) (a, b) -> m (Step (Maybe (a, b), s) (a, b))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (Maybe (a, b), s) (a, b)
 -> m (Step (Maybe (a, b), s) (a, b)))
-> Step (Maybe (a, b), s) (a, b)
-> m (Step (Maybe (a, b), s) (a, b))
forall a b. (a -> b) -> a -> b
$ (Maybe (a, b), s) -> Step (Maybe (a, b), s) (a, b)
forall s a. s -> Step s a
MS.Skip ((a, b) -> Maybe (a, b)
forall a. a -> Maybe a
Just (a
x, b
i), s
s')
        Step s a
MS.Done -> Step (Maybe (a, b), s) (a, b) -> m (Step (Maybe (a, b), s) (a, b))
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (Maybe (a, b), s) (a, b)
 -> m (Step (Maybe (a, b), s) (a, b)))
-> Step (Maybe (a, b), s) (a, b)
-> m (Step (Maybe (a, b), s) (a, b))
forall a b. (a -> b) -> a -> b
$ (a, b) -> (Maybe (a, b), s) -> Step (Maybe (a, b), s) (a, b)
forall a s. a -> s -> Step s a
MS.Yield (a
x, b
i) (Maybe (a, b)
forall a. Maybe a
Nothing, s
s)
    {-# INLINE [0] step' #-}
{-# INLINE [1] streamRLE #-}

{- |
>>> forAccum (0 :: Int) (U.fromList "abc") $ \acc c -> (acc + 1, (acc, c))
[(0,'a'),(1,'b'),(2,'c')]
-}
forAccum ::
  (G.Vector v a, G.Vector v b) =>
  s ->
  v a ->
  (s -> a -> (s, b)) ->
  v b
forAccum :: forall (v :: * -> *) a b s.
(Vector v a, Vector v b) =>
s -> v a -> (s -> a -> (s, b)) -> v b
forAccum s
x v a
v s -> a -> (s, b)
f = (s -> a -> (s, b)) -> s -> v a -> v b
forall (v :: * -> *) a b s.
(Vector v a, Vector v b) =>
(s -> a -> (s, b)) -> s -> v a -> v b
mapAccum s -> a -> (s, b)
f s
x v a
v
{-# INLINE forAccum #-}

mapAccum ::
  (G.Vector v a, G.Vector v b) =>
  (s -> a -> (s, b)) ->
  s ->
  v a ->
  v b
mapAccum :: forall (v :: * -> *) a b s.
(Vector v a, Vector v b) =>
(s -> a -> (s, b)) -> s -> v a -> v b
mapAccum s -> a -> (s, b)
f s
x =
  Bundle v b -> v b
forall (v :: * -> *) a. Vector v a => Bundle v a -> v a
G.unstream
    (Bundle v b -> v b) -> (v a -> Bundle v b) -> v a -> v b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall (m :: * -> *). Monad m => Stream m a -> Stream m b)
-> (Size -> Size) -> Bundle v a -> Bundle v b
forall a b (v :: * -> *).
(forall (m :: * -> *). Monad m => Stream m a -> Stream m b)
-> (Size -> Size) -> Bundle v a -> Bundle v b
Bundle.inplace
      ((s -> a -> m (s, b)) -> s -> Stream m a -> Stream m b
forall (m :: * -> *) s a b.
Monad m =>
(s -> a -> m (s, b)) -> s -> Stream m a -> Stream m b
streamAccumM (\s
s a
a -> (s, b) -> m (s, b)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (s -> a -> (s, b)
f s
s a
a)) s
x)
      Size -> Size
Bundle.toMax
    (Bundle v a -> Bundle v b)
-> (v a -> Bundle v a) -> v a -> Bundle v b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle v a
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
G.stream
{-# INLINE mapAccum #-}

forAccumM ::
  (PrimMonad m, G.Vector v a, G.Vector v b) =>
  s ->
  v a ->
  (s -> a -> m (s, b)) ->
  m (v b)
forAccumM :: forall (m :: * -> *) (v :: * -> *) a b s.
(PrimMonad m, Vector v a, Vector v b) =>
s -> v a -> (s -> a -> m (s, b)) -> m (v b)
forAccumM s
s v a
v s -> a -> m (s, b)
f = (s -> a -> m (s, b)) -> s -> v a -> m (v b)
forall (m :: * -> *) (v :: * -> *) a b s.
(PrimMonad m, Vector v a, Vector v b) =>
(s -> a -> m (s, b)) -> s -> v a -> m (v b)
mapAccumM s -> a -> m (s, b)
f s
s v a
v
{-# INLINE forAccumM #-}

forAccumM_ ::
  (Monad m, G.Vector v b) =>
  a ->
  v b ->
  (a -> b -> m a) ->
  m ()
forAccumM_ :: forall (m :: * -> *) (v :: * -> *) b a.
(Monad m, Vector v b) =>
a -> v b -> (a -> b -> m a) -> m ()
forAccumM_ a
x v b
v a -> b -> m a
f = m () -> m ()
forall (f :: * -> *) a. Functor f => f a -> f ()
void (m () -> m ()) -> m () -> m ()
forall a b. (a -> b) -> a -> b
$ (a -> b -> m a) -> a -> v b -> m ()
forall (m :: * -> *) (v :: * -> *) b a.
(Monad m, Vector v b) =>
(a -> b -> m a) -> a -> v b -> m ()
G.foldM'_ a -> b -> m a
f a
x v b
v
{-# INLINE forAccumM_ #-}

mapAccumM ::
  (PrimMonad m, G.Vector v a, G.Vector v b) =>
  (s -> a -> m (s, b)) ->
  s ->
  v a ->
  m (v b)
mapAccumM :: forall (m :: * -> *) (v :: * -> *) a b s.
(PrimMonad m, Vector v a, Vector v b) =>
(s -> a -> m (s, b)) -> s -> v a -> m (v b)
mapAccumM s -> a -> m (s, b)
f s
x =
  (m (Mutable v (PrimState m) b)
-> (Mutable v (PrimState m) b -> m (v b)) -> m (v b)
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Mutable v (PrimState m) b -> m (v b)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
G.unsafeFreeze)
    (m (Mutable v (PrimState m) b) -> m (v b))
-> (v a -> m (Mutable v (PrimState m) b)) -> v a -> m (v b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MBundle m v b -> m (Mutable v (PrimState m) b)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
GM.munstream
    (MBundle m v b -> m (Mutable v (PrimState m) b))
-> (v a -> MBundle m v b) -> v a -> m (Mutable v (PrimState m) b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (s -> a -> m (s, b)) -> s -> Bundle m v a -> MBundle m v b
forall (m :: * -> *) s a b (v :: * -> *).
Monad m =>
(s -> a -> m (s, b)) -> s -> Bundle m v a -> Bundle m v b
bundleAccumM s -> a -> m (s, b)
f s
x
    (Bundle m v a -> MBundle m v b)
-> (v a -> Bundle m v a) -> v a -> MBundle m v b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle Id v a -> Bundle m v a
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift
    (Bundle Id v a -> Bundle m v a)
-> (v a -> Bundle Id v a) -> v a -> Bundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle Id v a
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
G.stream
{-# INLINE mapAccumM #-}

forAccumMaybe ::
  (G.Vector v a, G.Vector v b) =>
  s ->
  v a ->
  (s -> a -> (s, Maybe b)) ->
  v b
forAccumMaybe :: forall (v :: * -> *) a b s.
(Vector v a, Vector v b) =>
s -> v a -> (s -> a -> (s, Maybe b)) -> v b
forAccumMaybe s
x v a
v s -> a -> (s, Maybe b)
f = (s -> a -> (s, Maybe b)) -> s -> v a -> v b
forall (v :: * -> *) a b s.
(Vector v a, Vector v b) =>
(s -> a -> (s, Maybe b)) -> s -> v a -> v b
mapAccumMaybe s -> a -> (s, Maybe b)
f s
x v a
v
{-# INLINE forAccumMaybe #-}

mapAccumMaybe ::
  (G.Vector v a, G.Vector v b) =>
  (s -> a -> (s, Maybe b)) ->
  s ->
  v a ->
  v b
mapAccumMaybe :: forall (v :: * -> *) a b s.
(Vector v a, Vector v b) =>
(s -> a -> (s, Maybe b)) -> s -> v a -> v b
mapAccumMaybe s -> a -> (s, Maybe b)
f s
x =
  Bundle v b -> v b
forall (v :: * -> *) a. Vector v a => Bundle v a -> v a
G.unstream
    (Bundle v b -> v b) -> (v a -> Bundle v b) -> v a -> v b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall (m :: * -> *). Monad m => Stream m a -> Stream m b)
-> (Size -> Size) -> Bundle v a -> Bundle v b
forall a b (v :: * -> *).
(forall (m :: * -> *). Monad m => Stream m a -> Stream m b)
-> (Size -> Size) -> Bundle v a -> Bundle v b
Bundle.inplace
      ((s -> a -> m (s, Maybe b)) -> s -> Stream m a -> Stream m b
forall (m :: * -> *) s a b.
Monad m =>
(s -> a -> m (s, Maybe b)) -> s -> Stream m a -> Stream m b
streamAccumMaybeM (\s
s a
a -> (s, Maybe b) -> m (s, Maybe b)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (s -> a -> (s, Maybe b)
f s
s a
a)) s
x)
      Size -> Size
Bundle.toMax
    (Bundle v a -> Bundle v b)
-> (v a -> Bundle v a) -> v a -> Bundle v b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle v a
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
G.stream
{-# INLINE mapAccumMaybe #-}

forAccumMaybeM ::
  (PrimMonad m, G.Vector v a, G.Vector v b) =>
  s ->
  v a ->
  (s -> a -> m (s, Maybe b)) ->
  m (v b)
forAccumMaybeM :: forall (m :: * -> *) (v :: * -> *) a b s.
(PrimMonad m, Vector v a, Vector v b) =>
s -> v a -> (s -> a -> m (s, Maybe b)) -> m (v b)
forAccumMaybeM s
s v a
v s -> a -> m (s, Maybe b)
f = (s -> a -> m (s, Maybe b)) -> s -> v a -> m (v b)
forall (m :: * -> *) (v :: * -> *) a b s.
(PrimMonad m, Vector v a, Vector v b) =>
(s -> a -> m (s, Maybe b)) -> s -> v a -> m (v b)
mapAccumMaybeM s -> a -> m (s, Maybe b)
f s
s v a
v
{-# INLINE forAccumMaybeM #-}

mapAccumMaybeM ::
  (PrimMonad m, G.Vector v a, G.Vector v b) =>
  (s -> a -> m (s, Maybe b)) ->
  s ->
  v a ->
  m (v b)
mapAccumMaybeM :: forall (m :: * -> *) (v :: * -> *) a b s.
(PrimMonad m, Vector v a, Vector v b) =>
(s -> a -> m (s, Maybe b)) -> s -> v a -> m (v b)
mapAccumMaybeM s -> a -> m (s, Maybe b)
f s
x =
  (m (Mutable v (PrimState m) b)
-> (Mutable v (PrimState m) b -> m (v b)) -> m (v b)
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Mutable v (PrimState m) b -> m (v b)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
G.unsafeFreeze)
    (m (Mutable v (PrimState m) b) -> m (v b))
-> (v a -> m (Mutable v (PrimState m) b)) -> v a -> m (v b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MBundle m v b -> m (Mutable v (PrimState m) b)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
GM.munstream
    (MBundle m v b -> m (Mutable v (PrimState m) b))
-> (v a -> MBundle m v b) -> v a -> m (Mutable v (PrimState m) b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (s -> a -> m (s, Maybe b)) -> s -> Bundle m v a -> MBundle m v b
forall (m :: * -> *) s a b (v :: * -> *).
Monad m =>
(s -> a -> m (s, Maybe b)) -> s -> Bundle m v a -> Bundle m v b
bundleAccumMaybeM s -> a -> m (s, Maybe b)
f s
x
    (Bundle m v a -> MBundle m v b)
-> (v a -> Bundle m v a) -> v a -> MBundle m v b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle Id v a -> Bundle m v a
forall (m :: * -> *) (v :: * -> *) a.
Monad m =>
Bundle Id v a -> Bundle m v a
Bundle.lift
    (Bundle Id v a -> Bundle m v a)
-> (v a -> Bundle Id v a) -> v a -> Bundle m v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle Id v a
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
G.stream
{-# INLINE mapAccumMaybeM #-}

bundleAccumM ::
  (Monad m) =>
  (s -> a -> m (s, b)) ->
  s ->
  MBundle.Bundle m v a ->
  MBundle.Bundle m v b
bundleAccumM :: forall (m :: * -> *) s a b (v :: * -> *).
Monad m =>
(s -> a -> m (s, b)) -> s -> Bundle m v a -> Bundle m v b
bundleAccumM s -> a -> m (s, b)
f s
x Bundle m v a
bundle =
  Stream m b -> Size -> Bundle m v b
forall (m :: * -> *) a (v :: * -> *).
Monad m =>
Stream m a -> Size -> Bundle m v a
MBundle.fromStream
    ((s -> a -> m (s, b)) -> s -> Stream m a -> Stream m b
forall (m :: * -> *) s a b.
Monad m =>
(s -> a -> m (s, b)) -> s -> Stream m a -> Stream m b
streamAccumM s -> a -> m (s, b)
f s
x (Bundle m v a -> Stream m a
forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Stream m a
MBundle.elements Bundle m v a
bundle))
    (Bundle m v a -> Size
forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Size
MBundle.size Bundle m v a
bundle)
{-# INLINE [1] bundleAccumM #-}

bundleAccumMaybeM ::
  (Monad m) =>
  (s -> a -> m (s, Maybe b)) ->
  s ->
  MBundle.Bundle m v a ->
  MBundle.Bundle m v b
bundleAccumMaybeM :: forall (m :: * -> *) s a b (v :: * -> *).
Monad m =>
(s -> a -> m (s, Maybe b)) -> s -> Bundle m v a -> Bundle m v b
bundleAccumMaybeM s -> a -> m (s, Maybe b)
f s
x Bundle m v a
bundle =
  Stream m b -> Size -> Bundle m v b
forall (m :: * -> *) a (v :: * -> *).
Monad m =>
Stream m a -> Size -> Bundle m v a
MBundle.fromStream
    ((s -> a -> m (s, Maybe b)) -> s -> Stream m a -> Stream m b
forall (m :: * -> *) s a b.
Monad m =>
(s -> a -> m (s, Maybe b)) -> s -> Stream m a -> Stream m b
streamAccumMaybeM s -> a -> m (s, Maybe b)
f s
x (Bundle m v a -> Stream m a
forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Stream m a
MBundle.elements Bundle m v a
bundle))
    (Bundle m v a -> Size
forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Size
MBundle.size Bundle m v a
bundle)
{-# INLINE [1] bundleAccumMaybeM #-}

streamAccumM :: (Monad m) => (s -> a -> m (s, b)) -> s -> MS.Stream m a -> MS.Stream m b
streamAccumM :: forall (m :: * -> *) s a b.
Monad m =>
(s -> a -> m (s, b)) -> s -> Stream m a -> Stream m b
streamAccumM s -> a -> m (s, b)
f s
s0 (MS.Stream s -> m (Step s a)
step s
x0) = ((s, s) -> m (Step (s, s) b)) -> (s, s) -> Stream m b
forall (m :: * -> *) a s. (s -> m (Step s a)) -> s -> Stream m a
MS.Stream (s, s) -> m (Step (s, s) b)
step' (s
s0, s
x0)
  where
    step' :: (s, s) -> m (Step (s, s) b)
step' (!s
s, s
x) = do
      Step s a
r <- s -> m (Step s a)
step s
x
      case Step s a
r of
        MS.Yield a
a s
x' -> do
          (s
s', b
b) <- s -> a -> m (s, b)
f s
s a
a
          Step (s, s) b -> m (Step (s, s) b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (s, s) b -> m (Step (s, s) b))
-> Step (s, s) b -> m (Step (s, s) b)
forall a b. (a -> b) -> a -> b
$ b -> (s, s) -> Step (s, s) b
forall a s. a -> s -> Step s a
MS.Yield b
b (s
s', s
x')
        MS.Skip s
x' -> Step (s, s) b -> m (Step (s, s) b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (s, s) b -> m (Step (s, s) b))
-> Step (s, s) b -> m (Step (s, s) b)
forall a b. (a -> b) -> a -> b
$ (s, s) -> Step (s, s) b
forall s a. s -> Step s a
MS.Skip (s
s, s
x')
        Step s a
MS.Done -> Step (s, s) b -> m (Step (s, s) b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Step (s, s) b
forall s a. Step s a
MS.Done
    {-# INLINE [0] step' #-}
{-# INLINE [1] streamAccumM #-}

streamAccumMaybeM :: (Monad m) => (s -> a -> m (s, Maybe b)) -> s -> MS.Stream m a -> MS.Stream m b
streamAccumMaybeM :: forall (m :: * -> *) s a b.
Monad m =>
(s -> a -> m (s, Maybe b)) -> s -> Stream m a -> Stream m b
streamAccumMaybeM s -> a -> m (s, Maybe b)
f s
s0 (MS.Stream s -> m (Step s a)
step s
x0) = ((s, s) -> m (Step (s, s) b)) -> (s, s) -> Stream m b
forall (m :: * -> *) a s. (s -> m (Step s a)) -> s -> Stream m a
MS.Stream (s, s) -> m (Step (s, s) b)
step' (s
s0, s
x0)
  where
    step' :: (s, s) -> m (Step (s, s) b)
step' (!s
s, s
x) = do
      Step s a
r <- s -> m (Step s a)
step s
x
      case Step s a
r of
        MS.Yield a
a s
x' -> do
          (s
s', Maybe b
mb) <- s -> a -> m (s, Maybe b)
f s
s a
a
          Step (s, s) b -> m (Step (s, s) b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (s, s) b -> m (Step (s, s) b))
-> Step (s, s) b -> m (Step (s, s) b)
forall a b. (a -> b) -> a -> b
$ case Maybe b
mb of
            Just b
b -> b -> (s, s) -> Step (s, s) b
forall a s. a -> s -> Step s a
MS.Yield b
b (s
s', s
x')
            Maybe b
Nothing -> (s, s) -> Step (s, s) b
forall s a. s -> Step s a
MS.Skip (s
s', s
x')
        MS.Skip s
x' -> Step (s, s) b -> m (Step (s, s) b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Step (s, s) b -> m (Step (s, s) b))
-> Step (s, s) b -> m (Step (s, s) b)
forall a b. (a -> b) -> a -> b
$ (s, s) -> Step (s, s) b
forall s a. s -> Step s a
MS.Skip (s
s, s
x')
        Step s a
MS.Done -> Step (s, s) b -> m (Step (s, s) b)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Step (s, s) b
forall s a. Step s a
MS.Done
    {-# INLINE [0] step' #-}
{-# INLINE [1] streamAccumMaybeM #-}

stream :: (G.Vector v a) => v a -> MS.Stream Id a
stream :: forall (v :: * -> *) a. Vector v a => v a -> Stream Id a
stream = Bundle Id v a -> Stream Id a
forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Stream m a
MBundle.elements (Bundle Id v a -> Stream Id a)
-> (v a -> Bundle Id v a) -> v a -> Stream Id a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle Id v a
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
G.stream
{-# INLINE stream #-}

streamM :: (G.Vector v a, Monad m) => v a -> MS.Stream m a
streamM :: forall (v :: * -> *) a (m :: * -> *).
(Vector v a, Monad m) =>
v a -> Stream m a
streamM = (forall z. Id z -> m z) -> Stream Id a -> Stream m a
forall (m :: * -> *) (m' :: * -> *) a.
(Monad m, Monad m') =>
(forall z. m z -> m' z) -> Stream m a -> Stream m' a
MS.trans (z -> m z
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (z -> m z) -> (Id z -> z) -> Id z -> m z
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Id z -> z
forall a. Id a -> a
unId) (Stream Id a -> Stream m a)
-> (v a -> Stream Id a) -> v a -> Stream m a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bundle Id v a -> Stream Id a
forall (m :: * -> *) (v :: * -> *) a. Bundle m v a -> Stream m a
MBundle.elements (Bundle Id v a -> Stream Id a)
-> (v a -> Bundle Id v a) -> v a -> Stream Id a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v a -> Bundle Id v a
forall (v :: * -> *) a. Vector v a => v a -> Bundle v a
G.stream
{-# INLINE streamM #-}

{- |
>>> asUVector . unstream 10 . stream $ U.fromList "abc"
"abc"
-}
unstream :: (G.Vector v a) => Int -> MS.Stream Id a -> v a
unstream :: forall (v :: * -> *) a. Vector v a => Int -> Stream Id a -> v a
unstream Int
ub =
  Bundle v a -> v a
forall (v :: * -> *) a. Vector v a => Bundle v a -> v a
G.unstream
    (Bundle v a -> v a)
-> (Stream Id a -> Bundle v a) -> Stream Id a -> v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Stream Id a -> Size -> Bundle v a)
-> Size -> Stream Id a -> Bundle v a
forall a b c. (a -> b -> c) -> b -> a -> c
flip Stream Id a -> Size -> Bundle v a
forall (m :: * -> *) a (v :: * -> *).
Monad m =>
Stream m a -> Size -> Bundle m v a
MBundle.fromStream (Int -> Size
Bundle.Max Int
ub)
{-# INLINE unstream #-}

unstreamM ::
  (PrimMonad m, G.Vector v a) =>
  Int ->
  MS.Stream m a ->
  m (v a)
unstreamM :: forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Int -> Stream m a -> m (v a)
unstreamM Int
ub Stream m a
s =
  MBundle m Any a -> m (Mutable v (PrimState m) a)
forall (m :: * -> *) (v :: * -> * -> *) a (u :: * -> *).
(PrimMonad m, MVector v a) =>
MBundle m u a -> m (v (PrimState m) a)
GM.munstream
    (Stream m a -> Size -> MBundle m Any a
forall (m :: * -> *) a (v :: * -> *).
Monad m =>
Stream m a -> Size -> Bundle m v a
MBundle.fromStream Stream m a
s (Int -> Size
Bundle.Max Int
ub))
    m (Mutable v (PrimState m) a)
-> (Mutable v (PrimState m) a -> m (v a)) -> m (v a)
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= Mutable v (PrimState m) a -> m (v a)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
Mutable v (PrimState m) a -> m (v a)
G.unsafeFreeze
{-# INLINE [1] unstreamM #-}

-- * Bits utils
infixl 8 `shiftRL`, `unsafeShiftRL`, !>>>.

shiftRL :: Int -> Int -> Int
shiftRL :: Int -> Int -> Int
shiftRL = Int -> Int -> Int
unsafeShiftRL
{-# INLINE shiftRL #-}

{- |
>>> unsafeShiftR (-1) 1
-1
>>> unsafeShiftRL (-1) 1
9223372036854775807
-}
unsafeShiftRL :: Int -> Int -> Int
unsafeShiftRL :: Int -> Int -> Int
unsafeShiftRL (I# Int#
x#) (I# Int#
i#) = Int# -> Int
I# (Int# -> Int# -> Int#
uncheckedIShiftRL# Int#
x# Int#
i#)
{-# INLINE unsafeShiftRL #-}

(!>>>.) :: Int -> Int -> Int
!>>>. :: Int -> Int -> Int
(!>>>.) = Int -> Int -> Int
unsafeShiftRL
{-# INLINE (!>>>.) #-}

-- * Parser utils
uvectorN :: (U.Unbox a) => Int -> PrimParser a -> PrimParser (U.Vector a)
uvectorN :: forall a. Unbox a => Int -> PrimParser a -> PrimParser (Vector a)
uvectorN = Int -> PrimParser a -> PrimParser (Vector a)
forall (v :: * -> *) a.
Vector v a =>
Int -> PrimParser a -> PrimParser (v a)
gvectorN
{-# INLINE uvectorN #-}

bvectorN :: Int -> PrimParser a -> PrimParser (V.Vector a)
bvectorN :: forall a. Int -> PrimParser a -> PrimParser (Vector a)
bvectorN = Int -> PrimParser a -> PrimParser (Vector a)
forall (v :: * -> *) a.
Vector v a =>
Int -> PrimParser a -> PrimParser (v a)
gvectorN
{-# INLINE bvectorN #-}

gvectorN :: (G.Vector v a) => Int -> PrimParser a -> PrimParser (v a)
gvectorN :: forall (v :: * -> *) a.
Vector v a =>
Int -> PrimParser a -> PrimParser (v a)
gvectorN Int
n PrimParser a
f = do
  (Ptr Word8
e, Ptr Word8
o) <- PrimParser (Ptr Word8, Ptr Word8)
viewPrimParser
  v a -> PrimParser (v a)
forall a. a -> PrimParser a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (v a -> PrimParser (v a)) -> v a -> PrimParser (v a)
forall a b. (a -> b) -> a -> b
$ Int -> (Ptr Word8 -> (a, Ptr Word8)) -> Ptr Word8 -> v a
forall (v :: * -> *) a b.
Vector v a =>
Int -> (b -> (a, b)) -> b -> v a
G.unfoldrExactN Int
n (PrimParser a -> Ptr Word8 -> Ptr Word8 -> (a, Ptr Word8)
forall a. PrimParser a -> Ptr Word8 -> Ptr Word8 -> (a, Ptr Word8)
runPrimParser PrimParser a
f Ptr Word8
e) Ptr Word8
o
{-# INLINE gvectorN #-}

streamN :: Int -> PrimParser a -> PrimParser (MS.Stream Id a)
streamN :: forall a. Int -> PrimParser a -> PrimParser (Stream Id a)
streamN Int
n PrimParser a
f = do
  (Ptr Word8
e, Ptr Word8
o) <- PrimParser (Ptr Word8, Ptr Word8)
viewPrimParser
  Stream Id a -> PrimParser (Stream Id a)
forall a. a -> PrimParser a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Stream Id a -> PrimParser (Stream Id a))
-> Stream Id a -> PrimParser (Stream Id a)
forall a b. (a -> b) -> a -> b
$ Int -> (Ptr Word8 -> (a, Ptr Word8)) -> Ptr Word8 -> Stream Id a
forall (m :: * -> *) s a.
Monad m =>
Int -> (s -> (a, s)) -> s -> Stream m a
MS.unfoldrExactN Int
n (PrimParser a -> Ptr Word8 -> Ptr Word8 -> (a, Ptr Word8)
forall a. PrimParser a -> Ptr Word8 -> Ptr Word8 -> (a, Ptr Word8)
runPrimParser PrimParser a
f Ptr Word8
e) Ptr Word8
o
{-# INLINE streamN #-}

uvector :: (U.Unbox a) => PrimParser a -> PrimParser (U.Vector a)
uvector :: forall a. Unbox a => PrimParser a -> PrimParser (Vector a)
uvector = PrimParser a -> PrimParser (Vector a)
forall (v :: * -> *) a.
Vector v a =>
PrimParser a -> PrimParser (v a)
gvector
{-# INLINE uvector #-}

gvector :: (G.Vector v a) => PrimParser a -> PrimParser (v a)
gvector :: forall (v :: * -> *) a.
Vector v a =>
PrimParser a -> PrimParser (v a)
gvector PrimParser a
f = do
  (Ptr Word8
e, Ptr Word8
o) <- PrimParser (Ptr Word8, Ptr Word8)
viewPrimParser
  v a -> PrimParser (v a)
forall a. a -> PrimParser a
forall (f :: * -> *) a. Applicative f => a -> f a
pure
    (v a -> PrimParser (v a)) -> v a -> PrimParser (v a)
forall a b. (a -> b) -> a -> b
$ (Ptr Word8 -> Maybe (a, Ptr Word8)) -> Ptr Word8 -> v a
forall (v :: * -> *) a b.
Vector v a =>
(b -> Maybe (a, b)) -> b -> v a
G.unfoldr
      ( \Ptr Word8
p -> case PrimParser a -> Ptr Word8 -> Ptr Word8 -> (a, Ptr Word8)
forall a. PrimParser a -> Ptr Word8 -> Ptr Word8 -> (a, Ptr Word8)
runPrimParser PrimParser a
f Ptr Word8
e Ptr Word8
p of
          (a
x, Ptr Word8
p')
            | Ptr Word8
p' Ptr Word8 -> Ptr Word8 -> Bool
forall a. Ord a => a -> a -> Bool
< Ptr Word8
e -> (a, Ptr Word8) -> Maybe (a, Ptr Word8)
forall a. a -> Maybe a
Just (a
x, Ptr Word8
p')
            | Bool
otherwise -> Maybe (a, Ptr Word8)
forall a. Maybe a
Nothing
      )
      Ptr Word8
o
{-# INLINE gvector #-}

byteArrayN :: Int -> PrimParser ByteArray
byteArrayN :: Int -> PrimParser ByteArray
byteArrayN n :: Int
n@(I# Int#
n#) = (Addr# -> Addr# -> (# Addr#, ByteArray #)) -> PrimParser ByteArray
forall a. (Addr# -> Addr# -> (# Addr#, a #)) -> PrimParser a
PrimParser ((Addr# -> Addr# -> (# Addr#, ByteArray #))
 -> PrimParser ByteArray)
-> (Addr# -> Addr# -> (# Addr#, ByteArray #))
-> PrimParser ByteArray
forall a b. (a -> b) -> a -> b
$ \Addr#
_ Addr#
p ->
  let !ba :: ByteArray
ba = (forall s. ST s ByteArray) -> ByteArray
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s ByteArray) -> ByteArray)
-> (forall s. ST s ByteArray) -> ByteArray
forall a b. (a -> b) -> a -> b
$ do
        MutableByteArray s
buf <- Int -> ST s (MutableByteArray (PrimState (ST s)))
forall (m :: * -> *).
PrimMonad m =>
Int -> m (MutableByteArray (PrimState m))
newByteArray Int
n
        forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutableByteArray (PrimState m) -> Int -> Ptr a -> Int -> m ()
copyPtrToMutableByteArray @_ @Word8 MutableByteArray s
MutableByteArray (PrimState (ST s))
buf Int
0 (Addr# -> Ptr Word8
forall a. Addr# -> Ptr a
Ptr Addr#
p) Int
n
        MutableByteArray (PrimState (ST s)) -> Int -> Int -> ST s ByteArray
forall (m :: * -> *).
PrimMonad m =>
MutableByteArray (PrimState m) -> Int -> Int -> m ByteArray
freezeByteArray MutableByteArray s
MutableByteArray (PrimState (ST s))
buf Int
0 Int
n
   in (# Addr# -> Int# -> Addr#
plusAddr# Addr#
p Int#
n#, ByteArray
ba #)
{-# INLINE byteArrayN #-}

byteArrayHW :: Int -> Int -> PrimParser ByteArray
byteArrayHW :: Int -> Int -> PrimParser ByteArray
byteArrayHW h :: Int
h@(I# Int#
h#) w :: Int
w@(I# Int#
w#) = (Addr# -> Addr# -> (# Addr#, ByteArray #)) -> PrimParser ByteArray
forall a. (Addr# -> Addr# -> (# Addr#, a #)) -> PrimParser a
PrimParser ((Addr# -> Addr# -> (# Addr#, ByteArray #))
 -> PrimParser ByteArray)
-> (Addr# -> Addr# -> (# Addr#, ByteArray #))
-> PrimParser ByteArray
forall a b. (a -> b) -> a -> b
$ \Addr#
_ Addr#
p ->
  let !ba :: ByteArray
ba = (forall s. ST s ByteArray) -> ByteArray
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s ByteArray) -> ByteArray)
-> (forall s. ST s ByteArray) -> ByteArray
forall a b. (a -> b) -> a -> b
$ do
        MutableByteArray s
buf <- Int -> ST s (MutableByteArray (PrimState (ST s)))
forall (m :: * -> *).
PrimMonad m =>
Int -> m (MutableByteArray (PrimState m))
newByteArray (Int
h Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
w)
        ((Ptr Word8 -> Int -> ST s ()) -> Ptr Word8 -> Int -> ST s ())
-> Ptr Word8 -> Int -> ST s ()
forall a. (a -> a) -> a
fix
          ( \Ptr Word8 -> Int -> ST s ()
loop !Ptr Word8
src !Int
i -> Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
h) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
              forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutableByteArray (PrimState m) -> Int -> Ptr a -> Int -> m ()
copyPtrToMutableByteArray @_ @Word8 MutableByteArray s
MutableByteArray (PrimState (ST s))
buf (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
w) Ptr Word8
src Int
w
              Ptr Word8 -> Int -> ST s ()
loop (Ptr Word8 -> Int -> Ptr Word8
forall a b. Ptr a -> Int -> Ptr b
plusPtr Ptr Word8
src (Int
w Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
          )
          (Addr# -> Ptr Word8
forall a. Addr# -> Ptr a
Ptr Addr#
p)
          Int
0
        MutableByteArray (PrimState (ST s)) -> Int -> Int -> ST s ByteArray
forall (m :: * -> *).
PrimMonad m =>
MutableByteArray (PrimState m) -> Int -> Int -> m ByteArray
freezeByteArray MutableByteArray s
MutableByteArray (PrimState (ST s))
buf Int
0 (Int
h Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
w)
   in (# Addr# -> Int# -> Addr#
plusAddr# Addr#
p (Int#
h# Int# -> Int# -> Int#
*# (Int#
w# Int# -> Int# -> Int#
+# Int#
1#)), ByteArray
ba #)
{-# INLINE byteArrayHW #-}

-- * Builder utils
unlinesB :: (G.Vector v a) => (a -> B.Builder) -> v a -> B.Builder
unlinesB :: forall (v :: * -> *) a.
Vector v a =>
(a -> Builder) -> v a -> Builder
unlinesB a -> Builder
f = (a -> Builder) -> v a -> Builder
forall m (v :: * -> *) a.
(Monoid m, Vector v a) =>
(a -> m) -> v a -> m
G.foldMap ((Builder -> Builder -> Builder
forall a. Semigroup a => a -> a -> a
<> Builder
lfB) (Builder -> Builder) -> (a -> Builder) -> a -> Builder
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Builder
f)

unwordsB :: (G.Vector v a) => (a -> B.Builder) -> v a -> B.Builder
unwordsB :: forall (v :: * -> *) a.
Vector v a =>
(a -> Builder) -> v a -> Builder
unwordsB a -> Builder
f v a
vec
  | v a -> Bool
forall (v :: * -> *) a. Vector v a => v a -> Bool
G.null v a
vec = Builder
forall a. Monoid a => a
mempty
  | Bool
otherwise =
      a -> Builder
f (v a -> a
forall (v :: * -> *) a. Vector v a => v a -> a
G.head v a
vec)
        Builder -> Builder -> Builder
forall a. Semigroup a => a -> a -> a
<> (a -> Builder) -> v a -> Builder
forall m (v :: * -> *) a.
(Monoid m, Vector v a) =>
(a -> m) -> v a -> m
G.foldMap ((Builder
spB <>) (Builder -> Builder) -> (a -> Builder) -> a -> Builder
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Builder
f) (v a -> v a
forall (v :: * -> *) a. Vector v a => v a -> v a
G.tail v a
vec)

concatB :: (G.Vector v a) => (a -> B.Builder) -> v a -> B.Builder
concatB :: forall (v :: * -> *) a.
Vector v a =>
(a -> Builder) -> v a -> Builder
concatB = (a -> Builder) -> v a -> Builder
forall m (v :: * -> *) a.
(Monoid m, Vector v a) =>
(a -> m) -> v a -> m
G.foldMap

{- |
>>> matrixB 2 3 B.intDec $ U.fromListN 6 [1, 2, 3, 4, 5, 6]
"1 2 3\n4 5 6\n"
-}
matrixB :: (G.Vector v a) => Int -> Int -> (a -> B.Builder) -> v a -> B.Builder
matrixB :: forall (v :: * -> *) a.
Vector v a =>
Int -> Int -> (a -> Builder) -> v a -> Builder
matrixB Int
h Int
w a -> Builder
f !v a
mat =
  (Int -> Builder) -> Vector Int -> Builder
forall m a. (Monoid m, Unbox a) => (a -> m) -> Vector a -> m
U.foldMap
    ( \Int
i ->
        (a -> Builder) -> v a -> Builder
forall (v :: * -> *) a.
Vector v a =>
(a -> Builder) -> v a -> Builder
unwordsB a -> Builder
f (Int -> Int -> v a -> v a
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
Int -> Int -> v a -> v a
G.slice (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
w) Int
w v a
mat) Builder -> Builder -> Builder
forall a. Semigroup a => a -> a -> a
<> Builder
lfB
    )
    (Vector Int -> Builder) -> Vector Int -> Builder
forall a b. (a -> b) -> a -> b
$ Int -> (Int -> Int) -> Vector Int
forall a. Unbox a => Int -> (Int -> a) -> Vector a
U.generate Int
h Int -> Int
forall a. a -> a
id

{- |
>>> gridB 2 3 B.char7 $ U.fromListN 6 ".#.#.#"
".#.\n#.#\n"
>>> gridB 2 3 B.intDec $ U.fromListN 6 [1, 2, 3, 4, 5, 6]
"123\n456\n"
-}
gridB :: (G.Vector v a) => Int -> Int -> (a -> B.Builder) -> v a -> B.Builder
gridB :: forall (v :: * -> *) a.
Vector v a =>
Int -> Int -> (a -> Builder) -> v a -> Builder
gridB Int
h Int
w a -> Builder
f v a
mat =
  (Int -> Builder) -> Vector Int -> Builder
forall m a. (Monoid m, Unbox a) => (a -> m) -> Vector a -> m
U.foldMap
    ( \Int
i ->
        (a -> Builder) -> v a -> Builder
forall m (v :: * -> *) a.
(Monoid m, Vector v a) =>
(a -> m) -> v a -> m
G.foldMap a -> Builder
f (Int -> Int -> v a -> v a
forall (v :: * -> *) a.
(HasCallStack, Vector v a) =>
Int -> Int -> v a -> v a
G.slice (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
* Int
w) Int
w v a
mat) Builder -> Builder -> Builder
forall a. Semigroup a => a -> a -> a
<> Builder
lfB
    )
    (Vector Int -> Builder) -> Vector Int -> Builder
forall a b. (a -> b) -> a -> b
$ Int -> (Int -> Int) -> Vector Int
forall a. Unbox a => Int -> (Int -> a) -> Vector a
U.generate Int
h Int -> Int
forall a. a -> a
id

sizedB :: (G.Vector v a) => (v a -> B.Builder) -> v a -> B.Builder
sizedB :: forall (v :: * -> *) a.
Vector v a =>
(v a -> Builder) -> v a -> Builder
sizedB v a -> Builder
f v a
vec = Int -> Builder
B.intDec (v a -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v a
vec) Builder -> Builder -> Builder
forall a. Semigroup a => a -> a -> a
<> Builder
lfB Builder -> Builder -> Builder
forall a. Semigroup a => a -> a -> a
<> v a -> Builder
f v a
vec

{- |
>>> yesnoB True
"Yes"
>>> yesnoB False
"No"
-}
yesnoB :: Bool -> B.Builder
yesnoB :: Bool -> Builder
yesnoB = BoundedPrim Bool -> Bool -> Builder
forall a. BoundedPrim a -> a -> Builder
BP.primBounded (BoundedPrim Bool -> Bool -> Builder)
-> BoundedPrim Bool -> Bool -> Builder
forall a b. (a -> b) -> a -> b
$ Int -> (Bool -> Ptr Word8 -> IO (Ptr Word8)) -> BoundedPrim Bool
forall a.
Int -> (a -> Ptr Word8 -> IO (Ptr Word8)) -> BoundedPrim a
BP.boundedPrim Int
4 ((Bool -> Ptr Word8 -> IO (Ptr Word8)) -> BoundedPrim Bool)
-> (Bool -> Ptr Word8 -> IO (Ptr Word8)) -> BoundedPrim Bool
forall a b. (a -> b) -> a -> b
$ \Bool
flg Ptr Word8
ptr -> do
  if Bool
flg
    then do
      Ptr Word32 -> Word32 -> IO ()
forall a. Storable a => Ptr a -> a -> IO ()
poke (Ptr Word8 -> Ptr Word32
forall a b. Ptr a -> Ptr b
castPtr Ptr Word8
ptr) (Word32
0x00736559 :: Word32)
      Ptr Word8 -> IO (Ptr Word8)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (Ptr Word8 -> IO (Ptr Word8)) -> Ptr Word8 -> IO (Ptr Word8)
forall a b. (a -> b) -> a -> b
$! Ptr Word8 -> Int -> Ptr Word8
forall a b. Ptr a -> Int -> Ptr b
plusPtr Ptr Word8
ptr Int
3
    else do
      Ptr Word16 -> Word16 -> IO ()
forall a. Storable a => Ptr a -> a -> IO ()
poke (Ptr Word8 -> Ptr Word16
forall a b. Ptr a -> Ptr b
castPtr Ptr Word8
ptr) (Word16
0x6f4e :: Word16)
      Ptr Word8 -> IO (Ptr Word8)
forall a. a -> IO a
forall (m :: * -> *) a. Monad m => a -> m a
return (Ptr Word8 -> IO (Ptr Word8)) -> Ptr Word8 -> IO (Ptr Word8)
forall a b. (a -> b) -> a -> b
$! Ptr Word8 -> Int -> Ptr Word8
forall a b. Ptr a -> Int -> Ptr b
plusPtr Ptr Word8
ptr Int
2
{-# INLINE yesnoB #-}

{- |
>>> pairB B.intDec B.intDec $ (0, 1)
"0 1"
>>> pairB B.intDec (pairB B.intDec B.intDec) $ (0, (1, 2))
"0 1 2"
-}
pairB :: (a -> B.Builder) -> (b -> B.Builder) -> (a, b) -> B.Builder
pairB :: forall a b. (a -> Builder) -> (b -> Builder) -> (a, b) -> Builder
pairB a -> Builder
f b -> Builder
g (a
x, b
y) = a -> Builder
f a
x Builder -> Builder -> Builder
forall a. Semigroup a => a -> a -> a
<> Builder
spB Builder -> Builder -> Builder
forall a. Semigroup a => a -> a -> a
<> b -> Builder
g b
y

showB :: (Show a) => a -> B.Builder
showB :: forall a. Show a => a -> Builder
showB = String -> Builder
B.string7 (String -> Builder) -> (a -> String) -> a -> Builder
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> String
forall a. Show a => a -> String
show

showLnB :: (Show a) => a -> B.Builder
showLnB :: forall a. Show a => a -> Builder
showLnB = String -> Builder
B.string7 (String -> Builder) -> (a -> String) -> a -> Builder
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> String -> String) -> String -> a -> String
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> String -> String
forall a. Show a => a -> String -> String
shows String
"\n"

{- |
>>> lfB
"\n"
-}
lfB :: B.Builder
lfB :: Builder
lfB = Word8 -> Builder
B.word8 Word8
0x0a

{- |
>>> spB
" "
-}
spB :: B.Builder
spB :: Builder
spB = Word8 -> Builder
B.word8 Word8
0x20

putBuilder :: (MonadIO m) => B.Builder -> m ()
putBuilder :: forall (m :: * -> *). MonadIO m => Builder -> m ()
putBuilder = IO () -> m ()
forall a. IO a -> m a
forall (m :: * -> *) a. MonadIO m => IO a -> m a
liftIO (IO () -> m ()) -> (Builder -> IO ()) -> Builder -> m ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Handle -> Builder -> IO ()
B.hPutBuilder Handle
stdout

putBuilderLn :: (MonadIO m) => B.Builder -> m ()
putBuilderLn :: forall (m :: * -> *). MonadIO m => Builder -> m ()
putBuilderLn Builder
b = Builder -> m ()
forall (m :: * -> *). MonadIO m => Builder -> m ()
putBuilder Builder
b m () -> m () -> m ()
forall a b. m a -> m b -> m b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> Builder -> m ()
forall (m :: * -> *). MonadIO m => Builder -> m ()
putBuilder Builder
lfB

-- * Misc
neighbor4 :: (Applicative f) => Int -> Int -> Int -> (Int -> f ()) -> f ()
neighbor4 :: forall (f :: * -> *).
Applicative f =>
Int -> Int -> Int -> (Int -> f ()) -> f ()
neighbor4 Int
h Int
w Int
xy Int -> f ()
f =
  Bool -> f () -> f ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
0) (Int -> f ()
f (Int -> f ()) -> Int -> f ()
forall a b. (a -> b) -> a -> b
$ Int
xy Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
w)
    f () -> f () -> f ()
forall a b. f a -> f b -> f b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> Bool -> f () -> f ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
y Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
0) (Int -> f ()
f (Int -> f ()) -> Int -> f ()
forall a b. (a -> b) -> a -> b
$ Int
xy Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
    f () -> f () -> f ()
forall a b. f a -> f b -> f b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> Bool -> f () -> f ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
y Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
w Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (Int -> f ()
f (Int -> f ()) -> Int -> f ()
forall a b. (a -> b) -> a -> b
$ Int
xy Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
    f () -> f () -> f ()
forall a b. f a -> f b -> f b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> Bool -> f () -> f ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
h Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) (Int -> f ()
f (Int -> f ()) -> Int -> f ()
forall a b. (a -> b) -> a -> b
$ Int
xy Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
w)
  where
    (!Int
x, !Int
y) = Int -> Int -> (Int, Int)
forall a. Integral a => a -> a -> (a, a)
quotRem Int
xy Int
w
{-# INLINE neighbor4 #-}

binarySearchM :: (Monad m) => Int -> Int -> (Int -> m Bool) -> m Int
binarySearchM :: forall (m :: * -> *).
Monad m =>
Int -> Int -> (Int -> m Bool) -> m Int
binarySearchM Int
low0 Int
high0 Int -> m Bool
p = Int -> Int -> m Int
go Int
low0 Int
high0
  where
    go :: Int -> Int -> m Int
go !Int
low !Int
high
      | Int
high Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
low = Int -> m Int
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Int
high
      | Bool
otherwise = Int -> m Bool
p Int
mid m Bool -> (Bool -> m Int) -> m Int
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= m Int -> m Int -> Bool -> m Int
forall a. a -> a -> Bool -> a
bool (Int -> Int -> m Int
go (Int
mid Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int
high) (Int -> Int -> m Int
go Int
low Int
mid)
      where
        mid :: Int
mid = Int
low Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Int -> Int
unsafeShiftRL (Int
high Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
low) Int
1
{-# INLINE binarySearchM #-}

binarySearch :: Int -> Int -> (Int -> Bool) -> Int
binarySearch :: Int -> Int -> (Int -> Bool) -> Int
binarySearch Int
low Int
high Int -> Bool
p = Identity Int -> Int
forall a. Identity a -> a
runIdentity (Identity Int -> Int) -> Identity Int -> Int
forall a b. (a -> b) -> a -> b
$ Int -> Int -> (Int -> Identity Bool) -> Identity Int
forall (m :: * -> *).
Monad m =>
Int -> Int -> (Int -> m Bool) -> m Int
binarySearchM Int
low Int
high (Bool -> Identity Bool
forall a. a -> Identity a
forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Identity Bool) -> (Int -> Bool) -> Int -> Identity Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Bool
p)
{-# INLINE binarySearch #-}

encode32x2 :: Int -> Int -> Int
encode32x2 :: Int -> Int -> Int
encode32x2 Int
x Int
y = Int -> Int -> Int
forall a. Bits a => a -> Int -> a
unsafeShiftL Int
x Int
32 Int -> Int -> Int
forall a. Bits a => a -> a -> a
.|. Int
y
{-# INLINE encode32x2 #-}

decode32x2 :: Int -> (Int, Int)
decode32x2 :: Int -> (Int, Int)
decode32x2 Int
xy =
  let !x :: Int
x = Int -> Int -> Int
unsafeShiftRL Int
xy Int
32
      !y :: Int
y = Int
xy Int -> Int -> Int
forall a. Bits a => a -> a -> a
.&. Int
0xffffffff
   in (Int
x, Int
y)
{-# INLINE decode32x2 #-}

runSolver :: (a -> IO ()) -> PrimParser a -> IO ()
runSolver :: forall a. (a -> IO ()) -> PrimParser a -> IO ()
runSolver = Handle -> (a -> IO ()) -> PrimParser a -> IO ()
forall a r. Handle -> (a -> IO r) -> PrimParser a -> IO r
withInputHandle Handle
stdin