    {-
    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

    #if MIN_VERSION_ghc(9,8,4) || (MIN_VERSION_ghc(9,6,7) && !MIN_VERSION_ghc(9,8,0))
    #define UNIQUE_IS_WORD64
    #endif

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

    import           Control.DeepSeq (NFData)
    import           Data.Binary (Binary (..))
    import           Data.Bifunctor (first)
    import           Data.Function (on)
    #ifdef UNIQUE_IS_WORD64
    import           GHC.Data.Word64Map.Strict (Word64Map)
    import qualified GHC.Data.Word64Map.Strict as IntMap
    #else
    import           Data.IntMap.Strict (IntMap)
    import qualified Data.IntMap.Strict as IntMap
    #endif
    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
    #ifdef UNIQUE_IS_WORD64
      = UniqMap { forall a. UniqMap a -> Word64Map a
    uniqMapToIntMap :: Word64Map a }
    #else
      = UniqMap { uniqMapToIntMap :: IntMap a }
    #endif
      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
        ( (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 -> Int)
    -> (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 -> Int
    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 -> Int)
    -> (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 -> Int
    length :: forall a. UniqMap a -> Int
    $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
        , Int -> UniqMap a -> ShowS
    [UniqMap a] -> ShowS
    UniqMap a -> String
    (Int -> UniqMap a -> ShowS)
    -> (UniqMap a -> String)
    -> ([UniqMap a] -> ShowS)
    -> Show (UniqMap a)
    forall a. Show a => Int -> UniqMap a -> ShowS
    forall a. Show a => [UniqMap a] -> ShowS
    forall a. Show a => UniqMap a -> String
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: forall a. Show a => Int -> UniqMap a -> ShowS
    showsPrec :: Int -> 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
        )
    #ifdef UNIQUE_IS_WORD64
    instance Binary a => Binary (UniqMap a) where
      put :: UniqMap a -> Put
    put (UniqMap Word64Map a
    m) = Int -> Put
    forall t. Binary t => t -> Put
    put (Word64Map a -> Int
    forall a. Word64Map a -> Int
    IntMap.size Word64Map a
    m) Put -> Put -> Put
    forall a. Semigroup a => a -> a -> a
    <> ((Unique, a) -> Put) -> [(Unique, a)] -> Put
    forall (t :: Type -> Type) (m :: Type -> Type) a b.
    (Foldable t, Monad m) =>
    (a -> m b) -> t a -> m ()
    mapM_ (Unique, a) -> Put
    forall t. Binary t => t -> Put
    put (Word64Map a -> [(Unique, a)]
    forall a. Word64Map a -> [(Unique, a)]
    IntMap.toAscList Word64Map a
    m)
      get :: Get (UniqMap a)
    get             = ([(Unique, a)] -> UniqMap a)
    -> Get [(Unique, a)] -> Get (UniqMap a)
    forall a b. (a -> b) -> Get a -> Get b
    forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
    fmap (Word64Map a -> UniqMap a
    forall a. Word64Map a -> UniqMap a
    UniqMap (Word64Map a -> UniqMap a)
    -> ([(Unique, a)] -> Word64Map a) -> [(Unique, a)] -> UniqMap a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [(Unique, a)] -> Word64Map a
    forall a. [(Unique, a)] -> Word64Map a
    IntMap.fromDistinctAscList) Get [(Unique, a)]
    forall t. Binary t => Get t
    get
    #else
      deriving newtype Binary
    #endif

    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 =
      Word64Map a -> UniqMap a
    forall a. Word64Map a -> UniqMap a
    UniqMap Word64Map a
    forall a. Word64Map 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 =
      Word64Map b -> UniqMap b
    forall a. Word64Map a -> UniqMap a
    UniqMap (Unique -> b -> Word64Map b
    forall a. Unique -> a -> Word64Map 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 =
      Word64Map a -> Bool
    forall a. Word64Map a -> Bool
    IntMap.null (Word64Map a -> Bool)
    -> (UniqMap a -> Word64Map a) -> UniqMap a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap a -> Word64Map a
    forall a. UniqMap a -> Word64Map 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 =
      Word64Map b -> UniqMap b
    forall a. Word64Map a -> UniqMap a
    UniqMap (Word64Map b -> UniqMap b)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Unique -> b -> Word64Map b -> Word64Map b
    forall a. Unique -> a -> Word64Map a -> Word64Map a
    IntMap.insert (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) b
    v (Word64Map b -> Word64Map b)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> Word64Map b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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 =
      Word64Map b -> UniqMap b
    forall a. Word64Map a -> UniqMap a
    UniqMap (Word64Map b -> UniqMap b)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> b -> b) -> Unique -> b -> Word64Map b -> Word64Map b
    forall a.
    (a -> a -> a) -> Unique -> a -> Word64Map a -> Word64Map a
    IntMap.insertWith b -> b -> b
    f (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) b
    v (Word64Map b -> Word64Map b)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> Word64Map b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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 -> Word64Map b -> Maybe b
    forall a. Unique -> Word64Map a -> Maybe a
    IntMap.lookup (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) (Word64Map b -> Maybe b)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> Maybe b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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 -> Word64Map b -> b
    forall a. a -> Unique -> Word64Map a -> a
    IntMap.findWithDefault b
    forall {a}. a
    notFound (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) (Word64Map b -> b) -> (UniqMap b -> Word64Map b) -> UniqMap b -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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 -> Word64Map b -> Bool
    forall a. Unique -> Word64Map a -> Bool
    IntMap.member (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) (Word64Map b -> Bool)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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 -> Word64Map b -> Bool
    forall a. Unique -> Word64Map a -> Bool
    IntMap.notMember (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) (Word64Map b -> Bool)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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 =
      Word64Map b -> UniqMap b
    forall a. Word64Map a -> UniqMap a
    UniqMap (Word64Map b -> UniqMap b)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> Bool) -> Word64Map b -> Word64Map b
    forall a. (a -> Bool) -> Word64Map a -> Word64Map a
    IntMap.filter b -> Bool
    p (Word64Map b -> Word64Map b)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> Word64Map b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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 =
      Word64Map b -> UniqMap b
    forall a. Word64Map a -> UniqMap a
    UniqMap (Word64Map b -> UniqMap b)
    -> (UniqMap a -> Word64Map b) -> UniqMap a -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Maybe b) -> Word64Map a -> Word64Map b
    forall a b. (a -> Maybe b) -> Word64Map a -> Word64Map b
    IntMap.mapMaybe a -> Maybe b
    f (Word64Map a -> Word64Map b)
    -> (UniqMap a -> Word64Map a) -> UniqMap a -> Word64Map b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap a -> Word64Map a
    forall a. UniqMap a -> Word64Map 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 -> Word64Map a -> b
    forall a b. (Unique -> a -> b -> b) -> b -> Word64Map a -> b
    IntMap.foldrWithKey Unique -> a -> b -> b
    f b
    x (Word64Map a -> b) -> (UniqMap a -> Word64Map a) -> UniqMap a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap a -> Word64Map a
    forall a. UniqMap a -> Word64Map 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 -> Word64Map a -> b
    forall a b. (a -> Unique -> b -> a) -> a -> Word64Map b -> a
    IntMap.foldlWithKey' b -> Unique -> a -> b
    f b
    x (Word64Map a -> b) -> (UniqMap a -> Word64Map a) -> UniqMap a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap a -> Word64Map a
    forall a. UniqMap a -> Word64Map 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 =
      Word64Map b -> UniqMap b
    forall a. Word64Map a -> UniqMap a
    UniqMap (Word64Map b -> UniqMap b)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Unique -> Word64Map b -> Word64Map b
    forall a. Unique -> Word64Map a -> Word64Map a
    IntMap.delete (a -> Unique
    forall a. Uniquable a => a -> Unique
    getUnique a
    k) (Word64Map b -> Word64Map b)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> Word64Map b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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 =
      Word64Map b -> UniqMap b
    forall a. Word64Map a -> UniqMap a
    UniqMap (((b -> b -> b) -> Word64Map b -> Word64Map b -> Word64Map b
    forall a.
    (a -> a -> a) -> Word64Map a -> Word64Map a -> Word64Map a
    IntMap.unionWith b -> b -> b
    f (Word64Map b -> Word64Map b -> Word64Map b)
    -> (UniqMap b -> Word64Map b)
    -> UniqMap b
    -> UniqMap b
    -> Word64Map b
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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 =
      Word64Map b -> UniqMap b
    forall a. Word64Map a -> UniqMap a
    UniqMap ((Word64Map b -> Word64Map b -> Word64Map b
    forall a b. Word64Map a -> Word64Map b -> Word64Map a
    IntMap.difference (Word64Map b -> Word64Map b -> Word64Map b)
    -> (UniqMap b -> Word64Map b)
    -> UniqMap b
    -> UniqMap b
    -> Word64Map b
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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 =
      Word64Map b -> Word64Map b -> Bool
    forall a b. Word64Map a -> Word64Map b -> Bool
    IntMap.disjoint (Word64Map b -> Word64Map b -> Bool)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> UniqMap b -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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) -> Word64Map b -> Word64Map b -> Bool
    forall a b. (a -> b -> Bool) -> Word64Map a -> Word64Map b -> Bool
    IntMap.isSubmapOfBy (\b
    _ b
    _ -> Bool
    True) (Word64Map b -> Word64Map b -> Bool)
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> UniqMap b -> Bool
    forall b c a. (b -> b -> c) -> (a -> b) -> a -> a -> c
    `on` UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map 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 =
      Word64Map b -> UniqMap b
    forall a. Word64Map a -> UniqMap a
    UniqMap (Word64Map b -> UniqMap b)
    -> ([(a, b)] -> Word64Map b) -> [(a, b)] -> UniqMap b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [(Unique, b)] -> Word64Map b
    forall a. [(Unique, a)] -> Word64Map a
    IntMap.fromList ([(Unique, b)] -> Word64Map b)
    -> ([(a, b)] -> [(Unique, b)]) -> [(a, b)] -> Word64Map 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 =
      Word64Map b -> [(Unique, b)]
    forall a. Word64Map a -> [(Unique, a)]
    IntMap.toList (Word64Map b -> [(Unique, b)])
    -> (UniqMap b -> Word64Map b) -> UniqMap b -> [(Unique, b)]
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . UniqMap b -> Word64Map b
    forall a. UniqMap a -> Word64Map a
    uniqMapToIntMap

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

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