{-
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 { 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
(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
    ( 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
    , 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
    )

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