{-# LANGUAGE CPP #-}
{-# LANGUAGE DeriveGeneric #-}
#if __GLASGOW_HASKELL__ >= 708
{-# LANGUAGE TypeFamilies #-}
#endif

{-|
An implementation of bidirectional maps between values of two
key types. A 'Bimap' is essentially a bijection between subsets of
its two argument types.

Each element of the left-hand type is associated with an element
of the right-hand type, and vice-versa, such that the two mappings
are inverses. Deleting an element will cause its twin to be deleted,
and inserting a pair of elements will cause any overlapping bindings
to be deleted.

Most functions implicitly consider the left-hand type to be the
key, and the right-hand type to be the value.
Functions with an @R@ suffix reverse this convention, treating the
right-hand type as the key and the left-hand type as the value.
-}
module Data.Bimap (
    -- * Bimap type
    Bimap(),
    -- * Query
    null,
    size,
    member,
    memberR,
    notMember,
    notMemberR,
    pairMember,
    pairNotMember,
    lookup,
    lookupR,
    (!),
    (!>),
    -- * Construction
    empty,
    singleton,
    -- * Update
    insert,
    tryInsert,
    adjust,
    adjustR,
    adjustWithKey,
    adjustWithKeyR,
    update,
    updateR,
    updateWithKey,
    updateWithKeyR,
    delete,
    deleteR,
    -- * Min\/Max
    findMin,
    findMinR,
    findMax,
    findMaxR,
    deleteMin,
    deleteMinR,
    deleteMax,
    deleteMaxR,
    deleteFindMin,
    deleteFindMinR,
    deleteFindMax,
    deleteFindMaxR,
    -- * Filter
    filter,
    partition,
    -- * Conversion\/traversal
    fromList,
    fromAList,
    fromAscPairList,
    fromAscPairListUnchecked,
    toList,
    toAscList,
    toAscListR,
    keys,
    keysR,
    elems,
    assocs,
    fold,
    Data.Bimap.map,
    mapR,
    mapMonotonic,
    mapMonotonicR,
    toMap,
    toMapR,
    -- * Miscellaneous
    valid,
    twist,
    twisted,
) where

import           Control.DeepSeq     (NFData)
import           Control.Monad.Catch

import           Data.Function       (on)
import           Data.List           (foldl', sort)
import qualified Data.Map            as M
import           Data.Maybe          (fromMaybe)
import           Data.Typeable

#if __GLASGOW_HASKELL__ >= 708
import qualified GHC.Exts            as GHCExts
#endif
import           GHC.Generics        (Generic)

import           Prelude             hiding (filter, lookup, null, pred)
import qualified Prelude             as P


infixr 9 .:
(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
.: :: (c -> d) -> (a -> b -> c) -> a -> b -> d
(.:) = ((b -> c) -> b -> d) -> (a -> b -> c) -> a -> b -> d
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.)(((b -> c) -> b -> d) -> (a -> b -> c) -> a -> b -> d)
-> ((c -> d) -> (b -> c) -> b -> d)
-> (c -> d)
-> (a -> b -> c)
-> a
-> b
-> d
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(c -> d) -> (b -> c) -> b -> d
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.)

{-|
A bidirectional map between values of types @a@ and @b@.
-}
data Bimap a b = MkBimap !(M.Map a b) !(M.Map b a) deriving ((forall x. Bimap a b -> Rep (Bimap a b) x)
-> (forall x. Rep (Bimap a b) x -> Bimap a b)
-> Generic (Bimap a b)
forall x. Rep (Bimap a b) x -> Bimap a b
forall x. Bimap a b -> Rep (Bimap a b) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a b x. Rep (Bimap a b) x -> Bimap a b
forall a b x. Bimap a b -> Rep (Bimap a b) x
$cto :: forall a b x. Rep (Bimap a b) x -> Bimap a b
$cfrom :: forall a b x. Bimap a b -> Rep (Bimap a b) x
Generic)

instance (Show a, Show b) => Show (Bimap a b) where
    show :: Bimap a b -> String
show Bimap a b
x = String
"fromList " String -> ShowS
forall a. [a] -> [a] -> [a]
++ ([(a, b)] -> String
forall a. Show a => a -> String
show ([(a, b)] -> String)
-> (Bimap a b -> [(a, b)]) -> Bimap a b -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> [(a, b)]
forall a b. Bimap a b -> [(a, b)]
toList (Bimap a b -> String) -> Bimap a b -> String
forall a b. (a -> b) -> a -> b
$ Bimap a b
x)

instance (Eq a, Eq b) => Eq (Bimap a b) where
    == :: Bimap a b -> Bimap a b -> Bool
(==) = [(a, b)] -> [(a, b)] -> Bool
forall a. Eq a => a -> a -> Bool
(==) ([(a, b)] -> [(a, b)] -> Bool)
-> (Bimap a b -> [(a, b)]) -> Bimap a b -> Bimap a b -> Bool
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Bimap a b -> [(a, b)]
forall a b. Bimap a b -> [(a, b)]
toAscList

instance (Ord a, Ord b) => Ord (Bimap a b) where
    compare :: Bimap a b -> Bimap a b -> Ordering
compare = [(a, b)] -> [(a, b)] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare ([(a, b)] -> [(a, b)] -> Ordering)
-> (Bimap a b -> [(a, b)]) -> Bimap a b -> Bimap a b -> Ordering
forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
`on` Bimap a b -> [(a, b)]
forall a b. Bimap a b -> [(a, b)]
toAscList

instance (NFData a, NFData b) => NFData (Bimap a b)

#if __GLASGOW_HASKELL__ >= 708
instance (Ord a, Ord b) => GHCExts.IsList (Bimap a b) where
    type Item (Bimap a b) = (a, b)
    fromList :: [Item (Bimap a b)] -> Bimap a b
fromList = [Item (Bimap a b)] -> Bimap a b
forall a b. (Ord a, Ord b) => [(a, b)] -> Bimap a b
fromList
    toList :: Bimap a b -> [Item (Bimap a b)]
toList = Bimap a b -> [Item (Bimap a b)]
forall a b. Bimap a b -> [(a, b)]
toList
#endif

{-|
A 'Bimap' action failed.
-}
data BimapException = KeyNotFound String
  deriving(BimapException -> BimapException -> Bool
(BimapException -> BimapException -> Bool)
-> (BimapException -> BimapException -> Bool) -> Eq BimapException
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: BimapException -> BimapException -> Bool
$c/= :: BimapException -> BimapException -> Bool
== :: BimapException -> BimapException -> Bool
$c== :: BimapException -> BimapException -> Bool
Eq, Int -> BimapException -> ShowS
[BimapException] -> ShowS
BimapException -> String
(Int -> BimapException -> ShowS)
-> (BimapException -> String)
-> ([BimapException] -> ShowS)
-> Show BimapException
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [BimapException] -> ShowS
$cshowList :: [BimapException] -> ShowS
show :: BimapException -> String
$cshow :: BimapException -> String
showsPrec :: Int -> BimapException -> ShowS
$cshowsPrec :: Int -> BimapException -> ShowS
Show, Typeable)

instance Exception BimapException

{-| /O(1)/. The empty bimap.
/Version: 0.2/-}
empty :: Bimap a b
empty :: Bimap a b
empty = Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap Map a b
forall k a. Map k a
M.empty Map b a
forall k a. Map k a
M.empty

{-| /O(1)/. A bimap with a single element.
/Version: 0.2/-}
singleton :: a -> b -> Bimap a b
singleton :: a -> b -> Bimap a b
singleton a
x b
y = Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap (a -> b -> Map a b
forall k a. k -> a -> Map k a
M.singleton a
x b
y) (b -> a -> Map b a
forall k a. k -> a -> Map k a
M.singleton b
y a
x)

{-| /O(1)/. Is the bimap empty?
/Version: 0.2/-}
null :: Bimap a b -> Bool
null :: Bimap a b -> Bool
null (MkBimap Map a b
left Map b a
_) = Map a b -> Bool
forall k a. Map k a -> Bool
M.null Map a b
left

{-| /O(1)/. The number of elements in the bimap.
/Version: 0.2/-}
size :: Bimap a b -> Int
size :: Bimap a b -> Int
size (MkBimap Map a b
left Map b a
_) = Map a b -> Int
forall k a. Map k a -> Int
M.size Map a b
left

{-| /O(log n)/. Is the specified value a member of the bimap?
/Version: 0.2/-}
member :: (Ord a, Ord b) => a -> Bimap a b -> Bool
member :: a -> Bimap a b -> Bool
member a
x (MkBimap Map a b
left Map b a
_) = a -> Map a b -> Bool
forall k a. Ord k => k -> Map k a -> Bool
M.member a
x Map a b
left
{-| /O(log n)/. A version of 'member' specialized to the right key.
/Version: 0.2/-}
memberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool
memberR :: b -> Bimap a b -> Bool
memberR b
y (MkBimap Map a b
_ Map b a
right) = b -> Map b a -> Bool
forall k a. Ord k => k -> Map k a -> Bool
M.member b
y Map b a
right

{-| /O(log n)/. Is the specified value not a member of the bimap?
/Version: 0.2/-}
notMember :: (Ord a, Ord b) => a -> Bimap a b -> Bool
notMember :: a -> Bimap a b -> Bool
notMember = Bool -> Bool
not (Bool -> Bool)
-> (a -> Bimap a b -> Bool) -> a -> Bimap a b -> Bool
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: a -> Bimap a b -> Bool
forall a b. (Ord a, Ord b) => a -> Bimap a b -> Bool
member
{-| /O(log n)/. A version of 'notMember' specialized to the right key.
/Version: 0.2/-}
notMemberR :: (Ord a, Ord b) => b -> Bimap a b -> Bool
notMemberR :: b -> Bimap a b -> Bool
notMemberR = Bool -> Bool
not (Bool -> Bool)
-> (b -> Bimap a b -> Bool) -> b -> Bimap a b -> Bool
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: b -> Bimap a b -> Bool
forall a b. (Ord a, Ord b) => b -> Bimap a b -> Bool
memberR

{-| /O(log n)/.
Are the two values associated /with each other/ in the bimap?

This function is uncurried in its first two arguments, so that it
can be used infix.

/Version: 0.2/-}
pairMember :: (Ord a, Ord b)
           => (a, b) -> Bimap a b -> Bool
pairMember :: (a, b) -> Bimap a b -> Bool
pairMember (a
x, b
y) (MkBimap Map a b
left Map b a
_) =
    Bool -> (b -> Bool) -> Maybe b -> Bool
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Bool
False (b -> b -> Bool
forall a. Eq a => a -> a -> Bool
== b
y) (a -> Map a b -> Maybe b
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup a
x Map a b
left)

{-| /O(log n)/.
Are the two values not in the bimap, or not associated
with each other? (Complement of 'pairMember'.)
/Version: 0.2/-}
pairNotMember :: (Ord a, Ord b)
              => (a, b) -> Bimap a b -> Bool
pairNotMember :: (a, b) -> Bimap a b -> Bool
pairNotMember = Bool -> Bool
not (Bool -> Bool)
-> ((a, b) -> Bimap a b -> Bool) -> (a, b) -> Bimap a b -> Bool
forall c d a b. (c -> d) -> (a -> b -> c) -> a -> b -> d
.: (a, b) -> Bimap a b -> Bool
forall a b. (Ord a, Ord b) => (a, b) -> Bimap a b -> Bool
pairMember

{-| /O(log n)/.
Insert a pair of values into the bimap, associating them.

If either of the values is already in the bimap, any overlapping
bindings are deleted.

/Version: 0.2/-}
insert :: (Ord a, Ord b)
       => a -> b -> Bimap a b -> Bimap a b
insert :: a -> b -> Bimap a b -> Bimap a b
insert a
x b
y = a -> Bimap a b -> Bimap a b
forall a b. (Ord a, Ord b) => a -> Bimap a b -> Bimap a b
delete a
x (Bimap a b -> Bimap a b)
-> (Bimap a b -> Bimap a b) -> Bimap a b -> Bimap a b
forall a b c. (a -> b) -> (b -> c) -> a -> c
>>> b -> Bimap a b -> Bimap a b
forall a b. (Ord a, Ord b) => b -> Bimap a b -> Bimap a b
deleteR b
y (Bimap a b -> Bimap a b)
-> (Bimap a b -> Bimap a b) -> Bimap a b -> Bimap a b
forall a b c. (a -> b) -> (b -> c) -> a -> c
>>> a -> b -> Bimap a b -> Bimap a b
forall a b. (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b
unsafeInsert a
x b
y
    where
    >>> :: (a -> b) -> (b -> c) -> a -> c
(>>>) = ((b -> c) -> (a -> b) -> a -> c) -> (a -> b) -> (b -> c) -> a -> c
forall a b c. (a -> b -> c) -> b -> a -> c
flip (b -> c) -> (a -> b) -> a -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.)

{-| /O(log n)/.
Insert a pair of values into the bimap, but only if neither is
already in the bimap.
/Version: 0.2.2/-}
tryInsert :: (Ord a, Ord b)
          => a -> b -> Bimap a b -> Bimap a b
tryInsert :: a -> b -> Bimap a b -> Bimap a b
tryInsert a
x b
y Bimap a b
bi
    | a
x a -> Bimap a b -> Bool
forall a b. (Ord a, Ord b) => a -> Bimap a b -> Bool
`notMember` Bimap a b
bi Bool -> Bool -> Bool
&& b
y b -> Bimap a b -> Bool
forall a b. (Ord a, Ord b) => b -> Bimap a b -> Bool
`notMemberR` Bimap a b
bi = a -> b -> Bimap a b -> Bimap a b
forall a b. (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b
unsafeInsert a
x b
y Bimap a b
bi
    | Bool
otherwise                               = Bimap a b
bi

{-| /O(log n)/.
Insert a pair of values into the bimap, without checking for
overlapping bindings.

If either value is already in the bimap, and
is not bound to the other value, the bimap will become inconsistent.
-}
unsafeInsert :: (Ord a, Ord b)
             => a -> b -> Bimap a b -> Bimap a b
unsafeInsert :: a -> b -> Bimap a b -> Bimap a b
unsafeInsert a
x b
y (MkBimap Map a b
left Map b a
right) =
    Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap (a -> b -> Map a b -> Map a b
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert a
x b
y Map a b
left) (b -> a -> Map b a -> Map b a
forall k a. Ord k => k -> a -> Map k a -> Map k a
M.insert b
y a
x Map b a
right)

{-| /O(log n)/. Common implementation for 'delete' and 'deleteR'. -}
deleteE :: (Ord a, Ord b)
       => Either a b -> Bimap a b -> Bimap a b
deleteE :: Either a b -> Bimap a b -> Bimap a b
deleteE Either a b
e (MkBimap Map a b
left Map b a
right) =
    Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap
        ((a -> Map a b -> Map a b) -> Maybe a -> Map a b -> Map a b
forall a a. (a -> a -> a) -> Maybe a -> a -> a
perhaps a -> Map a b -> Map a b
forall k a. Ord k => k -> Map k a -> Map k a
M.delete Maybe a
x  Map a b
left)
        ((b -> Map b a -> Map b a) -> Maybe b -> Map b a -> Map b a
forall a a. (a -> a -> a) -> Maybe a -> a -> a
perhaps b -> Map b a -> Map b a
forall k a. Ord k => k -> Map k a -> Map k a
M.delete Maybe b
y  Map b a
right)
    where
    perhaps :: (a -> a -> a) -> Maybe a -> a -> a
perhaps = (a -> a) -> (a -> a -> a) -> Maybe a -> a -> a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe a -> a
forall a. a -> a
id
    x :: Maybe a
x = (a -> Maybe a) -> (b -> Maybe a) -> Either a b -> Maybe a
forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either a -> Maybe a
forall a. a -> Maybe a
Just (b -> Map b a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
`M.lookup` Map b a
right) Either a b
e
    y :: Maybe b
y = (a -> Maybe b) -> (b -> Maybe b) -> Either a b -> Maybe b
forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either (a -> Map a b -> Maybe b
forall k a. Ord k => k -> Map k a -> Maybe a
`M.lookup` Map a b
left) b -> Maybe b
forall a. a -> Maybe a
Just  Either a b
e

{-| /O(log n)/.
Delete a value and its twin from a bimap.

When the value is not a member of the bimap, the original bimap is
returned.

/Version: 0.2/-}
delete :: (Ord a, Ord b) => a -> Bimap a b -> Bimap a b
delete :: a -> Bimap a b -> Bimap a b
delete = Either a b -> Bimap a b -> Bimap a b
forall a b. (Ord a, Ord b) => Either a b -> Bimap a b -> Bimap a b
deleteE (Either a b -> Bimap a b -> Bimap a b)
-> (a -> Either a b) -> a -> Bimap a b -> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Either a b
forall a b. a -> Either a b
Left

{-| /O(log n)/ A version of 'delete' specialized to the right key.
/Version: 0.2/-}
deleteR :: (Ord a, Ord b) => b -> Bimap a b -> Bimap a b
deleteR :: b -> Bimap a b -> Bimap a b
deleteR = Either a b -> Bimap a b -> Bimap a b
forall a b. (Ord a, Ord b) => Either a b -> Bimap a b -> Bimap a b
deleteE (Either a b -> Bimap a b -> Bimap a b)
-> (b -> Either a b) -> b -> Bimap a b -> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> Either a b
forall a b. b -> Either a b
Right

{-| /O(log n)/.
Update a value at a specific left key with the result of the provided function.

When the left key is not a member of the bimap, the original bimap is returned.-}
adjust :: (Ord a, Ord b) => (b -> b) -> a -> Bimap a b -> Bimap a b
adjust :: (b -> b) -> a -> Bimap a b -> Bimap a b
adjust b -> b
f = (a -> b -> b) -> a -> Bimap a b -> Bimap a b
forall a b.
(Ord a, Ord b) =>
(a -> b -> b) -> a -> Bimap a b -> Bimap a b
adjustWithKey ((b -> b) -> a -> b -> b
forall a b. a -> b -> a
const b -> b
f)

{-| /O(log n)/.
Update a value at a specific right key with the result of the provided function.

When the right key is not a member of the bimap, the original bimap is returned.-}
adjustR :: (Ord a, Ord b) => (a -> a) -> b -> Bimap a b -> Bimap a b
adjustR :: (a -> a) -> b -> Bimap a b -> Bimap a b
adjustR a -> a
f b
b = Bimap b a -> Bimap a b
forall b a. Bimap b a -> Bimap a b
reverseBimap (Bimap b a -> Bimap a b)
-> (Bimap a b -> Bimap b a) -> Bimap a b -> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> a) -> b -> Bimap b a -> Bimap b a
forall a b.
(Ord a, Ord b) =>
(b -> b) -> a -> Bimap a b -> Bimap a b
adjust a -> a
f b
b (Bimap b a -> Bimap b a)
-> (Bimap a b -> Bimap b a) -> Bimap a b -> Bimap b a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Bimap b a
forall b a. Bimap b a -> Bimap a b
reverseBimap
  where reverseBimap :: Bimap b a -> Bimap a b
reverseBimap (MkBimap Map b a
left Map a b
right) = Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap Map a b
right Map b a
left

{-| /O(log n)/.
Adjust a value at a specific left key.

When the left key is not a member of the bimap, the original bimap is returned.-}
adjustWithKey :: (Ord a, Ord b) => (a -> b -> b) -> a -> Bimap a b -> Bimap a b
adjustWithKey :: (a -> b -> b) -> a -> Bimap a b -> Bimap a b
adjustWithKey a -> b -> b
f = (a -> b -> Maybe b) -> a -> Bimap a b -> Bimap a b
forall a b.
(Ord a, Ord b) =>
(a -> b -> Maybe b) -> a -> Bimap a b -> Bimap a b
updateWithKey (\a
a -> b -> Maybe b
forall a. a -> Maybe a
Just (b -> Maybe b) -> (b -> b) -> b -> Maybe b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> b -> b
f a
a)

{-| /O(log n)/.
Adjust a value at a specific right key.

When the right key is not a member of the bimap, the original bimap is returned.-}
adjustWithKeyR :: (Ord a, Ord b) => (b -> a -> a) -> b -> Bimap a b -> Bimap a b
adjustWithKeyR :: (b -> a -> a) -> b -> Bimap a b -> Bimap a b
adjustWithKeyR b -> a -> a
f b
b = Bimap b a -> Bimap a b
forall b a. Bimap b a -> Bimap a b
reverseBimap (Bimap b a -> Bimap a b)
-> (Bimap a b -> Bimap b a) -> Bimap a b -> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> a -> a) -> b -> Bimap b a -> Bimap b a
forall a b.
(Ord a, Ord b) =>
(a -> b -> b) -> a -> Bimap a b -> Bimap a b
adjustWithKey b -> a -> a
f b
b (Bimap b a -> Bimap b a)
-> (Bimap a b -> Bimap b a) -> Bimap a b -> Bimap b a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Bimap b a
forall b a. Bimap b a -> Bimap a b
reverseBimap
  where reverseBimap :: Bimap b a -> Bimap a b
reverseBimap (MkBimap Map b a
left Map a b
right) = Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap Map a b
right Map b a
left

{-| /O(log n)/.
The expression (@'update' f a bimap@) updates the right value @b@ at @a@ (if it is in the bimap).

If (@f b@) is 'Nothing', the element is deleted.

If it is (@'Just' y@), the left key @a@ is bound to the new value @y@.-}
update :: (Ord a, Ord b) => (b -> Maybe b) -> a -> Bimap a b -> Bimap a b
update :: (b -> Maybe b) -> a -> Bimap a b -> Bimap a b
update b -> Maybe b
f = (a -> b -> Maybe b) -> a -> Bimap a b -> Bimap a b
forall a b.
(Ord a, Ord b) =>
(a -> b -> Maybe b) -> a -> Bimap a b -> Bimap a b
updateWithKey ((b -> Maybe b) -> a -> b -> Maybe b
forall a b. a -> b -> a
const b -> Maybe b
f)

{-| /O(log n)/.
The expression (@'updateR' f b bimap@) updates the left value @a@ at @b@ (if it is in the bimap).

If (@f a@) is 'Nothing', the element is deleted.

If it is (@'Just' x@), the right key @b@ is bound to the new value @x@.-}
updateR :: (Ord a, Ord b) => (a -> Maybe a) -> b -> Bimap a b -> Bimap a b
updateR :: (a -> Maybe a) -> b -> Bimap a b -> Bimap a b
updateR a -> Maybe a
f b
b = Bimap b a -> Bimap a b
forall b a. Bimap b a -> Bimap a b
reverseBimap (Bimap b a -> Bimap a b)
-> (Bimap a b -> Bimap b a) -> Bimap a b -> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Maybe a) -> b -> Bimap b a -> Bimap b a
forall a b.
(Ord a, Ord b) =>
(b -> Maybe b) -> a -> Bimap a b -> Bimap a b
update a -> Maybe a
f b
b (Bimap b a -> Bimap b a)
-> (Bimap a b -> Bimap b a) -> Bimap a b -> Bimap b a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Bimap b a
forall b a. Bimap b a -> Bimap a b
reverseBimap
  where reverseBimap :: Bimap b a -> Bimap a b
reverseBimap (MkBimap Map b a
left Map a b
right) = Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap Map a b
right Map b a
left

{-| /O(log n)/.
The expression (@'updateWithKey' f a bimap@) updates the right value @b@ at @a@ (if it is in the bimap).

If (@f a b@) is 'Nothing', the element is deleted.

If it is (@'Just' y@), the left key @a@ is bound to the new value @y@.-}
updateWithKey :: (Ord a, Ord b) => (a -> b -> Maybe b) -> a -> Bimap a b -> Bimap a b
updateWithKey :: (a -> b -> Maybe b) -> a -> Bimap a b -> Bimap a b
updateWithKey a -> b -> Maybe b
f a
a (MkBimap Map a b
left Map b a
right) = Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap Map a b
left' Map b a
right' where
  oldB :: Maybe b
oldB = a -> Map a b -> Maybe b
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup a
a Map a b
left
  newB :: Maybe b
newB = a -> b -> Maybe b
f a
a (b -> Maybe b) -> Maybe b -> Maybe b
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Maybe b
oldB
  oldA :: Maybe a
oldA = Maybe b
newB Maybe b -> (b -> Maybe a) -> Maybe a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (b -> Map b a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
`M.lookup` Map b a
right) Maybe a -> (a -> Maybe a) -> Maybe a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \a
x -> if a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
a then Maybe a
forall a. Maybe a
Nothing else a -> Maybe a
forall a. a -> Maybe a
Just a
x
  left' :: Map a b
left' = (Map a b -> Map a b)
-> (a -> Map a b -> Map a b) -> Maybe a -> Map a b -> Map a b
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map a b -> Map a b
forall a. a -> a
id a -> Map a b -> Map a b
forall k a. Ord k => k -> Map k a -> Map k a
M.delete Maybe a
oldA (Map a b -> Map a b) -> Map a b -> Map a b
forall a b. (a -> b) -> a -> b
$ (a -> b -> Maybe b) -> a -> Map a b -> Map a b
forall k a. Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
M.updateWithKey a -> b -> Maybe b
f a
a Map a b
left
  right' :: Map b a
right' = (Map b a -> Map b a)
-> (b -> Map b a -> Map b a) -> Maybe b -> Map b a -> Map b a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map b a -> Map b a
forall a. a -> a
id (b -> a -> Map b a -> Map b a
forall k a. Ord k => k -> a -> Map k a -> Map k a
`M.insert` a
a) Maybe b
newB (Map b a -> Map b a) -> Map b a -> Map b a
forall a b. (a -> b) -> a -> b
$ (Map b a -> Map b a)
-> (b -> Map b a -> Map b a) -> Maybe b -> Map b a -> Map b a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Map b a -> Map b a
forall a. a -> a
id b -> Map b a -> Map b a
forall k a. Ord k => k -> Map k a -> Map k a
M.delete Maybe b
oldB Map b a
right

{-| /O(log n)/.
The expression (@'updateWithKeyR' f b bimap@) updates the left value @a@ at @b@ (if it is in the bimap).

If (@f b a@) is 'Nothing', the element is deleted.

If it is (@'Just' x@), the right key @b@ is bound to the new value @x@.-}
updateWithKeyR :: (Ord a, Ord b) => (b -> a -> Maybe a) -> b -> Bimap a b -> Bimap a b
updateWithKeyR :: (b -> a -> Maybe a) -> b -> Bimap a b -> Bimap a b
updateWithKeyR b -> a -> Maybe a
f b
b = Bimap b a -> Bimap a b
forall b a. Bimap b a -> Bimap a b
reverseBimap (Bimap b a -> Bimap a b)
-> (Bimap a b -> Bimap b a) -> Bimap a b -> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> a -> Maybe a) -> b -> Bimap b a -> Bimap b a
forall a b.
(Ord a, Ord b) =>
(a -> b -> Maybe b) -> a -> Bimap a b -> Bimap a b
updateWithKey b -> a -> Maybe a
f b
b (Bimap b a -> Bimap b a)
-> (Bimap a b -> Bimap b a) -> Bimap a b -> Bimap b a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Bimap b a
forall b a. Bimap b a -> Bimap a b
reverseBimap
  where reverseBimap :: Bimap b a -> Bimap a b
