{-# LANGUAGE DeriveTraversable #-}

{-| __Warning:__ This module is __internal__, and does __not__ follow
  the Package Versioning Policy. It may be useful for extending
  Brassica, but be prepared to track development closely if you import
  this module.
-}
module Brassica.SoundChange.Apply.Internal.MultiZipper
       ( MultiZipper
       -- * Conversion

       , fromListStart
       , fromListPos
       , toList
       -- * Querying

       , curPos
       , atStart
       , atEnd
       , atBoundary
       , value
       , valueN
       , locationOf
       , yank
       -- * Movement

       , move
       , fwd
       , bwd
       , consume
       , seek
       , toBeginning
       , toEnd
       -- * Modification

       , insert
       , insertMany
       , zap
       , tag
       , tagAt
       , query
       , untag
       , untagWhen
       , modifyBetween
       , extend
       , extend'
       ) where

import Control.Applicative (Alternative((<|>)))
import Data.Foldable (Foldable(foldl'))
import qualified Data.Map.Strict as M

-- | A 'MultiZipper' is a list zipper (list+current index), with the

-- addition of ‘tags’ which can be assigned to indices in the

-- list. Any tag may be assigned to any index, with the restriction

-- that two different indices may not be tagged with the same

-- tag. This sort of data structure is useful for certain algorithms,

-- where it can be convenient to use tags to save positions in the

-- list and then return back to them later.

--

-- (One subtlety: unlike most list zipper implementations, a

-- 'MultiZipper' positioned at the ‘end’ of a list is actually at

-- positioned at the index one past the end of the list, rather than

-- at the last element of the list. Although this makes some functions

-- slightly more complex — most notably, 'value' becomes non-total —

-- it makes other algorithms simpler. For instance, this lets

-- functions processing a 'MultiZipper' to process a portion of the

-- 'MultiZipper' and then move to the next element immediately after

-- the processed portion, allowing another function to be run to

-- process the next part of the 'MultiZipper'.)

data MultiZipper t a = MultiZipper [a] Int (M.Map t Int)
    deriving (Int -> MultiZipper t a -> ShowS
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall t a. (Show a, Show t) => Int -> MultiZipper t a -> ShowS
forall t a. (Show a, Show t) => [MultiZipper t a] -> ShowS
forall t a. (Show a, Show t) => MultiZipper t a -> String
showList :: [MultiZipper t a] -> ShowS
$cshowList :: forall t a. (Show a, Show t) => [MultiZipper t a] -> ShowS
show :: MultiZipper t a -> String
$cshow :: forall t a. (Show a, Show t) => MultiZipper t a -> String
showsPrec :: Int -> MultiZipper t a -> ShowS
$cshowsPrec :: forall t a. (Show a, Show t) => Int -> MultiZipper t a -> ShowS
Show, forall a b. a -> MultiZipper t b -> MultiZipper t a
forall a b. (a -> b) -> MultiZipper t a -> MultiZipper t b
forall t a b. a -> MultiZipper t b -> MultiZipper t a
forall t a b. (a -> b) -> MultiZipper t a -> MultiZipper t b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> MultiZipper t b -> MultiZipper t a
$c<$ :: forall t a b. a -> MultiZipper t b -> MultiZipper t a
fmap :: forall a b. (a -> b) -> MultiZipper t a -> MultiZipper t b
$cfmap :: forall t a b. (a -> b) -> MultiZipper t a -> MultiZipper t b
Functor, forall a. MultiZipper t a -> Bool
forall t a. Eq a => a -> MultiZipper t a -> Bool
forall t a. Num a => MultiZipper t a -> a
forall t a. Ord a => MultiZipper t a -> a
forall m a. Monoid m => (a -> m) -> MultiZipper t a -> m
forall t m. Monoid m => MultiZipper t m -> m
forall t a. MultiZipper t a -> Bool
forall t a. MultiZipper t a -> Int
forall t a. MultiZipper t a -> [a]
forall a b. (a -> b -> b) -> b -> MultiZipper t a -> b
forall t a. (a -> a -> a) -> MultiZipper t a -> a
forall t m a. Monoid m => (a -> m) -> MultiZipper t a -> m
forall t b a. (b -> a -> b) -> b -> MultiZipper t a -> b
forall t a b. (a -> b -> b) -> b -> MultiZipper t 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 :: forall a. Num a => MultiZipper t a -> a
$cproduct :: forall t a. Num a => MultiZipper t a -> a
sum :: forall a. Num a => MultiZipper t a -> a
$csum :: forall t a. Num a => MultiZipper t a -> a
minimum :: forall a. Ord a => MultiZipper t a -> a
$cminimum :: forall t a. Ord a => MultiZipper t a -> a
maximum :: forall a. Ord a => MultiZipper t a -> a
$cmaximum :: forall t a. Ord a => MultiZipper t a -> a
elem :: forall a. Eq a => a -> MultiZipper t a -> Bool
$celem :: forall t a. Eq a => a -> MultiZipper t a -> Bool
length :: forall a. MultiZipper t a -> Int
$clength :: forall t a. MultiZipper t a -> Int
null :: forall a. MultiZipper t a -> Bool
$cnull :: forall t a. MultiZipper t a -> Bool
toList :: forall a. MultiZipper t a -> [a]
$ctoList :: forall t a. MultiZipper t a -> [a]
foldl1 :: forall a. (a -> a -> a) -> MultiZipper t a -> a
$cfoldl1 :: forall t a. (a -> a -> a) -> MultiZipper t a -> a
foldr1 :: forall a. (a -> a -> a) -> MultiZipper t a -> a
$cfoldr1 :: forall t a. (a -> a -> a) -> MultiZipper t a -> a
foldl' :: forall b a. (b -> a -> b) -> b -> MultiZipper t a -> b
$cfoldl' :: forall t b a. (b -> a -> b) -> b -> MultiZipper t a -> b
foldl :: forall b a. (b -> a -> b) -> b -> MultiZipper t a -> b
$cfoldl :: forall t b a. (b -> a -> b) -> b -> MultiZipper t a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> MultiZipper t a -> b
$cfoldr' :: forall t a b. (a -> b -> b) -> b -> MultiZipper t a -> b
foldr :: forall a b. (a -> b -> b) -> b -> MultiZipper t a -> b
$cfoldr :: forall t a b. (a -> b -> b) -> b -> MultiZipper t a -> b
foldMap' :: forall m a. Monoid m => (a -> m) -> MultiZipper t a -> m
$cfoldMap' :: forall t m a. Monoid m => (a -> m) -> MultiZipper t a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> MultiZipper t a -> m
$cfoldMap :: forall t m a. Monoid m => (a -> m) -> MultiZipper t a -> m
fold :: forall m. Monoid m => MultiZipper t m -> m
$cfold :: forall t m. Monoid m => MultiZipper t m -> m
Foldable, forall t. Functor (MultiZipper t)
forall t. Foldable (MultiZipper t)
forall t (m :: * -> *) a.
Monad m =>
MultiZipper t (m a) -> m (MultiZipper t a)
forall t (f :: * -> *) a.
Applicative f =>
MultiZipper t (f a) -> f (MultiZipper t a)
forall t (m :: * -> *) a b.
Monad m =>
(a -> m b) -> MultiZipper t a -> m (MultiZipper t b)
forall t (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> MultiZipper t a -> f (MultiZipper t b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> MultiZipper t a -> f (MultiZipper t b)
sequence :: forall (m :: * -> *) a.
Monad m =>
MultiZipper t (m a) -> m (MultiZipper t a)
$csequence :: forall t (m :: * -> *) a.
Monad m =>
MultiZipper t (m a) -> m (MultiZipper t a)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> MultiZipper t a -> m (MultiZipper t b)
$cmapM :: forall t (m :: * -> *) a b.
Monad m =>
(a -> m b) -> MultiZipper t a -> m (MultiZipper t b)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
MultiZipper t (f a) -> f (MultiZipper t a)
$csequenceA :: forall t (f :: * -> *) a.
Applicative f =>
MultiZipper t (f a) -> f (MultiZipper t a)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> MultiZipper t a -> f (MultiZipper t b)
$ctraverse :: forall t (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> MultiZipper t a -> f (MultiZipper t b)
Traversable)

-- | Convert a list to a 'MultiZipper' positioned at the start of that

-- list.

fromListStart :: [a] -> MultiZipper t a
fromListStart :: forall a t. [a] -> MultiZipper t a
fromListStart [a]
as = forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
0 forall k a. Map k a
M.empty

-- | Convert a list to a 'MultiZipper' at a specific position in the

-- list. Returns 'Nothing' if the index is invalid.

fromListPos :: [a] -> Int -> Maybe (MultiZipper t a)
fromListPos :: forall a t. [a] -> Int -> Maybe (MultiZipper t a)
fromListPos [a]
as Int
pos =
    if forall a. Int -> [a] -> Bool
invalid Int
pos [a]
as
    then forall a. Maybe a
Nothing
    else forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
pos forall k a. Map k a
M.empty

-- | Get the list stored in a 'MultiZipper'.

toList :: MultiZipper t a -> [a]
toList :: forall t a. MultiZipper t a -> [a]
toList (MultiZipper [a]
as Int
_ Map t Int
_) = [a]
as

-- | The current position of the 'MultiZipper'.

curPos :: MultiZipper t a -> Int
curPos :: forall t a. MultiZipper t a -> Int
curPos (MultiZipper [a]
_ Int
pos Map t Int
_) = Int
pos

-- | Determine whether the 'MultiZipper' is positioned at the start of

-- its list.

atStart :: MultiZipper t a -> Bool
atStart :: forall t a. MultiZipper t a -> Bool
atStart (MultiZipper [a]
_ Int
pos Map t Int
_) = Int
pos forall a. Ord a => a -> a -> Bool
<= Int
0

-- | Determine whether the 'MultiZipper' is positioned at the end of

-- its list.

atEnd :: MultiZipper t a -> Bool
atEnd :: forall t a. MultiZipper t a -> Bool
atEnd (MultiZipper [a]
as Int
pos Map t Int
_) = Int
pos forall a. Ord a => a -> a -> Bool
>= forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
as

-- | Determine whether the 'MultiZipper' is positioned at the start or

-- end of its list.

atBoundary :: MultiZipper t a -> Bool
atBoundary :: forall t a. MultiZipper t a -> Bool
atBoundary = Bool -> Bool -> Bool
(||) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall t a. MultiZipper t a -> Bool
atStart forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall t a. MultiZipper t a -> Bool
atEnd

-- | The element at the current position of the 'MultiZipper'. Returns

-- 'Nothing' if the 'MultiZipper' is positioned ‘at the end of the

-- list’ (recall this actually means that the 'MultiZipper' is

-- positioned /after/ the last element of its list).

value :: MultiZipper t a -> Maybe a
value :: forall t a. MultiZipper t a -> Maybe a
value (MultiZipper [a]
as Int
pos Map t Int
_) =
    if forall a. Int -> [a] -> Bool
atNonvalue Int
pos [a]
as
    then forall a. Maybe a
Nothing
    else forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ [a]
as forall a. [a] -> Int -> a
!! Int
pos

-- | @valueN n mz@ returns the next @n@ elements of @mz@ starting from

-- the current position, as well as returning a new 'MultiZipper'

-- positioned past the end of those @n@ elements. (So running

-- @valueN m@ and then @valueN n@ would return the next @m+n@

-- elements.) Returns 'Nothing' if this would move the position of the

-- 'MultiZipper' past the end of the list.

valueN :: Int -> MultiZipper t a -> Maybe ([a], MultiZipper t a)
valueN :: forall t a. Int -> MultiZipper t a -> Maybe ([a], MultiZipper t a)
valueN Int
i (MultiZipper [a]
as Int
pos Map t Int
ts) =
    let pos' :: Int
pos' = Int
pos forall a. Num a => a -> a -> a
+ Int
i in
        if forall a. Int -> [a] -> Bool
invalid Int
pos' [a]
as Bool -> Bool -> Bool
|| Int
i forall a. Ord a => a -> a -> Bool
< Int
0
        then forall a. Maybe a
Nothing
        else forall a. a -> Maybe a
Just (forall a. Int -> [a] -> [a]
take Int
i forall a b. (a -> b) -> a -> b
$ forall a. Int -> [a] -> [a]
drop Int
pos [a]
as, forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
pos' Map t Int
ts)

-- | Given a tag, return its position

locationOf :: Ord t => t -> MultiZipper t a -> Maybe Int
locationOf :: forall t a. Ord t => t -> MultiZipper t a -> Maybe Int
locationOf t
t (MultiZipper [a]
_ Int
_ Map t Int
ts) = forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup t
t Map t Int
ts

-- | Get all tags at the current position

query :: Ord t => MultiZipper t a -> [t]
query :: forall t a. Ord t => MultiZipper t a -> [t]
query (MultiZipper [a]
_ Int
pos Map t Int
ts) = forall k a. Map k a -> [k]
M.keys forall a b. (a -> b) -> a -> b
$ forall a k. (a -> Bool) -> Map k a -> Map k a
M.filter (forall a. Eq a => a -> a -> Bool
==Int
pos) Map t Int
ts

seekIx :: Int -> MultiZipper t a -> Maybe (MultiZipper t a)
seekIx :: forall t a. Int -> MultiZipper t a -> Maybe (MultiZipper t a)
seekIx Int
i (MultiZipper [a]
as Int
_ Map t Int
ts) =
    if forall a. Int -> [a] -> Bool
invalid Int
i [a]
as
    then forall a. Maybe a
Nothing
    else forall a. a -> Maybe a
Just (forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
i Map t Int
ts)

-- | @move n mz@ will move the position of @mz@ by @n@ forward (if

-- n>0) or by @-n@ backward (if n<0). Returns 'Nothing' if this would

-- cause the 'MultiZipper' to move after the end or before the

-- beginning of the list.

move :: Int -> MultiZipper t a -> Maybe (MultiZipper t a)
move :: forall t a. Int -> MultiZipper t a -> Maybe (MultiZipper t a)
move Int
s mz :: MultiZipper t a
mz@(MultiZipper [a]
_ Int
pos Map t Int
_) = forall t a. Int -> MultiZipper t a -> Maybe (MultiZipper t a)
seekIx (Int
pos forall a. Num a => a -> a -> a
+ Int
s) MultiZipper t a
mz

-- | Move one position forward if possible, otherwise return 'Nothing'.

fwd :: MultiZipper t a -> Maybe (MultiZipper t a)
fwd :: forall t a. MultiZipper t a -> Maybe (MultiZipper t a)
fwd = forall t a. Int -> MultiZipper t a -> Maybe (MultiZipper t a)
move Int
1

-- | Move one position backwards if possible, otherwise return 'Nothing'.

bwd :: MultiZipper t a -> Maybe (MultiZipper t a)
bwd :: forall t a. MultiZipper t a -> Maybe (MultiZipper t a)
bwd = forall t a. Int -> MultiZipper t a -> Maybe (MultiZipper t a)
move (-Int
1)

-- | If possible, move one position forward, returning the value moved

-- over

consume :: MultiZipper t a -> Maybe (a, MultiZipper t a)
consume :: forall t a. MultiZipper t a -> Maybe (a, MultiZipper t a)
consume (MultiZipper [a]
as Int
pos Map t Int
ts) =
    if forall a. Int -> [a] -> Bool
invalid (Int
posforall a. Num a => a -> a -> a
+Int
1) [a]
as
    then forall a. Maybe a
Nothing
    else forall a. a -> Maybe a
Just ([a]
asforall a. [a] -> Int -> a
!!Int
pos, forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as (Int
posforall a. Num a => a -> a -> a
+Int
1) Map t Int
ts)

-- | Move the 'MultiZipper' to be at the specified tag. Returns

-- 'Nothing' if that tag is not present.

seek :: Ord t => t -> MultiZipper t a -> Maybe (MultiZipper t a)
seek :: forall t a.
Ord t =>
t -> MultiZipper t a -> Maybe (MultiZipper t a)
seek t
t (MultiZipper [a]
as Int
_ Map t Int
ts) = case forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup t
t Map t Int
ts of
    Maybe Int
Nothing  -> forall a. Maybe a
Nothing
    Just Int
pos -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
pos Map t Int
ts

-- | Move to the beginning of the 'MultiZipper'.

toBeginning :: MultiZipper t a -> MultiZipper t a
toBeginning :: forall t a. MultiZipper t a -> MultiZipper t a
toBeginning (MultiZipper [a]
as Int
_ Map t Int
ts) = forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
0 Map t Int
ts

-- | Move to the end of the 'MultiZipper'.

toEnd :: MultiZipper t a -> MultiZipper t a
toEnd :: forall t a. MultiZipper t a -> MultiZipper t a
toEnd (MultiZipper [a]
as Int
_ Map t Int
ts) = forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as (forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
as) Map t Int
ts

-- | Find first element before point which returns 'Just' when

-- queried, if any, returning the result of the query function.

yank :: (a -> Maybe b) -> MultiZipper t a -> Maybe b
yank :: forall a b t. (a -> Maybe b) -> MultiZipper t a -> Maybe b
yank a -> Maybe b
p MultiZipper t a
mz = forall t a. MultiZipper t a -> Maybe (MultiZipper t a)
bwd MultiZipper t a
mz forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \MultiZipper t a
mz' -> (forall t a. MultiZipper t a -> Maybe a
value MultiZipper t a
mz' forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Maybe b
p) forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> forall a b t. (a -> Maybe b) -> MultiZipper t a -> Maybe b
yank a -> Maybe b
p MultiZipper t a
mz'

-- | Insert a new element at point and move forward by one position.

insert :: a -> MultiZipper t a -> MultiZipper t a
insert :: forall a t. a -> MultiZipper t a -> MultiZipper t a
insert a
a (MultiZipper [a]
as Int
pos Map t Int
ts) =
    case forall a. Int -> [a] -> ([a], [a])
splitAt Int
pos [a]
as of
        ([a]
as1, [a]
as2) -> forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper ([a]
as1 forall a. [a] -> [a] -> [a]
++ [a
a] forall a. [a] -> [a] -> [a]
++ [a]
as2) (Int
posforall a. Num a => a -> a -> a
+Int
1) forall a b. (a -> b) -> a -> b
$ forall t. Int -> (Int -> Int) -> Map t Int -> Map t Int
correctIxsFrom Int
pos (forall a. Num a => a -> a -> a
+Int
1) Map t Int
ts

-- | Insert multiple elements at point and move after them. A simple

-- wrapper around 'insert'.

insertMany :: [a] -> MultiZipper t a -> MultiZipper t a
insertMany :: forall a t. [a] -> MultiZipper t a -> MultiZipper t a
insertMany = forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' forall a b. (a -> b) -> a -> b
$ forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a t. a -> MultiZipper t a -> MultiZipper t a
insert

-- | Modify the first element before point to which the modification

-- function returns 'Just'.

zap :: (a -> Maybe a) -> MultiZipper t a -> MultiZipper t a
zap :: forall a t. (a -> Maybe a) -> MultiZipper t a -> MultiZipper t a
zap a -> Maybe a
p = \mz :: MultiZipper t a
mz@(MultiZipper [a]
as Int
pos Map t Int
ts) -> case [a] -> Int -> Maybe [a]
go [a]
as (Int
posforall a. Num a => a -> a -> a
-Int
1) of
    Maybe [a]
Nothing  -> MultiZipper t a
mz
    Just [a]
as' -> forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as' Int
pos Map t Int
ts
  where
    go :: [a] -> Int -> Maybe [a]
go [a]
_ (-1) = forall a. Maybe a
Nothing
    go [a]
as Int
pos
      | Int
pos forall a. Eq a => a -> a -> Bool
== forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
as = [a] -> Int -> Maybe [a]
go [a]
as (Int
posforall a. Num a => a -> a -> a
-Int
1)
      | Bool
otherwise = case a -> Maybe a
p ([a]
as forall a. [a] -> Int -> a
!! Int
pos) of
        Maybe a
Nothing -> [a] -> Int -> Maybe [a]
go [a]
as (Int
posforall a. Num a => a -> a -> a
-Int
1)
        Just a
a' -> case forall a. Int -> [a] -> ([a], [a])
splitAt Int
pos [a]
as of
            ([a]
as1, a
_:[a]
as2) -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ [a]
as1 forall a. [a] -> [a] -> [a]
++ (a
a'forall a. a -> [a] -> [a]
:[a]
as2)
            ([a], [a])
_ -> forall a. HasCallStack => String -> a
error String
"error in zap: impossible case reached"

-- | Set a tag at the current position.

tag :: Ord t => t -> MultiZipper t a -> MultiZipper t a
tag :: forall t a. Ord t => t -> MultiZipper t a -> MultiZipper t a
tag t
t (MultiZipper [a]
as Int
pos Map t Int
ts) = forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
pos forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert t
t Int
pos Map t Int
ts

-- | Set a tag at a given position if possible, otherwise return 'Nothing'.

tagAt :: Ord t => t -> Int -> MultiZipper t a -> Maybe (MultiZipper t a)
tagAt :: forall t a.
Ord t =>
t -> Int -> MultiZipper t a -> Maybe (MultiZipper t a)
tagAt t
t Int
i (MultiZipper [a]
as Int
pos Map t Int
ts) =
    if forall a. Int -> [a] -> Bool
invalid Int
i [a]
as
    then forall a. Maybe a
Nothing
    else forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
pos forall a b. (a -> b) -> a -> b
$ forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert t
t Int
i Map t Int
ts

-- | Remove tags satisfying predicate

untagWhen :: (t -> Bool) -> MultiZipper t a -> MultiZipper t a
untagWhen :: forall t a. (t -> Bool) -> MultiZipper t a -> MultiZipper t a
untagWhen t -> Bool
p (MultiZipper [a]
as Int
pos Map t Int
ts) = forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
pos forall a b. (a -> b) -> a -> b
$ forall a b. (a, b) -> b
snd forall a b. (a -> b) -> a -> b
$ forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
M.partitionWithKey (forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a b. (a -> b) -> a -> b
$ forall a b. a -> b -> a
const t -> Bool
p) Map t Int
ts

-- | Remove all tags.

untag :: MultiZipper t a -> MultiZipper t a
untag :: forall t a. MultiZipper t a -> MultiZipper t a
untag (MultiZipper [a]
as Int
pos Map t Int
_) = forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
pos forall k a. Map k a
M.empty

-- | Modify a 'MultiZipper' between the selected tags. Returns

-- 'Nothing' if a nonexistent tag is selected, else returns the

-- modified 'MultiZipper'.

modifyBetween :: Ord t
              => (t, t)
              -- ^ Selected tags. Note that the resulting interval

              -- will be [inclusive, exclusive).

              -> ([a] -> [a])
              -- ^ Function to modify designated interval.

              -> MultiZipper t a
              -> Maybe (MultiZipper t a)
modifyBetween :: forall t a.
Ord t =>
(t, t)
-> ([a] -> [a]) -> MultiZipper t a -> Maybe (MultiZipper t a)
modifyBetween (t
t1, t
t2) [a] -> [a]
f mz :: MultiZipper t a
mz@(MultiZipper [a]
as Int
pos Map t Int
ts) = do
    (Int
i1, Int
i2) <- forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall {b}. Ord b => (b, b) -> (b, b)
correctOrder forall a b. (a -> b) -> a -> b
$ (,) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall t a. Ord t => t -> MultiZipper t a -> Maybe Int
locationOf t
t1 MultiZipper t a
mz forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> forall t a. Ord t => t -> MultiZipper t a -> Maybe Int
locationOf t
t2 MultiZipper t a
mz
    let ([a]
before_t1, [a]
after_t1) = forall a. Int -> [a] -> ([a], [a])
splitAt Int
i1 [a]
as
        ([a]
cut_part, [a]
after_t2) = forall a. Int -> [a] -> ([a], [a])
splitAt (Int
i2forall a. Num a => a -> a -> a
-Int
i1) [a]
after_t1
        replacement :: [a]
replacement = [a] -> [a]
f [a]
cut_part
        dEnd :: Int
dEnd = forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
replacement forall a. Num a => a -> a -> a
- forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
cut_part
        pos' :: Int
pos' = Int
pos forall a. Num a => a -> a -> a
+ Int
dEnd
    forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper ([a]
before_t1 forall a. [a] -> [a] -> [a]
++ [a]
replacement forall a. [a] -> [a] -> [a]
++ [a]
after_t2) Int
pos' (forall t. Int -> (Int -> Int) -> Map t Int -> Map t Int
correctIxsFrom Int
i2 (forall a. Num a => a -> a -> a
+Int
dEnd) Map t Int
ts)
  where
    correctOrder :: (b, b) -> (b, b)
correctOrder (b
m, b
n) = if b
m forall a. Ord a => a -> a -> Bool
<= b
n then (b
m, b
n) else (b
n, b
m)

-- | Given a function to compute a value from a 'MultiZipper' starting

-- at a particular point, apply that function to all possible starting

-- points and collect the results. Tags are left unchanged.

--

-- (Note: this is really just the same @extend@ method as in the

-- @Comonad@ typeclass, although 'MultiZipper' wouldn’t be a lawful

-- comonad.)

extend :: (MultiZipper t a -> b) -> MultiZipper t a -> MultiZipper t b
extend :: forall t a b.
(MultiZipper t a -> b) -> MultiZipper t a -> MultiZipper t b
extend MultiZipper t a -> b
f (MultiZipper [a]
as Int
pos Map t Int
ts) = forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [b]
as' Int
pos Map t Int
ts
  where
    as' :: [b]
as' = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Int
i -> MultiZipper t a -> b
f forall a b. (a -> b) -> a -> b
$ forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
i Map t Int
ts) [Int
0 .. forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
as forall a. Num a => a -> a -> a
- Int
1]

-- | Like 'extend', but includes the end position of the zipper, thus

-- increasing the 'MultiZipper' length by one when called.

extend' :: (MultiZipper t a -> b) -> MultiZipper t a -> MultiZipper t b
extend' :: forall t a b.
(MultiZipper t a -> b) -> MultiZipper t a -> MultiZipper t b
extend' MultiZipper t a -> b
f (MultiZipper [a]
as Int
pos Map t Int
ts) = forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [b]
as' Int
pos Map t Int
ts
  where
    as' :: [b]
as' = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Int
i -> MultiZipper t a -> b
f forall a b. (a -> b) -> a -> b
$ forall t a. [a] -> Int -> Map t Int -> MultiZipper t a
MultiZipper [a]
as Int
i Map t Int
ts) [Int
0 .. forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
as]

-- Utility functions for checking and modifying indices in lists:

invalid :: Int -> [a] -> Bool
invalid :: forall a. Int -> [a] -> Bool
invalid Int
pos [a]
as = (Int
pos forall a. Ord a => a -> a -> Bool
< Int
0) Bool -> Bool -> Bool
|| (Int
pos forall a. Ord a => a -> a -> Bool
> forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
as)

atNonvalue :: Int -> [a] -> Bool
atNonvalue :: forall a. Int -> [a] -> Bool
atNonvalue Int
pos [a]
as = (Int
pos forall a. Ord a => a -> a -> Bool
< Int
0) Bool -> Bool -> Bool
|| (Int
pos forall a. Ord a => a -> a -> Bool
>= forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
as)

correctIxsFrom :: Int -> (Int -> Int) -> M.Map t Int -> M.Map t Int
correctIxsFrom :: forall t. Int -> (Int -> Int) -> Map t Int -> Map t Int
correctIxsFrom Int
i Int -> Int
f = forall a b k. (a -> b) -> Map k a -> Map k b
M.map forall a b. (a -> b) -> a -> b
$ \Int
pos -> if Int
pos forall a. Ord a => a -> a -> Bool
>= Int
i then Int -> Int
f Int
pos else Int
pos