module Language.Parser.Ptera.Data.Symbolic.IntMap where

import           Language.Parser.Ptera.Prelude

import qualified Data.HashMap.Strict                        as HashMap
import qualified Data.IntMap.Strict                         as DataIntMap
import qualified Data.IntSet                                as DataIntSet
import qualified Language.Parser.Ptera.Data.Symbolic.IntSet as IntSet


type T = IntMap

type Key = Int

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

empty :: IntMap a
empty :: IntMap a
empty = IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
    {
        $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = IntMap (Maybe a)
forall a. IntMap a
DataIntMap.empty,
        $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = Maybe a
forall a. Maybe a
Nothing
    }

full :: a -> IntMap a
full :: a -> IntMap a
full a
v = IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
    {
        $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = IntMap (Maybe a)
forall a. IntMap a
DataIntMap.empty,
        $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = a -> Maybe a
forall a. a -> Maybe a
Just a
v
    }

singleton :: Key -> a -> IntMap a
singleton :: Int -> a -> IntMap a
singleton Int
k a
v = IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
    {
        $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = Int -> Maybe a -> IntMap (Maybe a)
forall a. Int -> a -> IntMap a
DataIntMap.singleton Int
k do a -> Maybe a
forall a. a -> Maybe a
Just a
v,
        $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = Maybe a
forall a. Maybe a
Nothing
    }

normalize :: Eq a => IntMap a -> IntMap a
normalize :: IntMap a -> IntMap a
normalize IntMap a
m = case IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m of
    Maybe a
