{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE TupleSections #-}

{-| __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
       , delete
       , extend
       , extend'
       ) where

import Control.Applicative (Alternative((<|>)))
import Data.Foldable (Foldable(foldl'))
import Data.Vector ((!?), (!))
import Data.Vector.Mutable (write)
import qualified Data.Vector as V
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 (V.Vector 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. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper (forall a. [a] -> Vector a
V.fromList [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 Int -> Int -> Bool
invalid Int
pos (forall (t :: * -> *) a. Foldable t => t a -> Int
length [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. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper (forall a. [a] -> Vector a
V.fromList [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 Vector a
as Int
_ Map t Int
_) = forall a. Vector a -> [a]
V.toList Vector a
as

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

curPos :: MultiZipper t a -> Int
curPos :: forall t a. MultiZipper t a -> Int
curPos (MultiZipper Vector 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 Vector 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 Vector 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 Vector 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 Vector a
as Int
pos Map t Int
_) = Vector a
as forall a. Vector a -> Int -> Maybe 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 Vector 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 Int -> Int -> Bool
invalid Int
pos' (forall a. Vector a -> Int
V.length Vector 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 forall a b. (a -> b) -> a -> b
$ forall a. Vector a -> [a]
V.toList Vector a
as, forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector 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 Vector 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 Vector 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 Vector a
as Int
_ Map t Int
ts) =
    if Int -> Int -> Bool
invalid Int
i (forall a. Vector a -> Int
V.length Vector a
as)
    then forall a. Maybe a
Nothing
    else forall a. a -> Maybe a
Just (forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector 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 Vector 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 Vector a
as Int
pos Map t Int
ts) =
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (,forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector a
as (Int
posforall a. Num a => a -> a -> a
+Int
1) Map t Int
ts) (Vector a
asforall a. Vector a -> Int -> Maybe a
!?Int
pos)

-- | 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 Vector 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. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector 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 Vector a
as Int
_ Map t Int
ts) = forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector 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 Vector a
as Int
_ Map t Int
ts) = forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector a
as (forall (t :: * -> *) a. Foldable t => t a -> Int
length Vector 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 Vector a
as Int
pos Map t Int
ts) =
    case forall a. Int -> Vector a -> (Vector a, Vector a)
V.splitAt Int
pos Vector a
as of
        (Vector a
as1, Vector a
as2) -> forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper
            (Vector a
as1 forall a. Vector a -> Vector a -> Vector a
V.++ forall a. a -> Vector a -> Vector a
V.cons a
a Vector a
as2)
            (Int
posforall a. Num a => a -> a -> a
+Int
1)
            (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 Vector a
as Int
pos Map t Int
ts) -> case Vector a -> Int -> Maybe (Vector a)
go Vector a
as (Int
posforall a. Num a => a -> a -> a
-Int
1) of
    Maybe (Vector a)
Nothing  -> MultiZipper t a
mz
    Just Vector a
as' -> forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector a
as' Int
pos Map t Int
ts
  where
    go :: Vector a -> Int -> Maybe (Vector a)
go Vector a
_ (-1) = forall a. Maybe a
Nothing
    go Vector a
as Int
pos
      | Int
pos forall a. Eq a => a -> a -> Bool
== forall (t :: * -> *) a. Foldable t => t a -> Int
length Vector a
as = Vector a -> Int -> Maybe (Vector a)
go Vector a
as (Int
posforall a. Num a => a -> a -> a
-Int
1)
      | Bool
otherwise = case a -> Maybe a
p (Vector a
as forall a. Vector a -> Int -> a
! Int
pos) of
        Maybe a
Nothing -> Vector a -> Int -> Maybe (Vector a)
go Vector a
as (Int
posforall a. Num a => a -> a -> a
-Int
1)
        Just a
a' -> forall a. a -> Maybe a
Just forall a b. (a -> b) -> a -> b
$ forall a.
(forall s. MVector s a -> ST s ()) -> Vector a -> Vector a
V.modify (\MVector s a
v -> forall (m :: * -> *) a.
PrimMonad m =>
MVector (PrimState m) a -> Int -> a -> m ()
write MVector s a
v Int
pos a
a') Vector a
as

-- | 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 Vector a
as Int
pos Map t Int
ts) = forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector 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 Vector a
as Int
pos Map t Int
ts) =
    if Int -> Int -> Bool
invalid Int
i (forall (t :: * -> *) a. Foldable t => t a -> Int
length Vector 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. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector 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 Vector a
as Int
pos Map t Int
ts) = forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector 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 Vector a
as Int
pos Map t Int
_) = forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector a
as Int
pos forall k a. Map k a
M.empty

-- | Delete the portion of a 'MultiZipper' between the selected tags.

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

-- the modified 'MultiZipper'.

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

    -- will be [inclusive, exclusive).

    -> MultiZipper t a
    -> Maybe (MultiZipper t a)
delete :: forall t a.
Ord t =>
(t, t) -> MultiZipper t a -> Maybe (MultiZipper t a)
delete (t
t1, t
t2) mz :: MultiZipper t a
mz@(MultiZipper Vector 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 (Vector a
before_t1, Vector a
after_t1) = forall a. Int -> Vector a -> (Vector a, Vector a)
V.splitAt Int
i1 Vector a
as
        (Vector a
cut_part, Vector a
after_t2) = forall a. Int -> Vector a -> (Vector a, Vector a)
V.splitAt (Int
i2forall a. Num a => a -> a -> a
-Int
i1) Vector a
after_t1
        removed :: Int
removed = forall (t :: * -> *) a. Foldable t => t a -> Int
length Vector a
cut_part
        pos' :: Int
pos' = Int
pos forall a. Num a => a -> a -> a
- Int
removed
    forall (m :: * -> *) a. Monad m => a -> m a
return forall a b. (a -> b) -> a -> b
$ forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper (Vector a
before_t1 forall a. Vector a -> Vector a -> Vector a
V.++ Vector 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
subtract Int
removed) 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 Vector a
as Int
pos Map t Int
ts) = forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector b
as' Int
pos Map t Int
ts
  where
    as' :: Vector b
as' = forall a b. (a -> b) -> Vector a -> Vector b
V.map (\Int
i -> MultiZipper t a -> b
f forall a b. (a -> b) -> a -> b
$ forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector a
as Int
i Map t Int
ts) forall a b. (a -> b) -> a -> b
$ forall a. Num a => a -> Int -> Vector a
V.enumFromN Int
0 (forall (t :: * -> *) a. Foldable t => t a -> Int
length Vector a
as)

-- | 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 Vector a
as Int
pos Map t Int
ts) = forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector b
as' Int
pos Map t Int
ts
  where
    as' :: Vector b
as' = forall a b. (a -> b) -> Vector a -> Vector b
V.map (\Int
i -> MultiZipper t a -> b
f forall a b. (a -> b) -> a -> b
$ forall t a. Vector a -> Int -> Map t Int -> MultiZipper t a
MultiZipper Vector a
as Int
i Map t Int
ts) forall a b. (a -> b) -> a -> b
$ forall a. Num a => a -> Int -> Vector a
V.enumFromN Int
0 (forall (t :: * -> *) a. Foldable t => t a -> Int
length Vector a
as forall a. Num a => a -> a -> a
+ Int
1)

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

invalid :: Int -> Int -> Bool
invalid :: Int -> Int -> Bool
invalid Int
pos Int
len = (Int
pos forall a. Ord a => a -> a -> Bool
< Int
0) Bool -> Bool -> Bool
|| (Int
pos forall a. Ord a => a -> a -> Bool
> Int
len)

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