-- |
-- Copyright: © 2022–2024 Jonathan Knowles
-- License: Apache-2.0
--
-- A __lawful__ implementation of 'MultiMap', implemented in terms of 'Map' and
-- 'Set'.
--
module Examples.MultiMap.Instances.MultiMap2 where

import Prelude

import Data.Map.Strict
    ( Map )
import Data.Set
    ( Set )

import qualified Data.Map.Merge.Strict as Map
import qualified Data.Map.Strict as Map
import qualified Data.Set as Set
import qualified Examples.MultiMap.Class as Class

newtype MultiMap2 k v = MultiMap (Map k (Set v))
    deriving stock (MultiMap2 k v -> MultiMap2 k v -> Bool
(MultiMap2 k v -> MultiMap2 k v -> Bool)
-> (MultiMap2 k v -> MultiMap2 k v -> Bool) -> Eq (MultiMap2 k v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k v. (Eq k, Eq v) => MultiMap2 k v -> MultiMap2 k v -> Bool
$c== :: forall k v. (Eq k, Eq v) => MultiMap2 k v -> MultiMap2 k v -> Bool
== :: MultiMap2 k v -> MultiMap2 k v -> Bool
$c/= :: forall k v. (Eq k, Eq v) => MultiMap2 k v -> MultiMap2 k v -> Bool
/= :: MultiMap2 k v -> MultiMap2 k v -> Bool
Eq, Int -> MultiMap2 k v -> ShowS
[MultiMap2 k v] -> ShowS
MultiMap2 k v -> String
(Int -> MultiMap2 k v -> ShowS)
-> (MultiMap2 k v -> String)
-> ([MultiMap2 k v] -> ShowS)
-> Show (MultiMap2 k v)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k v. (Show k, Show v) => Int -> MultiMap2 k v -> ShowS
forall k v. (Show k, Show v) => [MultiMap2 k v] -> ShowS
forall k v. (Show k, Show v) => MultiMap2 k v -> String
$cshowsPrec :: forall k v. (Show k, Show v) => Int -> MultiMap2 k v -> ShowS
showsPrec :: Int -> MultiMap2 k v -> ShowS
$cshow :: forall k v. (Show k, Show v) => MultiMap2 k v -> String
show :: MultiMap2 k v -> String
$cshowList :: forall k v. (Show k, Show v) => [MultiMap2 k v] -> ShowS
showList :: [MultiMap2 k v] -> ShowS
Show)

instance (Ord k, Ord v) => Class.MultiMap MultiMap2 k v where

    fromList :: [(k, Set v)] -> MultiMap2 k v
fromList = Map k (Set v) -> MultiMap2 k v
forall k v. Map k (Set v) -> MultiMap2 k v
MultiMap (Map k (Set v) -> MultiMap2 k v)
-> ([(k, Set v)] -> Map k (Set v)) -> [(k, Set v)] -> MultiMap2 k v
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Set v -> Set v -> Set v) -> [(k, Set v)] -> Map k (Set v)
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith Set v -> Set v -> Set v
forall a. Semigroup a => a -> a -> a
(<>) ([(k, Set v)] -> Map k (Set v))
-> ([(k, Set v)] -> [(k, Set v)]) -> [(k, Set v)] -> Map k (Set v)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, Set v) -> Bool) -> [(k, Set v)] -> [(k, Set v)]
forall a. (a -> Bool) -> [a] -> [a]
filter ((Set v -> Set v -> Bool
forall a. Eq a => a -> a -> Bool
/= Set v
forall a. Monoid a => a
mempty) (Set v -> Bool) -> ((k, Set v) -> Set v) -> (k, Set v) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k, Set v) -> Set v
forall a b. (a, b) -> b
snd)

    toList :: MultiMap2 k v -> [(k, Set v)]
toList (MultiMap Map k (Set v)
m) = Map k (Set v) -> [(k, Set v)]
forall k a. Map k a -> [(k, a)]
Map.toList Map k (Set v)
m

    empty :: MultiMap2 k v
empty = Map k (Set v) -> MultiMap2 k v
forall k v. Map k (Set v) -> MultiMap2 k v
MultiMap Map k (Set v)
forall k a. Map k a
Map.empty

    lookup :: k -> MultiMap2 k v -> Set v
