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

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

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

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

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

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

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

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

update :: (a -> Maybe a) -> Key -> IntMap a -> IntMap a
update :: forall a. (a -> Maybe a) -> Int -> IntMap a -> IntMap a
update a -> Maybe a
f Int
k IntMap a
m = case forall a. Int -> IntMap a -> Maybe a
DataIntMap.lookup Int
k do 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 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 = forall a. Int -> a -> IntMap a -> IntMap a
DataIntMap.insert Int
k Maybe a
jv do forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
                    }

alter :: (Maybe a -> Maybe a) -> Key -> IntMap a -> IntMap a
alter :: forall a. (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
alter Maybe a -> Maybe a
f Int
k IntMap a
m = case forall a. Int -> IntMap a -> Maybe a
DataIntMap.lookup Int
k do 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 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 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 = forall a. Int -> a -> IntMap a -> IntMap a
DataIntMap.insert Int
k Maybe a
jv do 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 = forall a. Int -> a -> IntMap a -> IntMap a
DataIntMap.insert Int
k
                        do Maybe a -> Maybe a
f Maybe a
jv0
                        do forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
                }

alterBulk :: (Maybe a -> Maybe a) -> IntSet.T -> IntMap a -> IntMap a
alterBulk :: forall a. (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 forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m0 of
        Maybe a
Nothing -> IntMap a
m0
            {
                $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'
                    do \IntMap (Maybe a)
m Int
k -> 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 forall (m :: * -> *) a. Monad m => m (m a) -> m a
join Maybe (Maybe a)
mmv of
                            Maybe a
Nothing   -> forall a. Maybe a
Nothing
                            jv :: Maybe a
jv@Just{} -> forall a. a -> Maybe a
Just Maybe a
jv
                        Int
k IntMap (Maybe a)
m
                    do 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 = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl'
                    do \IntMap (Maybe a)
m Int
k -> forall a. (Maybe a -> Maybe a) -> Int -> IntMap a -> IntMap a
DataIntMap.alter
                        do \case
                            Maybe (Maybe a)
Nothing -> forall a. a -> Maybe a
Just do Maybe a -> Maybe a
f Maybe a
njv
                            Just Maybe a
mv -> forall a. a -> Maybe a
Just do Maybe a -> Maybe a
f Maybe a
mv
                        Int
k IntMap (Maybe a)
m
                    do forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
                    do IntSet -> [Int]
DataIntSet.elems IntSet
s
            }
    IntSet.NegativeSet IntSet
s -> case forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m0 of
        Maybe a
Nothing -> case Maybe a -> Maybe a
f forall a. Maybe a
Nothing of
            Maybe a
Nothing -> IntMap a
m0
                {
                    $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = 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 forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
mv0
                                else forall a. a -> Maybe a
Just forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a -> Maybe a
f Maybe a
mv0
                        do forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
                }
            jv :: Maybe a
jv@Just{} -> IntMap
                { $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = 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 forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
mv0
                        else case Maybe a
mv0 of
                            Maybe a
Nothing -> forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
jv
                            Just{}  -> forall (f :: * -> *) a. Applicative f => a -> f a
pure do Maybe a -> Maybe a
f Maybe a
mv0
                    do 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
                { $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = 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 forall a. a -> Maybe a
Just forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a
mv0
                        else forall a. a -> Maybe a
Just forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a -> Maybe a
f Maybe a
mv0
                    do forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
                , $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = forall a. Maybe a
Nothing
                }
            njv :: Maybe a
njv@Just{} -> IntMap
                { $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = 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 forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
mv0
                        else forall (f :: * -> *) a. Applicative f => a -> f a
pure do Maybe a -> Maybe a
f Maybe a
mv0
                    do 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 :: forall a. Int -> IntMap a -> Maybe a
lookup Int
k IntMap a
m = case forall a. Int -> IntMap a -> Maybe a
DataIntMap.lookup Int
k do forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m of
    Just Maybe a
mv -> Maybe a
mv
    Maybe (Maybe a)
Nothing -> forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m

keys :: IntMap a -> IntSet.T
keys :: forall a. IntMap a -> T
keys IntMap a
m = case 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) <- forall a. IntMap a -> [(Int, a)]
DataIntMap.assocs do 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) <- forall a. IntMap a -> [(Int, a)]
DataIntMap.assocs do 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 :: forall a. IntMap a -> T -> IntMap a
restrictKeys IntMap a
m T
s = case forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m of
    Maybe a
Nothing -> case T
s of
        IntSet.StraightSet IntSet
is ->
            IntMap
                { $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = forall a. Maybe a
Nothing
                , $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = forall a. IntMap a -> IntSet -> IntMap a
DataIntMap.restrictKeys
                    do forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m
                    do IntSet
is
                }
        IntSet.NegativeSet IntSet
is ->
            IntMap
                { $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = forall a. Maybe a
Nothing
                , $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = forall a. IntMap a -> IntSet -> IntMap a
DataIntMap.withoutKeys
                    do 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 = forall a. (Int -> a) -> IntSet -> IntMap a
DataIntMap.fromSet
                    do \Int
_ -> Maybe a
notMx
                    do IntSet
is
            IntMap
                { $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = forall a. Maybe a
Nothing
                , $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
DataIntMap.unionWith
                    do \Maybe a
x Maybe a
_ -> Maybe a
x
                    do 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 = forall a. (Int -> a) -> IntSet -> IntMap a
DataIntMap.fromSet
                    do \Int
_ -> forall a. Maybe a
Nothing
                    do IntSet
is
            IntMap
                { $sel:intMapNegative:IntMap :: Maybe a
intMapNegative = Maybe a
notMx
                , $sel:intMapStraight:IntMap :: IntMap (Maybe a)
intMapStraight = forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
DataIntMap.unionWith
                    do \Maybe a
_ Maybe a
x -> Maybe a
x
                    do 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 :: forall a b c.
(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 forall a. IntMap a -> Maybe a
intMapNegative IntMap a
sma0 of
    Maybe a
Nothing -> case 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 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
            { $sel:intMapStraight:IntMap :: IntMap (Maybe c)
intMapStraight = 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 -> forall a. Maybe a
Nothing
                        Just b
y  -> forall a. a -> Maybe a
Just 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 -> forall a. a -> Maybe a
Just forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> Maybe c
fa a
x
                        Just b
y  -> forall a. a -> Maybe a
Just 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 forall a. IntMap a -> Maybe a
intMapNegative IntMap b
smb0 of
                    Maybe b
Nothing -> forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybe
                        do \Maybe a
mx -> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Maybe a
Just do Maybe a
mx 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 -> forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybe
                        do \Maybe a
mx -> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Maybe a
Just do Maybe a
mx 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 forall a. IntMap a -> Maybe a
intMapNegative IntMap a
sma0 of
                    Maybe a
Nothing -> forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybe
                        do \Maybe b
my -> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Maybe a
Just do Maybe b
my 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 -> forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
DataIntMap.mapMaybe
                        do \Maybe b
my -> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. a -> Maybe a
Just do Maybe b
my 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 forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
sma0
                do forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap b
smb0
            , $sel:intMapNegative:IntMap :: Maybe c
intMapNegative = forall a. Maybe a
Nothing
            }

        goMergeNegative :: c -> IntMap a -> IntMap b -> IntMap c
goMergeNegative c
n1 IntMap a
sma0 IntMap b
smb0 = IntMap
            { $sel:intMapStraight:IntMap :: IntMap (Maybe c)
intMapStraight = 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 -> forall a. a -> Maybe a
Just forall a. Maybe a
Nothing
                        Just b
y  -> forall a. a -> Maybe a
Just do b -> Maybe c
fb b
y
                    Just a
x  -> case Maybe b
my of
                        Maybe b
Nothing -> forall a. a -> Maybe a
Just do a -> Maybe c
fa a
x
                        Just b
y  -> forall a. a -> Maybe a
Just do a -> b -> Maybe c
fab a
x b
y
                do \IntMap (Maybe a)
ma -> case forall a. IntMap a -> Maybe a
intMapNegative IntMap b
smb0 of
                    Maybe b
Nothing -> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
                        do \Maybe a
mx -> Maybe a
mx 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 -> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
                        do \Maybe a
mx -> Maybe a
mx 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 forall a. IntMap a -> Maybe a
intMapNegative IntMap a
sma0 of
                    Maybe a
Nothing -> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
                        do \Maybe b
my -> Maybe b
my 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 -> forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap
                        do \Maybe b
my -> Maybe b
my 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 forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
sma0
                do forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap b
smb0
            , $sel:intMapNegative:IntMap :: Maybe c
intMapNegative = forall a. a -> Maybe a
Just c
n1
            }

groupBy :: Eq b => Hashable b => (a -> b) -> IntMap a -> HashMap.HashMap b IntSet.T
groupBy :: forall b a.
(Eq b, Hashable b) =>
(a -> b) -> IntMap a -> HashMap b T
groupBy a -> b
f IntMap a
m0 = case forall a. IntMap a -> Maybe a
intMapNegative IntMap a
m0 of
    Maybe a
Nothing -> 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
                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 -> forall a. a -> Maybe a
Just do Int -> T -> T
IntSet.insert Int
k T
ks
                        Maybe T
Nothing -> forall a. a -> Maybe a
Just do Int -> T
IntSet.singleton Int
k
                    b
fv HashMap b T
m
        do forall k v. HashMap k v
HashMap.empty
        do forall a. IntMap a -> [(Int, a)]
DataIntMap.assocs do 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) = 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 forall a. Eq a => a -> a -> Bool
== b
fnv
                            then (HashMap b T
m, T
nks)
                            else
                                ( 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 -> forall a. a -> Maybe a
Just do Int -> T -> T
IntSet.insert Int
k T
ks
                                        Maybe T
Nothing -> forall a. a -> Maybe a
Just do Int -> T
IntSet.singleton Int
k
                                    b
fv HashMap b T
m
                                , T
nks
                                )
                do (forall k v. HashMap k v
HashMap.empty, T
IntSet.full)
                do forall a. IntMap a -> [(Int, a)]
DataIntMap.assocs do forall a. IntMap a -> IntMap (Maybe a)
intMapStraight IntMap a
m0
        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