{-# LANGUAGE RecordWildCards #-}

module Unison.Util.Relation3 where

import Data.Function (on)
import Data.Map qualified as Map
import Data.Ord (comparing)
import Data.Semigroup (Sum (Sum, getSum))
import Data.Tuple.Extra (uncurry3)
import Unison.Prelude hiding (empty, toList)
import Unison.Util.Relation (Relation)
import Unison.Util.Relation qualified as R

data Relation3 a b c = Relation3
  { forall a b c. Relation3 a b c -> Map a (Relation b c)
d1 :: Map a (Relation b c),
    forall a b c. Relation3 a b c -> Map b (Relation a c)
d2 :: Map b (Relation a c),
    forall a b c. Relation3 a b c -> Map c (Relation a b)
d3 :: Map c (Relation a b)
  }

instance (Eq a, Eq b, Eq c) => Eq (Relation3 a b c) where
  == :: Relation3 a b c -> Relation3 a b c -> Bool
(==) = Map a (Relation b c) -> Map a (Relation b c) -> Bool
forall a. Eq a => a -> a -> Bool
(==) (Map a (Relation b c) -> Map a (Relation b c) -> Bool)
-> (Relation3 a b c -> Map a (Relation b c))
-> Relation3 a b c
-> Relation3 a b c
-> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Relation3 a b c -> Map a (Relation b c)
forall a b c. Relation3 a b c -> Map a (Relation b c)
d1

instance (Ord a, Ord b, Ord c) => Ord (Relation3 a b c) where
  compare :: Relation3 a b c -> Relation3 a b c -> Ordering
compare = (Relation3 a b c -> Map a (Relation b c))
-> Relation3 a b c -> Relation3 a b c -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing Relation3 a b c -> Map a (Relation b c)
forall a b c. Relation3 a b c -> Map a (Relation b c)
d1

instance (Show a, Show b, Show c) => Show (Relation3 a b c) where
  show :: Relation3 a b c -> String
show = [(a, b, c)] -> String
forall a. Show a => a -> String
show ([(a, b, c)] -> String)
-> (Relation3 a b c -> [(a, b, c)]) -> Relation3 a b c -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation3 a b c -> [(a, b, c)]
forall a b c. Relation3 a b c -> [(a, b, c)]
toList

d1s :: Relation3 a b c -> Set a
d1s :: forall a b c. Relation3 a b c -> Set a
d1s = Map a (Relation b c) -> Set a
forall k a. Map k a -> Set k
Map.keysSet (Map a (Relation b c) -> Set a)
-> (Relation3 a b c -> Map a (Relation b c))
-> Relation3 a b c
-> Set a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation3 a b c -> Map a (Relation b c)
forall a b c. Relation3 a b c -> Map a (Relation b c)
d1

d2s :: Relation3 a b c -> Set b
d2s :: forall a b c. Relation3 a b c -> Set b
d2s = Map b (Relation a c) -> Set b
forall k a. Map k a -> Set k
Map.keysSet (Map b (Relation a c) -> Set b)
-> (Relation3 a b c -> Map b (Relation a c))
-> Relation3 a b c
-> Set b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation3 a b c -> Map b (Relation a c)
forall a b c. Relation3 a b c -> Map b (Relation a c)
d2

d3s :: Relation3 a b c -> Set c
d3s :: forall a b c. Relation3 a b c -> Set c
d3s = Map c (Relation a b) -> Set c
forall k a. Map k a -> Set k
Map.keysSet (Map c (Relation a b) -> Set c)
-> (Relation3 a b c -> Map c (Relation a b))
-> Relation3 a b c
-> Set c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation3 a b c -> Map c (Relation a b)
forall a b c. Relation3 a b c -> Map c (Relation a b)
d3

-- | Project out a relation that only includes the 1st and 2nd dimensions.
d12 :: Relation3 a b c -> Relation a b
d12 :: forall a b c. Relation3 a b c -> Relation a b
d12 Relation3 {Map a (Relation b c)
d1 :: forall a b c. Relation3 a b c -> Map a (Relation b c)
d1 :: Map a (Relation b c)
d1, Map b (Relation a c)
d2 :: forall a b c. Relation3 a b c -> Map b (Relation a c)
d2 :: Map b (Relation a c)
d2} =
  Map a (Set b) -> Map b (Set a) -> Relation a b
forall a b. Map a (Set b) -> Map b (Set a) -> Relation a b
R.unsafeFromMultimaps ((Relation b c -> Set b) -> Map a (Relation b c) -> Map a (Set b)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map Relation b c -> Set b
forall a b. Relation a b -> Set a
R.dom Map a (Relation b c)
d1) ((Relation a c -> Set a) -> Map b (Relation a c) -> Map b (Set a)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map Relation a c -> Set a
forall a b. Relation a b -> Set a
R.dom Map b (Relation a c)
d2)

-- | Project out a relation that only includes the 1st and 3rd dimensions.
d13 :: Relation3 a b c -> Relation a c
d13 :: forall a b c. Relation3 a b c -> Relation a c
d13 Relation3 {Map a (Relation b c)
d1 :: forall a b c. Relation3 a b c -> Map a (Relation b c)
d1 :: Map a (Relation b c)
d1, Map c (Relation a b)
d3 :: forall a b c. Relation3 a b c -> Map c (Relation a b)
d3 :: Map c (Relation a b)
d3} =
  Map a (Set c) -> Map c (Set a) -> Relation a c
forall a b. Map a (Set b) -> Map b (Set a) -> Relation a b
R.unsafeFromMultimaps ((Relation b c -> Set c) -> Map a (Relation b c) -> Map a (Set c)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map Relation b c -> Set c
forall a b. Relation a b -> Set b
R.ran Map a (Relation b c)
d1) ((Relation a b -> Set a) -> Map c (Relation a b) -> Map c (Set a)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map Relation a b -> Set a
forall a b. Relation a b -> Set a
R.dom Map c (Relation a b)
d3)

-- | Project out a relation that only includes the 2nd and 3rd dimensions.
d23 :: Relation3 a b c -> Relation b c
d23 :: forall a b c. Relation3 a b c -> Relation b c
d23 Relation3 {Map b (Relation a c)
d2 :: forall a b c. Relation3 a b c -> Map b (Relation a c)
d2 :: Map b (Relation a c)
d2, Map c (Relation a b)
d3 :: forall a b c. Relation3 a b c -> Map c (Relation a b)
d3 :: Map c (Relation a b)
d3} =
  Map b (Set c) -> Map c (Set b) -> Relation b c
forall a b. Map a (Set b) -> Map b (Set a) -> Relation a b
R.unsafeFromMultimaps ((Relation a c -> Set c) -> Map b (Relation a c) -> Map b (Set c)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map Relation a c -> Set c
forall a b. Relation a b -> Set b
R.ran Map b (Relation a c)
d2) ((Relation a b -> Set b) -> Map c (Relation a b) -> Map c (Set b)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map Relation a b -> Set b
forall a b. Relation a b -> Set b
R.ran Map c (Relation a b)
d3)

filter ::
  (Ord a, Ord b, Ord c) =>
  ((a, b, c) -> Bool) ->
  Relation3 a b c ->
  Relation3 a b c
filter :: forall a b c.
(Ord a, Ord b, Ord c) =>
((a, b, c) -> Bool) -> Relation3 a b c -> Relation3 a b c
filter (a, b, c) -> Bool
f = [(a, b, c)] -> Relation3 a b c
forall a b c.
(Ord a, Ord b, Ord c) =>
[(a, b, c)] -> Relation3 a b c
fromList ([(a, b, c)] -> Relation3 a b c)
-> (Relation3 a b c -> [(a, b, c)])
-> Relation3 a b c
-> Relation3 a b c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, b, c) -> Bool) -> [(a, b, c)] -> [(a, b, c)]
forall a. (a -> Bool) -> [a] -> [a]
Prelude.filter (a, b, c) -> Bool
f ([(a, b, c)] -> [(a, b, c)])
-> (Relation3 a b c -> [(a, b, c)])
-> Relation3 a b c
-> [(a, b, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation3 a b c -> [(a, b, c)]
forall a b c. Relation3 a b c -> [(a, b, c)]
toList

mapD1 :: (Ord a, Ord a', Ord b, Ord c) => (a -> a') -> Relation3 a b c -> Relation3 a' b c
mapD1 :: forall a a' b c.
(Ord a, Ord a', Ord b, Ord c) =>
(a -> a') -> Relation3 a b c -> Relation3 a' b c
mapD1 a -> a'
f Relation3 {Map a (Relation b c)
d1 :: forall a b c. Relation3 a b c -> Map a (Relation b c)
d1 :: Map a (Relation b c)
d1, Map b (Relation a c)
d2 :: forall a b c. Relation3 a b c -> Map b (Relation a c)
d2 :: Map b (Relation a c)
d2, Map c (Relation a b)
d3 :: forall a b c. Relation3 a b c -> Map c (Relation a b)
d3 :: Map c (Relation a b)
d3} =
  Relation3
    { d1 :: Map a' (Relation b c)
d1 = (Relation b c -> Relation b c -> Relation b c)
-> (a -> a') -> Map a (Relation b c) -> Map a' (Relation b c)
forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysWith Relation b c -> Relation b c -> Relation b c
forall a b.
(Ord a, Ord b) =>
Relation a b -> Relation a b -> Relation a b
R.union a -> a'
f Map a (Relation b c)
d1,
      d2 :: Map b (Relation a' c)
d2 = (Relation a c -> Relation a' c)
-> Map b (Relation a c) -> Map b (Relation a' c)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map ((a -> a') -> Relation a c -> Relation a' c
forall a a' b.
(Ord a, Ord a', Ord b) =>
(a -> a') -> Relation a b -> Relation a' b
R.mapDom a -> a'
f) Map b (Relation a c)
d2,
      d3 :: Map c (Relation a' b)
d3 = (Relation a b -> Relation a' b)
-> Map c (Relation a b) -> Map c (Relation a' b)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map ((a -> a') -> Relation a b -> Relation a' b
forall a a' b.
(Ord a, Ord a', Ord b) =>
(a -> a') -> Relation a b -> Relation a' b
R.mapDom a -> a'
f) Map c (Relation a b)
d3
    }

-- | Like 'mapD1', but takes a function that must be monotonic; i.e. @compare x y == compare (f x) (f y)@.
mapD1Monotonic :: (Ord a, Ord a', Ord b, Ord c) => (a -> a') -> Relation3 a b c -> Relation3 a' b c
mapD1Monotonic :: forall a a' b c.
(Ord a, Ord a', Ord b, Ord c) =>
(a -> a') -> Relation3 a b c -> Relation3 a' b c
mapD1Monotonic a -> a'
f Relation3 {Map a (Relation b c)
d1 :: forall a b c. Relation3 a b c -> Map a (Relation b c)
d1 :: Map a (Relation b c)
d1, Map b (Relation a c)
d2 :: forall a b c. Relation3 a b c -> Map b (Relation a c)
d2 :: Map b (Relation a c)
d2, Map c (Relation a b)
d3 :: forall a b c. Relation3 a b c -> Map c (Relation a b)
d3 :: Map c (Relation a b)
d3} =
  Relation3
    { d1 :: Map a' (Relation b c)
d1 = (a -> a') -> Map a (Relation b c) -> Map a' (Relation b c)
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysMonotonic a -> a'
f Map a (Relation b c)
d1,
      d2 :: Map b (Relation a' c)
d2 = (Relation a c -> Relation a' c)
-> Map b (Relation a c) -> Map b (Relation a' c)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map ((a -> a') -> Relation a c -> Relation a' c
forall a a' b.
(Ord a, Ord a', Ord b) =>
(a -> a') -> Relation a b -> Relation a' b
R.mapDomMonotonic a -> a'
f) Map b (Relation a c)
d2,
      d3 :: Map c (Relation a' b)
d3 = (Relation a b -> Relation a' b)
-> Map c (Relation a b) -> Map c (Relation a' b)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map ((a -> a') -> Relation a b -> Relation a' b
forall a a' b.
(Ord a, Ord a', Ord b) =>
(a -> a') -> Relation a b -> Relation a' b
R.mapDomMonotonic a -> a'
f) Map c (Relation a b)
d3
    }

mapD2 :: (Ord a, Ord b, Ord b', Ord c) => (b -> b') -> Relation3 a b c -> Relation3 a b' c
mapD2 :: forall a b b' c.
(Ord a, Ord b, Ord b', Ord c) =>
(b -> b') -> Relation3 a b c -> Relation3 a b' c
mapD2 b -> b'
f Relation3 {Map a (Relation b c)
d1 :: forall a b c. Relation3 a b c -> Map a (Relation b c)
d1 :: Map a (Relation b c)
d1, Map b (Relation a c)
d2 :: forall a b c. Relation3 a b c -> Map b (Relation a c)
d2 :: Map b (Relation a c)
d2, Map c (Relation a b)
d3 :: forall a b c. Relation3 a b c -> Map c (Relation a b)
d3 :: Map c (Relation a b)
d3} =
  Relation3
    { d1 :: Map a (Relation b' c)
d1 = (Relation b c -> Relation b' c)
-> Map a (Relation b c) -> Map a (Relation b' c)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map ((b -> b') -> Relation b c -> Relation b' c
forall a a' b.
(Ord a, Ord a', Ord b) =>
(a -> a') -> Relation a b -> Relation a' b
R.mapDom b -> b'
f) Map a (Relation b c)
d1,
      d2 :: Map b' (Relation a c)
d2 = (Relation a c -> Relation a c -> Relation a c)
-> (b -> b') -> Map b (Relation a c) -> Map b' (Relation a c)
forall k2 a k1.
Ord k2 =>
(a -> a -> a) -> (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysWith Relation a c -> Relation a c -> Relation a c
forall a b.
(Ord a, Ord b) =>
Relation a b -> Relation a b -> Relation a b
R.union b -> b'
f Map b (Relation a c)
d2,
      d3 :: Map c (Relation a b')
d3 = (Relation a b -> Relation a b')
-> Map c (Relation a b) -> Map c (Relation a b')
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map ((b -> b') -> Relation a b -> Relation a b'
forall a b b'.
(Ord a, Ord b, Ord b') =>
(b -> b') -> Relation a b -> Relation a b'
R.mapRan b -> b'
f) Map c (Relation a b)
d3
    }

-- | Like 'mapD2', but takes a function that must be monotonic; i.e. @compare x y == compare (f x) (f y)@.
mapD2Monotonic :: (Ord a, Ord b, Ord b', Ord c) => (b -> b') -> Relation3 a b c -> Relation3 a b' c
mapD2Monotonic :: forall a b b' c.
(Ord a, Ord b, Ord b', Ord c) =>
(b -> b') -> Relation3 a b c -> Relation3 a b' c
mapD2Monotonic b -> b'
f Relation3 {Map a (Relation b c)
d1 :: forall a b c. Relation3 a b c -> Map a (Relation b c)
d1 :: Map a (Relation b c)
d1, Map b (Relation a c)
d2 :: forall a b c. Relation3 a b c -> Map b (Relation a c)
d2 :: Map b (Relation a c)
d2, Map c (Relation a b)
d3 :: forall a b c. Relation3 a b c -> Map c (Relation a b)
d3 :: Map c (Relation a b)
d3} =
  Relation3
    { d1 :: Map a (Relation b' c)
d1 = (Relation b c -> Relation b' c)
-> Map a (Relation b c) -> Map a (Relation b' c)
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map ((b -> b') -> Relation b c -> Relation b' c
forall a a' b.
(Ord a, Ord a', Ord b) =>
(a -> a') -> Relation a b -> Relation a' b
R.mapDomMonotonic b -> b'
f) Map a (Relation b c)
d1,
      d2 :: Map b' (Relation a c)
d2 = (b -> b') -> Map b (Relation a c) -> Map b' (Relation a c)
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
Map.mapKeysMonotonic b -> b'
f Map b (Relation a c)
d2,
      d3 :: Map c (Relation a b')
d3 = (Relation a b -> Relation a b')
-> Map c (Relation a b) -> Map c (Relation a b')
forall a b k. (a -> b) -> Map k a -> Map k b
Map.map ((b -> b') -> Relation a b -> Relation a b'
forall a b b'.
(Ord a, Ord b, Ord b') =>
(b -> b') -> Relation a b -> Relation a b'
R.mapRanMonotonic b -> b'
f) Map c (Relation a b)
d3
    }

member :: (Ord a, Ord b, Ord c) => a -> b -> c -> Relation3 a b c -> Bool
member :: forall a b c.
(Ord a, Ord b, Ord c) =>
a -> b -> c -> Relation3 a b c -> Bool
member a
a b
b c
c = b -> c -> Relation b c -> Bool
forall a b. (Ord a, Ord b) => a -> b -> Relation a b -> Bool
R.member b
b c
c (Relation b c -> Bool)
-> (Relation3 a b c -> Relation b c) -> Relation3 a b c -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Relation3 a b c -> Relation b c
forall a b c.
(Ord a, Ord b, Ord c) =>
a -> Relation3 a b c -> Relation b c
lookupD1 a
a

memberD2 :: (Ord b) => b -> Relation3 a b c -> Bool
memberD2 :: forall b a c. Ord b => b -> Relation3 a b c -> Bool
memberD2 b
b =
  b -> Map b (Relation a c) -> Bool
forall k a. Ord k => k -> Map k a -> Bool
Map.member b
b (Map b (Relation a c) -> Bool)
-> (Relation3 a b c -> Map b (Relation a c))
-> Relation3 a b c
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation3 a b c -> Map b (Relation a c)
forall a b c. Relation3 a b c -> Map b (Relation a c)
d2

lookupD1 :: (Ord a, Ord b, Ord c) => a -> Relation3 a b c -> Relation b c
lookupD1 :: forall a b c.
(Ord a, Ord b, Ord c) =>
a -> Relation3 a b c -> Relation b c
lookupD1 a
a = Relation b c -> Maybe (Relation b c) -> Relation b c
forall a. a -> Maybe a -> a
fromMaybe Relation b c
forall a. Monoid a => a
mempty (Maybe (Relation b c) -> Relation b c)
-> (Relation3 a b c -> Maybe (Relation b c))
-> Relation3 a b c
-> Relation b c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Map a (Relation b c) -> Maybe (Relation b c)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup a
a (Map a (Relation b c) -> Maybe (Relation b c))
-> (Relation3 a b c -> Map a (Relation b c))
-> Relation3 a b c
-> Maybe (Relation b c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation3 a b c -> Map a (Relation b c)
forall a b c. Relation3 a b c -> Map a (Relation b c)
d1

lookupD2 :: (Ord a, Ord b, Ord c) => b -> Relation3 a b c -> Relation a c
lookupD2 :: forall a b c.
(Ord a, Ord b, Ord c) =>
b -> Relation3 a b c -> Relation a c
lookupD2 b
b = Relation a c -> Maybe (Relation a c) -> Relation a c
forall a. a -> Maybe a -> a
fromMaybe Relation a c
forall a. Monoid a => a
mempty (Maybe (Relation a c) -> Relation a c)
-> (Relation3 a b c -> Maybe (Relation a c))
-> Relation3 a b c
-> Relation a c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> Map b (Relation a c) -> Maybe (Relation a c)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup b
b (Map b (Relation a c) -> Maybe (Relation a c))
-> (Relation3 a b c -> Map b (Relation a c))
-> Relation3 a b c
-> Maybe (Relation a c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation3 a b c -> Map b (Relation a c)
forall a b c. Relation3 a b c -> Map b (Relation a c)
d2

lookupD3 :: (Ord a, Ord b, Ord c) => c -> Relation3 a b c -> Relation a b
lookupD3 :: forall a b c.
(Ord a, Ord b, Ord c) =>
c -> Relation3 a b c -> Relation a b
lookupD3 c
c = Relation a b -> Maybe (Relation a b) -> Relation a b
forall a. a -> Maybe a -> a
fromMaybe Relation a b
forall a. Monoid a => a
mempty (Maybe (Relation a b) -> Relation a b)
-> (Relation3 a b c -> Maybe (Relation a b))
-> Relation3 a b c
-> Relation a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. c -> Map c (Relation a b) -> Maybe (Relation a b)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup c
c (Map c (Relation a b) -> Maybe (Relation a b))
-> (Relation3 a b c -> Map c (Relation a b))
-> Relation3 a b c
-> Maybe (Relation a b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation3 a b c -> Map c (Relation a b)
forall a b c. Relation3 a b c -> Map c (Relation a b)
d3

size :: (Ord a, Ord b, Ord c) => Relation3 a b c -> Int
size :: forall a b c. (Ord a, Ord b, Ord c) => Relation3 a b c -> Int
size = Sum Int -> Int
forall a. Sum a -> a
getSum (Sum Int -> Int)
-> (Relation3 a b c -> Sum Int) -> Relation3 a b c -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Relation b c -> Sum Int) -> Map a (Relation b c) -> Sum Int
forall m a. Monoid m => (a -> m) -> Map a a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (Int -> Sum Int
forall a. a -> Sum a
Sum (Int -> Sum Int)
-> (Relation b c -> Int) -> Relation b c -> Sum Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation b c -> Int
forall a b. Relation a b -> Int
R.size) (Map a (Relation b c) -> Sum Int)
-> (Relation3 a b c -> Map a (Relation b c))
-> Relation3 a b c
-> Sum Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation3 a b c -> Map a (Relation b c)
forall a b c. Relation3 a b c -> Map a (Relation b c)
d1

toList :: Relation3 a b c -> [(a, b, c)]
toList :: forall a b c. Relation3 a b c -> [(a, b, c)]
toList = ((a, (b, c)) -> (a, b, c)) -> [(a, (b, c))] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(a
a, (b
b, c
c)) -> (a
a, b
b, c
c)) ([(a, (b, c))] -> [(a, b, c)])
-> (Relation3 a b c -> [(a, (b, c))])
-> Relation3 a b c
-> [(a, b, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation3 a b c -> [(a, (b, c))]
forall a b c. Relation3 a b c -> [(a, (b, c))]
toNestedList

toNestedList :: Relation3 a b c -> [(a, (b, c))]
toNestedList :: forall a b c. Relation3 a b c -> [(a, (b, c))]
toNestedList Relation3 a b c
r3 =
  [ (a
a, (b, c)
bc) | (a
a, Relation b c
r2) <- Map a (Relation b c) -> [(a, Relation b c)]
forall k a. Map k a -> [(k, a)]
Map.toList (Map a (Relation b c) -> [(a, Relation b c)])
-> Map a (Relation b c) -> [(a, Relation b c)]
forall a b. (a -> b) -> a -> b
$ Relation3 a b c -> Map a (Relation b c)
forall a b c. Relation3 a b c -> Map a (Relation b c)
d1 Relation3 a b c
r3, (b, c)
bc <- Relation b c -> [(b, c)]
forall a b. Relation a b -> [(a, b)]
R.toList Relation b c
r2
  ]

nestD12 :: (Ord a, Ord b, Ord c) => Relation3 a b c -> Relation (a, b) c
nestD12 :: forall a b c.
(Ord a, Ord b, Ord c) =>
Relation3 a b c -> Relation (a, b) c
nestD12 Relation3 a b c
r = [((a, b), c)] -> Relation (a, b) c
forall a b. (Ord a, Ord b) => [(a, b)] -> Relation a b
R.fromList [((a
a, b
b), c
c) | (a
a, b
b, c
c) <- Relation3 a b c -> [(a, b, c)]
forall a b c. Relation3 a b c -> [(a, b, c)]
toList Relation3 a b c
r]

fromNestedDom :: (Ord a, Ord b, Ord c) => Relation (a, b) c -> Relation3 a b c
fromNestedDom :: forall a b c.
(Ord a, Ord b, Ord c) =>
Relation (a, b) c -> Relation3 a b c
fromNestedDom = [(a, b, c)] -> Relation3 a b c
forall a b c.
(Ord a, Ord b, Ord c) =>
[(a, b, c)] -> Relation3 a b c
fromList ([(a, b, c)] -> Relation3 a b c)
-> (Relation (a, b) c -> [(a, b, c)])
-> Relation (a, b) c
-> Relation3 a b c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (((a, b), c) -> (a, b, c)) -> [((a, b), c)] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\((a
a, b
b), c
c) -> (a
a, b
b, c
c)) ([((a, b), c)] -> [(a, b, c)])
-> (Relation (a, b) c -> [((a, b), c)])
-> Relation (a, b) c
-> [(a, b, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation (a, b) c -> [((a, b), c)]
forall a b. Relation a b -> [(a, b)]
R.toList

fromNestedRan :: (Ord a, Ord b, Ord c) => Relation a (b, c) -> Relation3 a b c
fromNestedRan :: forall a b c.
(Ord a, Ord b, Ord c) =>
Relation a (b, c) -> Relation3 a b c
fromNestedRan = [(a, b, c)] -> Relation3 a b c
forall a b c.
(Ord a, Ord b, Ord c) =>
[(a, b, c)] -> Relation3 a b c
fromList ([(a, b, c)] -> Relation3 a b c)
-> (Relation a (b, c) -> [(a, b, c)])
-> Relation a (b, c)
-> Relation3 a b c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, (b, c)) -> (a, b, c)) -> [(a, (b, c))] -> [(a, b, c)]
forall a b. (a -> b) -> [a] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(a
a, (b
b, c
c)) -> (a
a, b
b, c
c)) ([(a, (b, c))] -> [(a, b, c)])
-> (Relation a (b, c) -> [(a, (b, c))])
-> Relation a (b, c)
-> [(a, b, c)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation a (b, c) -> [(a, (b, c))]
forall a b. Relation a b -> [(a, b)]
R.toList

fromList :: (Ord a, Ord b, Ord c) => [(a, b, c)] -> Relation3 a b c
fromList :: forall a b c.
(Ord a, Ord b, Ord c) =>
[(a, b, c)] -> Relation3 a b c
fromList [(a, b, c)]
xs = [(a, b, c)] -> Relation3 a b c -> Relation3 a b c
forall (f :: * -> *) a b c.
(Foldable f, Ord a, Ord b, Ord c) =>
f (a, b, c) -> Relation3 a b c -> Relation3 a b c
insertAll [(a, b, c)]
xs Relation3 a b c
forall a b c. (Ord a, Ord b, Ord c) => Relation3 a b c
empty

empty :: (Ord a, Ord b, Ord c) => Relation3 a b c
empty :: forall a b c. (Ord a, Ord b, Ord c) => Relation3 a b c
empty = Relation3 a b c
forall a. Monoid a => a
mempty

null :: Relation3 a b c -> Bool
null :: forall a b c. Relation3 a b c -> Bool
null Relation3 a b c
r = Map a (Relation b c) -> Bool
forall k a. Map k a -> Bool
Map.null (Map a (Relation b c) -> Bool) -> Map a (Relation b c) -> Bool
forall a b. (a -> b) -> a -> b
$ Relation3 a b c -> Map a (Relation b c)
forall a b c. Relation3 a b c -> Map a (Relation b c)
d1 Relation3 a b c
r

insert,
  delete ::
    (Ord a, Ord b, Ord c) =>
    a ->
    b ->
    c ->
    Relation3 a b c ->
    Relation3 a b c
insert :: forall a b c.
(Ord a, Ord b, Ord c) =>
a -> b -> c -> Relation3 a b c -> Relation3 a b c
insert a
a b
b c
c Relation3 {Map a (Relation b c)
Map b (Relation a c)
Map c (Relation a b)
d1 :: forall a b c. Relation3 a b c -> Map a (Relation b c)
d2 :: forall a b c. Relation3 a b c -> Map b (Relation a c)
d3 :: forall a b c. Relation3 a b c -> Map c (Relation a b)
d1 :: Map a (Relation b c)
d2 :: Map b (Relation a c)
d3 :: Map c (Relation a b)
..} =
  Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
forall a b c.
Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
Relation3
    ((Maybe (Relation b c) -> Maybe (Relation b c))
-> a -> Map a (Relation b c) -> Map a (Relation b c)
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter (b -> c -> Maybe (Relation b c) -> Maybe (Relation b c)
forall {a} {b}.
(Ord a, Ord b) =>
a -> b -> Maybe (Relation a b) -> Maybe (Relation a b)
ins b
b c
c) a
a Map a (Relation b c)
d1)
    ((Maybe (Relation a c) -> Maybe (Relation a c))
-> b -> Map b (Relation a c) -> Map b (Relation a c)
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter (a -> c -> Maybe (Relation a c) -> Maybe (Relation a c)
forall {a} {b}.
(Ord a, Ord b) =>
a -> b -> Maybe (Relation a b) -> Maybe (Relation a b)
ins a
a c
c) b
b Map b (Relation a c)
d2)
    ((Maybe (Relation a b) -> Maybe (Relation a b))
-> c -> Map c (Relation a b) -> Map c (Relation a b)
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter (a -> b -> Maybe (Relation a b) -> Maybe (Relation a b)
forall {a} {b}.
(Ord a, Ord b) =>
a -> b -> Maybe (Relation a b) -> Maybe (Relation a b)
ins a
a b
b) c
c Map c (Relation a b)
d3)
  where
    ins :: a -> b -> Maybe (Relation a b) -> Maybe (Relation a b)
ins a
x b
y = Relation a b -> Maybe (Relation a b)
forall a. a -> Maybe a
Just (Relation a b -> Maybe (Relation a b))
-> (Maybe (Relation a b) -> Relation a b)
-> Maybe (Relation a b)
-> Maybe (Relation a b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b -> Relation a b -> Relation a b
forall a b.
(Ord a, Ord b) =>
a -> b -> Relation a b -> Relation a b
R.insert a
x b
y (Relation a b -> Relation a b)
-> (Maybe (Relation a b) -> Relation a b)
-> Maybe (Relation a b)
-> Relation a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Relation a b -> Maybe (Relation a b) -> Relation a b
forall a. a -> Maybe a -> a
fromMaybe Relation a b
forall a. Monoid a => a
mempty

insertAll,
  deleteAll ::
    (Foldable f) =>
    (Ord a) =>
    (Ord b) =>
    (Ord c) =>
    f (a, b, c) ->
    Relation3 a b c ->
    Relation3 a b c
insertAll :: forall (f :: * -> *) a b c.
(Foldable f, Ord a, Ord b, Ord c) =>
f (a, b, c) -> Relation3 a b c -> Relation3 a b c
insertAll f (a, b, c)
f Relation3 a b c
r = (Relation3 a b c -> (a, b, c) -> Relation3 a b c)
-> Relation3 a b c -> f (a, b, c) -> Relation3 a b c
forall b a. (b -> a -> b) -> b -> f a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Relation3 a b c
r (a, b, c)
x -> (a -> b -> c -> Relation3 a b c -> Relation3 a b c)
-> (a, b, c) -> Relation3 a b c -> Relation3 a b c
forall a b c d. (a -> b -> c -> d) -> (a, b, c) -> d
uncurry3 a -> b -> c -> Relation3 a b c -> Relation3 a b c
forall a b c.
(Ord a, Ord b, Ord c) =>
a -> b -> c -> Relation3 a b c -> Relation3 a b c
insert (a, b, c)
x Relation3 a b c
r) Relation3 a b c
r f (a, b, c)
f
deleteAll :: forall (f :: * -> *) a b c.
(Foldable f, Ord a, Ord b, Ord c) =>
f (a, b, c) -> Relation3 a b c -> Relation3 a b c
deleteAll f (a, b, c)
f Relation3 a b c
r = (Relation3 a b c -> (a, b, c) -> Relation3 a b c)
-> Relation3 a b c -> f (a, b, c) -> Relation3 a b c
forall b a. (b -> a -> b) -> b -> f a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\Relation3 a b c
r (a, b, c)
x -> (a -> b -> c -> Relation3 a b c -> Relation3 a b c)
-> (a, b, c) -> Relation3 a b c -> Relation3 a b c
forall a b c d. (a -> b -> c -> d) -> (a, b, c) -> d
uncurry3 a -> b -> c -> Relation3 a b c -> Relation3 a b c
forall a b c.
(Ord a, Ord b, Ord c) =>
a -> b -> c -> Relation3 a b c -> Relation3 a b c
delete (a, b, c)
x Relation3 a b c
r) Relation3 a b c
r f (a, b, c)
f

-- | Compute the difference of two relations.
difference :: (Ord a, Ord b, Ord c) => Relation3 a b c -> Relation3 a b c -> Relation3 a b c
difference :: forall a b c.
(Ord a, Ord b, Ord c) =>
Relation3 a b c -> Relation3 a b c -> Relation3 a b c
difference (Relation3 Map a (Relation b c)
a1 Map b (Relation a c)
b1 Map c (Relation a b)
c1) (Relation3 Map a (Relation b c)
a2 Map b (Relation a c)
b2 Map c (Relation a b)
c2) =
  Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
forall a b c.
Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
Relation3
    ((Relation b c -> Relation b c -> Maybe (Relation b c))
-> Map a (Relation b c)
-> Map a (Relation b c)
-> Map a (Relation b c)
forall k a b.
Ord k =>
(a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
Map.differenceWith Relation b c -> Relation b c -> Maybe (Relation b c)
forall a b.
(Ord a, Ord b) =>
Relation a b -> Relation a b -> Maybe (Relation a b)
R.difference1 Map a (Relation b c)
a1 Map a (Relation b c)
a2)
    ((Relation a c -> Relation a c -> Maybe (Relation a c))
-> Map b (Relation a c)
-> Map b (Relation a c)
-> Map b (Relation a c)
forall k a b.
Ord k =>
(a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
Map.differenceWith Relation a c -> Relation a c -> Maybe (Relation a c)
forall a b.
(Ord a, Ord b) =>
Relation a b -> Relation a b -> Maybe (Relation a b)
R.difference1 Map b (Relation a c)
b1 Map b (Relation a c)
b2)
    ((Relation a b -> Relation a b -> Maybe (Relation a b))
-> Map c (Relation a b)
-> Map c (Relation a b)
-> Map c (Relation a b)
forall k a b.
Ord k =>
(a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
Map.differenceWith Relation a b -> Relation a b -> Maybe (Relation a b)
forall a b.
(Ord a, Ord b) =>
Relation a b -> Relation a b -> Maybe (Relation a b)
R.difference1 Map c (Relation a b)
c1 Map c (Relation a b)
c2)

-- | @union x y@ computes the union of @x@ and @y@.
union :: (Ord a, Ord b, Ord c) => Relation3 a b c -> Relation3 a b c -> Relation3 a b c
union :: forall a b c.
(Ord a, Ord b, Ord c) =>
Relation3 a b c -> Relation3 a b c -> Relation3 a b c
union (Relation3 Map a (Relation b c)
a1 Map b (Relation a c)
b1 Map c (Relation a b)
c1) (Relation3 Map a (Relation b c)
a2 Map b (Relation a c)
b2 Map c (Relation a b)
c2) =
  Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
forall a b c.
Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
Relation3
    ((Relation b c -> Relation b c -> Relation b c)
-> Map a (Relation b c)
-> Map a (Relation b c)
-> Map a (Relation b c)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith Relation b c -> Relation b c -> Relation b c
forall a b.
(Ord a, Ord b) =>
Relation a b -> Relation a b -> Relation a b
R.union Map a (Relation b c)
a1 Map a (Relation b c)
a2)
    ((Relation a c -> Relation a c -> Relation a c)
-> Map b (Relation a c)
-> Map b (Relation a c)
-> Map b (Relation a c)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith Relation a c -> Relation a c -> Relation a c
forall a b.
(Ord a, Ord b) =>
Relation a b -> Relation a b -> Relation a b
R.union Map b (Relation a c)
b1 Map b (Relation a c)
b2)
    ((Relation a b -> Relation a b -> Relation a b)
-> Map c (Relation a b)
-> Map c (Relation a b)
-> Map c (Relation a b)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith Relation a b -> Relation a b -> Relation a b
forall a b.
(Ord a, Ord b) =>
Relation a b -> Relation a b -> Relation a b
R.union Map c (Relation a b)
c1 Map c (Relation a b)
c2)

delete :: forall a b c.
(Ord a, Ord b, Ord c) =>
a -> b -> c -> Relation3 a b c -> Relation3 a b c
delete a
a b
b c
c Relation3 {Map a (Relation b c)
Map b (Relation a c)
Map c (Relation a b)
d1 :: forall a b c. Relation3 a b c -> Map a (Relation b c)
d2 :: forall a b c. Relation3 a b c -> Map b (Relation a c)
d3 :: forall a b c. Relation3 a b c -> Map c (Relation a b)
d1 :: Map a (Relation b c)
d2 :: Map b (Relation a c)
d3 :: Map c (Relation a b)
..} =
  Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
forall a b c.
Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
Relation3
    ((Maybe (Relation b c) -> Maybe (Relation b c))
-> a -> Map a (Relation b c) -> Map a (Relation b c)
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter (b -> c -> Maybe (Relation b c) -> Maybe (Relation b c)
forall {a} {b}.
(Ord a, Ord b) =>
a -> b -> Maybe (Relation a b) -> Maybe (Relation a b)
del b
b c
c) a
a Map a (Relation b c)
d1)
    ((Maybe (Relation a c) -> Maybe (Relation a c))
-> b -> Map b (Relation a c) -> Map b (Relation a c)
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter (a -> c -> Maybe (Relation a c) -> Maybe (Relation a c)
forall {a} {b}.
(Ord a, Ord b) =>
a -> b -> Maybe (Relation a b) -> Maybe (Relation a b)
del a
a c
c) b
b Map b (Relation a c)
d2)
    ((Maybe (Relation a b) -> Maybe (Relation a b))
-> c -> Map c (Relation a b) -> Map c (Relation a b)
forall k a.
Ord k =>
(Maybe a -> Maybe a) -> k -> Map k a -> Map k a
Map.alter (a -> b -> Maybe (Relation a b) -> Maybe (Relation a b)
forall {a} {b}.
(Ord a, Ord b) =>
a -> b -> Maybe (Relation a b) -> Maybe (Relation a b)
del a
a b
b) c
c Map c (Relation a b)
d3)
  where
    del :: p -> p -> Maybe (Relation p p) -> Maybe (Relation p p)
del p
_ p
_ Maybe (Relation p p)
Nothing = Maybe (Relation p p)
forall a. Maybe a
Nothing
    del p
x p
y (Just Relation p p
r) =
      let r' :: Relation p p
r' = p -> p -> Relation p p -> Relation p p
forall a b.
(Ord a, Ord b) =>
a -> b -> Relation a b -> Relation a b
R.delete p
x p
y Relation p p
r
       in if Relation p p
r' Relation p p -> Relation p p -> Bool
forall a. Eq a => a -> a -> Bool
== Relation p p
forall a. Monoid a => a
mempty then Maybe (Relation p p)
forall a. Maybe a
Nothing else Relation p p -> Maybe (Relation p p)
forall a. a -> Maybe a
Just Relation p p
r'

instance (Ord a, Ord b, Ord c) => Semigroup (Relation3 a b c) where
  Relation3 a b c
s1 <> :: Relation3 a b c -> Relation3 a b c -> Relation3 a b c
<> Relation3 a b c
s2 = Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
forall a b c.
Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
Relation3 Map a (Relation b c)
d1' Map b (Relation a c)
d2' Map c (Relation a b)
d3'
    where
      d1' :: Map a (Relation b c)
d1' = (Relation b c -> Relation b c -> Relation b c)
-> Map a (Relation b c)
-> Map a (Relation b c)
-> Map a (Relation b c)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith Relation b c -> Relation b c -> Relation b c
forall a. Semigroup a => a -> a -> a
(<>) (Relation3 a b c -> Map a (Relation b c)
forall a b c. Relation3 a b c -> Map a (Relation b c)
d1 Relation3 a b c
s1) (Relation3 a b c -> Map a (Relation b c)
forall a b c. Relation3 a b c -> Map a (Relation b c)
d1 Relation3 a b c
s2)
      d2' :: Map b (Relation a c)
d2' = (Relation a c -> Relation a c -> Relation a c)
-> Map b (Relation a c)
-> Map b (Relation a c)
-> Map b (Relation a c)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith Relation a c -> Relation a c -> Relation a c
forall a. Semigroup a => a -> a -> a
(<>) (Relation3 a b c -> Map b (Relation a c)
forall a b c. Relation3 a b c -> Map b (Relation a c)
d2 Relation3 a b c
s1) (Relation3 a b c -> Map b (Relation a c)
forall a b c. Relation3 a b c -> Map b (Relation a c)
d2 Relation3 a b c
s2)
      d3' :: Map c (Relation a b)
d3' = (Relation a b -> Relation a b -> Relation a b)
-> Map c (Relation a b)
-> Map c (Relation a b)
-> Map c (Relation a b)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith Relation a b -> Relation a b -> Relation a b
forall a. Semigroup a => a -> a -> a
(<>) (Relation3 a b c -> Map c (Relation a b)
forall a b c. Relation3 a b c -> Map c (Relation a b)
d3 Relation3 a b c
s1) (Relation3 a b c -> Map c (Relation a b)
forall a b c. Relation3 a b c -> Map c (Relation a b)
d3 Relation3 a b c
s2)

instance (Ord a, Ord b, Ord c) => Monoid (Relation3 a b c) where
  mempty :: Relation3 a b c
mempty = Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
forall a b c.
Map a (Relation b c)
-> Map b (Relation a c) -> Map c (Relation a b) -> Relation3 a b c
Relation3 Map a (Relation b c)
forall a. Monoid a => a
mempty Map b (Relation a c)
forall a. Monoid a => a
mempty Map c (Relation a b)
forall a. Monoid a => a
mempty