reverseBimap (MkBimap Map b a
left Map a b
right) = Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap Map a b
right Map b a
left


{-| /O(log n)/.
Lookup a left key in the bimap, returning the associated right key.

This function will @return@ the result in the monad, or @fail@ if
the value isn't in the bimap.

/Version: 0.2/-}
lookup :: (Ord a, Ord b, MonadThrow m)
       => a -> Bimap a b -> m b
lookup :: a -> Bimap a b -> m b
lookup a
x (MkBimap Map a b
left Map b a
_) =
    m b -> (b -> m b) -> Maybe b -> m b
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (BimapException -> m b
forall (m :: * -> *) e a. (MonadThrow m, Exception e) => e -> m a
throwM (BimapException -> m b) -> BimapException -> m b
forall a b. (a -> b) -> a -> b
$ String -> BimapException
KeyNotFound String
"Data.Bimap.lookup")
          b -> m b
forall (m :: * -> *) a. Monad m => a -> m a
return
          (a -> Map a b -> Maybe b
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup a
x Map a b
left)

{-| /O(log n)/.
A version of 'lookup' that is specialized to the right key,
and returns the corresponding left key.
/Version: 0.2/-}
lookupR :: (Ord a, Ord b, MonadThrow m)
        => b -> Bimap a b -> m a
