{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeFamilies #-}

{-# OPTIONS_GHC -O2 #-}
module Data.Map.Unboxed.Lifted
  ( Map(..) -- TODO: use an internal module for this
  , empty
  , singleton
  , lookup
  , size
  , map
  , mapMaybe
  , mapMaybeWithKey
  , mapWithKey
  , keys
  , intersectionWith
  , intersectionsWith
  , restrict
  , appendWithKey
    -- * Folds
  , foldrWithKey
  , foldlWithKey'
  , foldrWithKey'
  , foldMapWithKey
  , foldMapWithKey'
    -- * Monadic Folds
  , foldlWithKeyM'
  , foldrWithKeyM'
  , foldlMapWithKeyM'
  , foldrMapWithKeyM'
    -- * Traversals
  , traverse
  , traverseWithKey
  , traverseWithKey_
    -- * List Conversion
  , toList
  , fromList
  , fromListAppend
  , fromListN
  , fromListAppendN
  , fromSet
  , elems
    -- * Array Conversion
  , unsafeFreezeZip
  ) where

import Prelude hiding (lookup,map,traverse)

import Control.DeepSeq (NFData)
import Control.Monad.ST (ST)
import Data.List.NonEmpty (NonEmpty)
import Data.Primitive (PrimArray,Array,MutablePrimArray,MutableArray)
import Data.Primitive.Types (Prim)
import Data.Semigroup (Semigroup)
import Data.Set.Unboxed.Internal (Set(..))

import qualified Control.DeepSeq
import qualified Data.Map.Internal as I
import qualified Data.Semigroup as SG
import qualified GHC.Exts as E

-- | A map from keys @k@ to values @v@. The key type must have a
--   'Prim' instance and the value type is unconstrained.
newtype Map k v = Map (I.Map PrimArray Array k v)

-- | This fails the functor laws since fmap is strict.
instance Prim k => Functor (Map k) where
  fmap :: forall a b. (a -> b) -> Map k a -> Map k b
fmap = forall k v w. Prim k => (v -> w) -> Map k v -> Map k w
map

instance (Prim k, NFData k, NFData v) => NFData (Map k v) where
  rnf :: Map k v -> ()
rnf (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, NFData k, NFData v) =>
Map karr varr k v -> ()
I.rnf Map PrimArray Array k v
m

instance (Prim k, Ord k, Semigroup v) => Semigroup (Map k v) where
  Map Map PrimArray Array k v
x <> :: Map k v -> Map k v -> Map k v
<> Map Map PrimArray Array k v
y = forall k v. Map PrimArray Array k v -> Map k v
Map (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k, Semigroup v) =>
Map karr varr k v -> Map karr varr k v -> Map karr varr k v
I.append Map PrimArray Array k v
x Map PrimArray Array k v
y)

instance (Prim k, Ord k, Semigroup v) => Monoid (Map k v) where
  mempty :: Map k v
mempty = forall k v. Map PrimArray Array k v -> Map k v
Map forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, ContiguousU varr) =>
Map karr varr k v
I.empty
  mappend :: Map k v -> Map k v -> Map k v
mappend = forall a. Semigroup a => a -> a -> a
(SG.<>)
  mconcat :: [Map k v] -> Map k v
mconcat = forall k v. Map PrimArray Array k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Semigroup v) =>
[Map karr varr k v] -> Map karr varr k v
I.concat forall b c a. (b -> c) -> (a -> b) -> a -> c
. coerce :: forall a b. Coercible a b => a -> b
E.coerce

instance (Prim k, Eq k, Eq v) => Eq (Map k v) where
  Map Map PrimArray Array k v
x == :: Map k v -> Map k v -> Bool
== Map Map PrimArray Array k v
y = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Eq k, ContiguousU varr,
 Element varr v, Eq v) =>
Map karr varr k v -> Map karr varr k v -> Bool
I.equals Map PrimArray Array k v
x Map PrimArray Array k v
y

instance (Prim k, Ord k, Ord v) => Ord (Map k v) where
  compare :: Map k v -> Map k v -> Ordering
compare (Map Map PrimArray Array k v
x) (Map Map PrimArray Array k v
y) = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Ord v) =>
Map karr varr k v -> Map karr varr k v -> Ordering
I.compare Map PrimArray Array k v
x Map PrimArray Array k v
y

instance (Prim k, Ord k) => E.IsList (Map k v) where
  type Item (Map k v) = (k,v)
  fromListN :: Int -> [Item (Map k v)] -> Map k v
