module StreamPatch.Patch.Linearize.Insert where
import Control.Monad.State
import Data.List qualified as List
import StreamPatch.Util ( traverseM )
linearize
:: (Integral sf, Integral st)
=> (a -> sf)
-> (st -> a -> b)
-> [a] -> Either (a, a) (Maybe (a, [b]))
linearize :: forall sf st a b.
(Integral sf, Integral st) =>
(a -> sf)
-> (st -> a -> b) -> [a] -> Either (a, a) (Maybe (a, [b]))
linearize a -> sf
f st -> a -> b
g [a]
as =
case forall a. (a -> a -> Ordering) -> [a] -> [a]
List.sortBy a -> a -> Ordering
cmp [a]
as of
[] -> forall a b. b -> Either a b
Right forall a. Maybe a
Nothing
(a
a:[a]
as') -> do
[b]
bs <- forall s a. State s a -> s -> a
evalState (forall (t :: * -> *) (f :: * -> *) (m :: * -> *) v v'.
(Traversable t, Applicative f, Monad m) =>
(v -> m (f v')) -> t v -> m (f (t v'))
traverseM a -> StateT a Identity (Either (a, a) b)
go [a]
as') a
a
forall a b. b -> Either a b
Right forall a b. (a -> b) -> a -> b
$ forall a. a -> Maybe a
Just (a
a, [b]
bs)
where
cmp :: a -> a -> Ordering
cmp a
a1 a
a2 = forall a. Ord a => a -> a -> Ordering
compare (a -> sf
f a
a1) (a -> sf
f a
a2)
go :: a -> StateT a Identity (Either (a, a) b)
go a
a = do
a
a' <- forall s (m :: * -> *). MonadState s m => m s
get
let s' :: st
s' = forall a b. (Integral a, Num b) => a -> b
fromIntegral forall a b. (a -> b) -> a -> b
$ a -> sf
f a
a forall a. Num a => a -> a -> a
- a -> sf
f a
a'
if st
s' forall a. Eq a => a -> a -> Bool
== st
0
then forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$ forall a b. a -> Either a b
Left (a
a, a
a')
else forall s (m :: * -> *). MonadState s m => s -> m ()
put a
a forall (m :: * -> *) a b. Monad m => m a -> m b -> m b
>> forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall a b. b -> Either a b
Right (st -> a -> b
g st
s' a
a))
linearize' :: (Integral sf, Integral st) => [sf] -> Either (sf, sf) (Maybe (sf, [st]))
linearize' :: forall sf st.
(Integral sf, Integral st) =>
[sf] -> Either (sf, sf) (Maybe (sf, [st]))
linearize' = forall sf st a b.
(Integral sf, Integral st) =>
(a -> sf)
-> (st -> a -> b) -> [a] -> Either (a, a) (Maybe (a, [b]))
linearize forall a. a -> a
id forall a b. a -> b -> a
const