lookupR :: b -> Bimap a b -> m a
lookupR b
y (MkBimap Map a b
_ Map b a
right) =
    m a -> (a -> m a) -> Maybe a -> m a
forall b a. b -> (a -> b) -> Maybe a -> b
maybe (BimapException -> m a
forall (m :: * -> *) e a. (MonadThrow m, Exception e) => e -> m a
throwM (BimapException -> m a) -> BimapException -> m a
forall a b. (a -> b) -> a -> b
$ String -> BimapException
KeyNotFound String
"Data.Bimap.lookupR")
          a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return
          (b -> Map b a -> Maybe a
forall k a. Ord k => k -> Map k a -> Maybe a
M.lookup b
y Map b a
right)

{-| /O(log n)/.
Find the right key corresponding to a given left key.
Calls @'error'@ when the key is not in the bimap.
/Version: 0.2/-}
(!) :: (Ord a, Ord b) => Bimap a b -> a -> b
(!) Bimap a b
bi a
x = b -> Maybe b -> b
forall a. a -> Maybe a -> a
fromMaybe (String -> b
forall a. HasCallStack => String -> a
error String
"Data.Bimap.(!): Left key not found") (Maybe b -> b) -> Maybe b -> b
forall a b. (a -> b) -> a -> b
$ a -> Bimap a b -> Maybe b
forall a b (m :: * -> *).
(Ord a, Ord b, MonadThrow m) =>
a -> Bimap a b -> m b
lookup a
x Bimap a b
bi