fromListN Int
n = forall k v. Map PrimArray Array k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Int -> [(k, v)] -> Map karr varr k v
I.fromListN Int
n
  fromList :: [Item (Map k v)] -> Map k v
fromList = forall k v. Map PrimArray Array k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
[(k, v)] -> Map karr varr k v
I.fromList
  toList :: Map k v -> [Item (Map k v)]
toList (Map Map PrimArray Array k v
s) = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
Map karr varr k v -> [(k, v)]
I.toList Map PrimArray Array k v
s

instance (Prim k, Show k, Show v) => Show (Map k v) where
  showsPrec :: Int -> Map k v -> ShowS
showsPrec Int
p (Map Map PrimArray Array k v
s) = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Show k, ContiguousU varr,
 Element varr v, Show v) =>
Int -> Map karr varr k v -> ShowS
I.showsPrec Int
p Map PrimArray Array k v
s

-- | /O(log n)/ Lookup the value at a key in the map.
lookup :: (Prim k, Ord k) => k -> Map k v -> Maybe v
lookup :: forall k v. (Prim k, Ord k) => k -> Map k v -> Maybe v
lookup k
a (Map Map PrimArray Array k v
s) = forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
k -> Map karr varr k v -> Maybe v
I.lookup k
a Map PrimArray Array k v
s

-- | The empty map.
empty :: Map k v
empty :: forall k v. Map k v
empty = forall k v. Map PrimArray Array k v -> Map k v
Map forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, ContiguousU varr) =>
Map karr varr k v
I.empty

-- | /O(1)/ Create a map with a single element.
singleton :: Prim k => k -> v -> Map k v
singleton :: forall k v. Prim k => k -> v -> Map k v
singleton k
k v
v = forall k v. Map PrimArray Array k v -> Map k v
Map (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
k -> v -> Map karr varr k v
I.singleton k
k v
v)

-- | /O(n)/ A list of key-value pairs in ascending order.
toList :: (Prim k, Ord k) => Map k v -> [(k,v)]
toList :: forall k v. (Prim k, Ord k) => Map k v -> [(k, v)]
toList (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
Map karr varr k v -> [(k, v)]
I.toList Map PrimArray Array k v
m

-- | /O(n*log n)/ Create a map from a list of key-value pairs.
-- If the list contains more than one value for the same key,
-- the last value is retained. If the keys in the argument are
-- in nondescending order, this algorithm runs in /O(n)/ time instead.
fromList :: (Prim k, Ord k) => [(k,v)] -> Map k v
fromList :: forall k v. (Prim k, Ord k) => [(k, v)] -> Map k v
fromList = forall k v. Map PrimArray Array k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
[(k, v)] -> Map karr varr k v
I.fromList

-- | /O(n*log n)/ This function has the same behavior as 'fromList'
-- regardless of whether or not the expected size is accurate. Additionally,
-- negative sizes are handled correctly. The expected size is used as the
-- size of the initially allocated buffer when building the 'Map'. If the
-- keys in the argument are in nondescending order, this algorithm runs
-- in /O(n)/ time.
fromListN :: (Prim k, Ord k)
  => Int -- ^ expected size of resulting 'Map'
  -> [(k,v)] -- ^ key-value pairs
  -> Map k v
fromListN :: forall k v. (Prim k, Ord k) => Int -> [(k, v)] -> Map k v
fromListN Int
n = forall k v. Map PrimArray Array k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Int -> [(k, v)] -> Map karr varr k v
I.fromListN Int
n

-- | /O(n*log n)/ This function has the same behavior as 'fromList',
-- but it combines values with the 'Semigroup' instances instead of
-- choosing the last occurrence.
fromListAppend :: (Prim k, Ord k, Semigroup v) => [(k,v)] -> Map k v
fromListAppend :: forall k v. (Prim k, Ord k, Semigroup v) => [(k, v)] -> Map k v
fromListAppend = forall k v. Map PrimArray Array k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Semigroup v) =>
[(k, v)] -> Map karr varr k v
I.fromListAppend

-- | /O(n*log n)/ This function has the same behavior as 'fromListN',
-- but it combines values with the 'Semigroup' instances instead of
-- choosing the last occurrence.
fromListAppendN :: (Prim k, Ord k, Semigroup v)
  => Int -- ^ expected size of resulting 'Map'
  -> [(k,v)] -- ^ key-value pairs
  -> Map k v
