cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor{- |

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorModule : $Header$

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorDescription : injective maps

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorCopyright : (c) Uni Bremen 2006

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorLicense : similar to LGPL, see HetCATS/LICENSE.txt or LIZENZ.txt

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorMaintainer : Christian.Maeder@dfki.de

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorStability : provisional

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorPortability : portable

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

d29d9ab4614ff992b0e8de6e2b88d52b6f1f153erbowenInjective maps

d29d9ab4614ff992b0e8de6e2b88d52b6f1f153erbowen-}

d29d9ab4614ff992b0e8de6e2b88d52b6f1f153erbowen

d29d9ab4614ff992b0e8de6e2b88d52b6f1f153erbowenmodule Common.InjMap

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor ( InjMap

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor , unsafeConstructInjMap

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor , getAToB

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor , getBToA

3f08db06526d6901aa08c110b5bc7dde6bc39905nd , empty

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor , member

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor , insert

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor , delete

3f08db06526d6901aa08c110b5bc7dde6bc39905nd , deleteA

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor , deleteB

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor , lookupWithA

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor , lookupWithB

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor , updateBWithA

f086b4b402fa9a2fefc7dda85de2a3cc1cd0a654rjung , updateAWithB

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor ) where

48b62528cd9513fe8b5f1bbcee92ab3b28c94807rbowen

48b62528cd9513fe8b5f1bbcee92ab3b28c94807rbowenimport qualified Data.Map as Map

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor-- | the data type of injective maps

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzordata InjMap a b = InjMap

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor { getAToB :: Map.Map a b -- ^ the actual injective map

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor , getBToA :: Map.Map b a -- ^ the inverse map

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor } deriving (Show, Eq, Ord)

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor-- | for serialization only

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorunsafeConstructInjMap :: Map.Map a b -> Map.Map b a -> InjMap a b

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorunsafeConstructInjMap = InjMap

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor-- * the visible interface

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor-- | get an empty injective map

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorempty :: InjMap a b

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorempty = InjMap Map.empty Map.empty

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor{- | insert a pair into the given injective map. An existing key and the

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorcorresponding content will be overridden. -}

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorinsert :: (Ord a, Ord b) => a -> b -> InjMap a b -> InjMap a b

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorinsert a b i = let InjMap m n = delete a b i in

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor InjMap (Map.insert a b m) (Map.insert b a n)

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor{- | delete the pair with the given key in the injective

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzormap. Possibly two pairs may be deleted if the pair is not a member. -}

e40d2af13fd7ff120eda49cd327c68fbc16443e8sfdelete :: (Ord a, Ord b) => a -> b -> InjMap a b -> InjMap a b

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzordelete a b (InjMap m n) =

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor InjMap (Map.delete (Map.findWithDefault a b n) $ Map.delete a m)

df135dbebadfdf65d0c45e181d6c19b84d17b7c6sf (Map.delete (Map.findWithDefault b a m) $ Map.delete b n)

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor-- | delete domain entry

7e9c796f2dc0dba993a817b3a58cfd56b4e511edwrowedeleteA :: (Ord a, Ord b) => a -> InjMap a b -> InjMap a b

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzordeleteA a i@(InjMap m n) = case Map.lookup a m of

ffb01336be79c64046b636e59fa8ddca8ec029edsf Just b -> case Map.lookup b n of

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor Just e -> if e == a then InjMap (Map.delete a m) $ Map.delete b n

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor else error "InjMap.deleteA1"

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor Nothing -> error "InjMap.deleteA2"

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor Nothing -> i

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor-- | delete codomain entry

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzordeleteB :: (Ord a, Ord b) => b -> InjMap a b -> InjMap a b

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzordeleteB b = transpose . deleteA b . transpose

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor-- | check membership of an injective pair

df135dbebadfdf65d0c45e181d6c19b84d17b7c6sfmember :: (Ord a, Ord b) => a -> b -> InjMap a b -> Bool

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzormember a b (InjMap m n) = case (Map.lookup a m, Map.lookup b n) of

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor (Just x, Just y) | x == b && y == a -> True

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor _ -> False

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor-- | transpose to avoid duplicate code

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzortranspose :: InjMap a b -> InjMap b a

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzortranspose (InjMap m n) = InjMap n m

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor-- | look up the content at domain

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorlookupWithA :: (Ord a, Ord b) => a -> InjMap a b -> Maybe b

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorlookupWithA a (InjMap m n) = case Map.lookup a m of

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor Just b -> case Map.lookup b n of

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor Just e -> if e == a then Just b

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor else error "InjMap.lookupWith1"

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor Nothing -> error "InjMap.lookupWith2"

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor Nothing -> Nothing

48c64aeceef385e19025b384bd719b2a9789592dnd-- the errors indicate that the injectivity is destroyed

48c64aeceef385e19025b384bd719b2a9789592dnd

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzor-- | look up the content at codomain

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorlookupWithB :: (Ord a, Ord b) => b -> InjMap a b -> Maybe a

cc8190433d13f5e9de618c5d7f10c824c0c1919cgryzorlookupWithB y = lookupWithA y . transpose

1462ff536f1b939bb337766b2056109c29664c4erbowen

1462ff536f1b939bb337766b2056109c29664c4erbowen-- | update codomain at domain value that must be defined

1462ff536f1b939bb337766b2056109c29664c4erbowenupdateBWithA:: (Ord a, Ord b) => a -> b -> InjMap a b -> InjMap a b

1462ff536f1b939bb337766b2056109c29664c4erbowenupdateBWithA a b m = case lookupWithA a m of

1462ff536f1b939bb337766b2056109c29664c4erbowen Nothing -> error "InjMap.updateBWithA"

1462ff536f1b939bb337766b2056109c29664c4erbowen _ -> insert a b m

1462ff536f1b939bb337766b2056109c29664c4erbowen

1462ff536f1b939bb337766b2056109c29664c4erbowen-- | update domain at codomain value that must be defined

1462ff536f1b939bb337766b2056109c29664c4erbowenupdateAWithB :: (Ord a, Ord b) => b -> a -> InjMap a b -> InjMap a b

1462ff536f1b939bb337766b2056109c29664c4erbowenupdateAWithB b newA = transpose . updateBWithA b newA . transpose

1462ff536f1b939bb337766b2056109c29664c4erbowen