{-| /O(log n)/.
A version of @(!)@ that is specialized to the right key,
and returns the corresponding left key.
/Version: 0.2/-}
(!>) :: (Ord a, Ord b) => Bimap a b -> b -> a
!> :: Bimap a b -> b -> a
(!>) Bimap a b
bi b
y = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe (String -> a
forall a. HasCallStack => String -> a
error String
"Data.Bimap.(!>): Right key not found") (Maybe a -> a) -> Maybe a -> a
forall a b. (a -> b) -> a -> b
$ b -> Bimap a b -> Maybe a
forall a b (m :: * -> *).
(Ord a, Ord b, MonadThrow m) =>
b -> Bimap a b -> m a
lookupR b
y Bimap a b
bi

{-| /O(n*log n)/.
Build a map from a list of pairs. If there are any overlapping
pairs in the list, the later ones will override the earlier ones.
/Version: 0.2/-}
fromList :: (Ord a, Ord b)
         => [(a, b)] -> Bimap a b
fromList :: [(a, b)] -> Bimap a b
fromList = (Bimap a b -> (a, b) -> Bimap a b)
-> Bimap a b -> [(a, b)] -> Bimap a b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (((a, b) -> Bimap a b -> Bimap a b)
-> Bimap a b -> (a, b) -> Bimap a b
forall a b c. (a -> b -> c) -> b -> a -> c
flip (((a, b) -> Bimap a b -> Bimap a b)
 -> Bimap a b -> (a, b) -> Bimap a b)
-> ((a -> b -> Bimap a b -> Bimap a b)
    -> (a, b) -> Bimap a b -> Bimap a b)
-> (a -> b -> Bimap a b -> Bimap a b)
-> Bimap a b
-> (a, b)
-> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> Bimap a b -> Bimap a b)
-> (a, b) -> Bimap a b -> Bimap a b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((a -> b -> Bimap a b -> Bimap a b)
 -> Bimap a b -> (a, b) -> Bimap a b)