fromListAppendN :: forall k v.
(Prim k, Ord k, Semigroup v) =>
Int -> [(k, v)] -> Map k v
fromListAppendN Int
n = forall k v. Map PrimArray Array k v -> Map k v
Map forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v, Semigroup v) =>
Int -> [(k, v)] -> Map karr varr k v
I.fromListAppendN Int
n

-- | /O(n)/ Build a map from a set. This function is uses the underlying
-- array that backs the set as the array for the keys. It constructs the
-- values by applying the given function to each key.
fromSet :: Prim k
  => (k -> v)
  -> Set k
  -> Map k v
fromSet :: forall k v. Prim k => (k -> v) -> Set k -> Map k v
fromSet k -> v
f (Set Set PrimArray k
s) = forall k v. Map PrimArray Array k v -> Map k v
Map (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v) -> Set karr k -> Map karr varr k v
I.fromSet k -> v
f Set PrimArray k
s)

-- | /O(1)/ The number of elements in the map.
size :: Map k v -> Int
size :: forall k v. Map k v -> Int
size (Map Map PrimArray Array k v
m) = forall (varr :: * -> *) v (karr :: * -> *) k.
(ContiguousU varr, Element varr v) =>
Map karr varr k v -> Int
I.size Map PrimArray Array k v
m

-- | /O(n)/ Map over the values in the map.
map :: Prim k
  => (v -> w)
  -> Map k v
  -> Map k w
map :: forall k v w. Prim k => (v -> w) -> Map k v -> Map k w
map v -> w
f (Map Map PrimArray Array k v
m) = forall k v. Map PrimArray Array k v -> Map k v
Map (forall (varr :: * -> *) (warr :: * -> *) v w (karr :: * -> *) k.
(ContiguousU varr, ContiguousU warr, Element varr v,
 Element warr w) =>
(v -> w) -> Map karr varr k v -> Map karr warr k w
I.map v -> w
f Map PrimArray Array k v
m)

-- | /O(n)/ Drop elements for which the predicate returns 'Nothing'.
mapMaybe :: Prim k
  => (v -> Maybe w)
  -> Map k v
  -> Map k w
mapMaybe :: forall k v w. Prim k => (v -> Maybe w) -> Map k v -> Map k w
mapMaybe v -> Maybe w
f (Map Map PrimArray Array k v
m) = forall k v. Map PrimArray Array k v -> Map k v
Map (forall (karr :: * -> *) (varr :: * -> *) k v w.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(v -> Maybe w) -> Map karr varr k v -> Map karr varr k w
I.mapMaybe v -> Maybe w
f Map PrimArray Array k v
m)

-- | /O(n)/ Drop elements for which the predicate returns 'Nothing'.
-- The predicate is given access to the key.
mapMaybeWithKey :: Prim k
  => (k -> v -> Maybe w)
  -> Map k v
  -> Map k w
mapMaybeWithKey :: forall k v w. Prim k => (k -> v -> Maybe w) -> Map k v -> Map k w
mapMaybeWithKey k -> v -> Maybe w
f (Map Map PrimArray Array k v
m) = forall k v. Map PrimArray Array k v -> Map k v
Map (forall (karr :: * -> *) (varr :: * -> *) k v w.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(k -> v -> Maybe w) -> Map karr varr k v -> Map karr varr k w
I.mapMaybeWithKey k -> v -> Maybe w
f Map PrimArray Array k v
m)

-- | /O(n)/ Map over the elements with access to their corresponding keys.
mapWithKey :: Prim k
  => (k -> v -> w)
  -> Map k v
  -> Map k w
mapWithKey :: forall k v w. Prim k => (k -> v -> w) -> Map k v -> Map k w
mapWithKey k -> v -> w
f (Map Map PrimArray Array k v
m) = forall k v. Map PrimArray Array k v -> Map k v
Map (forall (karr :: * -> *) (varr :: * -> *) k v w.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(k -> v -> w) -> Map karr varr k v -> Map karr varr k w
I.mapWithKey k -> v -> w
f Map PrimArray Array k v
m)

appendWithKey :: (Prim k, Ord k)
  => (k -> v -> v -> v)
  -> Map k v
  -> Map k v
  -> Map k v