lookup k
k (MultiMap Map k (Set v)
m) = Set v -> k -> Map k (Set v) -> Set v
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault Set v
forall a. Set a
Set.empty k
k Map k (Set v)
m

    null :: MultiMap2 k v -> Bool
null (MultiMap Map k (Set v)
m) = Map k (Set v) -> Bool
forall k a. Map k a -> Bool
Map.null Map k (Set v)
m

    nonNull :: MultiMap2 k v -> Bool
nonNull (MultiMap Map k (Set v)
m) = Bool -> Bool
not (Map k (Set v) -> Bool
forall k a. Map k a -> Bool
Map.null Map k (Set v)
m)

    nonNullKey :: k -> MultiMap2 k v -> Bool
nonNullKey k
k (MultiMap Map k (Set v)
m) = k -> Map k (Set v) -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member k
k Map k (Set v)
m

    nonNullKeys :: MultiMap2 k v -> Set k
nonNullKeys (MultiMap Map k (Set v)
m) = Map k (Set v) -> Set k
forall k a. Map k a -> Set k
Map.keysSet Map k (Set v)
m

    nonNullCount :: MultiMap2 k v -> Int
nonNullCount (MultiMap Map k (Set v)
m) = Map k (Set v) -> Int
forall k a. Map k a -> Int
Map.size Map k (Set v)
m

    isSubmapOf :: MultiMap2 k v -> MultiMap2 k v -> Bool
isSubmapOf (MultiMap Map k (Set v)
m1) (MultiMap Map k (Set v)
m2) =
        (Set v -> Set v -> Bool) -> Map k (Set v) -> Map k (Set v) -> Bool
forall k a b.
Ord k =>
(a -> b -> Bool) -> Map k a -> Map k b -> Bool
Map.isSubmapOfBy Set v -> Set v -> Bool
forall a. Ord a => Set a -> Set a -> Bool
Set.isSubsetOf Map k (Set v)
m1 Map k (Set v)
m2

    update :: k -> Set v -> MultiMap2 k v -> MultiMap2 k v
update k
k Set v
vs (MultiMap Map k (Set v)
m)
        | Set v -> Bool
forall a. Set a -> Bool
Set.null Set v
vs = Map k (Set v) -> MultiMap2 k v
forall k v. Map k (Set v) -> MultiMap2 k v
MultiMap (k -> Map k (Set v) -> Map k (Set v)
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k    Map k (Set v)
m)
        | Bool
otherwise   = Map k (Set v) -> MultiMap2 k v
forall k v. Map k (Set v) -> MultiMap2 k v
MultiMap (k -> Set v -> Map k (Set v) -> Map k (Set v)
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k Set v
vs Map k (Set v)
m)

    insert :: k -> Set v -> MultiMap2 k v -> MultiMap2 k v
insert k
k Set v
vs (MultiMap Map k (Set v)
m)
        | Set v -> Bool
forall a. Set a -> Bool
Set.null Set v
xs = Map k (Set v) -> MultiMap2 k v
forall k v. Map k (Set v) -> MultiMap2 k v
MultiMap (k -> Map k (Set v) -> Map k (Set v)
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k    Map k (Set v)
m)
        | Bool
otherwise   = Map k (Set v) -> MultiMap2 k v
forall k v. Map k (Set v) -> MultiMap2 k v
MultiMap (k -> Set v -> Map k (Set v) -> Map k (Set v)
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k Set v
xs Map k (Set v)
m)
      where
        xs :: Set v
xs = Set v -> k -> Map k (Set v) -> Set v
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault Set v
forall a. Set a
Set.empty k
k Map k (Set v)
m Set v -> Set v -> Set v
forall a. Ord a => Set a -> Set a -> Set a
`Set.union` Set v
vs

    remove :: k -> Set v -> MultiMap2 k v -> MultiMap2 k v
remove k
k Set v
vs (MultiMap Map k (Set v)
m)
        | Set v -> Bool