Nothing -> IntMap a
m
        {
            $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = (Maybe a -> Maybe (Maybe a))
-> IntMap (Maybe a) -> IntMap (Maybe a)
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybe
                do \Maybe a
x -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> Maybe a -> Maybe (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a
x
                do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
        }
    Just a
nx -> IntMap a
m
        {
            $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = (Maybe a -> Maybe (Maybe a))
-> IntMap (Maybe a) -> IntMap (Maybe a)
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybe
                do \case
                    Maybe a
Nothing ->
                        Maybe a -> Maybe (Maybe a)
forall a. a -> Maybe a
Just Maybe a
forall a. Maybe a
Nothing
                    Just a
x | a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
nx ->
                        Maybe (Maybe a)
forall a. Maybe a
Nothing
                    jx :: Maybe a
jx@Just{} ->
                        Maybe a -> Maybe (Maybe a)
forall a. a -> Maybe a
Just Maybe a
jx
                do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
        }

instance Eq a => Eq (IntMap a) where
    IntMap a
m1 == :: IntMap a -> IntMap a -> Bool
== IntMap a
m2 = IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m1 Maybe a -> Maybe a -> Bool
forall a. Eq a => a -> a -> Bool
== IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m2
        Bool -> Bool -> Bool
&& IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight (IntMap a -> IntMap a
forall a. Eq a => IntMap a -> IntMap a
normalize IntMap a
m1) IntMap (Maybe a) -> IntMap (Maybe a) -> Bool
forall a. Eq a => a -> a -> Bool
== IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight (IntMap a -> IntMap a
forall a. Eq a => IntMap a -> IntMap a
normalize IntMap a
m2)

insert :: Key -> a -> IntMap a -> IntMap a
insert :: Int -> a -> IntMap a -> IntMap a
insert Int
k a
v IntMap a
m = IntMap a
m
    {
        $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = Int -> Maybe a -> IntMap (Maybe a) -> IntMap (Maybe a)
forall a. Int -> a -> IntMap a -> IntMap a
DataIntMap.insert Int
k
            do a -> Maybe a
forall a. a -> Maybe a
Just a
v
            do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
    }

insertBulk :: IntSet.T -> a -> IntMap a -> IntMap a
insertBulk :: T -> a -> IntMap a -> IntMap a
insertBulk T
ss a
v IntMap a
m0 = case T
ss of
    IntSet.StraightSet IntSet
s -> do
        let jv :: Maybe a
jv = a -> Maybe a
forall a. a -> Maybe a
Just a
v
        IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
            { $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = (IntMap (Maybe a) -> Int -> IntMap (Maybe a))
-> IntMap (Maybe a) -> [Int] -> IntMap (Maybe a)
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'
                do \IntMap (Maybe a)
m Int
k -> Int -> Maybe a -> IntMap (Maybe a) -> IntMap (Maybe a)
forall a. Int -> a -> IntMap a -> IntMap a
DataIntMap.insert Int
k Maybe a
jv IntMap (Maybe a)
m
                do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
                do IntSet -> [Int]
DataIntSet.elems IntSet
s
            , $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m0
            }
    IntSet.NegativeSet IntSet
s -> IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
        { $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = IntMap (Maybe a) -> IntSet -> IntMap (Maybe a)
forall a. IntMap a -> IntSet -> IntMap a
DataIntMap.restrictKeys
            do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
            do IntSet
s
        , $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = a -> Maybe a
forall a. a -> Maybe a
Just a
v
        }

delete :: Key -> IntMap a -> IntMap a
delete :: Int -> IntMap a -> IntMap a
delete Int
k IntMap a
m = case IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m of
    Maybe a
Nothing -> IntMap a
m
        {
            $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = Int -> IntMap (Maybe a) -> IntMap (Maybe a)
forall a. Int -> IntMap a -> IntMap a
DataIntMap.delete Int
k do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
        }
    Just a
_ -> IntMap a
m
        {
            $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = Int -> Maybe a -> IntMap (Maybe a) -> IntMap (Maybe a)
forall a. Int -> a -> IntMap a -> IntMap a
DataIntMap.insert Int
k Maybe a
forall a. Maybe a
Nothing do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
        }

update :: (a -> Maybe a) -> Key -> IntMap a -> IntMap a
update :: (a -> Maybe a) -> Int -> IntMap a -> IntMap a
update a -> Maybe a
f Int
k IntMap a
m = case Int -> IntMap (Maybe a) -> Maybe (Maybe a)
forall a. Int -> IntMap a -> Maybe a
DataIntMap.lookup Int
k do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m of
    Just Maybe a
mv -> Maybe a -> IntMap a
go Maybe a
mv
    Maybe (Maybe a)
Nothing -> Maybe a -> IntMap a
go do IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m
    where
        go :: Maybe a -> IntMap a
go = \case
            Maybe a
Nothing -> IntMap a
m
            Just a
v -> case a -> Maybe a
f a
v of
                Maybe a
Nothing -> IntMap a
m
                jv :: Maybe a
jv@Just{} -> IntMap a
m
                    {
                        $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = Int -> Maybe a -> IntMap (Maybe a) -> IntMap (Maybe a)
forall a. Int -> a -> IntMap a -> IntMap a
DataIntMap.insert Int
k Maybe a
jv do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
                    }

alter :: (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a
alter :: (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
alter Maybe a -> Maybe a
f Int
k IntMap a
m = case Int -> IntMap (Maybe a) -> Maybe (Maybe a)
forall a. Int -> IntMap a -> Maybe a
DataIntMap.lookup Int
k do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m of
    Just Maybe a
mv -> Maybe a -> IntMap a
go Maybe a
mv
    Maybe (Maybe a)
Nothing -> Maybe a -> IntMap a
go do IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m
    where
        go :: Maybe a -> IntMap a
go = \case
            Maybe a
Nothing -> case Maybe a -> Maybe a
f Maybe a
forall a. Maybe a
Nothing of
                Maybe a
Nothing -> IntMap a
m
                jv :: Maybe a
jv@Just{} -> IntMap a
m
                    {
                        $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = Int -> Maybe a -> IntMap (Maybe a) -> IntMap (Maybe a)
forall a. Int -> a -> IntMap a -> IntMap a
DataIntMap.insert Int
k Maybe a
jv do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
                    }
            jv0 :: Maybe a
jv0@Just{} -> IntMap a
m
                {
                    $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = Int -> Maybe a -> IntMap (Maybe a) -> IntMap (Maybe a)
forall a. Int -> a -> IntMap a -> IntMap a
DataIntMap.insert Int
k
                        do Maybe a -> Maybe a
f Maybe a
jv0
                        do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
                }

alterBulk :: (Maybe a -> Maybe a) -> IntSet.T -> IntMap a -> IntMap a
alterBulk :: (Maybe a -> Maybe a) -> T -> IntMap a -> IntMap a
alterBulk Maybe a -> Maybe a
f T
ks IntMap a
m0 = case T
ks of
    IntSet.StraightSet IntSet
s -> case IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m0 of
        Maybe a
Nothing -> IntMap a
m0
            {
                $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = (IntMap (Maybe a) -> Int -> IntMap (Maybe a))
-> IntMap (Maybe a) -> [Int] -> IntMap (Maybe a)
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'
                    do \IntMap (Maybe a)
m Int
k -> (Maybe (Maybe a) -> Maybe (Maybe a))
-> Int -> IntMap (Maybe a) -> IntMap (Maybe a)
forall a. (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
DataIntMap.alter
                        do \Maybe (Maybe a)
mmv -> case Maybe a -> Maybe a
f do Maybe (Maybe a) -> Maybe a
forall (m :: * -> *) a. Monad m => m (m a) -> m a
join Maybe (Maybe a)
mmv of
                            Maybe a
Nothing   -> Maybe (Maybe a)
forall a. Maybe a
Nothing
                            jv :: Maybe a
jv@Just{} -> Maybe a -> Maybe (Maybe a)
forall a. a -> Maybe a
Just Maybe a
jv
                        Int
k IntMap (Maybe a)
m
                    do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
                    do IntSet -> [Int]
DataIntSet.elems IntSet
s
            }
        njv :: Maybe a
njv@Just{} -> IntMap a
m0
            {
                $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = (IntMap (Maybe a) -> Int -> IntMap (Maybe a))
-> IntMap (Maybe a) -> [Int] -> IntMap (Maybe a)
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'
                    do \IntMap (Maybe a)
m Int
k -> (Maybe (Maybe a) -> Maybe (Maybe a))
-> Int -> IntMap (Maybe a) -> IntMap (Maybe a)
forall a. (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
DataIntMap.alter
                        do \case
                            Maybe (Maybe a)
Nothing -> Maybe a -> Maybe (Maybe a)
forall a. a -> Maybe a
Just do Maybe a -> Maybe a
f Maybe a
njv
                            Just Maybe a
mv -> Maybe a -> Maybe (Maybe a)
forall a. a -> Maybe a
Just do Maybe a -> Maybe a
f Maybe a
mv
                        Int
k IntMap (Maybe a)
m
                    do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
                    do IntSet -> [Int]
DataIntSet.elems IntSet
s
            }
    IntSet.NegativeSet IntSet
s -> case IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m0 of
        Maybe a
Nothing -> case Maybe a -> Maybe a
f Maybe a
forall a. Maybe a
Nothing of
            Maybe a
Nothing -> IntMap a
m0
                {
                    $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = (Int -> Maybe a -> Maybe (Maybe a))
-> IntMap (Maybe a) -> IntMap (Maybe a)
forall a b. (Int -> a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybeWithKey
                        do \Int
k Maybe a
mv0 -> do
                            a
_ <- Maybe a
mv0
                            if Int -> IntSet -> Bool
DataIntSet.member Int
k IntSet
s
                                then Maybe a -> Maybe (Maybe a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
mv0
                                else a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> Maybe a -> Maybe (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a -> Maybe a
f Maybe a
mv0
                        do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
                }
            jv :: Maybe a
jv@Just{} -> IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
                { $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = (Int -> Maybe a -> Maybe (Maybe a))
-> IntMap (Maybe a) -> IntMap (Maybe a)
forall a b. (Int -> a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybeWithKey
                    do \Int
k Maybe a
mv0 -> if Int -> IntSet -> Bool
DataIntSet.member Int
k IntSet
s
                        then Maybe a -> Maybe (Maybe a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
mv0
                        else case Maybe a
mv0 of
                            Maybe a
Nothing -> Maybe a -> Maybe (Maybe a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
jv
                            Just{}  -> Maybe a -> Maybe (Maybe a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure do Maybe a -> Maybe a
f Maybe a
mv0
                    do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
                , $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = Maybe a
jv
                }
        njv0 :: Maybe a
njv0@Just{} -> case Maybe a -> Maybe a
f Maybe a
njv0 of
            Maybe a
Nothing -> IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
                { $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = (Int -> Maybe a -> Maybe (Maybe a))
-> IntMap (Maybe a) -> IntMap (Maybe a)
forall a b. (Int -> a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybeWithKey
                    do \Int
k Maybe a
mv0 -> if Int -> IntSet -> Bool
DataIntSet.member Int
k IntSet
s
                        then a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> Maybe a -> Maybe (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a
mv0
                        else a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> Maybe a -> Maybe (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a -> Maybe a
f Maybe a
mv0
                    do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
                , $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = Maybe a
forall a. Maybe a
Nothing
                }
            njv :: Maybe a
njv@Just{} -> IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
                { $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = (Int -> Maybe a -> Maybe (Maybe a))
-> IntMap (Maybe a) -> IntMap (Maybe a)
forall a b. (Int -> a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybeWithKey
                    do \Int
k Maybe a
mv0 -> if Int -> IntSet -> Bool
DataIntSet.member Int
k IntSet
s
                        then Maybe a -> Maybe (Maybe a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
mv0
                        else Maybe a -> Maybe (Maybe a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure do Maybe a -> Maybe a
f Maybe a
mv0
                    do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
                , $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = Maybe a
njv
                }

lookup :: Key -> IntMap a -> Maybe a
lookup :: Int -> IntMap a -> Maybe a
lookup Int
k IntMap a
m = case Int -> IntMap (Maybe a) -> Maybe (Maybe a)
forall a. Int -> IntMap a -> Maybe a
DataIntMap.lookup Int
k do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m of
    Just Maybe a
mv -> Maybe a
mv
    Maybe (Maybe a)
Nothing -> IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m

keys :: IntMap a -> IntSet.T
keys :: IntMap a -> T
keys IntMap a
m = case IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m of
    Just{}  -> IntSet -> T
IntSet.NegativeSet
        do [Int] -> IntSet
DataIntSet.fromList
            [ Int
k
            | (Int
k, Maybe a
mv) <- IntMap (Maybe a) -> [(Int, Maybe a)]
forall a. IntMap a -> [(Int, a)]
DataIntMap.assocs do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
            , case Maybe a
mv of { Maybe a
Nothing -> Bool
True; Just{} -> Bool
False }
            ]
    Maybe a
Nothing -> IntSet -> T
IntSet.StraightSet
        do [Int] -> IntSet
DataIntSet.fromList
            [ Int
k
            | (Int
k, Maybe a
mv) <- IntMap (Maybe a) -> [(Int, Maybe a)]
forall a. IntMap a -> [(Int, a)]
DataIntMap.assocs do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
            , case Maybe a
mv of { Maybe a
Nothing -> Bool
False; Just{} -> Bool
True }
            ]

restrictKeys :: IntMap a -> IntSet.T -> IntMap a
restrictKeys :: IntMap a -> T -> IntMap a
restrictKeys IntMap a
m T
s = case IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m of
    Maybe a
Nothing -> case T
s of
        IntSet.StraightSet IntSet
is ->
            IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
                { $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = Maybe a
forall a. Maybe a
Nothing
                , $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = IntMap (Maybe a) -> IntSet -> IntMap (Maybe a)
forall a. IntMap a -> IntSet -> IntMap a
DataIntMap.restrictKeys
                    do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
                    do IntSet
is
                }
        IntSet.NegativeSet IntSet
is ->
            IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
                { $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = Maybe a
forall a. Maybe a
Nothing
                , $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = IntMap (Maybe a) -> IntSet -> IntMap (Maybe a)
forall a. IntMap a -> IntSet -> IntMap a
DataIntMap.withoutKeys
                    do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
                    do IntSet
is
                }
    notMx :: Maybe a
notMx@Just{} -> case T
s of
        IntSet.StraightSet IntSet
is -> do
            let notM :: IntMap (Maybe a)
notM = (Int -> Maybe a) -> IntSet -> IntMap (Maybe a)
forall a. (Int -> a) -> IntSet -> IntMap a
DataIntMap.fromSet
                    do \Int
_ -> Maybe a
notMx
                    do IntSet
is
            IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
                { $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = Maybe a
forall a. Maybe a
Nothing
                , $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = (Maybe a -> Maybe a -> Maybe a)
-> IntMap (Maybe a) -> IntMap (Maybe a) -> IntMap (Maybe a)
forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
DataIntMap.unionWith
                    do \Maybe a
x Maybe a
_ -> Maybe a
x
                    do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
                    do IntMap (Maybe a)
notM
                }
        IntSet.NegativeSet IntSet
is -> do
            let deleteM :: IntMap (Maybe a)
deleteM = (Int -> Maybe a) -> IntSet -> IntMap (Maybe a)
forall a. (Int -> a) -> IntSet -> IntMap a
DataIntMap.fromSet
                    do \Int
_ -> Maybe a
forall a. Maybe a
Nothing
                    do IntSet
is
            IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
                { $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = Maybe a
notMx
                , $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = (Maybe a -> Maybe a -> Maybe a)
-> IntMap (Maybe a) -> IntMap (Maybe a) -> IntMap (Maybe a)
forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
DataIntMap.unionWith
                    do \Maybe a
_ Maybe a
x -> Maybe a
x
                    do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
                    do IntMap (Maybe a)
deleteM
                }



merge :: (a -> b -> Maybe c) -> (a -> Maybe c) -> (b -> Maybe c) -> IntMap a -> IntMap b -> IntMap c
merge :: (a -> b -> Maybe c)
-> (a -> Maybe c)
-> (b -> Maybe c)
-> IntMap a
-> IntMap b
-> IntMap c
merge a -> b -> Maybe c
fab a -> Maybe c
fa b -> Maybe c
fb = \IntMap a
sma0 IntMap b
smb0 -> case IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
sma0 of
    Maybe a
Nothing -> case IntMap b -> Maybe b
forall a. IntMap a -> Maybe a
intMapNegative IntMap b
smb0 of
        Maybe b
Nothing -> IntMap a -> IntMap b -> IntMap c
goMergeStraight IntMap a
sma0 IntMap b
smb0
        Just b
nb0 -> case b -> Maybe c
fb b
nb0 of
            Maybe c
Nothing  -> IntMap a -> IntMap b -> IntMap c
goMergeStraight IntMap a
sma0 IntMap b
smb0
            Just c
nb1 -> c -> IntMap a -> IntMap b -> IntMap c
goMergeNegative c
nb1 IntMap a
sma0 IntMap b
smb0
    Just a
na0 -> case IntMap b -> Maybe b
forall a. IntMap a -> Maybe a
intMapNegative IntMap b
smb0 of
        Maybe b
Nothing -> case a -> Maybe c
fa a
na0 of
            Maybe c
Nothing  -> IntMap a -> IntMap b -> IntMap c
goMergeStraight IntMap a
sma0 IntMap b
smb0
            Just c
na1 -> c -> IntMap a -> IntMap b -> IntMap c
goMergeNegative c
na1 IntMap a
sma0 IntMap b
smb0
        Just b
nb0 -> case a -> b -> Maybe c
fab a
na0 b
nb0 of
            Maybe c
Nothing   -> IntMap a -> IntMap b -> IntMap c
goMergeStraight IntMap a
sma0 IntMap b
smb0
            Just c
nab1 -> c -> IntMap a -> IntMap b -> IntMap c
goMergeNegative c
nab1 IntMap a
sma0 IntMap b
smb0
    where
        goMergeStraight :: IntMap a -> IntMap b -> IntMap c
goMergeStraight IntMap a
sma0 IntMap b
smb0 = IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
            { $sel:intMapStraight:IntMap :: IntMap (Maybe c)
intMapStraight = (Int -> Maybe a -> Maybe b -> Maybe (Maybe c))
-> (IntMap (Maybe a) -> IntMap (Maybe c))
-> (IntMap (Maybe b) -> IntMap (Maybe c))
-> IntMap (Maybe a)
-> IntMap (Maybe b)
-> IntMap (Maybe c)
forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
DataIntMap.mergeWithKey
                do \Int
_ Maybe a
mx Maybe b
my -> case Maybe a
mx of
                    Maybe a
Nothing -> case Maybe b
my of
                        Maybe b
Nothing -> Maybe (Maybe c)
forall a. Maybe a
Nothing
                        Just b
y  -> c -> Maybe c
forall a. a -> Maybe a
Just (c -> Maybe c) -> Maybe c -> Maybe (Maybe c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> b -> Maybe c
fb b
y
                    Just a
x  -> case Maybe b
my of
                        Maybe b
Nothing -> c -> Maybe c
forall a. a -> Maybe a
Just (c -> Maybe c) -> Maybe c -> Maybe (Maybe c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Maybe c
fa a
x
                        Just b
y  -> c -> Maybe c
forall a. a -> Maybe a
Just (c -> Maybe c) -> Maybe c -> Maybe (Maybe c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> b -> Maybe c
fab a
x b
y
                do \IntMap (Maybe a)
ma -> case IntMap b -> Maybe b
forall a. IntMap a -> Maybe a
intMapNegative IntMap b
smb0 of
                    Maybe b
Nothing -> (Maybe a -> Maybe (Maybe c))
-> IntMap (Maybe a) -> IntMap (Maybe c)
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybe
                        do \Maybe a
mx -> (c -> Maybe c) -> Maybe c -> Maybe (Maybe c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap c -> Maybe c
forall a. a -> Maybe a
Just do Maybe a
mx Maybe a -> (a -> Maybe c) -> Maybe c
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Maybe c
fa
                        do IntMap (Maybe a)
ma
                    Just b
nb1 -> (Maybe a -> Maybe (Maybe c))
-> IntMap (Maybe a) -> IntMap (Maybe c)
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybe
                        do \Maybe a
mx -> (c -> Maybe c) -> Maybe c -> Maybe (Maybe c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap c -> Maybe c
forall a. a -> Maybe a
Just do Maybe a
mx Maybe a -> (a -> Maybe c) -> Maybe c
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \a
x -> a -> b -> Maybe c
fab a
x b
nb1
                        do IntMap (Maybe a)
ma
                do \IntMap (Maybe b)
mb -> case IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
sma0 of
                    Maybe a
Nothing -> (Maybe b -> Maybe (Maybe c))
-> IntMap (Maybe b) -> IntMap (Maybe c)
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybe
                        do \Maybe b
my -> (c -> Maybe c) -> Maybe c -> Maybe (Maybe c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap c -> Maybe c
forall a. a -> Maybe a
Just do Maybe b
my Maybe b -> (b -> Maybe c) -> Maybe c
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= b -> Maybe c
fb
                        do IntMap (Maybe b)
mb
                    Just a
na1 -> (Maybe b -> Maybe (Maybe c))
-> IntMap (Maybe b) -> IntMap (Maybe c)
forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybe
                        do \Maybe b
my -> (c -> Maybe c) -> Maybe c -> Maybe (Maybe c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap c -> Maybe c
forall a. a -> Maybe a
Just do Maybe b
my Maybe b -> (b -> Maybe c) -> Maybe c
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \b
y -> a -> b -> Maybe c
fab a
na1 b
y
                        do IntMap (Maybe b)
mb
                do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
sma0
                do IntMap b -> IntMap (Maybe b)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap b
smb0
            , $sel:intMapNegative:IntMap :: Maybe c
intMapNegative = Maybe c
forall a. Maybe a
Nothing
            }

        goMergeNegative :: c -> IntMap a -> IntMap b -> IntMap c
goMergeNegative c
n1 IntMap a
sma0 IntMap b
smb0 = IntMap :: forall a. IntMap (Maybe a) -> Maybe a -> IntMap a
IntMap
            { $sel:intMapStraight:IntMap :: IntMap (Maybe c)
intMapStraight = (Int -> Maybe a -> Maybe b -> Maybe (Maybe c))
-> (IntMap (Maybe a) -> IntMap (Maybe c))
-> (IntMap (Maybe b) -> IntMap (Maybe c))
-> IntMap (Maybe a)
-> IntMap (Maybe b)
-> IntMap (Maybe c)
forall a b c.
(Int -> a -> b -> Maybe c)
-> (IntMap a -> IntMap c)
-> (IntMap b -> IntMap c)
-> IntMap a
-> IntMap b
-> IntMap c
DataIntMap.mergeWithKey
                do \Int
_ Maybe a
mx Maybe b
my -> case Maybe a
mx of
                    Maybe a
Nothing -> case Maybe b
my of
                        Maybe b
Nothing -> Maybe c -> Maybe (Maybe c)
forall a. a -> Maybe a
Just Maybe c
forall a. Maybe a
Nothing
                        Just b
y  -> Maybe c -> Maybe (Maybe c)
forall a. a -> Maybe a
Just do b -> Maybe c
fb b
y
                    Just a
x  -> case Maybe b
my of
                        Maybe b
Nothing -> Maybe c -> Maybe (Maybe c)
forall a. a -> Maybe a
Just do a -> Maybe c
fa a
x
                        Just b
y  -> Maybe c -> Maybe (Maybe c)
forall a. a -> Maybe a
Just do a -> b -> Maybe c
fab a
x b
y
                do \IntMap (Maybe a)
ma -> case IntMap b -> Maybe b
forall a. IntMap a -> Maybe a
intMapNegative IntMap b
smb0 of
                    Maybe b
Nothing -> (Maybe a -> Maybe c) -> IntMap (Maybe a) -> IntMap (Maybe c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
                        do \Maybe a
mx -> Maybe a
mx Maybe a -> (a -> Maybe c) -> Maybe c
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Maybe c
fa
                        do IntMap (Maybe a)
ma
                    Just b
nb1 -> (Maybe a -> Maybe c) -> IntMap (Maybe a) -> IntMap (Maybe c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
                        do \Maybe a
mx -> Maybe a
mx Maybe a -> (a -> Maybe c) -> Maybe c
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \a
x -> a -> b -> Maybe c
fab a
x b
nb1
                        do IntMap (Maybe a)
ma
                do \IntMap (Maybe b)
mb -> case IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
sma0 of
                    Maybe a
Nothing -> (Maybe b -> Maybe c) -> IntMap (Maybe b) -> IntMap (Maybe c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
                        do \Maybe b
my -> Maybe b
my Maybe b -> (b -> Maybe c) -> Maybe c
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= b -> Maybe c
fb
                        do IntMap (Maybe b)
mb
                    Just a
na1 -> (Maybe b -> Maybe c) -> IntMap (Maybe b) -> IntMap (Maybe c)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
                        do \Maybe b
my -> Maybe b
my Maybe b -> (b -> Maybe c) -> Maybe c
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \b
y -> a -> b -> Maybe c
fab a
na1 b
y
                        do IntMap (Maybe b)
mb
                do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
sma0
                do IntMap b -> IntMap (Maybe b)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap b
smb0
            , $sel:intMapNegative:IntMap :: Maybe c
intMapNegative = c -> Maybe c
forall a. a -> Maybe a
Just c
n1
            }

groupBy :: Eq b => Hashable b => (a -> b) -> IntMap a -> HashMap.HashMap b IntSet.T
groupBy :: (a -> b) -> IntMap a -> HashMap b T
groupBy a -> b
f IntMap a
m0 = case IntMap a -> Maybe a
forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m0 of
    Maybe a
Nothing -> (HashMap b T -> (Int, Maybe a) -> HashMap b T)
-> HashMap b T -> [(Int, Maybe a)] -> HashMap b T
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'
        do \HashMap b T
m (Int
k, Maybe a
mv) -> case Maybe a
mv of
            Maybe a
Nothing ->
                HashMap b T
m
            Just a
v -> do
                let fv :: b
fv = a -> b
f a
v
                (Maybe T -> Maybe T) -> b -> HashMap b T -> HashMap b T
forall k v.
(Eq k, Hashable k) =>
(Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
HashMap.alter
                    do \case
                        Just T
ks -> T -> Maybe T
forall a. a -> Maybe a
Just do Int -> T -> T
IntSet.insert Int
k T
ks
                        Maybe T
Nothing -> T -> Maybe T
forall a. a -> Maybe a
Just do Int -> T
IntSet.singleton Int
k
                    b
fv HashMap b T
m
        do HashMap b T
forall k v. HashMap k v
HashMap.empty
        do IntMap (Maybe a) -> [(Int, Maybe a)]
forall a. IntMap a -> [(Int, a)]
DataIntMap.assocs do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
    Just a
nv -> do
        let fnv :: b
fnv = a -> b
f a
nv
        let (HashMap b T
m1, T
nks1) = ((HashMap b T, T) -> (Int, Maybe a) -> (HashMap b T, T))
-> (HashMap b T, T) -> [(Int, Maybe a)] -> (HashMap b T, T)
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'
                do \(HashMap b T
m, T
nks) (Int
k, Maybe a
mv) -> case Maybe a
mv of
                    Maybe a
Nothing ->
                        (HashMap b T
m, Int -> T -> T
IntSet.delete Int
k T
nks)
                    Just a
v -> do
                        let fv :: b
fv = a -> b
f a
v
                        if b
fv b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
fnv
                            then (HashMap b T
m, T
nks)
                            else
                                ( (Maybe T -> Maybe T) -> b -> HashMap b T -> HashMap b T
forall k v.
(Eq k, Hashable k) =>
(Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v
HashMap.alter
                                    do \case
                                        Just T
ks -> T -> Maybe T
forall a. a -> Maybe a
Just do Int -> T -> T
IntSet.insert Int
k T
ks
                                        Maybe T
Nothing -> T -> Maybe T
forall a. a -> Maybe a
Just do Int -> T
IntSet.singleton Int
k
                                    b
fv HashMap b T
m
                                , T
nks
                                )
                do (HashMap b T
forall k v. HashMap k v
HashMap.empty, T
IntSet.full)
                do IntMap (Maybe a) -> [(Int, Maybe a)]
forall a. IntMap a -> [(Int, a)]
DataIntMap.assocs do IntMap a -> IntMap (Maybe a)
forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
        b -> T -> HashMap b T -> HashMap b T
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HashMap.insert b
fnv T
nks1 HashMap b T
m1