appendWithKey :: forall k v.
(Prim k, Ord k) =>
(k -> v -> v -> v) -> Map k v -> Map k v -> Map k v
appendWithKey k -> v -> v -> v
f (Map Map PrimArray Array k v
m) (Map Map PrimArray Array k v
n) = forall k v. Map PrimArray Array k v -> Map k v
Map (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k) =>
(k -> v -> v -> v)
-> Map karr varr k v -> Map karr varr k v -> Map karr varr k v
I.appendWithKey k -> v -> v -> v
f Map PrimArray Array k v
m Map PrimArray Array k v
n)

-- | /O(n)/ traversal over the values in the map.
traverse :: (Applicative f, Prim k)
  => (v -> f b)
  -> Map k v
  -> f (Map k b)
traverse :: forall (f :: * -> *) k v b.
(Applicative f, Prim k) =>
(v -> f b) -> Map k v -> f (Map k b)
traverse v -> f b
f (Map Map PrimArray Array k v
m) = forall k v. Map PrimArray Array k v -> Map k v
Map forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (m :: * -> *) (karr :: * -> *) k (varr :: * -> *) v w.
(Applicative m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr w) =>
(v -> m w) -> Map karr varr k v -> m (Map karr varr k w)
I.traverse v -> f b
f Map PrimArray Array k v
m

-- | /O(n)/ traversal over the values in the map, using the keys.
traverseWithKey :: (Applicative f, Prim k)
  => (k -> v -> f b)
  -> Map k v
  -> f (Map k b)
traverseWithKey :: forall (f :: * -> *) k v b.
(Applicative f, Prim k) =>
(k -> v -> f b) -> Map k v -> f (Map k b)
traverseWithKey k -> v -> f b
f (Map Map PrimArray Array k v
m) = forall k v. Map PrimArray Array k v -> Map k v
Map forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (karr :: * -> *) k (varr :: * -> *) v v' (f :: * -> *).
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Element varr v', Applicative f) =>
(k -> v -> f v') -> Map karr varr k v -> f (Map karr varr k v')
I.traverseWithKey k -> v -> f b
f Map PrimArray Array k v
m

-- | /O(n)/ like 'traverseWithKey', but discards the results.
traverseWithKey_ :: (Applicative f, Prim k)
  => (k -> v -> f b)
  -> Map k v
  -> f ()
traverseWithKey_ :: forall (f :: * -> *) k v b.
(Applicative f, Prim k) =>
(k -> v -> f b) -> Map k v -> f ()
traverseWithKey_ k -> v -> f b
f (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Applicative m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> m b) -> Map karr varr k v -> m ()
I.traverseWithKey_ k -> v -> f b
f Map PrimArray Array k v
m

-- | /O(n)/ Left monadic fold over the keys and values of the map. This fold
-- is strict in the accumulator.
foldlWithKeyM' :: (Monad m, Prim k)
  => (b -> k -> v -> m b)
  -> b
  -> Map k v
  -> m b