forall a. Set a -> Bool
Set.null Set v
xs = Map k (Set v) -> MultiMap2 k v
forall k v. Map k (Set v) -> MultiMap2 k v
MultiMap (k -> Map k (Set v) -> Map k (Set v)
forall k a. Ord k => k -> Map k a -> Map k a
Map.delete k
k    Map k (Set v)
m)
        | Bool
otherwise   = Map k (Set v) -> MultiMap2 k v
forall k v. Map k (Set v) -> MultiMap2 k v
MultiMap (k -> Set v -> Map k (Set v) -> Map k (Set v)
forall k a. Ord k => k -> a -> Map k a -> Map k a
Map.insert k
k Set v
xs Map k (Set v)
m)
      where
        xs :: Set v
xs = Set v -> k -> Map k (Set v) -> Set v
forall k a. Ord k => a -> k -> Map k a -> a
Map.findWithDefault Set v
forall a. Set a
Set.empty k
k Map k (Set v)
m Set v -> Set v -> Set v
forall a. Ord a => Set a -> Set a -> Set a
`Set.difference` Set v
vs

    union :: MultiMap2 k v -> MultiMap2 k v -> MultiMap2 k v
union (MultiMap Map k (Set v)
m1) (MultiMap Map k (Set v)
m2) = Map k (Set v) -> MultiMap2 k v
forall k v. Map k (Set v) -> MultiMap2 k v
MultiMap (Map k (Set v) -> MultiMap2 k v) -> Map k (Set v) -> MultiMap2 k v
forall a b. (a -> b) -> a -> b
$
        (Set v -> Set v -> Set v)
-> Map k (Set v) -> Map k (Set v) -> Map k (Set v)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith Set v -> Set v -> Set v
forall a. Ord a => Set a -> Set a -> Set a
Set.union Map k (Set v)
m1 Map k (Set v)
m2

    intersection :: MultiMap2 k v -> MultiMap2 k v -> MultiMap2 k v
intersection (MultiMap Map k (Set v)
m1) (MultiMap Map k (Set v)
m2) = Map k (Set v) -> MultiMap2 k v
forall k v. Map k (Set v) -> MultiMap2 k v
MultiMap (Map k (Set v) -> MultiMap2 k v) -> Map k (Set v) -> MultiMap2 k v
forall a b. (a -> b) -> a -> b
$
        SimpleWhenMissing k (Set v) (Set v)
-> SimpleWhenMissing k (Set v) (Set v)
-> SimpleWhenMatched k (Set v) (Set v) (Set v)
-> Map k (Set v)
-> Map k (Set v)
-> Map k (Set v)
forall k a c b.
Ord k =>
SimpleWhenMissing k a c
-> SimpleWhenMissing k b c
-> SimpleWhenMatched k a b c
-> Map k a
-> Map k b
-> Map k c
Map.merge
            SimpleWhenMissing k (Set v) (Set v)
forall (f :: * -> *) k x y. Applicative f => WhenMissing f k x y
Map.dropMissing
            SimpleWhenMissing k (Set v) (Set v)
forall (f :: * -> *) k x y. Applicative f => WhenMissing f k x y
Map.dropMissing
            ((k -> Set v -> Set v -> Maybe (Set v))
-> SimpleWhenMatched k (Set v) (Set v) (Set v)
forall (f :: * -> *) k x y z.
Applicative f =>
(k -> x -> y -> Maybe z) -> WhenMatched f k x y z
Map.zipWithMaybeMatched k -> Set v -> Set v -> Maybe (Set v)
mergeValues)
            Map k (Set v)
m1
            Map k (Set v)
m2
      where
        mergeValues :: k -> Set v -> Set v -> Maybe (Set v)
        mergeValues :: k -> Set v -> Set v -> Maybe (Set v)
mergeValues k
_k Set v
s1 Set v
s2
            | Set v -> Bool
forall a. Set a -> Bool
Set.null Set v
s3 = Maybe (Set v)
forall a. Maybe a
Nothing
            | Bool
otherwise   = Set v -> Maybe (Set v)
forall a. a -> Maybe a
Just Set v
s3
          where
            s3 :: Set v
s3 = Set v -> Set v -> Set v
forall a. Ord a => Set a -> Set a -> Set a
Set.intersection Set v
s1 Set v
s2