{-
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)
#if MIN_VERSION_ghc(9,8,4)
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
#if MIN_VERSION_ghc(9,8,4)
  = UniqMap { uniqMapToIntMap :: Word64Map a }
#else
  = UniqMap { UniqMap a -> IntMap a
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
(a -> f b) -> UniqMap a -> f (UniqMap b)
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)
sequence :: UniqMap (m a) -> m (UniqMap a)
$csequence :: forall (m :: Type -> Type) a.
Monad m =>
UniqMap (m a) -> m (UniqMap a)
mapM :: (a -> m b) -> UniqMap a -> m (UniqMap b)
$cmapM :: forall (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> UniqMap a -> m (UniqMap b)
sequenceA :: UniqMap (f a) -> f (UniqMap a)
$csequenceA :: forall (f :: Type -> Type) a.
Applicative f =>
UniqMap (f a) -> f (UniqMap a)
traverse :: (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)
$cp2Traversable :: Foldable UniqMap
$cp1Traversable :: Functor UniqMap
Traversable
  deriving newtype
    ( a -> UniqMap a -> Bool
UniqMap m -> m
UniqMap a -> [a]
UniqMap a -> Bool
UniqMap a -> Int
UniqMap a -> a
UniqMap a -> a
UniqMap a -> a
UniqMap a -> a
(a -> m) -> UniqMap a -> m
(a -> m) -> UniqMap a -> m
(a -> b -> b) -> b -> UniqMap a -> b
(a -> b -> b) -> b -> UniqMap a -> b
(b -> a -> b) -> b -> UniqMap a -> b
(b -> a -> b) -> b -> UniqMap a -> b
(a -> a -> a) -> UniqMap a -> a
(a -> a -> a) -> UniqMap a -> a
(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
product :: UniqMap a -> a
$cproduct :: forall a. Num a => UniqMap a -> a
sum :: UniqMap a -> a
$csum :: forall a. Num a => UniqMap a -> a
minimum :: UniqMap a -> a
$cminimum :: forall a. Ord a => UniqMap a -> a
maximum :: UniqMap a -> a
$cmaximum :: forall a. Ord a => UniqMap a -> a
elem :: a -> UniqMap a -> Bool
$celem :: forall a. Eq a => a -> UniqMap a -> Bool
length :: UniqMap a -> Int
$clength :: forall a. UniqMap a -> Int
null :: UniqMap a -> Bool
$cnull :: forall a. UniqMap a -> Bool
toList :: UniqMap a -> [a]
$ctoList :: forall a. UniqMap a -> [a]
foldl1 :: (a -> a -> a) -> UniqMap a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> UniqMap a -> a
foldr1 :: (a -> a -> a) -> UniqMap a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> UniqMap a -> a
foldl' :: (b -> a -> b) -> b -> UniqMap a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> UniqMap a -> b
foldl :: (b -> a -> b) -> b -> UniqMap a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> UniqMap a -> b
foldr' :: (a -> b -> b) -> b -> UniqMap a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> UniqMap a -> b
foldr :: (a -> b -> b) -> b -> UniqMap a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> UniqMap a -> b
foldMap' :: (a -> m) -> UniqMap a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> UniqMap a -> m
foldMap :: (a -> m) -> UniqMap a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> UniqMap a -> m
fold :: UniqMap m -> m
$cfold :: forall m. Monoid m => UniqMap m -> m
Foldable
    , a -> UniqMap b -> UniqMap a
(a -> b) -> UniqMap a -> UniqMap b
(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
<$ :: a -> UniqMap b -> UniqMap a
$c<$ :: forall a b. a -> UniqMap b -> UniqMap a
fmap :: (a -> b) -> UniqMap a -> UniqMap b
$cfmap :: forall a b. (a -> b) -> UniqMap a -> UniqMap b
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
mconcat :: [UniqMap a] -> UniqMap a
$cmconcat :: forall a. [UniqMap a] -> UniqMap a
mappend :: UniqMap a -> UniqMap a -> UniqMap a
$cmappend :: forall a. UniqMap a -> UniqMap a -> UniqMap a
mempty :: UniqMap a
$cmempty :: forall a. UniqMap a
$cp1Monoid :: forall a. Semigroup (UniqMap a)
Monoid
    , UniqMap a -> ()
(UniqMap a -> ()) -> NFData (UniqMap a)
forall a. NFData a => UniqMap a -> ()
forall a. (a -> ()) -> NFData a
rnf :: UniqMap a -> ()
$crnf :: forall a. NFData a => UniqMap a -> ()
NFData
    , b -> UniqMap a -> UniqMap a
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
stimes :: b -> UniqMap a -> UniqMap a
$cstimes :: forall a b. Integral b => b -> UniqMap a -> UniqMap a
sconcat :: NonEmpty (UniqMap a) -> UniqMap a
$csconcat :: forall a. NonEmpty (UniqMap a) -> UniqMap a
<> :: UniqMap a -> UniqMap a -> UniqMap a
$c<> :: forall a. UniqMap a -> 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
showList :: [UniqMap a] -> ShowS
$cshowList :: forall a. Show a => [UniqMap a] -> ShowS
show :: UniqMap a -> String
$cshow :: forall a. Show a => UniqMap a -> String
showsPrec :: Int -> UniqMap a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> UniqMap a -> ShowS
Show
    )
#if MIN_VERSION_ghc(9,8,4)
instance Binary a => Binary (UniqMap a) where
  put (UniqMap m) = put (IntMap.size m) <> mapM_ put (IntMap.toAscList m)
  get             = fmap (UniqMap . IntMap.fromDistinctAscList) get
#else
  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
putList :: [UniqMap a] -> Put
$cputList :: forall a. Binary a => [UniqMap a] -> Put
get :: Get (UniqMap a)
$cget :: forall a. Binary a => Get (UniqMap a)
put :: UniqMap a -> Put
$cput :: forall a. Binary a => UniqMap a -> Put
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
$
      [ Int -> Doc ()
forall a. Pretty a => a -> Doc ()
fromPretty Int
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
      | (Int
k, a
v) <- UniqMap a -> [(Int, a)]
forall b. UniqMap b -> [(Int, b)]
toList UniqMap a
xs
      ]

-- | An empty map.
empty :: UniqMap a
empty :: 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 :: a -> b -> UniqMap b
singleton a
k b
v =
  IntMap b -> UniqMap b
forall a. IntMap a -> UniqMap a
UniqMap (Int -> b -> IntMap b
forall a. Int -> a -> IntMap a
IntMap.singleton (a -> Int
forall a. Uniquable a => a -> Int
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 :: a -> UniqMap a
singletonUnique a
v =
  Int -> a -> UniqMap a
forall a b. Uniquable a => a -> b -> UniqMap b
singleton (a -> Int
forall a. Uniquable a => a -> Int
getUnique a
v) a
v

-- | Check if the map is empty.
null :: UniqMap a -> Bool
null :: 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 :: 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
. Int -> b -> IntMap b -> IntMap b
forall a. Int -> a -> IntMap a -> IntMap a
IntMap.insert (a -> Int
forall a. Uniquable a => a -> Int
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 :: a -> UniqMap a -> UniqMap a
insertUnique a
v =
  Int -> a -> UniqMap a -> UniqMap a
forall a b. Uniquable a => a -> b -> UniqMap b -> UniqMap b
insert (a -> Int
forall a. Uniquable a => a -> Int
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 :: (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) -> Int -> b -> IntMap b -> IntMap b
forall a. (a -> a -> a) -> Int -> a -> IntMap a -> IntMap a
IntMap.insertWith b -> b -> b
f (a -> Int
forall a. Uniquable a => a -> Int
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 :: [(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 (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 :: a -> UniqMap b -> Maybe b
lookup a
k =
  Int -> IntMap b -> Maybe b
forall a. Int -> IntMap a -> Maybe a
IntMap.lookup (a -> Int
forall a. Uniquable a => a -> Int
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 :: 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
<> Int -> String
forall a. Show a => a -> String
show (a -> Int
forall a. Uniquable a => a -> Int
getUnique a
k) String -> ShowS
forall a. Semigroup a => a -> a -> a
<> String
" is not in the UniqMap")
   in b -> Int -> IntMap b -> b
forall a. a -> Int -> IntMap a -> a
IntMap.findWithDefault b
forall a. a
notFound (a -> Int
forall a. Uniquable a => a -> Int
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 :: a -> UniqMap b -> Bool
elem a
k =
  Int -> IntMap b -> Bool
forall a. Int -> IntMap a -> Bool
IntMap.member (a -> Int
forall a. Uniquable a => a -> Int
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 :: a -> UniqMap b -> Bool
notElem a
k =
  Int -> IntMap b -> Bool
forall a. Int -> IntMap a -> Bool
IntMap.notMember (a -> Int
forall a. Uniquable a => a -> Int
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 :: (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 :: (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 :: (Int -> a -> b -> b) -> b -> UniqMap a -> b
foldrWithUnique Int -> a -> b -> b
f b
x =
  (Int -> a -> b -> b) -> b -> IntMap a -> b
forall a b. (Int -> a -> b -> b) -> b -> IntMap a -> b
IntMap.foldrWithKey Int -> 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' :: (b -> Int -> a -> b) -> b -> UniqMap a -> b
foldlWithUnique' b -> Int -> a -> b
f b
x =
  (b -> Int -> a -> b) -> b -> IntMap a -> b
forall a b. (a -> Int -> b -> a) -> a -> IntMap b -> a
IntMap.foldlWithKey' b -> Int -> 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 :: 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
. Int -> IntMap b -> IntMap b
forall a. Int -> IntMap a -> IntMap a
IntMap.delete (a -> Int
forall a. Uniquable a => a -> Int
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 :: [a] -> UniqMap b -> UniqMap b
deleteMany [a]
ks UniqMap b
xs =
  (UniqMap b -> a -> UniqMap b) -> UniqMap b -> [a] -> UniqMap 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 :: (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 :: UniqMap b -> UniqMap b -> UniqMap b
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 :: 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 :: 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 :: [(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
. [(Int, b)] -> IntMap b
forall a. [(Int, a)] -> IntMap a
IntMap.fromList ([(Int, b)] -> IntMap b)
-> ([(a, b)] -> [(Int, b)]) -> [(a, b)] -> IntMap b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, b) -> (Int, b)) -> [(a, b)] -> [(Int, b)]
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> Int) -> (a, b) -> (Int, b)
forall (p :: Type -> Type -> Type) a b c.
Bifunctor p =>
(a -> b) -> p a c -> p b c
first a -> Int
forall a. Uniquable a => a -> Int
getUnique)

-- | Convert a map to a list of unique-value pairs.
toList :: UniqMap b -> [(Unique, b)]
toList :: UniqMap b -> [(Int, b)]
toList =
  IntMap b -> [(Int, b)]
forall a. IntMap a -> [(Int, a)]
IntMap.toList (IntMap b -> [(Int, b)])
-> (UniqMap b -> IntMap b) -> UniqMap b -> [(Int, 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 :: UniqMap b -> [Int]
keys =
  IntMap b -> [Int]
forall a. IntMap a -> [Int]
IntMap.keys (IntMap b -> [Int])
-> (UniqMap b -> IntMap b) -> UniqMap b -> [Int]
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 :: UniqMap b -> [b]
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