foldlWithKeyM' :: forall (m :: * -> *) k b v.
(Monad m, Prim k) =>
(b -> k -> v -> m b) -> b -> Map k v -> m b
foldlWithKeyM' b -> k -> v -> m b
f b
b0 (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(b -> k -> v -> m b) -> b -> Map karr varr k v -> m b
I.foldlWithKeyM' b -> k -> v -> m b
f b
b0 Map PrimArray Array k v
m

-- | /O(n)/ Right monadic fold over the keys and values of the map. This fold
-- is strict in the accumulator.
foldrWithKeyM' :: (Monad m, Prim k)
  => (k -> v -> b -> m b)
  -> b
  -> Map k v
  -> m b
foldrWithKeyM' :: forall (m :: * -> *) k v b.
(Monad m, Prim k) =>
(k -> v -> b -> m b) -> b -> Map k v -> m b
foldrWithKeyM' k -> v -> b -> m b
f b
b0 (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> b -> m b) -> b -> Map karr varr k v -> m b
I.foldrWithKeyM' k -> v -> b -> m b
f b
b0 Map PrimArray Array k v
m

-- | /O(n)/ Monadic left fold over the keys and values of the map with a strict
-- monoidal accumulator. The monoidal accumulator is appended to the left
-- after each reduction.
foldlMapWithKeyM' :: (Monad m, Monoid b, Prim k)
  => (k -> v -> m b)
  -> Map k v
  -> m b
foldlMapWithKeyM' :: forall (m :: * -> *) b k v.
(Monad m, Monoid b, Prim k) =>
(k -> v -> m b) -> Map k v -> m b
foldlMapWithKeyM' k -> v -> m b
f (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Monoid b) =>
(k -> v -> m b) -> Map karr varr k v -> m b
I.foldlMapWithKeyM' k -> v -> m b
f Map PrimArray Array k v
m

-- | /O(n)/ Monadic right fold over the keys and values of the map with a strict
-- monoidal accumulator. The monoidal accumulator is appended to the right
-- after each reduction.
foldrMapWithKeyM' :: (Monad m, Monoid b, Prim k)
  => (k -> v -> m b) -- ^ reduction
  -> Map k v -- ^ map
  -> m b
foldrMapWithKeyM' :: forall (m :: * -> *) b k v.
(Monad m, Monoid b, Prim k) =>
(k -> v -> m b) -> Map k v -> m b
foldrMapWithKeyM' k -> v -> m b
f (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v (m :: * -> *) b.
(Monad m, ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Monoid b) =>
(k -> v -> m b) -> Map karr varr k v -> m b
I.foldrMapWithKeyM' k -> v -> m b
f Map PrimArray Array k v
m

-- | /O(n)/ Left fold over the keys and values with a strict accumulator.
foldlWithKey' :: Prim k
  => (b -> k -> v -> b) -- ^ reduction
  -> b -- ^ initial accumulator
  -> Map k v -- ^ map
  -> b
foldlWithKey' :: forall k b v. Prim k => (b -> k -> v -> b) -> b -> Map k v -> b
foldlWithKey' b -> k -> v -> b
f b
b0 (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v b.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(b -> k -> v -> b) -> b -> Map karr varr k v -> b
I.foldlWithKey' b -> k -> v -> b
f b
b0 Map PrimArray Array k v
m

-- | /O(n)/ Right fold over the keys and values with a lazy accumulator.
foldrWithKey :: Prim k
  => (k -> v -> b -> b) -- ^ reduction
  -> b -- ^ initial accumulator
  -> Map k v -- ^ map
  -> b
foldrWithKey :: forall k v b. Prim k => (k -> v -> b -> b) -> b -> Map k v -> b
foldrWithKey k -> v -> b -> b
f b
b0 (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) k (varr :: * -> *) v b.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> b -> b) -> b -> Map karr varr k v -> b
I.foldrWithKey k -> v -> b -> b
f b
b0 Map PrimArray Array k v
m

-- | /O(n)/ Right fold over the keys and values with a strict accumulator.
foldrWithKey' :: Prim k
  => (k -> v -> b -> b) -- ^ reduction
  -> b -- ^ initial accumulator
  -> Map k v -- ^ map
  -> b
foldrWithKey' :: forall k v b. Prim k => (k -> v -> b -> b) -> b -> Map k v -> b
foldrWithKey' k -> v -> b -> b
f b
b0 (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v b.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v) =>
(k -> v -> b -> b) -> b -> Map karr varr k v -> b
I.foldrWithKey' k -> v -> b -> b
f b
b0 Map PrimArray Array k v
m

-- | /O(n)/ Fold over the keys and values of the map with a lazy monoidal
-- accumulator. This function does not have left and right variants since
-- the associativity required by a monoid instance means that both variants
-- would always produce the same result.
foldMapWithKey :: (Monoid b, Prim k)
  => (k -> v -> b)
  -> Map k v
  -> b
foldMapWithKey :: forall b k v. (Monoid b, Prim k) => (k -> v -> b) -> Map k v -> b
foldMapWithKey k -> v -> b
f (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) k (varr :: * -> *) v m.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Monoid m) =>
(k -> v -> m) -> Map karr varr k v -> m
I.foldMapWithKey k -> v -> b
f Map PrimArray Array k v
m

-- | /O(n)/ Fold over the keys and values of the map with a strict monoidal
-- accumulator. This function does not have left and right variants since
-- the associativity required by a monoid instance means that both variants
-- would always produce the same result.
foldMapWithKey' :: (Monoid b, Prim k)
  => (k -> v -> b)
  -> Map k v
  -> b
foldMapWithKey' :: forall b k v. (Monoid b, Prim k) => (k -> v -> b) -> Map k v -> b
foldMapWithKey' k -> v -> b
f (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v m.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Monoid m) =>
(k -> v -> m) -> Map karr varr k v -> m
I.foldMapWithKey' k -> v -> b
f Map PrimArray Array k v
m

-- | /O(n*log n)/ Zip an array of keys with an array of values. If they are
-- not the same length, the longer one will be truncated to match the shorter
-- one. This function sorts and deduplicates the array of keys, preserving the
-- last value associated with each key. The argument arrays may not be
-- reused after being passed to this function.
--
-- This is by far the fastest way to create a map, since the functions backing it
-- are aggressively specialized. It internally uses a hybrid of mergesort and
-- insertion sort provided by the @primitive-sort@ package. It generates much
-- less garbage than any of the @fromList@ variants. 
unsafeFreezeZip :: (Ord k, Prim k)
  => MutablePrimArray s k
  -> MutableArray s v
  -> ST s (Map k v)
unsafeFreezeZip :: forall k s v.
(Ord k, Prim k) =>
MutablePrimArray s k -> MutableArray s v -> ST s (Map k v)
unsafeFreezeZip MutablePrimArray s k
theKeys MutableArray s v
vals = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall k v. Map PrimArray Array k v -> Map k v
Map (forall (karr :: * -> *) k (varr :: * -> *) v s.
(ContiguousU karr, Element karr k, Ord k, ContiguousU varr,
 Element varr v) =>
Mutable karr s k -> Mutable varr s v -> ST s (Map karr varr k v)
I.unsafeFreezeZip MutablePrimArray s k
theKeys MutableArray s v
vals)

-- | /O(1)/ Get the keys from the map.
keys :: Map k v -> Set k
keys :: forall k v. Map k v -> Set k
keys (Map Map PrimArray Array k v
m) = forall a. Set PrimArray a -> Set a
Set (forall (karr :: * -> *) (varr :: * -> *) k v.
Map karr varr k v -> Set karr k
I.keys Map PrimArray Array k v
m)

intersectionWith :: (Prim k, Ord k)
  => (a -> b -> c)
  -> Map k a
  -> Map k b
  -> Map k c
intersectionWith :: forall k a b c.
(Prim k, Ord k) =>
(a -> b -> c) -> Map k a -> Map k b -> Map k c
intersectionWith a -> b -> c
f (Map Map PrimArray Array k a
a) (Map Map PrimArray Array k b
b) = forall k v. Map PrimArray Array k v -> Map k v
Map (forall k v w x (karr :: * -> *) (varr :: * -> *) (warr :: * -> *)
       (xarr :: * -> *).
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, ContiguousU warr, Element warr w, ContiguousU xarr,
 Element xarr x, Ord k) =>
(v -> w -> x)
-> Map karr varr k v -> Map karr warr k w -> Map karr xarr k x
I.intersectionWith a -> b -> c
f Map PrimArray Array k a
a Map PrimArray Array k b
b)

