    {-# OPTIONS_GHC -Wunused-imports #-}

    -- | Partly invertible finite maps.
    --
    -- Time complexities are given under the assumption that all relevant
    -- instance functions, as well as arguments of function type, take
    -- constant time, and "n" is the number of keys involved in the
    -- operation.

    module Agda.Utils.BiMap where

    import Prelude hiding (null, lookup)

    import Control.Monad.Identity
    import Control.Monad.State

    import Data.Function (on)
    import qualified Data.List as List
    import Data.Map (Map)
    import qualified Data.Map as Map
    import Data.Maybe
    import Data.Ord
    import Data.Tuple

    import GHC.Generics (Generic)

    import Agda.Utils.List
    import Agda.Utils.Null

    -- | Partial injections from a type to some tag type.
    --
    -- The idea is that 'tag' should be injective on its domain: if
    -- @'tag' x = 'tag' y = 'Just' i@, then @x = y@. However, this
    -- property does not need to hold globally. The preconditions of the
    -- 'BiMap' operations below specify for which sets of values 'tag'
    -- must be injective.

    class HasTag a where
      type Tag a
      tag :: a -> Maybe (Tag a)

    -- | Checks if the function 'tag' is injective for the values in the
    -- given list for which the function is defined.

    tagInjectiveFor ::
      (Eq v, Eq (Tag v), HasTag v) =>
      [v] -> Bool
    tagInjectiveFor :: forall v. (Eq v, Eq (Tag v), HasTag v) => [v] -> Bool
    tagInjectiveFor [v]
    vs = [Bool] -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    and
      [ v
    v1 v -> v -> Bool
    forall a. Eq a => a -> a -> Bool
    == v
    v2
      | v
    v1 <- [v]
    vs
      , v
    v2 <- [v]
    vs
      , Maybe (Tag v) -> Bool
    forall a. Maybe a -> Bool
    isJust (v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v1)
      , v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v1 Maybe (Tag v) -> Maybe (Tag v) -> Bool
    forall a. Eq a => a -> a -> Bool
    == v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v2
      ]

    -- | Finite maps from @k@ to @v@, with a way to quickly get from @v@
    -- to @k@ for certain values of type @v@ (those for which 'tag' is
    -- defined).
    --
    -- Every value of this type must satisfy 'biMapInvariant'.

    data BiMap k v = BiMap
      { forall k v. BiMap k v -> Map k v
    biMapThere :: !(Map k v)
      , forall k v. BiMap k v -> Map (Tag v) k
    biMapBack  :: !(Map (Tag v) k)
      }
      deriving (forall x. BiMap k v -> Rep (BiMap k v) x)
    -> (forall x. Rep (BiMap k v) x -> BiMap k v)
    -> Generic (BiMap k v)
    forall x. Rep (BiMap k v) x -> BiMap k v
    forall x. BiMap k v -> Rep (BiMap k v) x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    forall k v x. Rep (BiMap k v) x -> BiMap k v
    forall k v x. BiMap k v -> Rep (BiMap k v) x
    $cfrom :: forall k v x. BiMap k v -> Rep (BiMap k v) x
    from :: forall x. BiMap k v -> Rep (BiMap k v) x
    $cto :: forall k v x. Rep (BiMap k v) x -> BiMap k v
    to :: forall x. Rep (BiMap k v) x -> BiMap k v
    Generic

    -- | The invariant for 'BiMap'.

    biMapInvariant ::
      (Eq k, Eq v, Ord (Tag v), HasTag v) =>
      BiMap k v -> Bool
    biMapInvariant :: forall k v.
    (Eq k, Eq v, Ord (Tag v), HasTag v) =>
    BiMap k v -> Bool
    biMapInvariant m :: BiMap k v
    m@(BiMap Map k v
    t Map (Tag v) k
    u) =
      Map (Tag v) k
    u Map (Tag v) k -> Map (Tag v) k -> Bool
    forall a. Eq a => a -> a -> Bool
    ==
      [(Tag v, k)] -> Map (Tag v) k
    forall k a. Ord k => [(k, a)] -> Map k a
    Map.fromList
        [ (Tag v
    k', k
    k)
        | (k
    k, v
    v) <- Map k v -> [(k, v)]
    forall k a. Map k a -> [(k, a)]
    Map.toList Map k v
    t
        , Just Tag v
    k' <- [v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v]
        ]
        Bool -> Bool -> Bool
    &&
      [v] -> Bool
    forall v. (Eq v, Eq (Tag v), HasTag v) => [v] -> Bool
    tagInjectiveFor (((k, v) -> v) -> [(k, v)] -> [v]
    forall a b. (a -> b) -> [a] -> [b]
    map (k, v) -> v
    forall a b. (a, b) -> b
    snd ([(k, v)] -> [v]) -> [(k, v)] -> [v]
    forall a b. (a -> b) -> a -> b
    $ BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList BiMap k v
    m)

    instance Null (BiMap k v) where
      empty :: BiMap k v
    empty = Map k v -> Map (Tag v) k -> BiMap k v
    forall k v. Map k v -> Map (Tag v) k -> BiMap k v
    BiMap Map k v
    forall k a. Map k a
    Map.empty Map (Tag v) k
    forall k a. Map k a
    Map.empty
      null :: BiMap k v -> Bool
    null  = Map k v -> Bool
    forall a. Null a => a -> Bool
    null (Map k v -> Bool) -> (BiMap k v -> Map k v) -> BiMap k v -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . BiMap k v -> Map k v
    forall k v. BiMap k v -> Map k v
    biMapThere

    -- | Is the value a source key? O(log n).

    source :: Ord k => k -> BiMap k v -> Bool
    source :: forall k v. Ord k => k -> BiMap k v -> Bool
    source k
    k = k -> Map k v -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Map.member k
    k (Map k v -> Bool) -> (BiMap k v -> Map k v) -> BiMap k v -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . BiMap k v -> Map k v
    forall k v. BiMap k v -> Map k v
    biMapThere

    -- | Is the value a target key? O(log n).

    target :: Ord (Tag v) => Tag v -> BiMap k v -> Bool
    target :: forall v k. Ord (Tag v) => Tag v -> BiMap k v -> Bool
    target Tag v
    k = Tag v -> Map (Tag v) k -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    Map.member Tag v
    k (Map (Tag v) k -> Bool)
    -> (BiMap k v -> Map (Tag v) k) -> BiMap k v -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . BiMap k v -> Map (Tag v) k
    forall k v. BiMap k v -> Map (Tag v) k
    biMapBack

    -- | Lookup. O(log n).

    lookup :: Ord k => k -> BiMap k v -> Maybe v
    lookup :: forall k v. Ord k => k -> BiMap k v -> Maybe v
    lookup k
    a = k -> Map k v -> Maybe v
    forall k a. Ord k => k -> Map k a -> Maybe a
    Map.lookup k
    a (Map k v -> Maybe v)
    -> (BiMap k v -> Map k v) -> BiMap k v -> Maybe v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . BiMap k v -> Map k v
    forall k v. BiMap k v -> Map k v
    biMapThere

    -- | Inverse lookup. O(log n).

    invLookup :: Ord (Tag v) => Tag v -> BiMap k v -> Maybe k
    invLookup :: forall v k. Ord (Tag v) => Tag v -> BiMap k v -> Maybe k
    invLookup Tag v
    k = Tag v -> Map (Tag v) k -> Maybe k
    forall k a. Ord k => k -> Map k a -> Maybe a
    Map.lookup Tag v
    k (Map (Tag v) k -> Maybe k)
    -> (BiMap k v -> Map (Tag v) k) -> BiMap k v -> Maybe k
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . BiMap k v -> Map (Tag v) k
    forall k v. BiMap k v -> Map (Tag v) k
    biMapBack

    -- | Singleton map. O(1).

    singleton :: HasTag v => k -> v -> BiMap k v
    singleton :: forall v k. HasTag v => k -> v -> BiMap k v
    singleton k
    k v
    v =
      Map k v -> Map (Tag v) k -> BiMap k v
    forall k v. Map k v -> Map (Tag v) k -> BiMap k v
    BiMap
        (k -> v -> Map k v
    forall k a. k -> a -> Map k a
    Map.singleton k
    k v
    v)
        (case v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v of
           Maybe (Tag v)
    Nothing -> Map (Tag v) k
    forall k a. Map k a
    Map.empty
           Just Tag v
    k' -> Tag v -> k -> Map (Tag v) k
    forall k a. k -> a -> Map k a
    Map.singleton Tag v
    k' k
    k)

    -- | Insertion. Overwrites existing values. O(log n).
    --
    -- Precondition: See 'insertPrecondition'.

    insert ::
      (Ord k, HasTag v, Ord (Tag v)) =>
      k -> v -> BiMap k v -> BiMap k v
    insert :: forall k v.
    (Ord k, HasTag v, Ord (Tag v)) =>
    k -> v -> BiMap k v -> BiMap k v
    insert k
    k v
    v (BiMap Map k v
    t Map (Tag v) k
    b) =
      Map k v -> Map (Tag v) k -> BiMap k v
    forall k v. Map k v -> Map (Tag v) k -> BiMap k v
    BiMap
        (k -> v -> Map k v -> Map k v
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    Map.insert k
    k v
    v Map k v
    t)
        (case v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v of
           Maybe (Tag v)
    Nothing -> Map (Tag v) k
    b'
           Just Tag v
    k' -> Tag v -> k -> Map (Tag v) k -> Map (Tag v) k
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    Map.insert Tag v
    k' k
    k Map (Tag v) k
    b')
      where
      b' :: Map (Tag v) k
    b' = case v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag (v -> Maybe (Tag v)) -> Maybe v -> Maybe (Tag v)
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< k -> Map k v -> Maybe v
    forall k a. Ord k => k -> Map k a -> Maybe a
    Map.lookup k
    k Map k v
    t of
        Maybe (Tag v)
    Nothing -> Map (Tag v) k
    b
        Just Tag v
    k' -> Tag v -> Map (Tag v) k -> Map (Tag v) k
    forall k a. Ord k => k -> Map k a -> Map k a
    Map.delete Tag v
    k' Map (Tag v) k
    b

    -- | The precondition for @'insert' k v m@: If @v@ has a 'tag' (@'tag'
    -- v ≠ 'Nothing'@), then @m@ must not contain any mapping @k' ↦ v'@
    -- for which @k ≠ k'@ and @'tag' v = 'tag' v'@.

    insertPrecondition ::
      (Eq k, Eq v, Eq (Tag v), HasTag v) =>
      k -> v -> BiMap k v -> Bool
    insertPrecondition :: forall k v.
    (Eq k, Eq v, Eq (Tag v), HasTag v) =>
    k -> v -> BiMap k v -> Bool
    insertPrecondition k
    k v
    v BiMap k v
    m =
      case v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v of
        Maybe (Tag v)
    Nothing -> Bool
    True
        Just Tag v
    _  ->
          Bool -> Bool
    not (Bool -> Bool) -> Bool -> Bool
    forall a b. (a -> b) -> a -> b
    $ ((k, v) -> Bool) -> [(k, v)] -> Bool
    forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
    any (\(k
    k', v
    v') -> k
    k' k -> k -> Bool
    forall a. Eq a => a -> a -> Bool
    /= k
    k Bool -> Bool -> Bool
    && v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v Maybe (Tag v) -> Maybe (Tag v) -> Bool
    forall a. Eq a => a -> a -> Bool
    == v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v') ([(k, v)] -> Bool) -> [(k, v)] -> Bool
    forall a b. (a -> b) -> a -> b
    $ BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList BiMap k v
    m

    -- | Modifies the value at the given position, if any. If the function
    -- returns 'Nothing', then the value is removed. O(log n).
    --
    -- The precondition for @'alterM' f k m@ is that, if the value @v@ is
    -- inserted into @m@, and @'tag' v@ is defined, then no key other than
    -- @k@ may map to a value @v'@ for which @'tag' v' = 'tag' v@.

    alterM ::
      forall k v m. (Ord k, Ord (Tag v), HasTag v, Monad m) =>
      (Maybe v -> m (Maybe v)) -> k -> BiMap k v -> m (BiMap k v)
    alterM :: forall k v (m :: * -> *).
    (Ord k, Ord (Tag v), HasTag v, Monad m) =>
    (Maybe v -> m (Maybe v)) -> k -> BiMap k v -> m (BiMap k v)
    alterM Maybe v -> m (Maybe v)
    f k
    k m :: BiMap k v
    m@(BiMap Map k v
    t Map (Tag v) k
    b) = do
      (t', r) <- StateT (Maybe (Maybe (Tag v), Maybe (Tag v))) m (Map k v)
    -> Maybe (Maybe (Tag v), Maybe (Tag v))
    -> m (Map k v, Maybe (Maybe (Tag v), Maybe (Tag v)))
    forall s (m :: * -> *) a. StateT s m a -> s -> m (a, s)
    runStateT ((Maybe v
     -> StateT (Maybe (Maybe (Tag v), Maybe (Tag v))) m (Maybe v))
    -> k
    -> Map k v
    -> StateT (Maybe (Maybe (Tag v), Maybe (Tag v))) m (Map k v)
    forall (f :: * -> *) k a.
    (Functor f, Ord k) =>
    (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
    Map.alterF Maybe v
    -> StateT (Maybe (Maybe (Tag v), Maybe (Tag v))) m (Maybe v)
    f' k
    k Map k v
    t) Maybe (Maybe (Tag v), Maybe (Tag v))
    forall a. Maybe a
    Nothing
      return $ case r of
        Maybe (Maybe (Tag v), Maybe (Tag v))
    Nothing -> BiMap k v
    m
        Just (Maybe (Tag v), Maybe (Tag v))
    r  -> Map k v -> Map (Tag v) k -> BiMap k v
    forall k v. Map k v -> Map (Tag v) k -> BiMap k v
    BiMap Map k v
    t' ((Maybe (Tag v), Maybe (Tag v)) -> Map (Tag v) k -> Map (Tag v) k
    updateBack (Maybe (Tag v), Maybe (Tag v))
    r Map (Tag v) k
    b)
      where
      f' ::
        Maybe v ->
        StateT (Maybe (Maybe (Tag v), Maybe (Tag v))) m (Maybe v)
      f' :: Maybe v
    -> StateT (Maybe (Maybe (Tag v), Maybe (Tag v))) m (Maybe v)
    f' Maybe v
    v = do
        r <- m (Maybe v)
    -> StateT (Maybe (Maybe (Tag v), Maybe (Tag v))) m (Maybe v)
    forall (m :: * -> *) a.
    Monad m =>
    m a -> StateT (Maybe (Maybe (Tag v), Maybe (Tag v))) m a
    forall (t :: (* -> *) -> * -> *) (m :: * -> *) a.
    (MonadTrans t, Monad m) =>
    m a -> t m a
    lift (Maybe v -> m (Maybe v)
    f Maybe v
    v)
        put $ Just (tag =<< v, tag =<< r)
        return r

      updateBack :: (Maybe (Tag v), Maybe (Tag v)) -> Map (Tag v) k -> Map (Tag v) k
    updateBack (Maybe (Tag v)
    k'1, Maybe (Tag v)
    k'2) =
        if Maybe (Tag v)
    k'1 Maybe (Tag v) -> Maybe (Tag v) -> Bool
    forall a. Eq a => a -> a -> Bool
    == Maybe (Tag v)
    k'2
        then Map (Tag v) k -> Map (Tag v) k
    forall a. a -> a
    id
        else (Map (Tag v) k -> Map (Tag v) k)
    -> (Tag v -> Map (Tag v) k -> Map (Tag v) k)
    -> Maybe (Tag v)
    -> Map (Tag v) k
    -> Map (Tag v) k
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map (Tag v) k -> Map (Tag v) k
    forall a. a -> a
    id ((Tag v -> k -> Map (Tag v) k -> Map (Tag v) k)
    -> k -> Tag v -> Map (Tag v) k -> Map (Tag v) k
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip Tag v -> k -> Map (Tag v) k -> Map (Tag v) k
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    Map.insert k
    k) Maybe (Tag v)
    k'2 (Map (Tag v) k -> Map (Tag v) k)
    -> (Map (Tag v) k -> Map (Tag v) k)
    -> Map (Tag v) k
    -> Map (Tag v) k
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    .
             (Map (Tag v) k -> Map (Tag v) k)
    -> (Tag v -> Map (Tag v) k -> Map (Tag v) k)
    -> Maybe (Tag v)
    -> Map (Tag v) k
    -> Map (Tag v) k
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map (Tag v) k -> Map (Tag v) k
    forall a. a -> a
    id Tag v -> Map (Tag v) k -> Map (Tag v) k
    forall k a. Ord k => k -> Map k a -> Map k a
    Map.delete Maybe (Tag v)
    k'1

    -- | Modifies the value at the given position, if any. If the function
    -- returns 'Nothing', then the value is removed. O(log n).
    --
    -- Precondition: See 'alterPrecondition'.

    alter ::
      forall k v. (Ord k, Ord (Tag v), HasTag v) =>
      (Maybe v -> Maybe v) -> k -> BiMap k v -> BiMap k v
    alter :: forall k v.
    (Ord k, Ord (Tag v), HasTag v) =>
    (Maybe v -> Maybe v) -> k -> BiMap k v -> BiMap k v
    alter Maybe v -> Maybe v
    f k
    k BiMap k v
    m = Identity (BiMap k v) -> BiMap k v
    forall a. Identity a -> a
    runIdentity (Identity (BiMap k v) -> BiMap k v)
    -> Identity (BiMap k v) -> BiMap k v
    forall a b. (a -> b) -> a -> b
    $ (Maybe v -> Identity (Maybe v))
    -> k -> BiMap k v -> Identity (BiMap k v)
    forall k v (m :: * -> *).
    (Ord k, Ord (Tag v), HasTag v, Monad m) =>
    (Maybe v -> m (Maybe v)) -> k -> BiMap k v -> m (BiMap k v)
    alterM (Maybe v -> Identity (Maybe v)
    forall a. a -> Identity a
    Identity (Maybe v -> Identity (Maybe v))
    -> (Maybe v -> Maybe v) -> Maybe v -> Identity (Maybe v)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Maybe v -> Maybe v
    f) k
    k BiMap k v
    m

    -- | The precondition for @'alter' f k m@ is that, if the value @v@ is
    -- inserted into @m@, and @'tag' v@ is defined, then no key other than
    -- @k@ may map to a value @v'@ for which @'tag' v' = 'tag' v@.

    alterPrecondition ::
      (Ord k, Eq v, Eq (Tag v), HasTag v) =>
      (Maybe v -> Maybe v) -> k -> BiMap k v -> Bool
    alterPrecondition :: forall k v.
    (Ord k, Eq v, Eq (Tag v), HasTag v) =>
    (Maybe v -> Maybe v) -> k -> BiMap k v -> Bool
    alterPrecondition Maybe v -> Maybe v
    f k
    k BiMap k v
    m =
      case v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag (v -> Maybe (Tag v)) -> Maybe v -> Maybe (Tag v)
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<< Maybe v -> Maybe v
    f (k -> BiMap k v -> Maybe v
    forall k v. Ord k => k -> BiMap k v -> Maybe v
    lookup k
    k BiMap k v
    m) of
        Maybe (Tag v)
    Nothing -> Bool
    True
        Just Tag v
    k' -> [Bool] -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    and
          [ Tag v -> Maybe (Tag v)
    forall a. a -> Maybe a
    Just Tag v
    k' Maybe (Tag v) -> Maybe (Tag v) -> Bool
    forall a. Eq a => a -> a -> Bool
    /= v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v
          | (k
    k'', v
    v) <- BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList BiMap k v
    m
          , k
    k'' k -> k -> Bool
    forall a. Eq a => a -> a -> Bool
    /= k
    k
          ]

    -- | Modifies the value at the given position, if any. If the function
    -- returns 'Nothing', then the value is removed. O(log n).
    --
    -- Precondition: See 'updatePrecondition'.

    update ::
      (Ord k, Ord (Tag v), HasTag v) =>
      (v -> Maybe v) -> k -> BiMap k v -> BiMap k v
    update :: forall k v.
    (Ord k, Ord (Tag v), HasTag v) =>
    (v -> Maybe v) -> k -> BiMap k v -> BiMap k v
    update v -> Maybe v
    f = (Maybe v -> Maybe v) -> k -> BiMap k v -> BiMap k v
    forall k v.
    (Ord k, Ord (Tag v), HasTag v) =>
    (Maybe v -> Maybe v) -> k -> BiMap k v -> BiMap k v
    alter (v -> Maybe v
    f (v -> Maybe v) -> Maybe v -> Maybe v
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<<)

    -- | The precondition for @'update' f k m@ is that, if the value @v@
    -- is inserted into @m@, and @'tag' v@ is defined, then no key other
    -- than @k@ may map to a value @v'@ for which @'tag' v' = 'tag' v@.

    updatePrecondition ::
      (Ord k, Eq v, Eq (Tag v), HasTag v) =>
      (v -> Maybe v) -> k -> BiMap k v -> Bool
    updatePrecondition :: forall k v.
    (Ord k, Eq v, Eq (Tag v), HasTag v) =>
    (v -> Maybe v) -> k -> BiMap k v -> Bool
    updatePrecondition v -> Maybe v
    f = (Maybe v -> Maybe v) -> k -> BiMap k v -> Bool
    forall k v.
    (Ord k, Eq v, Eq (Tag v), HasTag v) =>
    (Maybe v -> Maybe v) -> k -> BiMap k v -> Bool
    alterPrecondition (v -> Maybe v
    f (v -> Maybe v) -> Maybe v -> Maybe v
    forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
    =<<)

    -- | Modifies the value at the given position, if any. O(log n).
    --
    -- Precondition: See 'adjustPrecondition'.

    adjust ::
      (Ord k, Ord (Tag v), HasTag v) =>
      (v -> v) -> k -> BiMap k v -> BiMap k v
    adjust :: forall k v.
    (Ord k, Ord (Tag v), HasTag v) =>
    (v -> v) -> k -> BiMap k v -> BiMap k v
    adjust v -> v
    f = (v -> Maybe v) -> k -> BiMap k v -> BiMap k v
    forall k v.
    (Ord k, Ord (Tag v), HasTag v) =>
    (v -> Maybe v) -> k -> BiMap k v -> BiMap k v
    update (v -> Maybe v
    forall a. a -> Maybe a
    Just (v -> Maybe v) -> (v -> v) -> v -> Maybe v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . v -> v
    f)

    -- | The precondition for @'adjust' f k m@ is that, if the value @v@
    -- is inserted into @m@, and @'tag' v@ is defined, then no key other
    -- than @k@ may map to a value @v'@ for which @'tag' v' = 'tag' v@.

    adjustPrecondition ::
      (Ord k, Eq v, Eq (Tag v), HasTag v) =>
      (v -> v) -> k -> BiMap k v -> Bool
    adjustPrecondition :: forall k v.
    (Ord k, Eq v, Eq (Tag v), HasTag v) =>
    (v -> v) -> k -> BiMap k v -> Bool
    adjustPrecondition v -> v
    f = (v -> Maybe v) -> k -> BiMap k v -> Bool
    forall k v.
    (Ord k, Eq v, Eq (Tag v), HasTag v) =>
    (v -> Maybe v) -> k -> BiMap k v -> Bool
    updatePrecondition (v -> Maybe v
    forall a. a -> Maybe a
    Just (v -> Maybe v) -> (v -> v) -> v -> Maybe v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . v -> v
    f)

    -- | Inserts a binding into the map. If a binding for the key already
    -- exists, then the value obtained by applying the function to the
    -- key, the new value and the old value is inserted, and the old value
    -- is returned.
    --
    -- Precondition: See 'insertLookupWithKeyPrecondition'.

    insertLookupWithKey ::
      forall k v. (Ord k, Ord (Tag v), HasTag v) =>
      (k -> v -> v -> v) -> k -> v -> BiMap k v -> (Maybe v, BiMap k v)
    insertLookupWithKey :: forall k v.
    (Ord k, Ord (Tag v), HasTag v) =>
    (k -> v -> v -> v) -> k -> v -> BiMap k v -> (Maybe v, BiMap k v)
    insertLookupWithKey k -> v -> v -> v
    f k
    k v
    v BiMap k v
    m = (BiMap k v, Maybe v) -> (Maybe v, BiMap k v)
    forall a b. (a, b) -> (b, a)
    swap ((BiMap k v, Maybe v) -> (Maybe v, BiMap k v))
    -> (BiMap k v, Maybe v) -> (Maybe v, BiMap k v)
    forall a b. (a -> b) -> a -> b
    $ State (Maybe v) (BiMap k v) -> Maybe v -> (BiMap k v, Maybe v)
    forall s a. State s a -> s -> (a, s)
    runState ((Maybe v -> StateT (Maybe v) Identity (Maybe v))
    -> k -> BiMap k v -> State (Maybe v) (BiMap k v)
    forall k v (m :: * -> *).
    (Ord k, Ord (Tag v), HasTag v, Monad m) =>
    (Maybe v -> m (Maybe v)) -> k -> BiMap k v -> m (BiMap k v)
    alterM Maybe v -> StateT (Maybe v) Identity (Maybe v)
    f' k
    k BiMap k v
    m) Maybe v
    forall a. Maybe a
    Nothing
      where
      f' :: Maybe v -> State (Maybe v) (Maybe v)
      f' :: Maybe v -> StateT (Maybe v) Identity (Maybe v)
    f' Maybe v
    Nothing     = Maybe v -> StateT (Maybe v) Identity (Maybe v)
    forall a. a -> StateT (Maybe v) Identity a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Maybe v -> StateT (Maybe v) Identity (Maybe v))
    -> Maybe v -> StateT (Maybe v) Identity (Maybe v)
    forall a b. (a -> b) -> a -> b
    $ v -> Maybe v
    forall a. a -> Maybe a
    Just v
    v
      f' r :: Maybe v
    r@(Just v
    v') = do
        Maybe v -> StateT (Maybe v) Identity ()
    forall s (m :: * -> *). MonadState s m => s -> m ()
    put Maybe v
    r
        Maybe v -> StateT (Maybe v) Identity (Maybe v)
    forall a. a -> StateT (Maybe v) Identity a
    forall (m :: * -> *) a. Monad m => a -> m a
    return (Maybe v -> StateT (Maybe v) Identity (Maybe v))
    -> Maybe v -> StateT (Maybe v) Identity (Maybe v)
    forall a b. (a -> b) -> a -> b
    $ v -> Maybe v
    forall a. a -> Maybe a
    Just (k -> v -> v -> v
    f k
    k v
    v v
    v')

    -- | The precondition for @'insertLookupWithKey' f k v m@ is that, if
    -- the value @v'@ is inserted into @m@, and @'tag' v'@ is defined,
    -- then no key other than @k@ may map to a value @v''@ for which
    -- @'tag' v'' = 'tag' v'@.

    insertLookupWithKeyPrecondition ::
      (Ord k, Eq v, Eq (Tag v), HasTag v) =>
      (k -> v -> v -> v) -> k -> v -> BiMap k v -> Bool
    insertLookupWithKeyPrecondition :: forall k v.
    (Ord k, Eq v, Eq (Tag v), HasTag v) =>
    (k -> v -> v -> v) -> k -> v -> BiMap k v -> Bool
    insertLookupWithKeyPrecondition k -> v -> v -> v
    f k
    k v
    v =
      (Maybe v -> Maybe v) -> k -> BiMap k v -> Bool
    forall k v.
    (Ord k, Eq v, Eq (Tag v), HasTag v) =>
    (Maybe v -> Maybe v) -> k -> BiMap k v -> Bool
    alterPrecondition (v -> Maybe v
    forall a. a -> Maybe a
    Just (v -> Maybe v) -> (Maybe v -> v) -> Maybe v -> Maybe v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . v -> (v -> v) -> Maybe v -> v
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe v
    v (k -> v -> v -> v
    f k
    k v
    v)) k
    k

    -- | Changes all the values using the given function, which is also
    -- given access to keys. O(n log n).
    --
    -- Precondition: See 'mapWithKeyPrecondition'.

    mapWithKey ::
      (Ord k, Ord (Tag v), HasTag v) =>
      (k -> v -> v) -> BiMap k v -> BiMap k v
    mapWithKey :: forall k v.
    (Ord k, Ord (Tag v), HasTag v) =>
    (k -> v -> v) -> BiMap k v -> BiMap k v
    mapWithKey k -> v -> v
    f = [(k, v)] -> BiMap k v
    forall k v. (Ord k, Ord (Tag v), HasTag v) => [(k, v)] -> BiMap k v
    fromList ([(k, v)] -> BiMap k v)
    -> (BiMap k v -> [(k, v)]) -> BiMap k v -> BiMap k v
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((k, v) -> (k, v)) -> [(k, v)] -> [(k, v)]
    forall a b. (a -> b) -> [a] -> [b]
    map (\(k
    k, v
    v) -> (k
    k, k -> v -> v
    f k
    k v
    v)) ([(k, v)] -> [(k, v)])
    -> (BiMap k v -> [(k, v)]) -> BiMap k v -> [(k, v)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList

    -- | The precondition for @'mapWithKey' f m@: For any two distinct
    -- mappings @k₁ ↦ v₁@, @k₂ ↦ v₂@ in @m@ for which the tags of
    -- @f k₁ v₁@ and @f k₂ v₂@ are defined the values of @f@ must be
    -- distinct (@f k₁ v₁ ≠ f k₂ v₂@). Furthermore 'tag' must be injective
    -- for @{ f k v | (k, v) ∈ m }@.

    mapWithKeyPrecondition ::
      (Eq k, Eq v, Eq (Tag v), HasTag v) =>
      (k -> v -> v) -> BiMap k v -> Bool
    mapWithKeyPrecondition :: forall k v.
    (Eq k, Eq v, Eq (Tag v), HasTag v) =>
    (k -> v -> v) -> BiMap k v -> Bool
    mapWithKeyPrecondition k -> v -> v
    f =
      [(k, v)] -> Bool
    forall k v. (Eq k, Eq v, Eq (Tag v), HasTag v) => [(k, v)] -> Bool
    fromListPrecondition ([(k, v)] -> Bool) -> (BiMap k v -> [(k, v)]) -> BiMap k v -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((k, v) -> (k, v)) -> [(k, v)] -> [(k, v)]
    forall a b. (a -> b) -> [a] -> [b]
    map (\(k
    k, v
    v) -> (k
    k, k -> v -> v
    f k
    k v
    v)) ([(k, v)] -> [(k, v)])
    -> (BiMap k v -> [(k, v)]) -> BiMap k v -> [(k, v)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList

    -- | Changes all the values using the given function, which is also
    -- given access to keys. O(n).
    --
    -- Precondition: See 'mapWithKeyFixedTagsPrecondition'. Note that tags
    -- must not change.

    mapWithKeyFixedTags :: (k -> v -> v) -> BiMap k v -> BiMap k v
    mapWithKeyFixedTags :: forall k v. (k -> v -> v) -> BiMap k v -> BiMap k v
    mapWithKeyFixedTags k -> v -> v
    f (BiMap Map k v
    t Map (Tag v) k
    b) = Map k v -> Map (Tag v) k -> BiMap k v
    forall k v. Map k v -> Map (Tag v) k -> BiMap k v
    BiMap ((k -> v -> v) -> Map k v -> Map k v
    forall k a b. (k -> a -> b) -> Map k a -> Map k b
    Map.mapWithKey k -> v -> v
    f Map k v
    t) Map (Tag v) k
    b

    -- | The precondition for @'mapWithKeyFixedTags' f m@ is that, if @m@
    -- maps @k@ to @v@, then @'tag' (f k v) == 'tag' v@.

    mapWithKeyFixedTagsPrecondition ::
      (Eq v, Eq (Tag v), HasTag v) =>
      (k -> v -> v) -> BiMap k v -> Bool
    mapWithKeyFixedTagsPrecondition :: forall v k.
    (Eq v, Eq (Tag v), HasTag v) =>
    (k -> v -> v) -> BiMap k v -> Bool
    mapWithKeyFixedTagsPrecondition k -> v -> v
    f BiMap k v
    m = [Bool] -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    and
      [ v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag (k -> v -> v
    f k
    k v
    v) Maybe (Tag v) -> Maybe (Tag v) -> Bool
    forall a. Eq a => a -> a -> Bool
    == v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v
      | (k
    k, v
    v) <- BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList BiMap k v
    m
      ]

    -- | Left-biased union. For the time complexity, see 'Map.union'.
    --
    -- Precondition: See 'unionPrecondition'.

    union :: (Ord k, Ord (Tag v)) => BiMap k v -> BiMap k v -> BiMap k v
    union :: forall k v.
    (Ord k, Ord (Tag v)) =>
    BiMap k v -> BiMap k v -> BiMap k v
    union (BiMap Map k v
    t1 Map (Tag v) k
    b1) (BiMap Map k v
    t2 Map (Tag v) k
    b2) =
      Map k v -> Map (Tag v) k -> BiMap k v
    forall k v. Map k v -> Map (Tag v) k -> BiMap k v
    BiMap (Map k v -> Map k v -> Map k v
    forall k a. Ord k => Map k a -> Map k a -> Map k a
    Map.union Map k v
    t1 Map k v
    t2) (Map (Tag v) k -> Map (Tag v) k -> Map (Tag v) k
    forall k a. Ord k => Map k a -> Map k a -> Map k a
    Map.union Map (Tag v) k
    b1 Map (Tag v) k
    b2)

    -- The precondition for @'union' m₁ m₂@: If @k@ is mapped to @v₁@ in
    -- @m₁@ and @v₂@ in @m₂@, then @'tag' v₂ = 'Nothing'@ or @'tag' v₁ =
    -- 'tag' v₂@. Furthermore, if @k₁@ is mapped to @v₁@ in @m₁@ and @k₂@
    -- is mapped to @v₂@ in @m₂@, where @'tag' v₁ = 'tag' v₂ = 'Just' k@,
    -- then @k₁ = k₂@. Finally 'tag' must be injective for
    -- @{v₁ | (k₁, v₁) ∈ m₁} ∪ {v₂ | (k₂, v₂) ∈ m₂, k₂ ∉ m₁}@.

    unionPrecondition ::
      (Ord k, Eq v, Eq (Tag v), HasTag v) =>
      BiMap k v -> BiMap k v -> Bool
    unionPrecondition :: forall k v.
    (Ord k, Eq v, Eq (Tag v), HasTag v) =>
    BiMap k v -> BiMap k v -> Bool
    unionPrecondition m1 :: BiMap k v
    m1@(BiMap Map k v
    t1 Map (Tag v) k
    _) m2 :: BiMap k v
    m2@(BiMap Map k v
    t2 Map (Tag v) k
    _) =
      [Bool] -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    and
        [ v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v2 Maybe (Tag v) -> Maybe (Tag v) -> Bool
    forall a. Eq a => a -> a -> Bool
    == Maybe (Tag v)
    forall a. Maybe a
    Nothing Bool -> Bool -> Bool
    || v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v1 Maybe (Tag v) -> Maybe (Tag v) -> Bool
    forall a. Eq a => a -> a -> Bool
    == v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v2
        | (v
    v1, v
    v2) <- Map k (v, v) -> [(v, v)]
    forall k a. Map k a -> [a]
    Map.elems (Map k (v, v) -> [(v, v)]) -> Map k (v, v) -> [(v, v)]
    forall a b. (a -> b) -> a -> b
    $ (v -> v -> (v, v)) -> Map k v -> Map k v -> Map k (v, v)
    forall k a b c.
    Ord k =>
    (a -> b -> c) -> Map k a -> Map k b -> Map k c
    Map.intersectionWith (,) Map k v
    t1 Map k v
    t2
        ] Bool -> Bool -> Bool
    &&
      [Bool] -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    and
        [ k
    k1 k -> k -> Bool
    forall a. Eq a => a -> a -> Bool
    == k
    k2
        | (k
    k1, v
    v1) <- BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList BiMap k v
    m1
        , (k
    k2, v
    v2) <- BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList BiMap k v
    m2
        , v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v1 Maybe (Tag v) -> Maybe (Tag v) -> Bool
    forall a. Eq a => a -> a -> Bool
    == v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v2
        , Maybe (Tag v) -> Bool
    forall a. Maybe a -> Bool
    isJust (v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v1)
        ]
        Bool -> Bool -> Bool
    &&
      [v] -> Bool
    forall v. (Eq v, Eq (Tag v), HasTag v) => [v] -> Bool
    tagInjectiveFor
        ([ v
    v1
         | (k
    _, v
    v1) <- BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList BiMap k v
    m1
         ] [v] -> [v] -> [v]
    forall a. [a] -> [a] -> [a]
    ++
         [ v
    v2
         | (k
    k2, v
    v2) <- BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList BiMap k v
    m2
         , k
    k2 k -> [k] -> Bool
    forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
    `notElem` [k]
    ks1
         ])
      where
      ks1 :: [k]
    ks1 = ((k, v) -> k) -> [(k, v)] -> [k]
    forall a b. (a -> b) -> [a] -> [b]
    map (k, v) -> k
    forall a b. (a, b) -> a
    fst (BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList BiMap k v
    m1)

    -- | Conversion from lists of pairs. Later entries take precedence
    -- over earlier ones. O(n log n).
    --
    -- Precondition: See 'fromListPrecondition'.

    fromList ::
      (Ord k, Ord (Tag v), HasTag v) =>
      [(k, v)] -> BiMap k v
    fromList :: forall k v. (Ord k, Ord (Tag v), HasTag v) => [(k, v)] -> BiMap k v
    fromList = ((k, v) -> BiMap k v -> BiMap k v)
    -> BiMap k v -> [(k, v)] -> BiMap k v
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    List.foldr ((k -> v -> BiMap k v -> BiMap k v)
    -> (k, v) -> BiMap k v -> BiMap k v
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry k -> v -> BiMap k v -> BiMap k v
    forall k v.
    (Ord k, HasTag v, Ord (Tag v)) =>
    k -> v -> BiMap k v -> BiMap k v
    insert) BiMap k v
    forall a. Null a => a
    empty

    -- The precondition for @'fromList' kvs@: For all pairs @(k₁, v₁)@,
    -- @(k₂, v₂)@ in @kvs@ for which the tags of @v₁@ and @v₂@ are
    -- defined, if @v₁ = v₂@ then @k₁ = k₂@. Furthermore 'tag' must be
    -- injective for the values in the list.

    fromListPrecondition ::
      (Eq k, Eq v, Eq (Tag v), HasTag v) =>
      [(k, v)] -> Bool
    fromListPrecondition :: forall k v. (Eq k, Eq v, Eq (Tag v), HasTag v) => [(k, v)] -> Bool
    fromListPrecondition [(k, v)]
    kvs =
      [Bool] -> Bool
    forall (t :: * -> *). Foldable t => t Bool -> Bool
    and
        [ k
    k1 k -> k -> Bool
    forall a. Eq a => a -> a -> Bool
    == k
    k2
        | (k
    k1, v
    v1) <- [(k, v)]
    kvs
        , (k
    k2, v
    v2) <- [(k, v)]
    kvs
        , Maybe (Tag v) -> Bool
    forall a. Maybe a -> Bool
    isJust (v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v1)
        , Maybe (Tag v) -> Bool
    forall a. Maybe a -> Bool
    isJust (v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v2)
        , v
    v1 v -> v -> Bool
    forall a. Eq a => a -> a -> Bool
    == v
    v2
        ]
        Bool -> Bool -> Bool
    &&
      [v] -> Bool
    forall v. (Eq v, Eq (Tag v), HasTag v) => [v] -> Bool
    tagInjectiveFor (((k, v) -> v) -> [(k, v)] -> [v]
    forall a b. (a -> b) -> [a] -> [b]
    map (k, v) -> v
    forall a b. (a, b) -> b
    snd [(k, v)]
    kvs)

    -- | Conversion to lists of pairs, with the keys in ascending order.
    -- O(n).

    toList :: BiMap k v -> [(k, v)]
    toList :: forall k v. BiMap k v -> [(k, v)]
    toList = Map k v -> [(k, v)]
    forall k a. Map k a -> [(k, a)]
    Map.toAscList (Map k v -> [(k, v)])
    -> (BiMap k v -> Map k v) -> BiMap k v -> [(k, v)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . BiMap k v -> Map k v
    forall k v. BiMap k v -> Map k v
    biMapThere

    -- | The keys, in ascending order. O(n).

    keys :: BiMap k v -> [k]
    keys :: forall k v. BiMap k v -> [k]
    keys = Map k v -> [k]
    forall k a. Map k a -> [k]
    Map.keys (Map k v -> [k]) -> (BiMap k v -> Map k v) -> BiMap k v -> [k]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . BiMap k v -> Map k v
    forall k v. BiMap k v -> Map k v
    biMapThere

    -- | The values, ordered according to the corresponding keys. O(n).

    elems :: BiMap k v -> [v]
    elems :: forall k v. BiMap k v -> [v]
    elems = Map k v -> [v]
    forall k a. Map k a -> [a]
    Map.elems (Map k v -> [v]) -> (BiMap k v -> Map k v) -> BiMap k v -> [v]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . BiMap k v -> Map k v
    forall k v. BiMap k v -> Map k v
    biMapThere

    -- | Conversion from two lists that contain distinct keys/tags, with
    -- the keys/tags in ascending order. O(n).
    --
    -- Precondition: See 'fromDistinctAscendingListsPrecondition'.

    fromDistinctAscendingLists ::
      ([(k, v)], [(Tag v, k)]) -> BiMap k v
    fromDistinctAscendingLists :: forall k v. ([(k, v)], [(Tag v, k)]) -> BiMap k v
    fromDistinctAscendingLists ([(k, v)]
    t, [(Tag v, k)]
    b) =
      Map k v -> Map (Tag v) k -> BiMap k v
    forall k v. Map k v -> Map (Tag v) k -> BiMap k v
    BiMap ([(k, v)] -> Map k v
    forall k a. [(k, a)] -> Map k a
    Map.fromDistinctAscList [(k, v)]
    t) ([(Tag v, k)] -> Map (Tag v) k
    forall k a. [(k, a)] -> Map k a
    Map.fromDistinctAscList [(Tag v, k)]
    b)

    -- The precondition for @'fromDistinctAscendingLists' (kvs, kks)@: The
    -- lists must contain distinct keys/tags, and must be sorted according
    -- to the keys/tags. Furthermore, for every pair @(k, v)@ in the first
    -- list for which @'tag' v = 'Just' k'@ there must be a pair @(k', k)@
    -- in the second list, and there must not be any other pairs in that
    -- list. Finally 'tag' must be injective for @{v | (_, v) ∈ kvs }@.

    fromDistinctAscendingListsPrecondition ::
      (Ord k, Eq v, Ord (Tag v), HasTag v) =>
      ([(k, v)], [(Tag v, k)]) -> Bool
    fromDistinctAscendingListsPrecondition :: forall k v.
    (Ord k, Eq v, Ord (Tag v), HasTag v) =>
    ([(k, v)], [(Tag v, k)]) -> Bool
    fromDistinctAscendingListsPrecondition ([(k, v)]
    kvs, [(Tag v, k)]
    kks) =
      [k] -> Bool
    forall a. Ord a => [a] -> Bool
    fastDistinct (((k, v) -> k) -> [(k, v)] -> [k]
    forall a b. (a -> b) -> [a] -> [b]
    map (k, v) -> k
    forall a b. (a, b) -> a
    fst [(k, v)]
    kvs) Bool -> Bool -> Bool
    && [k] -> Bool
    forall a. Ord a => [a] -> Bool
    sorted (((k, v) -> k) -> [(k, v)] -> [k]
    forall a b. (a -> b) -> [a] -> [b]
    map (k, v) -> k
    forall a b. (a, b) -> a
    fst [(k, v)]
    kvs)
        Bool -> Bool -> Bool
    &&
      [Tag v] -> Bool
    forall a. Ord a => [a] -> Bool
    fastDistinct (((Tag v, k) -> Tag v) -> [(Tag v, k)] -> [Tag v]
    forall a b. (a -> b) -> [a] -> [b]
    map (Tag v, k) -> Tag v
    forall a b. (a, b) -> a
    fst [(Tag v, k)]
    kks) Bool -> Bool -> Bool
    && [Tag v] -> Bool
    forall a. Ord a => [a] -> Bool
    sorted (((Tag v, k) -> Tag v) -> [(Tag v, k)] -> [Tag v]
    forall a b. (a -> b) -> [a] -> [b]
    map (Tag v, k) -> Tag v
    forall a b. (a, b) -> a
    fst [(Tag v, k)]
    kks)
        Bool -> Bool -> Bool
    &&
      [(Tag v, k)]
    kks [(Tag v, k)] -> [(Tag v, k)] -> Bool
    forall a. Eq a => a -> a -> Bool
    ==
      ((Tag v, k) -> (Tag v, k) -> Ordering)
    -> [(Tag v, k)] -> [(Tag v, k)]
    forall a. (a -> a -> Ordering) -> [a] -> [a]
    List.sortBy (((Tag v, k) -> Tag v) -> (Tag v, k) -> (Tag v, k) -> Ordering
    forall a b. Ord a => (b -> a) -> b -> b -> Ordering
    comparing (Tag v, k) -> Tag v
    forall a b. (a, b) -> a
    fst)
        [ (Tag v
    k', k
    k)
        | (k
    k, v
    v) <- [(k, v)]
    kvs
        , Just Tag v
    k' <- [v -> Maybe (Tag v)
    forall a. HasTag a => a -> Maybe (Tag a)
    tag v
    v]
        ]
        Bool -> Bool -> Bool
    &&
      [v] -> Bool
    forall v. (Eq v, Eq (Tag v), HasTag v) => [v] -> Bool
    tagInjectiveFor [ v
    v | (k
    _, v
    v) <- [(k, v)]
    kvs ]

    -- | Generates input suitable for 'fromDistinctAscendingLists'. O(n).

    toDistinctAscendingLists :: BiMap k v -> ([(k, v)], [(Tag v, k)])
    toDistinctAscendingLists :: forall k v. BiMap k v -> ([(k, v)], [(Tag v, k)])
    toDistinctAscendingLists (BiMap Map k v
    t Map (Tag v) k
    b) =
      (Map k v -> [(k, v)]
    forall k a. Map k a -> [(k, a)]
    Map.toAscList Map k v
    t, Map (Tag v) k -> [(Tag v, k)]
    forall k a. Map k a -> [(k, a)]
    Map.toAscList Map (Tag v) k
    b)

    ------------------------------------------------------------------------
    -- Instances
    ------------------------------------------------------------------------

    instance (Eq k, Eq v) => Eq (BiMap k v) where
      == :: BiMap k v -> BiMap k v -> Bool
    (==) = Map k v -> Map k v -> Bool
    forall a. Eq a => a -> a -> Bool
    (==) (Map k v -> Map k v -> Bool)
    -> (BiMap k v -> Map k v) -> BiMap k v -> BiMap k v -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` BiMap k v -> Map k v
    forall k v. BiMap k v -> Map k v
    biMapThere

    instance (Ord k, Ord v) => Ord (BiMap k v) where
      compare :: BiMap k v -> BiMap k v -> Ordering
    compare = Map k v -> Map k v -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare (Map k v -> Map k v -> Ordering)
    -> (BiMap k v -> Map k v) -> BiMap k v -> BiMap k v -> Ordering
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` BiMap k v -> Map k v
    forall k v. BiMap k v -> Map k v
    biMapThere

    instance (Show k, Show v) => Show (BiMap k v) where
      show :: BiMap k v -> String
    show BiMap k v
    bimap = String
    "Agda.Utils.BiMap.fromList " String -> ShowS
    forall a. [a] -> [a] -> [a]
    ++ [(k, v)] -> String
    forall a. Show a => a -> String
    show (BiMap k v -> [(k, v)]
    forall k v. BiMap k v -> [(k, v)]
    toList BiMap k v
    bimap)