    {-
    Copyright   : (C) 2016-2021 QBayLogic B.V.
                           2022 Alexander McKenna
    License     : BSD2 (see the file LICENSE)
    Maintainer  : QBayLogic B.V. <devops@qbaylogic.com>
    -}

    {-# LANGUAGE CPP #-}
    {-# LANGUAGE GeneralizedNewtypeDeriving #-}
    {-# LANGUAGE OverloadedStrings #-}

    module Clash.Data.UniqMap
      ( UniqMap(..)
      , empty
      , singleton
      , singletonUnique
      , null
      , insert
      , insertUnique
      , insertWith
      , insertMany
      , lookup
      , find
      , elem
      , notElem
      , filter
      , mapMaybe
      , foldrWithUnique
      , foldlWithUnique'
      , delete
      , deleteMany
      , unionWith
      , difference
      , disjoint
      , submap
      , fromList
      , toList
      , keys
      , elems
      ) where

    import           Prelude hiding (elem, filter, lookup, notElem, null)

    import           Control.DeepSeq (NFData)
    import           Data.Binary (Binary)
    import           Data.Bifunctor (first)
    import           Data.Function (on)
    import           Data.IntMap.Strict (IntMap)
    import qualified Data.IntMap.Strict as IntMap
    import qualified Data.List as List (foldl')

    #if !MIN_VERSION_containers(0,6,2)
    import qualified Data.IntMap.Extra as IntMap
    #endif

    #if MIN_VERSION_prettyprinter(1,7,0)
    import           Prettyprinter
    #else
    import           Data.Text.Prettyprint.Doc
    #endif

    import           Clash.Pretty
    import           Clash.Unique (Unique, Uniquable(getUnique))

    -- | A map indexed by a 'Unique'. Typically the elements of this map are also
    -- uniqueable and provide their own key, however a unique can be associated
    -- with any value.
    newtype UniqMap a
      = UniqMap { forall a. UniqMap a -> IntMap a
    uniqMapToIntMap :: IntMap a }
      deriving stock Functor UniqMap
    Foldable UniqMap
    Functor UniqMap
    -> Foldable UniqMap
    -> (forall (f :: Type -> Type) a b.
        Applicative f =>
        (a -> f b) -> UniqMap a -> f (UniqMap b))
    -> (forall (f :: Type -> Type) a.
        Applicative f =>
        UniqMap (f a) -> f (UniqMap a))
    -> (forall (m :: Type -> Type) a b.
        Monad m =>
        (a -> m b) -> UniqMap a -> m (UniqMap b))
    -> (forall (m :: Type -> Type) a.
        Monad m =>
        UniqMap (m a) -> m (UniqMap a))
    -> Traversable UniqMap
    forall (t :: Type -> Type).
    Functor t
    -> Foldable t
    -> (forall (f :: Type -> Type) a b.
        Applicative f =>
        (a -> f b) -> t a -> f (t b))
    -> (forall (f :: Type -> Type) a.
        Applicative f =>
        t (f a) -> f (t a))
    -> (forall (m :: Type -> Type) a b.
        Monad m =>
        (a -> m b) -> t a -> m (t b))
    -> (forall (m :: Type -> Type) a. Monad m => t (m a) -> m (t a))
    -> Traversable t
    forall (m :: Type -> Type) a.
    Monad m =>
    UniqMap (m a) -> m (UniqMap a)
    forall (f :: Type -> Type) a.
    Applicative f =>
    UniqMap (f a) -> f (UniqMap a)
    forall (m :: Type -> Type) a b.
    Monad m =>
    (a -> m b) -> UniqMap a -> m (UniqMap b)
    forall (f :: Type -> Type) a b.
    Applicative f =>
    (a -> f b) -> UniqMap a -> f (UniqMap b)
    $ctraverse :: forall (f :: Type -> Type) a b.
    Applicative f =>
    (a -> f b) -> UniqMap a -> f (UniqMap b)
    traverse :: forall (f :: Type -> Type) a b.
    Applicative f =>
    (a -> f b) -> UniqMap a -> f (UniqMap b)
    $csequenceA :: forall (f :: Type -> Type) a.
    Applicative f =>
    UniqMap (f a) -> f (UniqMap a)
    sequenceA :: forall (f :: Type -> Type) a.
    Applicative f =>
    UniqMap (f a) -> f (UniqMap a)
    $cmapM :: forall (m :: Type -> Type) a b.
    Monad m =>
    (a -> m b) -> UniqMap a -> m (UniqMap b)
    mapM :: forall (m :: Type -> Type) a b.
    Monad m =>
    (a -> m b) -> UniqMap a -> m (UniqMap b)
    $csequence :: forall (m :: Type -> Type) a.
    Monad m =>
    UniqMap (m a) -> m (UniqMap a)
    sequence :: forall (m :: Type -> Type) a.
    Monad m =>
    UniqMap (m a) -> m (UniqMap a)
    Traversable
      deriving newtype
        ( Get (UniqMap a)
    [UniqMap a] -> Put
    UniqMap a -> Put
    (UniqMap a -> Put)
    -> Get (UniqMap a) -> ([UniqMap a] -> Put) -> Binary (UniqMap a)
    forall a. Binary a => Get (UniqMap a)
    forall a. Binary a => [UniqMap a] -> Put
    forall a. Binary a => UniqMap a -> Put
    forall t. (t -> Put) -> Get t -> ([t] -> Put) -> Binary t
    $cput :: forall a. Binary a => UniqMap a -> Put
    put :: UniqMap a -> Put
    $cget :: forall a. Binary a => Get (UniqMap a)
    get :: Get (UniqMap a)
    $cputList :: forall a. Binary a => [UniqMap a] -> Put
    putList :: [UniqMap a] -> Put
    Binary
        , (forall m. Monoid m => UniqMap m -> m)
    -> (forall m a. Monoid m => (a -> m) -> UniqMap a -> m)
    -> (forall m a. Monoid m => (a -> m) -> UniqMap a -> m)
    -> (forall a b. (a -> b -> b) -> b -> UniqMap a -> b)
    -> (forall a b. (a -> b -> b) -> b -> UniqMap a -> b)
    -> (forall b a. (b -> a -> b) -> b -> UniqMap a -> b)
    -> (forall b a. (b -> a -> b) -> b -> UniqMap a -> b)
    -> (forall a. (a -> a -> a) -> UniqMap a -> a)
    -> (forall a. (a -> a -> a) -> UniqMap a -> a)
    -> (forall a. UniqMap a -> [a])
    -> (forall a. UniqMap a -> Bool)
    -> (forall a. UniqMap a -> Unique)
    -> (forall a. Eq a => a -> UniqMap a -> Bool)
    -> (forall a. Ord a => UniqMap a -> a)
    -> (forall a. Ord a => UniqMap a -> a)
    -> (forall a. Num a => UniqMap a -> a)
    -> (forall a. Num a => UniqMap a -> a)
    -> Foldable UniqMap
    forall a. Eq a => a -> UniqMap a -> Bool
    forall a. Num a => UniqMap a -> a
    forall a. Ord a => UniqMap a -> a
    forall m. Monoid m => UniqMap m -> m
    forall a. UniqMap a -> Bool
    forall a. UniqMap a -> Unique
    forall a. UniqMap a -> [a]
    forall a. (a -> a -> a) -> UniqMap a -> a
    forall m a. Monoid m => (a -> m) -> UniqMap a -> m
    forall b a. (b -> a -> b) -> b -> UniqMap a -> b
    forall a b. (a -> b -> b) -> b -> UniqMap a -> b
    forall (t :: Type -> Type).
    (forall m. Monoid m => t m -> m)
    -> (forall m a. Monoid m => (a -> m) -> t a -> m)
    -> (forall m a. Monoid m => (a -> m) -> t a -> m)
    -> (forall a b. (a -> b -> b) -> b -> t a -> b)
    -> (forall a b. (a -> b -> b) -> b -> t a -> b)
    -> (forall b a. (b -> a -> b) -> b -> t a -> b)
    -> (forall b a. (b -> a -> b) -> b -> t a -> b)
    -> (forall a. (a -> a -> a) -> t a -> a)
    -> (forall a. (a -> a -> a) -> t a -> a)
    -> (forall a. t a -> [a])
    -> (forall a. t a -> Bool)
    -> (forall a. t a -> Unique)
    -> (forall a. Eq a => a -> t a -> Bool)
    -> (forall a. Ord a => t a -> a)
    -> (forall a. Ord a => t a -> a)
    -> (forall a. Num a => t a -> a)
    -> (forall a. Num a => t a -> a)
    -> Foldable t
    $cfold :: forall m. Monoid m => UniqMap m -> m
    fold :: forall m. Monoid m => UniqMap m -> m
    $cfoldMap :: forall m a. Monoid m => (a -> m) -> UniqMap a -> m
    foldMap :: forall m a. Monoid m => (a -> m) -> UniqMap a -> m
    $cfoldMap' :: forall m a. Monoid m => (a -> m) -> UniqMap a -> m
    foldMap' :: forall m a. Monoid m => (a -> m) -> UniqMap a -> m
    $cfoldr :: forall a b. (a -> b -> b) -> b -> UniqMap a -> b
    foldr :: forall a b. (a -> b -> b) -> b -> UniqMap a -> b
    $cfoldr' :: forall a b. (a -> b -> b) -> b -> UniqMap a -> b
    foldr' :: forall a b. (a -> b -> b) -> b -> UniqMap a -> b
    $cfoldl :: forall b a. (b -> a -> b) -> b -> UniqMap a -> b
    foldl :: forall b a. (b -> a -> b) -> b -> UniqMap a -> b
    $cfoldl' :: forall b a. (b -> a -> b) -> b -> UniqMap a -> b
    foldl' :: forall b a. (b -> a -> b) -> b -> UniqMap a -> b
    $cfoldr1 :: forall a. (a -> a -> a) -> UniqMap a -> a
    foldr1 :: forall a. (a -> a -> a) -> UniqMap a -> a
    $cfoldl1 :: forall a. (a -> a -> a) -> UniqMap a -> a
    foldl1 :: forall a. (a -> a -> a) -> UniqMap a -> a
    $ctoList :: forall a. UniqMap a -> [a]
    toList :: forall a. UniqMap a -> [a]
    $cnull :: forall a. UniqMap a -> Bool
    null :: forall a. UniqMap a -> Bool
    $clength :: forall a. UniqMap a -> Unique
    length :: forall a. UniqMap a -> Unique
    $celem :: forall a. Eq a => a -> UniqMap a -> Bool
    elem :: forall a. Eq a => a -> UniqMap a -> Bool
    $cmaximum :: forall a. Ord a => UniqMap a -> a
    maximum :: forall a. Ord a => UniqMap a -> a
    $cminimum :: forall a. Ord a => UniqMap a -> a
    minimum :: forall a. Ord a => UniqMap a -> a
    $csum :: forall a. Num a => UniqMap a -> a
    sum :: forall a. Num a => UniqMap a -> a
    $cproduct :: forall a. Num a => UniqMap a -> a
    product :: forall a. Num a => UniqMap a -> a
    Foldable
        , (forall a b. (a -> b) -> UniqMap a -> UniqMap b)
    -> (forall a b. a -> UniqMap b -> UniqMap a) -> Functor UniqMap
    forall a b. a -> UniqMap b -> UniqMap a
    forall a b. (a -> b) -> UniqMap a -> UniqMap b
    forall (f :: Type -> Type).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    $cfmap :: forall a b. (a -> b) -> UniqMap a -> UniqMap b
    fmap :: forall a b. (a -> b) -> UniqMap a -> UniqMap b
    $c<$ :: forall a b. a -> UniqMap b -> UniqMap a
    <$ :: forall a b. a -> UniqMap b -> UniqMap a
    Functor
        , Semigroup (UniqMap a)
    UniqMap a
    Semigroup (UniqMap a)
    -> UniqMap a
    -> (UniqMap a -> UniqMap a -> UniqMap a)
    -> ([UniqMap a] -> UniqMap a)
    -> Monoid (UniqMap a)
    [UniqMap a] -> UniqMap a
    UniqMap a -> UniqMap a -> UniqMap a
    forall {a}. Semigroup (UniqMap a)
    forall a. UniqMap a
    forall a.
    Semigroup a -> a -> (a -> a -> a) -> ([a] -> a) -> Monoid a
    forall a. [UniqMap a] -> UniqMap a
    forall a. UniqMap a -> UniqMap a -> UniqMap a
    $cmempty :: forall a. UniqMap a
    mempty :: UniqMap a
    $cmappend :: forall a. UniqMap a -> UniqMap a -> UniqMap a
    mappend :: UniqMap a -> UniqMap a -> UniqMap a
    $cmconcat :: forall a. [UniqMap a] -> UniqMap a
    mconcat :: [UniqMap a] -> UniqMap a
    Monoid
        , UniqMap a -> ()
    (UniqMap a -> ()) -> NFData (UniqMap a)
    forall a. NFData a => UniqMap a -> ()
    forall a. (a -> ()) -> NFData a
    $crnf :: forall a. NFData a => UniqMap a -> ()
    rnf :: UniqMap a -> ()
    NFData
        , NonEmpty (UniqMap a) -> UniqMap a
    UniqMap a -> UniqMap a -> UniqMap a
    (UniqMap a -> UniqMap a -> UniqMap a)
    -> (NonEmpty (UniqMap a) -> UniqMap a)
    -> (forall b. Integral b => b -> UniqMap a -> UniqMap a)
    -> Semigroup (UniqMap a)
    forall b. Integral b => b -> UniqMap a -> UniqMap a
    forall a. NonEmpty (UniqMap a) -> UniqMap a
    forall a. UniqMap a -> UniqMap a -> UniqMap a
    forall a.
    (a -> a -> a)
    -> (NonEmpty a -> a)
    -> (forall b. Integral b => b -> a -> a)
    -> Semigroup a
    forall a b. Integral b => b -> UniqMap a -> UniqMap a
    $c<> :: forall a. UniqMap a -> UniqMap a -> UniqMap a
    <> :: UniqMap a -> UniqMap a -> UniqMap a
    $csconcat :: forall a. NonEmpty (UniqMap a) -> UniqMap a
    sconcat :: NonEmpty (UniqMap a) -> UniqMap a
    $cstimes :: forall a b. Integral b => b -> UniqMap a -> UniqMap a
    stimes :: forall b. Integral b => b -> UniqMap a -> UniqMap a
    Semigroup
        , Unique -> UniqMap a -> ShowS
    [UniqMap a] -> ShowS
    UniqMap a -> String
    (Unique -> UniqMap a -> ShowS)
    -> (UniqMap a -> String)
    -> ([UniqMap a] -> ShowS)
    -> Show (UniqMap a)
    forall a. Show a => Unique -> UniqMap a -> ShowS
    forall a. Show a => [UniqMap a] -> ShowS
    forall a. Show a => UniqMap a -> String
    forall a.
    (Unique -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: forall a. Show a => Unique -> UniqMap a -> ShowS
    showsPrec :: Unique -> UniqMap a -> ShowS
    $cshow :: forall a. Show a => UniqMap a -> String
    show :: UniqMap a -> String
    $cshowList :: forall a. Show a => [UniqMap a] -> ShowS
    showList :: [UniqMap a] -> ShowS
    Show
        )

    instance ClashPretty a => ClashPretty (UniqMap a) where
      clashPretty :: UniqMap a -> Doc ()
    clashPretty UniqMap a
    xs =
        Doc () -> Doc ()
    forall ann. Doc ann -> Doc ann
    brackets (Doc () -> Doc ()) -> Doc () -> Doc ()
    forall a b. (a -> b) -> a -> b
    $ [Doc ()] -> Doc ()
    forall ann. [Doc ann] -> Doc ann
    fillSep ([Doc ()] -> Doc ()) -> [Doc ()] -> Doc ()
    forall a b. (a -> b) -> a -> b
    $ Doc () -> [Doc ()] -> [Doc ()]
    forall ann. Doc ann -> [Doc ann] -> [Doc ann]
    punctuate Doc ()
    forall ann. Doc ann
    comma ([Doc ()] -> [Doc ()]) -> [Doc ()] -> [Doc ()]
    forall a b. (a -> b) -> a -> b
    $
          [ Unique -> Doc ()
    forall a. Pretty a => a -> Doc ()
    fromPretty Unique
    k Doc () -> Doc () -> Doc ()
    forall ann. Doc ann -> Doc ann -> Doc ann
    <+> Doc ()
    ":->" Doc () -> Doc () -> Doc ()
    forall ann. Doc ann -> Doc ann -> Doc ann
    <+> a -> Doc ()
    forall a. ClashPretty a => a -> Doc ()
    clashPretty a
    v
          | (Unique
    k, a
    v) <- UniqMap a -> [(Unique, a)]
    forall b. UniqMap b -> [(Unique, b)]
    toList UniqMap a
    xs
          ]

    -- | An empty map.
    empty :: UniqMap a
    empty :: forall a. UniqMap a
    empty =
      IntMap a -> UniqMap a
    forall a. IntMap a -> UniqMap a
    UniqMap IntMap a
    forall a. IntMap a
    IntMap.empty

    {-# SPECIALIZE singleton :: Unique -> b -> UniqMap b #-}
    -- | A map containing a single value indexed by the given key's unique.
    singleton :: Uniquable a => a -> b -> UniqMap b
    singleton :: forall a b. Uniquable a => a -> b -> UniqMap b
    singleton a
    k b
    v =
      IntMap b -> UniqMap b
    forall a. IntMap a -> UniqMap a
    UniqMap (Unique -> b -> IntMap b
    forall a. Unique -> a -> IntMap a
    IntMap.singleton (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) b
    v)

    {-# SPECIALIZE singletonUnique :: Unique -> UniqMap Unique #-}
    -- | A map containing a single value indexed by the value's unique.
    singletonUnique :: Uniquable a => a -> UniqMap a
    singletonUnique :: forall a. Uniquable a => a -> UniqMap a
    singletonUnique a
    v =
      Unique -> a -> UniqMap a
    forall a b. Uniquable a => a -> b -> UniqMap b
    singleton (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    v) a
    v

    -- | Check if the map is empty.
    null :: UniqMap a -> Bool
    null :: forall a. UniqMap a -> Bool
    null =
      IntMap a -> Bool
    forall a. IntMap a -> Bool
    IntMap.null (IntMap a -> Bool) -> (UniqMap a -> IntMap a) -> UniqMap a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap a -> IntMap a
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    {-# SPECIALIZE insert :: Unique -> b -> UniqMap b -> UniqMap b #-}
    -- | Insert a new key-value pair into the map.
    insert :: Uniquable a => a -> b -> UniqMap b -> UniqMap b
    insert :: forall a b. Uniquable a => a -> b -> UniqMap b -> UniqMap b
    insert a
    k b
    v =
      IntMap b -> UniqMap b
    forall a. IntMap a -> UniqMap a
    UniqMap (IntMap b -> UniqMap b)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Unique -> b -> IntMap b -> IntMap b
    forall a. Unique -> a -> IntMap a -> IntMap a
    IntMap.insert (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) b
    v (IntMap b -> IntMap b)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> IntMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    {-# SPECIALIZE insertUnique :: Unique -> UniqMap Unique -> UniqMap Unique #-}
    -- | Insert a new value into the map, using the unique of the value as the key.
    insertUnique :: Uniquable a => a -> UniqMap a -> UniqMap a
    insertUnique :: forall a. Uniquable a => a -> UniqMap a -> UniqMap a
    insertUnique a
    v =
      Unique -> a -> UniqMap a -> UniqMap a
    forall a b. Uniquable a => a -> b -> UniqMap b -> UniqMap b
    insert (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    v) a
    v

    -- | Insert a new key-value pair into the map, using the given combining
    -- function if there is already an entry with the same unique in the map.
    insertWith :: Uniquable a => (b -> b -> b) -> a -> b -> UniqMap b -> UniqMap b
    insertWith :: forall a b.
    Uniquable a =>
    (b -> b -> b) -> a -> b -> UniqMap b -> UniqMap b
    insertWith b -> b -> b
    f a
    k b
    v =
      IntMap b -> UniqMap b
    forall a. IntMap a -> UniqMap a
    UniqMap (IntMap b -> UniqMap b)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> b -> b) -> Unique -> b -> IntMap b -> IntMap b
    forall a. (a -> a -> a) -> Unique -> a -> IntMap a -> IntMap a
    IntMap.insertWith b -> b -> b
    f (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) b
    v (IntMap b -> IntMap b)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> IntMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    -- | Insert a list of key-value pairs into the map.
    insertMany :: Uniquable a => [(a, b)] -> UniqMap b -> UniqMap b
    insertMany :: forall a b. Uniquable a => [(a, b)] -> UniqMap b -> UniqMap b
    insertMany [(a, b)]
    kvs UniqMap b
    xs =
      (UniqMap b -> (a, b) -> UniqMap b)
    -> UniqMap b -> [(a, b)] -> UniqMap b
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: Type -> Type) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    List.foldl' (\UniqMap b
    acc (a
    k, b
    v) -> a -> b -> UniqMap b -> UniqMap b
    forall a b. Uniquable a => a -> b -> UniqMap b -> UniqMap b
    insert a
    k b
    v UniqMap b
    acc) UniqMap b
    xs [(a, b)]
    kvs

    {-# SPECIALIZE lookup :: Unique -> UniqMap b -> Maybe b #-}
    -- | Lookup an item in the map, using the unique of the given key.
    lookup :: Uniquable a => a -> UniqMap b -> Maybe b
    lookup :: forall a b. Uniquable a => a -> UniqMap b -> Maybe b
    lookup a
    k =
      Unique -> IntMap b -> Maybe b
    forall a. Unique -> IntMap a -> Maybe a
    IntMap.lookup (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) (IntMap b -> Maybe b)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> Maybe b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    {-# SPECIALIZE find :: Unique -> UniqMap b -> b #-}
    -- | Lookup and item in the map, using the unique of the given key. If the item
    -- is not found in the map an error is raised.
    find :: Uniquable a => a -> UniqMap b -> b
    find :: forall a b. Uniquable a => a -> UniqMap b -> b
    find a
    k =
      let notFound :: a
    notFound =
            String -> a
    forall a. HasCallStack => String -> a
    error (String
    "find: Key " String -> ShowS
    forall a. Semigroup a => a -> a -> a
    <> Unique -> String
    forall a. Show a => a -> String
    show (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) String -> ShowS
    forall a. Semigroup a => a -> a -> a
    <> String
    " is not in the UniqMap")
       in b -> Unique -> IntMap b -> b
    forall a. a -> Unique -> IntMap a -> a
    IntMap.findWithDefault b
    forall {a}. a
    notFound (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) (IntMap b -> b) -> (UniqMap b -> IntMap b) -> UniqMap b -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    {-# SPECIALIZE elem :: Unique -> UniqMap b -> Bool #-}
    -- | Check if there is an entry in the map for the unique of the given value.
    elem :: Uniquable a => a -> UniqMap b -> Bool
    elem :: forall a b. Uniquable a => a -> UniqMap b -> Bool
    elem a
    k =
      Unique -> IntMap b -> Bool
    forall a. Unique -> IntMap a -> Bool
    IntMap.member (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) (IntMap b -> Bool) -> (UniqMap b -> IntMap b) -> UniqMap b -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    {-# SPECIALIZE notElem :: Unique -> UniqMap b -> Bool #-}
    -- | Check if there is not an entry in the map for the unique of the given
    -- value.
    notElem :: Uniquable a => a -> UniqMap b -> Bool
    notElem :: forall a b. Uniquable a => a -> UniqMap b -> Bool
    notElem a
    k =
      Unique -> IntMap b -> Bool
    forall a. Unique -> IntMap a -> Bool
    IntMap.notMember (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) (IntMap b -> Bool) -> (UniqMap b -> IntMap b) -> UniqMap b -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    -- | Filter all elements in the map according to some predicate.
    filter :: (b -> Bool) -> UniqMap b -> UniqMap b
    filter :: forall b. (b -> Bool) -> UniqMap b -> UniqMap b
    filter b -> Bool
    p =
      IntMap b -> UniqMap b
    forall a. IntMap a -> UniqMap a
    UniqMap (IntMap b -> UniqMap b)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> Bool) -> IntMap b -> IntMap b
    forall a. (a -> Bool) -> IntMap a -> IntMap a
    IntMap.filter b -> Bool
    p (IntMap b -> IntMap b)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> IntMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    -- | Apply a function to all elements in the map, keeping those where the
    -- result is not @Nothing@.
    mapMaybe :: (a -> Maybe b) -> UniqMap a -> UniqMap b
    mapMaybe :: forall a b. (a -> Maybe b) -> UniqMap a -> UniqMap b
    mapMaybe a -> Maybe b
    f =
      IntMap b -> UniqMap b
    forall a. IntMap a -> UniqMap a
    UniqMap (IntMap b -> UniqMap b)
    -> (UniqMap a -> IntMap b) -> UniqMap a -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Maybe b) -> IntMap a -> IntMap b
    forall a b. (a -> Maybe b) -> IntMap a -> IntMap b
    IntMap.mapMaybe a -> Maybe b
    f (IntMap a -> IntMap b)
    -> (UniqMap a -> IntMap a) -> UniqMap a -> IntMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap a -> IntMap a
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    -- | Lazily right-fold over the map using the given function.
    foldrWithUnique :: (Unique -> a -> b -> b) -> b -> UniqMap a -> b
    foldrWithUnique :: forall a b. (Unique -> a -> b -> b) -> b -> UniqMap a -> b
    foldrWithUnique Unique -> a -> b -> b
    f b
    x =
      (Unique -> a -> b -> b) -> b -> IntMap a -> b
    forall a b. (Unique -> a -> b -> b) -> b -> IntMap a -> b
    IntMap.foldrWithKey Unique -> a -> b -> b
    f b
    x (IntMap a -> b) -> (UniqMap a -> IntMap a) -> UniqMap a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap a -> IntMap a
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    -- | Strictly left-fold over the map using the given function.
    foldlWithUnique' :: (b -> Unique -> a -> b) -> b -> UniqMap a -> b
    foldlWithUnique' :: forall b a. (b -> Unique -> a -> b) -> b -> UniqMap a -> b
    foldlWithUnique' b -> Unique -> a -> b
    f b
    x =
      (b -> Unique -> a -> b) -> b -> IntMap a -> b
    forall a b. (a -> Unique -> b -> a) -> a -> IntMap b -> a
    IntMap.foldlWithKey' b -> Unique -> a -> b
    f b
    x (IntMap a -> b) -> (UniqMap a -> IntMap a) -> UniqMap a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap a -> IntMap a
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    {-# SPECIALIZE delete :: Unique -> UniqMap b -> UniqMap b #-}
    -- | Delete the entry in the map indexed by the unique of the given value.
    delete :: Uniquable a => a -> UniqMap b -> UniqMap b
    delete :: forall a b. Uniquable a => a -> UniqMap b -> UniqMap b
    delete a
    k =
      IntMap b -> UniqMap b
    forall a. IntMap a -> UniqMap a
    UniqMap (IntMap b -> UniqMap b)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Unique -> IntMap b -> IntMap b
    forall a. Unique -> IntMap a -> IntMap a
    IntMap.delete (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) (IntMap b -> IntMap b)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> IntMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    -- | Delete all entries in the map indexed by the uniques of the given values.
    deleteMany :: Uniquable a => [a] -> UniqMap b -> UniqMap b
    deleteMany :: forall a b. Uniquable a => [a] -> UniqMap b -> UniqMap b
    deleteMany [a]
    ks UniqMap b
    xs =
      (UniqMap b -> a -> UniqMap b) -> UniqMap b -> [a] -> UniqMap b
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: Type -> Type) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    List.foldl' (\UniqMap b
    acc a
    k -> a -> UniqMap b -> UniqMap b
    forall a b. Uniquable a => a -> UniqMap b -> UniqMap b
    delete a
    k UniqMap b
    acc) UniqMap b
    xs [a]
    ks

    -- | Merge two unique maps, using the given combining funcion if a value with
    -- the same unique key exists in both maps.
    unionWith :: (b -> b -> b) -> UniqMap b -> UniqMap b -> UniqMap b
    unionWith :: forall b. (b -> b -> b) -> UniqMap b -> UniqMap b -> UniqMap b
    unionWith b -> b -> b
    f UniqMap b
    xs UniqMap b
    ys =
      IntMap b -> UniqMap b
    forall a. IntMap a -> UniqMap a
    UniqMap (((b -> b -> b) -> IntMap b -> IntMap b -> IntMap b
    forall a. (a -> a -> a) -> IntMap a -> IntMap a -> IntMap a
    IntMap.unionWith b -> b -> b
    f (IntMap b -> IntMap b -> IntMap b)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> UniqMap b -> IntMap b
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap) UniqMap b
    xs UniqMap b
    ys)

    -- | Filter the first map to only contain keys which are not in the second map.
    difference :: UniqMap b -> UniqMap b -> UniqMap b
    difference :: forall a. UniqMap a -> UniqMap a -> UniqMap a
    difference UniqMap b
    xs UniqMap b
    ys =
      IntMap b -> UniqMap b
    forall a. IntMap a -> UniqMap a
    UniqMap ((IntMap b -> IntMap b -> IntMap b
    forall a b. IntMap a -> IntMap b -> IntMap a
    IntMap.difference (IntMap b -> IntMap b -> IntMap b)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> UniqMap b -> IntMap b
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap) UniqMap b
    xs UniqMap b
    ys)

    -- | Check if there are no common keys between two maps.
    disjoint :: UniqMap b -> UniqMap b -> Bool
    disjoint :: forall b. UniqMap b -> UniqMap b -> Bool
    disjoint =
      IntMap b -> IntMap b -> Bool
    forall a b. IntMap a -> IntMap b -> Bool
    IntMap.disjoint (IntMap b -> IntMap b -> Bool)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> UniqMap b -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    -- | Check if one map is a submap of another.
    submap :: UniqMap b -> UniqMap b -> Bool
    submap :: forall b. UniqMap b -> UniqMap b -> Bool
    submap =
      -- We only check that the keys of the map make it a submap, the elements do
      -- not need to be equal. Maybe this should be changed?
      (b -> b -> Bool) -> IntMap b -> IntMap b -> Bool
    forall a b. (a -> b -> Bool) -> IntMap a -> IntMap b -> Bool
    IntMap.isSubmapOfBy (\b
    _ b
    _ -> Bool
    True) (IntMap b -> IntMap b -> Bool)
    -> (UniqMap b -> IntMap b) -> UniqMap b -> UniqMap b -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    {-# SPECIALIZE fromList :: [(Unique, b)] -> UniqMap b #-}
    -- | Convert a list of key-value pairs to a map.
    fromList :: Uniquable a => [(a, b)] -> UniqMap b
    fromList :: forall a b. Uniquable a => [(a, b)] -> UniqMap b
    fromList =
      IntMap b -> UniqMap b
    forall a. IntMap a -> UniqMap a
    UniqMap (IntMap b -> UniqMap b)
    -> ([(a, b)] -> IntMap b) -> [(a, b)] -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [(Unique, b)] -> IntMap b
    forall a. [(Unique, a)] -> IntMap a
    IntMap.fromList ([(Unique, b)] -> IntMap b)
    -> ([(a, b)] -> [(Unique, b)]) -> [(a, b)] -> IntMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((a, b) -> (Unique, b)) -> [(a, b)] -> [(Unique, b)]
    forall a b. (a -> b) -> [a] -> [b]
    forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((a -> Unique) -> (a, b) -> (Unique, b)
    forall a b c. (a -> b) -> (a, c) -> (b, c)
    forall (p :: Type -> Type -> Type) a b c.
    Bifunctor p =>
    (a -> b) -> p a c -> p b c
    first a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique)

    -- | Convert a map to a list of unique-value pairs.
    toList :: UniqMap b -> [(Unique, b)]
    toList :: forall b. UniqMap b -> [(Unique, b)]
    toList =
      IntMap b -> [(Unique, b)]
    forall a. IntMap a -> [(Unique, a)]
    IntMap.toList (IntMap b -> [(Unique, b)])
    -> (UniqMap b -> IntMap b) -> UniqMap b -> [(Unique, b)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    -- | Get the unique keys of a map.
    keys :: UniqMap b -> [Unique]
    keys :: forall b. UniqMap b -> [Unique]
    keys =
      IntMap b -> [Unique]
    forall a. IntMap a -> [Unique]
    IntMap.keys (IntMap b -> [Unique])
    -> (UniqMap b -> IntMap b) -> UniqMap b -> [Unique]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap

    -- | Get the values of a map.
    elems :: UniqMap b -> [b]
    elems :: forall a. UniqMap a -> [a]
    elems =
      IntMap b -> [b]
    forall a. IntMap a -> [a]
    IntMap.elems (IntMap b -> [b]) -> (UniqMap b -> IntMap b) -> UniqMap b -> [b]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> IntMap b
    forall a. UniqMap a -> IntMap a
    uniqMapToIntMap