-> (a -> b -> Bimap a b -> Bimap a b)
-> Bimap a b
-> (a, b)
-> Bimap a b
forall a b. (a -> b) -> a -> b
$ a -> b -> Bimap a b -> Bimap a b
forall a b. (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b
insert) Bimap a b
forall a b. Bimap a b
empty

{-| /O(n*log n)/.
Build a map from a list of pairs. Unlike 'fromList', earlier pairs
will take precedence over later ones.

The name @fromAList@ is a reference to Lisp-style association
lists, where associations can be overridden by prepending new ones.

Note that when duplicates occur in both the keys and in the values,
@fromList xs /= fromAList (reverse xs)@. However, if either
contains no duplicates, then the equality holds.

/Version: 0.2.2/-}
fromAList :: (Ord a, Ord b)
          => [(a, b)] -> Bimap a b
fromAList :: [(a, b)] -> Bimap a b
fromAList = (Bimap a b -> (a, b) -> Bimap a b)
-> Bimap a b -> [(a, b)] -> Bimap a b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (((a, b) -> Bimap a b -> Bimap a b)
-> Bimap a b -> (a, b) -> Bimap a b
forall a b c. (a -> b -> c) -> b -> a -> c
flip (((a, b) -> Bimap a b -> Bimap a b)
 -> Bimap a b -> (a, b) -> Bimap a b)
-> ((a -> b -> Bimap a b -> Bimap a b)
    -> (a, b) -> Bimap a b -> Bimap a b)
-> (a -> b -> Bimap a b -> Bimap a b)
-> Bimap a b
-> (a, b)
-> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> b -> Bimap a b -> Bimap a b)
-> (a, b) -> Bimap a b -> Bimap a b
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((a -> b -> Bimap a b -> Bimap a b)
 -> Bimap a b -> (a, b) -> Bimap a b)
-> (a -> b -> Bimap a b -> Bimap a b)
-> Bimap a b
-> (a, b)
-> Bimap a b
forall a b. (a -> b) -> a -> b
$ a -> b -> Bimap a b -> Bimap a b
forall a b. (Ord a, Ord b) => a -> b -> Bimap a b -> Bimap a b
tryInsert) Bimap a b
forall a b. Bimap a b
empty

{-| /O(n)/. Convert to a list of associated pairs.
/Version: 0.2/-}
toList :: Bimap a b -> [(a, b)]
toList :: Bimap a b -> [(a, b)]
toList = Bimap a b -> [(a, b)]
forall a b. Bimap a b -> [(a, b)]
toAscList

{-| /O(n)/. Build a bimap from a list of pairs, where both the @fst@
and @snd@ halves of the list are in strictly ascending order.

This precondition is checked; an invalid list will cause an error.

/Version: 0.2.3/-}
fromAscPairList :: (Ord a, Ord b)
                => [(a, b)] -> Bimap a b
fromAscPairList :: [(a, b)] -> Bimap a b
fromAscPairList [(a, b)]
xs
    | [(a, b)] -> Bool
forall a b. (Ord a, Ord b) => [(a, b)] -> Bool
isBiAscending [(a, b)]
xs = [(a, b)] -> Bimap a b
forall a b. (Ord a, Ord b) => [(a, b)] -> Bimap a b
fromAscPairListUnchecked [(a, b)]
xs
    | Bool
otherwise        = String -> Bimap a b
forall a. HasCallStack => String -> a
error
        String
"Data.Bimap.fromAscPairList: list not correctly ascending"

isBiAscending :: (Ord a, Ord b)
              => [(a, b)] -> Bool
isBiAscending :: [(a, b)] -> Bool
isBiAscending = ((a, b) -> (a, b) -> Bool) -> [(a, b)] -> Bool
forall c. (c -> c -> Bool) -> [c] -> Bool
allAdjacent (a, b) -> (a, b) -> Bool
forall a a. (Ord a, Ord a) => (a, a) -> (a, a) -> Bool
bothLess
    where
    -- True if the binary relation f is true for all adjacent pairs
    -- in the input list
    allAdjacent :: (c -> c -> Bool) -> [c] -> Bool
    allAdjacent :: (c -> c -> Bool) -> [c] -> Bool