-- | Take the intersection of all of the maps, combining elements at
-- equal keys with the provided function. Since intersection of maps lacks an
-- identity, this is provided with a non-empty list.
intersectionsWith :: (Prim k, Ord k)
  => (v -> v -> v)
  -> NonEmpty (Map k v)
  -> Map k v
intersectionsWith :: forall k v.
(Prim k, Ord k) =>
(v -> v -> v) -> NonEmpty (Map k v) -> Map k v
intersectionsWith v -> v -> v
f NonEmpty (Map k v)
xs = forall k v. Map PrimArray Array k v -> Map k v
Map (forall (karr :: * -> *) k (varr :: * -> *) v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k) =>
(v -> v -> v) -> NonEmpty (Map karr varr k v) -> Map karr varr k v
I.intersectionsWith v -> v -> v
f (coerce :: forall a b. Coercible a b => a -> b
E.coerce NonEmpty (Map k v)
xs))

restrict :: (Prim k, Ord k)
  => Map k v
  -> Set k
  -> Map k v
restrict :: forall k v. (Prim k, Ord k) => Map k v -> Set k -> Map k v
restrict (Map Map PrimArray Array k v
m) (Set Set PrimArray k
s) = forall k v. Map PrimArray Array k v -> Map k v
Map (forall (karr :: * -> *) (varr :: * -> *) k v.
(ContiguousU karr, Element karr k, ContiguousU varr,
 Element varr v, Ord k) =>
Map karr varr k v -> Set karr k -> Map karr varr k v
I.restrict Map PrimArray Array k v
m Set PrimArray k
s)

-- | /O(1)/ The values in a map. This is a zero-cost operation.
elems :: Map k v -> Array v
elems :: forall k v. Map k v -> Array v
elems (Map Map PrimArray Array k v
m) = forall (karr :: * -> *) (varr :: * -> *) k v.
Map karr varr k v -> varr v
I.elems Map PrimArray Array k v
m