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