allAdjacent c -> c -> Bool
f [c]
xs = ((c, c) -> Bool) -> [(c, c)] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all ((c -> c -> Bool) -> (c, c) -> Bool
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry c -> c -> Bool
f) ([(c, c)] -> Bool) -> [(c, c)] -> Bool
forall a b. (a -> b) -> a -> b
$ [c] -> [c] -> [(c, c)]
forall a b. [a] -> [b] -> [(a, b)]
zip [c]
xs ([c] -> [c]
forall a. [a] -> [a]
tail [c]
xs)
    -- True if both components of the first pair are strictly less
    -- than their counterparts in the second pair
    bothLess :: (a, a) -> (a, a) -> Bool
bothLess (a
x1, a
y1) (a
x2, a
y2) = (a
x1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
x2) Bool -> Bool -> Bool
&& (a
y1 a -> a -> Bool
forall a. Ord a => a -> a -> Bool
< a
y2)

{-| /O(n)/. Build a bimap from a list of pairs, where both the @fst@
and @snd@ halves of the list are in strictly ascending order.

This precondition is /not/ checked; an invalid list will produce a
malformed bimap.

/Version: 0.2.3/-}
fromAscPairListUnchecked :: (Ord a, Ord b)
                         => [(a, b)] -> Bimap a b
fromAscPairListUnchecked :: [(a, b)] -> Bimap a b
fromAscPairListUnchecked [(a, b)]
xs = Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap
    ([(a, b)] -> Map a b
forall k a. Eq k => [(k, a)] -> Map k a
M.fromAscList [(a, b)]
xs)
    ([(b, a)] -> Map b a
forall k a. Eq k => [(k, a)] -> Map k a
M.fromAscList ([(b, a)] -> Map b a) -> [(b, a)] -> Map b a
forall a b. (a -> b) -> a -> b
$ ((a, b) -> (b, a)) -> [(a, b)] -> [(b, a)]
forall a b. (a -> b) -> [a] -> [b]
P.map (a, b) -> (b, a)
forall b a. (b, a) -> (a, b)
swap  [(a, b)]
xs)
    where
    swap :: (b, a) -> (a, b)
swap (b
x, a
y) = (a
y, b
x)

{-| /O(n)/.
Convert to a list of associated pairs, with the left-hand
values in ascending order.

Since pair ordering is lexical, the pairs will also be in
ascending order.

/Version: 0.2/-}
toAscList :: Bimap a b -> [(a, b)]
toAscList :: Bimap a b -> [(a, b)]
toAscList (MkBimap Map a b
left Map b a
_) = Map a b -> [(a, b)]
forall k a. Map k a -> [(k, a)]
M.toList Map a b
left

