    {-# 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 Data.BimapExt       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
    .: :: forall c d a b. (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
    $cfrom :: forall a b x. Bimap a b -> Rep (Bimap a b) x
    from :: forall x. Bimap a b -> Rep (Bimap a b) x
    $cto :: forall a b x. Rep (Bimap a b) x -> Bimap a b
    to :: forall x. Rep (Bimap a b) x -> Bimap a b
    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 = [(a, b)] -> Bimap a b
    [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 -> [(a, b)]
    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
    $c== :: BimapException -> BimapException -> Bool
    == :: BimapException -> BimapException -> Bool
    $c/= :: BimapException -> BimapException -> Bool
    /= :: 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
    $cshowsPrec :: Int -> BimapException -> ShowS
    showsPrec :: Int -> BimapException -> ShowS
    $cshow :: BimapException -> String
    show :: BimapException -> String
    $cshowList :: [BimapException] -> ShowS
    showList :: [BimapException] -> ShowS
    Show, Typeable)

    instance Exception BimapException

    {-| /O(1)/. The empty bimap.
    /Version: 0.2/-}
    empty :: Bimap a b
    empty :: forall a b. 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 :: forall a b. 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 :: forall a b. 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 :: forall a b. 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 :: forall a b. (Ord a, Ord b) => 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 :: forall a b. (Ord a, Ord b) => 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 :: forall a b. (Ord a, Ord b) => 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 :: forall a b. (Ord a, Ord b) => 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 :: forall a b. (Ord a, Ord b) => (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 :: forall a b. (Ord a, Ord b) => (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 :: forall a b. (Ord a, Ord b) => 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 :: forall a b. (Ord a, Ord b) => 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 :: forall a b. (Ord a, Ord b) => 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 :: forall a b. (Ord a, Ord b) => 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 :: forall a b. (Ord a, Ord b) => 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 :: forall a b. (Ord a, Ord b) => 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 :: forall a b.
    (Ord a, Ord b) =>
    (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 :: forall a b.
    (Ord a, Ord b) =>
    (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 :: forall a b.
    (Ord a, Ord b) =>
    (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 :: forall a b.
    (Ord a, Ord b) =>
    (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 :: forall a b.
    (Ord a, Ord b) =>
    (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 :: forall a b.
    (Ord a, Ord b) =>
    (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 :: forall a b.
    (Ord a, Ord b) =>
    (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 a b. Maybe a -> (a -> Maybe b) -> Maybe b
    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 a b. Maybe a -> (a -> Maybe b) -> Maybe b
    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 :: forall a b.
    (Ord a, Ord b) =>
    (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.

    Note that the signature differs slightly from Data.Map's @lookup@. This one is more general -
    it functions the same way as the "original" if @m@ is cast (or inferred) to Maybe.

    /Version: 0.2/-}
    lookup :: (Ord a, Ord b, MonadThrow m)
           => a -> Bimap a b -> m b
    lookup :: forall a b (m :: * -> *).
    (Ord a, Ord b, MonadThrow m) =>
    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 e a. (HasCallStack, Exception e) => e -> m a
    forall (m :: * -> *) e a.
    (MonadThrow m, HasCallStack, 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 a. a -> m a
    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 :: forall a b (m :: * -> *).
    (Ord a, Ord b, MonadThrow m) =>
    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 e a. (HasCallStack, Exception e) => e -> m a
    forall (m :: * -> *) e a.
    (MonadThrow m, HasCallStack, 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 a. 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
    ! :: forall a b. (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
    !> :: forall a b. (Ord a, Ord b) => 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(log n)/.
    See 'lookup'. -}
    (!?) :: (Ord a, Ord b, MonadThrow m) => Bimap a b -> a -> m b
    !? :: forall a b (m :: * -> *).
    (Ord a, Ord b, MonadThrow m) =>
    Bimap a b -> a -> m b
    (!?) = (a -> Bimap a b -> m b) -> Bimap a b -> a -> m b
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip a -> Bimap a b -> m b
    forall a b (m :: * -> *).
    (Ord a, Ord b, MonadThrow m) =>
    a -> Bimap a b -> m b
    lookup

    {-| /O(log n)/.
    See 'lookupR'. -}
    (!?>) :: (Ord a, Ord b, MonadThrow m) => Bimap a b -> b -> m a
    !?> :: forall a b (m :: * -> *).
    (Ord a, Ord b, MonadThrow m) =>
    Bimap a b -> b -> m a
    (!?>) = (b -> Bimap a b -> m a) -> Bimap a b -> b -> m a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip b -> Bimap a b -> m a
    forall a b (m :: * -> *).
    (Ord a, Ord b, MonadThrow m) =>
    b -> Bimap a b -> m a
    lookupR

    {-| /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 :: forall a b. (Ord a, Ord b) => [(a, b)] -> Bimap a b
    fromList = (Bimap a b -> (a, b) -> Bimap a b)
    -> Bimap a b -> [(a, b)] -> Bimap a b
    forall b a. (b -> a -> b) -> b -> [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 :: forall a b. (Ord a, Ord b) => [(a, b)] -> Bimap a b
    fromAList = (Bimap a b -> (a, b) -> Bimap a b)
    -> Bimap a b -> [(a, b)] -> Bimap a b
    forall b a. (b -> a -> b) -> b -> [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 :: forall a b. 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 :: forall a b. (Ord a, Ord b) => [(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 :: forall a b. (Ord a, Ord b) => [(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 :: forall c. (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. HasCallStack => [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 :: forall a b. (Ord a, Ord b) => [(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 :: forall a b. 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 :: forall a b. 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 :: forall a b. 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 :: forall a b. 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 :: forall a b. 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 :: forall a b. 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 :: forall a b. 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 :: forall a b. 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 :: forall a b.
    (Ord a, Ord b) =>
    (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 :: forall a b.
    (Ord a, Ord b) =>
    (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 :: forall a b. (Ord a, Ord b) => 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 :: forall {b} {a}. Bimap b a -> Bimap a b
    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 :: forall a b. (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 :: forall a b c. (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 a b. (a -> b -> b) -> b -> [a] -> b
    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 :: forall c a b. Ord c => (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 :: forall c b a. Ord c => (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 :: forall a c b. (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 :: forall b c a. (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 :: forall b a. Ord b => 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 :: forall a b. Ord a => 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 :: forall b a. Ord b => 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 :: forall a b. Ord a => 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 :: forall a b. 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 :: forall a b. 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 :: forall b a. Ord b => 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 :: forall a b. Ord a => 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 :: forall b a. Ord b => 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 :: forall a b. Ord a => 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 :: forall a b. 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 :: forall a b. 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