{-| /O(n)/.
Convert to a list of associated pairs, with the right-hand
values first in the pair and in ascending order.

Since pair ordering is lexical, the pairs will also be in
ascending order.

/Version: 0.2/-}
toAscListR :: Bimap a b -> [(b, a)]
toAscListR :: Bimap a b -> [(b, a)]
toAscListR = Bimap b a -> [(b, a)]
forall a b. Bimap a b -> [(a, b)]
toAscList (Bimap b a -> [(b, a)])
-> (Bimap a b -> Bimap b a) -> Bimap a b -> [(b, a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Bimap b a
forall b a. Bimap b a -> Bimap a b
twist

{-| /O(n)/.
Return all associated pairs in the bimap, with the left-hand
values in ascending order.
/Version: 0.2/-}
assocs :: Bimap a b -> [(a, b)]
assocs :: Bimap a b -> [(a, b)]
assocs = Bimap a b -> [(a, b)]
forall a b. Bimap a b -> [(a, b)]
toList

{-| /O(n)/.
Return all left-hand keys in the bimap in ascending order.
/Version: 0.2/-}
keys :: Bimap a b -> [a]
keys :: Bimap a b -> [a]
keys (MkBimap Map a b
left Map b a
_) = Map a b -> [a]
forall k a. Map k a -> [k]
M.keys Map a b
left

{-| /O(n)/.
Return all right-hand keys in the bimap in ascending order.
/Version: 0.2/-}
keysR :: Bimap a b -> [b]
keysR :: Bimap a b -> [b]
keysR (MkBimap Map a b
_ Map b a
right) = Map b a -> [b]
forall k a. Map k a -> [k]
M.keys Map b a
right

{-| /O(n)/. An alias for 'keysR'.
/Version: 0.2/-}
elems :: Bimap a b -> [b]
elems :: Bimap a b -> [b]
elems = Bimap a b -> [b]
forall a b. Bimap a b -> [b]
keysR

{-| /O(1)/. Extract only the left-to-right component of a bimap.
/Version: 0.2.1/-}
toMap :: Bimap a b -> M.Map a b
toMap :: Bimap a b -> Map a b
toMap (MkBimap Map a b
left Map b a
_) = Map a b
left

{-| /O(1)/. Extract only the right-to-left component of a bimap.
/Version: 0.2.1/-}
toMapR :: Bimap a b -> M.Map b a
toMapR :: Bimap a b -> Map b a
toMapR (MkBimap Map a b
_ Map b a
right) = Map b a
right

{-| /O(n)/.
Filter all association pairs that satisfy the predicate.

Note that the predicate will be applied /twice/ for each association
in the bimap.

/Version: 0.2.4/-}
filter :: (Ord a, Ord b)
              => (a -> b -> Bool) -> Bimap a b -> Bimap a b
filter :: (a -> b -> Bool) -> Bimap a b -> Bimap a b
filter a -> b -> Bool
pred (MkBimap Map a b
left Map b a
right) =
    Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap
        ((a -> b -> Bool) -> Map a b -> Map a b
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
M.filterWithKey a -> b -> Bool
pred Map a b
left)
        ((b -> a -> Bool) -> Map b a -> Map b a
forall k a. (k -> a -> Bool) -> Map k a -> Map k a
M.filterWithKey ((a -> b -> Bool) -> b -> a -> Bool
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> Bool
pred) Map b a
right)

{-| /O(n)/.
Partition the bimap according to a predicate.
The first bimap contains all associations that satisfy the predicate;
the second contains all associations that fail the predicate.

Note that the predicate will be applied /twice/ for each association
in the bimap.

/Version: 0.2.4/-}
partition :: (Ord a, Ord b)
          => (a -> b -> Bool) -> Bimap a b -> (Bimap a b, Bimap a b)
partition :: (a -> b -> Bool) -> Bimap a b -> (Bimap a b, Bimap a b)
partition a -> b -> Bool
pred (MkBimap Map a b
left Map b a
right) =
    (,) (Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap Map a b
leftA Map b a
rightA) (Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap Map a b
leftB Map b a
rightB)
    where
    (Map a b
leftA, Map a b
leftB) = (a -> b -> Bool) -> Map a b -> (Map a b, Map a b)
forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
M.partitionWithKey a -> b -> Bool
pred Map a b
left
    (Map b a
rightA, Map b a
rightB) = (b -> a -> Bool) -> Map b a -> (Map b a, Map b a)
forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
M.partitionWithKey ((a -> b -> Bool) -> b -> a -> Bool
forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> Bool
pred) Map b a
right


{-| /O(n*log n)/.
Test if the internal bimap structure is valid. This should be true
for any bimap created using the public interface, unless
'fromAscPairListUnchecked' has been used inappropriately.
/Version: 0.2/-}
valid :: (Ord a, Ord b)
      => Bimap a b -> Bool
valid :: Bimap a b -> Bool
valid (MkBimap Map a b
left Map b a
right) = [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and
    [ Map a b -> Bool
forall k a. Ord k => Map k a -> Bool
M.valid Map a b
left, Map b a -> Bool
forall k a. Ord k => Map k a -> Bool
M.valid Map b a
right
    , [(a, b)] -> [(a, b)] -> Bool
forall a. Eq a => a -> a -> Bool
(==)
        ([(a, b)] -> [(a, b)]
forall a. Ord a => [a] -> [a]
sort ([(a, b)] -> [(a, b)])
-> (Map a b -> [(a, b)]) -> Map a b -> [(a, b)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
.                Map a b -> [(a, b)]
forall k a. Map k a -> [(k, a)]
M.toList (Map a b -> [(a, b)]) -> Map a b -> [(a, b)]
forall a b. (a -> b) -> a -> b
$ Map a b
left )
        ([(a, b)] -> [(a, b)]
forall a. Ord a => [a] -> [a]
sort ([(a, b)] -> [(a, b)])
-> (Map b a -> [(a, b)]) -> Map b a -> [(a, b)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((b, a) -> (a, b)) -> [(b, a)] -> [(a, b)]
forall a b. (a -> b) -> [a] -> [b]
P.map (b, a) -> (a, b)
forall b a. (b, a) -> (a, b)
flipPair ([(b, a)] -> [(a, b)])
-> (Map b a -> [(b, a)]) -> Map b a -> [(a, b)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map b a -> [(b, a)]
forall k a. Map k a -> [(k, a)]
M.toList (Map b a -> [(a, b)]) -> Map b a -> [(a, b)]
forall a b. (a -> b) -> a -> b
$ Map b a
right)
    ]
    where
    flipPair :: (b, a) -> (a, b)
flipPair (b
x, a
y) = (a
y, b
x)

{-| /O(1)/.
Reverse the positions of the two element types in the bimap.
/Version: 0.2/-}
twist ::  Bimap a b -> Bimap b a
twist :: Bimap a b -> Bimap b a
twist (MkBimap Map a b
left Map b a
right) = Map b a -> Map a b -> Bimap b a
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap Map b a
right Map a b
left

{-| /O(1)/.
Reverse the positions of the two element types in a bimap
transformation.
/Version: 0.2/-}
twisted :: (Bimap a b -> Bimap a b) -> (Bimap b a -> Bimap b a)
twisted :: (Bimap a b -> Bimap a b) -> Bimap b a -> Bimap b a
twisted Bimap a b -> Bimap a b
f = Bimap a b -> Bimap b a
forall b a. Bimap b a -> Bimap a b
twist (Bimap a b -> Bimap b a)
-> (Bimap b a -> Bimap a b) -> Bimap b a -> Bimap b a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Bimap a b
f (Bimap a b -> Bimap a b)
-> (Bimap b a -> Bimap a b) -> Bimap b a -> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap b a -> Bimap a b
forall b a. Bimap b a -> Bimap a b
twist

{-| /O(n)/.
Fold the association pairs in the map, such that
@'fold' f z == 'foldr' f z . 'assocs'@.
/Version: 0.2/-}
fold :: (a -> b -> c -> c) -> c -> Bimap a b -> c
fold :: (a -> b -> c -> c) -> c -> Bimap a b -> c
fold a -> b -> c -> c
f c
z = ((a, b) -> c -> c) -> c -> [(a, b)] -> c
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((a -> b -> c -> c) -> (a, b) -> c -> c
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry a -> b -> c -> c
f) c
z ([(a, b)] -> c) -> (Bimap a b -> [(a, b)]) -> Bimap a b -> c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> [(a, b)]
forall a b. Bimap a b -> [(a, b)]
assocs

{-| /O(n*log n)/
Map a function over all the left keys in the map.
/Version 0.3/-}
map :: Ord c => (a -> c) -> Bimap a b -> Bimap c b
map :: (a -> c) -> Bimap a b -> Bimap c b
map a -> c
f (MkBimap Map a b
left Map b a
right) =
    Map c b -> Map b c -> Bimap c b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap ((a -> c) -> Map a b -> Map c b
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys a -> c
f Map a b
left) ((a -> c) -> Map b a -> Map b c
forall a b k. (a -> b) -> Map k a -> Map k b
M.map a -> c
f Map b a
right)

{-| /O(n*log n)/
Map a function over all the right keys in the map.
/Version 0.3/-}
mapR :: Ord c => (b -> c) -> Bimap a b -> Bimap a c
mapR :: (b -> c) -> Bimap a b -> Bimap a c
mapR b -> c
f (MkBimap Map a b
left Map b a
right) =
    Map a c -> Map c a -> Bimap a c
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap ((b -> c) -> Map a b -> Map a c
forall a b k. (a -> b) -> Map k a -> Map k b
M.map b -> c
f Map a b
left) ((b -> c) -> Map b a -> Map c a
forall k2 k1 a. Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeys b -> c
f Map b a
right)

{-| /O(n)/.
Map a strictly increasing function over all left keys in the map.
/The precondition is not checked./
/Version 0.3/-}
mapMonotonic :: (a -> c) -> Bimap a b -> Bimap c b
mapMonotonic :: (a -> c) -> Bimap a b -> Bimap c b
mapMonotonic a -> c
f (MkBimap Map a b
left Map b a
right) =
    Map c b -> Map b c -> Bimap c b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap ((a -> c) -> Map a b -> Map c b
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeysMonotonic a -> c
f Map a b
left) ((a -> c) -> Map b a -> Map b c
forall a b k. (a -> b) -> Map k a -> Map k b
M.map a -> c
f Map b a
right)

{-| /O(n)/.
Map a strictly increasing function over all right keys in the map.
/The precondition is not checked./
/Version 0.3/-}
mapMonotonicR :: (b -> c) -> Bimap a b -> Bimap a c
mapMonotonicR :: (b -> c) -> Bimap a b -> Bimap a c
mapMonotonicR b -> c
f (MkBimap Map a b
left Map b a
right) =
    Map a c -> Map c a -> Bimap a c
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap ((b -> c) -> Map a b -> Map a c
forall a b k. (a -> b) -> Map k a -> Map k b
M.map b -> c
f Map a b
left) ((b -> c) -> Map b a -> Map c a
forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
M.mapKeysMonotonic b -> c
f Map b a
right)

{-| /O(log n)/.
Delete and find the element with maximal left key.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
deleteFindMax :: (Ord b) => Bimap a b -> ((a, b), Bimap a b)
deleteFindMax :: Bimap a b -> ((a, b), Bimap a b)
deleteFindMax (MkBimap Map a b
left Map b a
right) = ((a
a, b
b), Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap Map a b
left' Map b a
right') where
    ((a
a, b
b), Map a b
left') = Map a b -> ((a, b), Map a b)
forall k a. Map k a -> ((k, a), Map k a)
M.deleteFindMax Map a b
left
    right' :: Map b a
right' = b
b b -> Map b a -> Map b a
forall k a. Ord k => k -> Map k a -> Map k a
`M.delete` Map b a
right

{-| /O(log n)/.
Delete and find the element with maximal right key.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
deleteFindMaxR :: (Ord a) => Bimap a b ->  ((b, a), Bimap a b)
deleteFindMaxR :: Bimap a b -> ((b, a), Bimap a b)
deleteFindMaxR = (Bimap b a -> Bimap a b)
-> ((b, a), Bimap b a) -> ((b, a), Bimap a b)
forall t b a. (t -> b) -> (a, t) -> (a, b)
second Bimap b a -> Bimap a b
forall b a. Bimap b a -> Bimap a b
twist (((b, a), Bimap b a) -> ((b, a), Bimap a b))
-> (Bimap a b -> ((b, a), Bimap b a))
-> Bimap a b
-> ((b, a), Bimap a b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap b a -> ((b, a), Bimap b a)
forall b a. Ord b => Bimap a b -> ((a, b), Bimap a b)
deleteFindMax (Bimap b a -> ((b, a), Bimap b a))
-> (Bimap a b -> Bimap b a) -> Bimap a b -> ((b, a), Bimap b a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Bimap b a
forall b a. Bimap b a -> Bimap a b
twist where
    second :: (t -> b) -> (a, t) -> (a, b)
second t -> b
f (a
x, t
y) = (a
x, t -> b
f t
y)

{-| /O(log n)/.
Delete the element with maximal left key.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
deleteMax :: (Ord b) => Bimap a b -> Bimap a b
deleteMax :: Bimap a b -> Bimap a b
deleteMax = ((a, b), Bimap a b) -> Bimap a b
forall a b. (a, b) -> b
snd (((a, b), Bimap a b) -> Bimap a b)
-> (Bimap a b -> ((a, b), Bimap a b)) -> Bimap a b -> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> ((a, b), Bimap a b)
forall b a. Ord b => Bimap a b -> ((a, b), Bimap a b)
deleteFindMax

{-| /O(log n)/.
Delete the element with maximal right key.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
deleteMaxR :: (Ord a) => Bimap a b -> Bimap a b
deleteMaxR :: Bimap a b -> Bimap a b
deleteMaxR = ((b, a), Bimap a b) -> Bimap a b
forall a b. (a, b) -> b
snd (((b, a), Bimap a b) -> Bimap a b)
-> (Bimap a b -> ((b, a), Bimap a b)) -> Bimap a b -> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> ((b, a), Bimap a b)
forall a b. Ord a => Bimap a b -> ((b, a), Bimap a b)
deleteFindMaxR

{-| /O(log n)/.
Find the element with maximal left key.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
findMax :: Bimap a b -> (a, b)
findMax :: Bimap a b -> (a, b)
findMax = Map a b -> (a, b)
forall k a. Map k a -> (k, a)
M.findMax (Map a b -> (a, b))
-> (Bimap a b -> Map a b) -> Bimap a b -> (a, b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Map a b
forall a b. Bimap a b -> Map a b
toMap

{-| /O(log n)/.
Find the element with maximal right key. The
right-hand key is the first entry in the pair.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
findMaxR :: Bimap a b -> (b, a)
findMaxR :: Bimap a b -> (b, a)
findMaxR = Map b a -> (b, a)
forall k a. Map k a -> (k, a)
M.findMax (Map b a -> (b, a))
-> (Bimap a b -> Map b a) -> Bimap a b -> (b, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Map b a
forall a b. Bimap a b -> Map b a
toMapR

{-| /O(log n)/.
Delete and find the element with minimal left key.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
deleteFindMin :: (Ord b) => Bimap a b -> ((a, b), Bimap a b)
deleteFindMin :: Bimap a b -> ((a, b), Bimap a b)
deleteFindMin (MkBimap Map a b
left Map b a
right) = ((a
a, b
b), Map a b -> Map b a -> Bimap a b
forall a b. Map a b -> Map b a -> Bimap a b
MkBimap Map a b
left' Map b a
right') where
    ((a
a, b
b), Map a b
left') = Map a b -> ((a, b), Map a b)
forall k a. Map k a -> ((k, a), Map k a)
M.deleteFindMin Map a b
left
    right' :: Map b a
right' = b
b b -> Map b a -> Map b a
forall k a. Ord k => k -> Map k a -> Map k a
`M.delete` Map b a
right

{-| /O(log n)/.
Delete and find the element with minimal right key.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
deleteFindMinR :: (Ord a) => Bimap a b ->  ((b, a), Bimap a b)
deleteFindMinR :: Bimap a b -> ((b, a), Bimap a b)
deleteFindMinR = (Bimap b a -> Bimap a b)
-> ((b, a), Bimap b a) -> ((b, a), Bimap a b)
forall t b a. (t -> b) -> (a, t) -> (a, b)
second Bimap b a -> Bimap a b
forall b a. Bimap b a -> Bimap a b
twist (((b, a), Bimap b a) -> ((b, a), Bimap a b))
-> (Bimap a b -> ((b, a), Bimap b a))
-> Bimap a b
-> ((b, a), Bimap a b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap b a -> ((b, a), Bimap b a)
forall b a. Ord b => Bimap a b -> ((a, b), Bimap a b)
deleteFindMin (Bimap b a -> ((b, a), Bimap b a))
-> (Bimap a b -> Bimap b a) -> Bimap a b -> ((b, a), Bimap b a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Bimap b a
forall b a. Bimap b a -> Bimap a b
twist where
    second :: (t -> b) -> (a, t) -> (a, b)
second t -> b
f (a
x, t
y) = (a
x, t -> b
f t
y)

{-| /O(log n)/.
Delete the element with minimal left key.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
deleteMin :: (Ord b) => Bimap a b -> Bimap a b
deleteMin :: Bimap a b -> Bimap a b
deleteMin = ((a, b), Bimap a b) -> Bimap a b
forall a b. (a, b) -> b
snd (((a, b), Bimap a b) -> Bimap a b)
-> (Bimap a b -> ((a, b), Bimap a b)) -> Bimap a b -> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> ((a, b), Bimap a b)
forall b a. Ord b => Bimap a b -> ((a, b), Bimap a b)
deleteFindMin

{-| /O(log n)/.
Delete the element with minimal right key.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
deleteMinR :: (Ord a) => Bimap a b -> Bimap a b
deleteMinR :: Bimap a b -> Bimap a b
deleteMinR = ((b, a), Bimap a b) -> Bimap a b
forall a b. (a, b) -> b
snd (((b, a), Bimap a b) -> Bimap a b)
-> (Bimap a b -> ((b, a), Bimap a b)) -> Bimap a b -> Bimap a b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> ((b, a), Bimap a b)
forall a b. Ord a => Bimap a b -> ((b, a), Bimap a b)
deleteFindMinR

{-| /O(log n)/.
Find the element with minimal left key.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
findMin :: Bimap a b -> (a, b)
findMin :: Bimap a b -> (a, b)
findMin = Map a b -> (a, b)
forall k a. Map k a -> (k, a)
M.findMin (Map a b -> (a, b))
-> (Bimap a b -> Map a b) -> Bimap a b -> (a, b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Map a b
forall a b. Bimap a b -> Map a b
toMap

{-| /O(log n)/.
Find the element with minimal right key. The
right-hand key is the first entry in the pair.
Calls @'error'@ if the bimap is empty.
/Version: 0.2.2/-}
findMinR :: Bimap a b -> (b, a)
findMinR :: Bimap a b -> (b, a)
findMinR = Map b a -> (b, a)
forall k a. Map k a -> (k, a)
M.findMin (Map b a -> (b, a))
-> (Bimap a b -> Map b a) -> Bimap a b -> (b, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Bimap a b -> Map b a
forall a b. Bimap a b -> Map b a
toMapR