-- |
-- Description : Fast, mutable sparse sets.
-- Copyright   : (c) Jeremy Nuttall, 2025
-- License     : BSD-3-Clause
-- Maintainer  : jeremy@jeremy-nuttall.com
-- Stability   : experimental
-- Portability : GHC
--
-- Generic mutable sparse sets, usable in any state transformer monad.
--
-- __This implementation is NOT thread-safe.__ Thread safety must be maintained by a whole-set
-- locking mechanism.
module Data.SparseSet.Generic.Mutable (
  MutableSparseSet,

  -- * Creation
  withCapacity,
  new,

  -- * Read
  length,
  contains,
  members,
  lookup,

  -- * Update
  insert,
  delete,
  clear,
  compact,

  -- * Iteration
  foldM,
  ifoldM,
  mapM_,
  imapM_,
  ifoldIntersectionM,
)
where

import Control.Monad hiding (foldM, foldM_, mapM_)
import Control.Monad.Primitive
import Data.Primitive
import Data.Typeable (Typeable)
import Data.Vector.Generic qualified as VG
import Data.Vector.Generic.Mutable qualified as MVG
import Data.Vector.Primitive.Mutable qualified as MVP
import GHC.Generics (Generic)
import Prelude hiding (length, lookup, mapM_)

import Data.SparseSet.Generic.Mutable.Internal.GrowVec (GrowVec)
import Data.SparseSet.Generic.Mutable.Internal.GrowVec qualified as GrowVec
import Data.SparseSet.Generic.Mutable.Internal.MutableSparseArray (MutableSparseArray)
import Data.SparseSet.Generic.Mutable.Internal.MutableSparseArray qualified as MSA
import Data.Vector.Internal.Check (HasCallStack)

data MutableSparseSet v s a = MutableSparseSet
  { forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssDense :: {-# UNPACK #-} !(MutVar s (GrowVec v s a))
  , forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssIndices :: {-# UNPACK #-} !(MutVar s (GrowVec MVP.MVector s Int))
  , forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssSparse :: {-# UNPACK #-} !(MutVar s (MutableSparseArray s))
  }
  deriving ((forall x.
 MutableSparseSet v s a -> Rep (MutableSparseSet v s a) x)
-> (forall x.
    Rep (MutableSparseSet v s a) x -> MutableSparseSet v s a)
-> Generic (MutableSparseSet v s a)
forall x. Rep (MutableSparseSet v s a) x -> MutableSparseSet v s a
forall x. MutableSparseSet v s a -> Rep (MutableSparseSet v s a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall (v :: * -> * -> *) s a x.
Rep (MutableSparseSet v s a) x -> MutableSparseSet v s a
forall (v :: * -> * -> *) s a x.
MutableSparseSet v s a -> Rep (MutableSparseSet v s a) x
$cfrom :: forall (v :: * -> * -> *) s a x.
MutableSparseSet v s a -> Rep (MutableSparseSet v s a) x
from :: forall x. MutableSparseSet v s a -> Rep (MutableSparseSet v s a) x
$cto :: forall (v :: * -> * -> *) s a x.
Rep (MutableSparseSet v s a) x -> MutableSparseSet v s a
to :: forall x. Rep (MutableSparseSet v s a) x -> MutableSparseSet v s a
Generic, Typeable)

-- | Create a sparse set with a given dense and sparse capacity
--
-- It's a good idea to use this function if you have an estimate of your data requirements,
-- as it can prevent costly re-allocations as the set grows.
--
-- @since 0.1.0.0
withCapacity
  :: forall a v m
   . (PrimMonad m, MVG.MVector v a)
  => Int
  -- ^ Capacity for the dense set
  -> Int
  -- ^ Capacity for the sparse set
  -> m (MutableSparseSet v (PrimState m) a)
withCapacity :: forall a (v :: * -> * -> *) (m :: * -> *).
(PrimMonad m, MVector v a) =>
Int -> Int -> m (MutableSparseSet v (PrimState m) a)
withCapacity Int
dc Int
sc =
  MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> MutableSparseSet v (PrimState m) a
forall (v :: * -> * -> *) s a.
MutVar s (GrowVec v s a)
-> MutVar s (GrowVec MVector s Int)
-> MutVar s (MutableSparseArray s)
-> MutableSparseSet v s a
MutableSparseSet
    (MutVar (PrimState m) (GrowVec v (PrimState m) a)
 -> MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
 -> MutVar (PrimState m) (MutableSparseArray (PrimState m))
 -> MutableSparseSet v (PrimState m) a)
-> m (MutVar (PrimState m) (GrowVec v (PrimState m) a))
-> m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
      -> MutVar (PrimState m) (MutableSparseArray (PrimState m))
      -> MutableSparseSet v (PrimState m) a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (GrowVec v (PrimState m) a
-> m (MutVar (PrimState m) (GrowVec v (PrimState m) a))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar (GrowVec v (PrimState m) a
 -> m (MutVar (PrimState m) (GrowVec v (PrimState m) a)))
-> m (GrowVec v (PrimState m) a)
-> m (MutVar (PrimState m) (GrowVec v (PrimState m) a))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Int -> m (GrowVec v (PrimState m) a)
forall a (v :: * -> * -> *) (m :: * -> *).
(PrimMonad m, MVector v a) =>
Int -> m (GrowVec v (PrimState m) a)
GrowVec.withCapacity Int
dc)
    m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
   -> MutVar (PrimState m) (MutableSparseArray (PrimState m))
   -> MutableSparseSet v (PrimState m) a)
-> m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int))
-> m (MutVar (PrimState m) (MutableSparseArray (PrimState m))
      -> MutableSparseSet v (PrimState m) a)
forall a b. m (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (GrowVec MVector (PrimState m) Int
-> m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar (GrowVec MVector (PrimState m) Int
 -> m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)))
-> m (GrowVec MVector (PrimState m) Int)
-> m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Int -> m (GrowVec MVector (PrimState m) Int)
forall a (v :: * -> * -> *) (m :: * -> *).
(PrimMonad m, MVector v a) =>
Int -> m (GrowVec v (PrimState m) a)
GrowVec.withCapacity Int
dc)
    m (MutVar (PrimState m) (MutableSparseArray (PrimState m))
   -> MutableSparseSet v (PrimState m) a)
-> m (MutVar (PrimState m) (MutableSparseArray (PrimState m)))
-> m (MutableSparseSet v (PrimState m) a)
forall a b. m (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (MutableSparseArray (PrimState m)
-> m (MutVar (PrimState m) (MutableSparseArray (PrimState m)))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar (MutableSparseArray (PrimState m)
 -> m (MutVar (PrimState m) (MutableSparseArray (PrimState m))))
-> m (MutableSparseArray (PrimState m))
-> m (MutVar (PrimState m) (MutableSparseArray (PrimState m)))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Int -> m (MutableSparseArray (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
Int -> m (MutableSparseArray (PrimState m))
MSA.withCapacity Int
sc)
{-# INLINE withCapacity #-}

-- | Create an empty sparse set with default capacities.
--
-- @since 0.1.0.0
new :: forall a v m. (PrimMonad m, MVG.MVector v a) => m (MutableSparseSet v (PrimState m) a)
new :: forall a (v :: * -> * -> *) (m :: * -> *).
(PrimMonad m, MVector v a) =>
m (MutableSparseSet v (PrimState m) a)
new =
  MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> MutableSparseSet v (PrimState m) a
forall (v :: * -> * -> *) s a.
MutVar s (GrowVec v s a)
-> MutVar s (GrowVec MVector s Int)
-> MutVar s (MutableSparseArray s)
-> MutableSparseSet v s a
MutableSparseSet
    (MutVar (PrimState m) (GrowVec v (PrimState m) a)
 -> MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
 -> MutVar (PrimState m) (MutableSparseArray (PrimState m))
 -> MutableSparseSet v (PrimState m) a)
-> m (MutVar (PrimState m) (GrowVec v (PrimState m) a))
-> m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
      -> MutVar (PrimState m) (MutableSparseArray (PrimState m))
      -> MutableSparseSet v (PrimState m) a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (GrowVec v (PrimState m) a
-> m (MutVar (PrimState m) (GrowVec v (PrimState m) a))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar (GrowVec v (PrimState m) a
 -> m (MutVar (PrimState m) (GrowVec v (PrimState m) a)))
-> m (GrowVec v (PrimState m) a)
-> m (MutVar (PrimState m) (GrowVec v (PrimState m) a))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< m (GrowVec v (PrimState m) a)
forall a (v :: * -> * -> *) (m :: * -> *).
(PrimMonad m, MVector v a) =>
m (GrowVec v (PrimState m) a)
GrowVec.new)
    m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
   -> MutVar (PrimState m) (MutableSparseArray (PrimState m))
   -> MutableSparseSet v (PrimState m) a)
-> m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int))
-> m (MutVar (PrimState m) (MutableSparseArray (PrimState m))
      -> MutableSparseSet v (PrimState m) a)
forall a b. m (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (GrowVec MVector (PrimState m) Int
-> m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar (GrowVec MVector (PrimState m) Int
 -> m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)))
-> m (GrowVec MVector (PrimState m) Int)
-> m (MutVar (PrimState m) (GrowVec MVector (PrimState m) Int))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< m (GrowVec MVector (PrimState m) Int)
forall a (v :: * -> * -> *) (m :: * -> *).
(PrimMonad m, MVector v a) =>
m (GrowVec v (PrimState m) a)
GrowVec.new)
    m (MutVar (PrimState m) (MutableSparseArray (PrimState m))
   -> MutableSparseSet v (PrimState m) a)
-> m (MutVar (PrimState m) (MutableSparseArray (PrimState m)))
-> m (MutableSparseSet v (PrimState m) a)
forall a b. m (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (MutableSparseArray (PrimState m)
-> m (MutVar (PrimState m) (MutableSparseArray (PrimState m)))
forall (m :: * -> *) a.
PrimMonad m =>
a -> m (MutVar (PrimState m) a)
newMutVar (MutableSparseArray (PrimState m)
 -> m (MutVar (PrimState m) (MutableSparseArray (PrimState m))))
-> m (MutableSparseArray (PrimState m))
-> m (MutVar (PrimState m) (MutableSparseArray (PrimState m)))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< m (MutableSparseArray (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
m (MutableSparseArray (PrimState m))
MSA.new)
{-# INLINE new #-}

-- | O(1) Number of elements in the set (dense)
--
-- @since 0.1.0.0
length :: forall a v m. (PrimMonad m) => MutableSparseSet v (PrimState m) a -> m Int
length :: forall a (v :: * -> * -> *) (m :: * -> *).
PrimMonad m =>
MutableSparseSet v (PrimState m) a -> m Int
length MutableSparseSet{MutVar (PrimState m) (GrowVec v (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} = GrowVec v (PrimState m) a -> Int
forall a (v :: * -> * -> *) s. GrowVec v s a -> Int
GrowVec.length (GrowVec v (PrimState m) a -> Int)
-> m (GrowVec v (PrimState m) a) -> m Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> m (GrowVec v (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense
{-# INLINE length #-}

-- | O(1) Check whether an element is in the set
--
-- @since 0.1.0.0
contains :: forall a v m. (PrimMonad m) => MutableSparseSet v (PrimState m) a -> Int -> m Bool
contains :: forall a (v :: * -> * -> *) (m :: * -> *).
PrimMonad m =>
MutableSparseSet v (PrimState m) a -> Int -> m Bool
contains MutableSparseSet{MutVar (PrimState m) (GrowVec v (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} Int
i = MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> m (MutableSparseArray (PrimState m))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssSparse m (MutableSparseArray (PrimState m))
-> (MutableSparseArray (PrimState m) -> m Bool) -> m Bool
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (MutableSparseArray (PrimState m) -> Int -> m Bool
forall (m :: * -> *).
PrimMonad m =>
MutableSparseArray (PrimState m) -> Int -> m Bool
`MSA.contains` Int
i)
{-# INLINE contains #-}

-- | O(n) The members of the set in an unspecified order.
--
-- @since 0.1.0.0
members
  :: forall w a v m. (VG.Vector v Int, PrimMonad m) => MutableSparseSet w (PrimState m) a -> m (v Int)
members :: forall (w :: * -> * -> *) a (v :: * -> *) (m :: * -> *).
(Vector v Int, PrimMonad m) =>
MutableSparseSet w (PrimState m) a -> m (v Int)
members MutableSparseSet{MutVar (PrimState m) (GrowVec w (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec w (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} = (Vector Int -> v Int) -> m (Vector Int) -> m (v Int)
forall a b. (a -> b) -> m a -> m b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Vector Int -> v Int
forall (v :: * -> *) a (w :: * -> *).
(Vector v a, Vector w a) =>
v a -> w a
VG.convert (m (Vector Int) -> m (v Int))
-> (GrowVec (Mutable Vector) (PrimState m) Int -> m (Vector Int))
-> GrowVec (Mutable Vector) (PrimState m) Int
-> m (v Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. GrowVec (Mutable Vector) (PrimState m) Int -> m (Vector Int)
forall (m :: * -> *) (v :: * -> *) a.
(PrimMonad m, Vector v a) =>
GrowVec (Mutable v) (PrimState m) a -> m (v a)
GrowVec.freeze (GrowVec (Mutable Vector) (PrimState m) Int -> m (v Int))
-> m (GrowVec (Mutable Vector) (PrimState m) Int) -> m (v Int)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MutVar (PrimState m) (GrowVec (Mutable Vector) (PrimState m) Int)
-> m (GrowVec (Mutable Vector) (PrimState m) Int)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec (Mutable Vector) (PrimState m) Int)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssIndices
{-# INLINE members #-}

-- | O(1) Look up an element in the set
--
-- @since 0.1.0.0
lookup
  :: forall a v m
   . (PrimMonad m, MVG.MVector v a)
  => MutableSparseSet v (PrimState m) a
  -> Int
  -> m (Maybe a)
lookup :: forall a (v :: * -> * -> *) (m :: * -> *).
(PrimMonad m, MVector v a) =>
MutableSparseSet v (PrimState m) a -> Int -> m (Maybe a)
lookup MutableSparseSet{MutVar (PrimState m) (GrowVec v (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} Int
i = do
  Maybe Int
mSi <- (MutableSparseArray (PrimState m) -> Int -> m (Maybe Int)
forall (m :: * -> *).
PrimMonad m =>
MutableSparseArray (PrimState m) -> Int -> m (Maybe Int)
`MSA.lookup` Int
i) (MutableSparseArray (PrimState m) -> m (Maybe Int))
-> m (MutableSparseArray (PrimState m)) -> m (Maybe Int)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> m (MutableSparseArray (PrimState m))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssSparse
  case Maybe Int
mSi of
    Just Int
si -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> m a -> m (Maybe a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> m (GrowVec v (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense m (GrowVec v (PrimState m) a)
-> (GrowVec v (PrimState m) a -> m a) -> m a
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (GrowVec v (PrimState m) a -> Int -> m a
forall a (m :: * -> *) (v :: * -> * -> *).
(PrimMonad m, MVector v a) =>
GrowVec v (PrimState m) a -> Int -> m a
`GrowVec.unsafeRead` Int
si))
    Maybe Int
Nothing -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
forall a. Maybe a
Nothing
{-# INLINE lookup #-}

-- | O(1) amortized. Insert a value for a given key.
--
-- If the key is already in the set, its value is overwritten.
--
-- __INVARIANT__: Keys cannot be negative. An unchecked exception is
-- thrown if a negative key is added to the set.
--
-- @since 0.1.0.0
insert
  :: forall a v m
   . (HasCallStack, PrimMonad m, MVG.MVector v a)
  => MutableSparseSet v (PrimState m) a
  -> Int
  -> a
  -> m ()
insert :: forall a (v :: * -> * -> *) (m :: * -> *).
(HasCallStack, PrimMonad m, MVector v a) =>
MutableSparseSet v (PrimState m) a -> Int -> a -> m ()
insert MutableSparseSet{MutVar (PrimState m) (GrowVec v (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} Int
i a
v
  | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
0 = [Char] -> m ()
forall a. HasCallStack => [Char] -> a
error ([Char] -> m ()) -> [Char] -> m ()
forall a b. (a -> b) -> a -> b
$ [Char]
"Key cannot be negative, got: " [Char] -> [Char] -> [Char]
forall a. Semigroup a => a -> a -> a
<> Int -> [Char]
forall a. Show a => a -> [Char]
show Int
i
  | Bool
otherwise =
      MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> m (MutableSparseArray (PrimState m))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssSparse m (MutableSparseArray (PrimState m))
-> (MutableSparseArray (PrimState m) -> m (Maybe Int))
-> m (Maybe Int)
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (MutableSparseArray (PrimState m) -> Int -> m (Maybe Int)
forall (m :: * -> *).
PrimMonad m =>
MutableSparseArray (PrimState m) -> Int -> m (Maybe Int)
`MSA.lookup` Int
i) m (Maybe Int) -> (Maybe Int -> m ()) -> m ()
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
        Just Int
di -> do
          GrowVec v (PrimState m) a
dense <- MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> m (GrowVec v (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense
          GrowVec v (PrimState m) a -> Int -> a -> m ()
forall a (m :: * -> *) (v :: * -> * -> *).
(PrimMonad m, MVector v a) =>
GrowVec v (PrimState m) a -> Int -> a -> m ()
GrowVec.unsafeWrite GrowVec v (PrimState m) a
dense Int
di a
v
        Maybe Int
Nothing -> do
          GrowVec v (PrimState m) a
dense <- MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> m (GrowVec v (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense
          MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> GrowVec v (PrimState m) a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense (GrowVec v (PrimState m) a -> m ())
-> m (GrowVec v (PrimState m) a) -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< GrowVec v (PrimState m) a -> a -> m (GrowVec v (PrimState m) a)
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
GrowVec v (PrimState m) a -> a -> m (GrowVec v (PrimState m) a)
GrowVec.snoc GrowVec v (PrimState m) a
dense a
v
          MutableSparseArray (PrimState m)
sparse <- MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> m (MutableSparseArray (PrimState m))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssSparse m (MutableSparseArray (PrimState m))
-> (MutableSparseArray (PrimState m)
    -> m (MutableSparseArray (PrimState m)))
-> m (MutableSparseArray (PrimState m))
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \MutableSparseArray (PrimState m)
arr -> MutableSparseArray (PrimState m)
-> Int -> Int -> m (MutableSparseArray (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
MutableSparseArray (PrimState m)
-> Int -> Int -> m (MutableSparseArray (PrimState m))
MSA.unsafeInsert MutableSparseArray (PrimState m)
arr Int
i (GrowVec v (PrimState m) a -> Int
forall a (v :: * -> * -> *) s. GrowVec v s a -> Int
GrowVec.length GrowVec v (PrimState m) a
dense)
          MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> MutableSparseArray (PrimState m) -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssSparse MutableSparseArray (PrimState m)
sparse
          MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> GrowVec MVector (PrimState m) Int -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssIndices (GrowVec MVector (PrimState m) Int -> m ())
-> m (GrowVec MVector (PrimState m) Int) -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< (GrowVec MVector (PrimState m) Int
-> Int -> m (GrowVec MVector (PrimState m) Int)
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
GrowVec v (PrimState m) a -> a -> m (GrowVec v (PrimState m) a)
`GrowVec.snoc` Int
i) (GrowVec MVector (PrimState m) Int
 -> m (GrowVec MVector (PrimState m) Int))
-> m (GrowVec MVector (PrimState m) Int)
-> m (GrowVec MVector (PrimState m) Int)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> m (GrowVec MVector (PrimState m) Int)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssIndices
{-# INLINE insert #-}

-- | O(1) Delete an element from the set
--
-- @since 0.1.0.0
delete
  :: forall a v m
   . (PrimMonad m, MVG.MVector v a)
  => MutableSparseSet v (PrimState m) a
  -> Int
  -> m (Maybe a)
delete :: forall a (v :: * -> * -> *) (m :: * -> *).
(PrimMonad m, MVector v a) =>
MutableSparseSet v (PrimState m) a -> Int -> m (Maybe a)
delete MutableSparseSet{MutVar (PrimState m) (GrowVec v (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} Int
i = do
  MutableSparseArray (PrimState m)
sparse <- MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> m (MutableSparseArray (PrimState m))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssSparse
  MutableSparseArray (PrimState m) -> Int -> m (Maybe Int)
forall (m :: * -> *).
PrimMonad m =>
MutableSparseArray (PrimState m) -> Int -> m (Maybe Int)
MSA.delete MutableSparseArray (PrimState m)
sparse Int
i m (Maybe Int) -> (Maybe Int -> m (Maybe a)) -> m (Maybe a)
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
    Just Int
di -> do
      GrowVec v (PrimState m) a
dense <- MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> m (GrowVec v (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense
      GrowVec MVector (PrimState m) Int
indices <- MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> m (GrowVec MVector (PrimState m) Int)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssIndices
      (a
value, GrowVec v (PrimState m) a
dense') <- GrowVec v (PrimState m) a
-> Int -> m (a, GrowVec v (PrimState m) a)
forall a (m :: * -> *) (v :: * -> * -> *).
(PrimMonad m, MVector v a) =>
GrowVec v (PrimState m) a
-> Int -> m (a, GrowVec v (PrimState m) a)
GrowVec.unsafeSwapRemove GrowVec v (PrimState m) a
dense Int
di
      MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> GrowVec v (PrimState m) a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense GrowVec v (PrimState m) a
dense'
      (Int
_, GrowVec MVector (PrimState m) Int
indices') <- GrowVec MVector (PrimState m) Int
-> Int -> m (Int, GrowVec MVector (PrimState m) Int)
forall a (m :: * -> *) (v :: * -> * -> *).
(PrimMonad m, MVector v a) =>
GrowVec v (PrimState m) a
-> Int -> m (a, GrowVec v (PrimState m) a)
GrowVec.unsafeSwapRemove GrowVec MVector (PrimState m) Int
indices Int
di
      MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> GrowVec MVector (PrimState m) Int -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssIndices GrowVec MVector (PrimState m) Int
indices'
      Bool -> m () -> m ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
unless (Int
di Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== GrowVec v (PrimState m) a -> Int
forall a (v :: * -> * -> *) s. GrowVec v s a -> Int
GrowVec.length GrowVec v (PrimState m) a
dense Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) do
        Int
swapped <- GrowVec MVector (PrimState m) Int -> Int -> m Int
forall a (m :: * -> *) (v :: * -> * -> *).
(PrimMonad m, MVector v a) =>
GrowVec v (PrimState m) a -> Int -> m a
GrowVec.unsafeRead GrowVec MVector (PrimState m) Int
indices' Int
di
        MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> MutableSparseArray (PrimState m) -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssSparse (MutableSparseArray (PrimState m) -> m ())
-> m (MutableSparseArray (PrimState m)) -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MutableSparseArray (PrimState m)
-> Int -> Int -> m (MutableSparseArray (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
MutableSparseArray (PrimState m)
-> Int -> Int -> m (MutableSparseArray (PrimState m))
MSA.unsafeInsert MutableSparseArray (PrimState m)
sparse Int
swapped Int
di
      Maybe a -> m (Maybe a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Maybe a -> m (Maybe a)) -> Maybe a -> m (Maybe a)
forall a b. (a -> b) -> a -> b
$ a -> Maybe a
forall a. a -> Maybe a
Just a
value
    Maybe Int
Nothing -> Maybe a -> m (Maybe a)
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure Maybe a
forall a. Maybe a
Nothing
{-# INLINE delete #-}

-- | O(n) Clear all elements from the set.
--
-- @since 0.1.0.0
clear :: forall a v m. (PrimMonad m) => MutableSparseSet v (PrimState m) a -> m ()
clear :: forall a (v :: * -> * -> *) (m :: * -> *).
PrimMonad m =>
MutableSparseSet v (PrimState m) a -> m ()
clear MutableSparseSet{MutVar (PrimState m) (GrowVec v (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} = do
  GrowVec MVector (PrimState m) Int
indices <- MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> m (GrowVec MVector (PrimState m) Int)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssIndices
  MutableSparseArray (PrimState m)
sparse <- MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> m (MutableSparseArray (PrimState m))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssSparse
  (Int -> m (Maybe Int)) -> GrowVec MVector (PrimState m) Int -> m ()
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(a -> m b) -> GrowVec v (PrimState m) a -> m ()
GrowVec.mapM_ (MutableSparseArray (PrimState m) -> Int -> m (Maybe Int)
forall (m :: * -> *).
PrimMonad m =>
MutableSparseArray (PrimState m) -> Int -> m (Maybe Int)
MSA.unsafeDelete MutableSparseArray (PrimState m)
sparse) GrowVec MVector (PrimState m) Int
indices

  MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> (GrowVec v (PrimState m) a -> (GrowVec v (PrimState m) a, ()))
-> m ()
forall (m :: * -> *) a b.
PrimMonad m =>
MutVar (PrimState m) a -> (a -> (a, b)) -> m b
atomicModifyMutVar' MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense ((,()) (GrowVec v (PrimState m) a -> (GrowVec v (PrimState m) a, ()))
-> (GrowVec v (PrimState m) a -> GrowVec v (PrimState m) a)
-> GrowVec v (PrimState m) a
-> (GrowVec v (PrimState m) a, ())
forall b c a. (b -> c) -> (a -> b) -> a -> c
. GrowVec v (PrimState m) a -> GrowVec v (PrimState m) a
forall a s (v :: * -> * -> *). GrowVec v s a -> GrowVec v s a
GrowVec.cleared)
  MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> (GrowVec MVector (PrimState m) Int
    -> (GrowVec MVector (PrimState m) Int, ()))
-> m ()
forall (m :: * -> *) a b.
PrimMonad m =>
MutVar (PrimState m) a -> (a -> (a, b)) -> m b
atomicModifyMutVar' MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssIndices ((,()) (GrowVec MVector (PrimState m) Int
 -> (GrowVec MVector (PrimState m) Int, ()))
-> (GrowVec MVector (PrimState m) Int
    -> GrowVec MVector (PrimState m) Int)
-> GrowVec MVector (PrimState m) Int
-> (GrowVec MVector (PrimState m) Int, ())
forall b c a. (b -> c) -> (a -> b) -> a -> c
. GrowVec MVector (PrimState m) Int
-> GrowVec MVector (PrimState m) Int
forall a s (v :: * -> * -> *). GrowVec v s a -> GrowVec v s a
GrowVec.cleared)
{-# INLINE clear #-}

-- | O(n) Shrink the capacity of the set to fit exactly the current number of elements.
--
-- @since 0.1.0.0
compact
  :: forall a v m. (PrimMonad m, MVG.MVector v a) => MutableSparseSet v (PrimState m) a -> m ()
compact :: forall a (v :: * -> * -> *) (m :: * -> *).
(PrimMonad m, MVector v a) =>
MutableSparseSet v (PrimState m) a -> m ()
compact MutableSparseSet{MutVar (PrimState m) (GrowVec v (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} = do
  MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> GrowVec v (PrimState m) a -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense (GrowVec v (PrimState m) a -> m ())
-> m (GrowVec v (PrimState m) a) -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< GrowVec v (PrimState m) a -> m (GrowVec v (PrimState m) a)
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
GrowVec v (PrimState m) a -> m (GrowVec v (PrimState m) a)
GrowVec.compact (GrowVec v (PrimState m) a -> m (GrowVec v (PrimState m) a))
-> m (GrowVec v (PrimState m) a) -> m (GrowVec v (PrimState m) a)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> m (GrowVec v (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense
  GrowVec MVector (PrimState m) Int
indices <- MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> m (GrowVec MVector (PrimState m) Int)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssIndices
  GrowVec MVector (PrimState m) Int
indices' <- GrowVec MVector (PrimState m) Int
-> m (GrowVec MVector (PrimState m) Int)
forall (v :: * -> * -> *) a (m :: * -> *).
(MVector v a, PrimMonad m) =>
GrowVec v (PrimState m) a -> m (GrowVec v (PrimState m) a)
GrowVec.compact GrowVec MVector (PrimState m) Int
indices
  MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> GrowVec MVector (PrimState m) Int -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssIndices GrowVec MVector (PrimState m) Int
indices'
  GrowVec MVector (PrimState m) Int -> m (Maybe Int)
forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a, Ord a, Bounded a) =>
GrowVec v (PrimState m) a -> m (Maybe a)
GrowVec.maximum GrowVec MVector (PrimState m) Int
indices m (Maybe Int) -> (Maybe Int -> m ()) -> m ()
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
    Maybe Int
Nothing -> () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
    Just Int
maxIndex -> do
      MutableSparseArray (PrimState m)
sparse <- MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> m (MutableSparseArray (PrimState m))
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssSparse
      MutVar (PrimState m) (MutableSparseArray (PrimState m))
-> MutableSparseArray (PrimState m) -> m ()
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> a -> m ()
writeMutVar MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssSparse (MutableSparseArray (PrimState m) -> m ())
-> m (MutableSparseArray (PrimState m)) -> m ()
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< MutableSparseArray (PrimState m)
-> Int -> m (MutableSparseArray (PrimState m))
forall (m :: * -> *).
PrimMonad m =>
MutableSparseArray (PrimState m)
-> Int -> m (MutableSparseArray (PrimState m))
MSA.unsafeCompactTo MutableSparseArray (PrimState m)
sparse (Int
maxIndex Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
{-# INLINE compact #-}

-- | O(n) Iterate over the values of the set with an accumulator.
--
-- @since 0.1.0.0
foldM
  :: (PrimMonad m, MVG.MVector v a)
  => (b -> a -> m b)
  -> b
  -> MutableSparseSet v (PrimState m) a
  -> m b
foldM :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> a -> m b) -> b -> MutableSparseSet v (PrimState m) a -> m b
foldM b -> a -> m b
f b
initAcc MutableSparseSet{MutVar (PrimState m) (GrowVec v (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} = do
  GrowVec v (PrimState m) a
denseGV <- MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> m (GrowVec v (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense
  let !len :: Int
len = GrowVec v (PrimState m) a -> Int
forall a (v :: * -> * -> *) s. GrowVec v s a -> Int
GrowVec.length GrowVec v (PrimState m) a
denseGV
      go :: Int -> b -> m b
go !Int
idx !b
acc
        | Int
idx Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
len = b -> m b
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure b
acc
        | Bool
otherwise = do
            a
component <- GrowVec v (PrimState m) a -> Int -> m a
forall a (m :: * -> *) (v :: * -> * -> *).
(PrimMonad m, MVector v a) =>
GrowVec v (PrimState m) a -> Int -> m a
GrowVec.unsafeRead GrowVec v (PrimState m) a
denseGV Int
idx
            b
newAcc <- b -> a -> m b
f b
acc a
component
            Int -> b -> m b
go (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) b
newAcc

  Int -> b -> m b
go Int
0 b
initAcc
{-# INLINE foldM #-}

-- | O(n) Iterate over the keys and values of the set with an accumulator.
--
-- @since 0.1.0.0
ifoldM
  :: (PrimMonad m, MVG.MVector v a)
  => (b -> (Int, a) -> m b)
  -> b
  -> MutableSparseSet v (PrimState m) a
  -> m b
ifoldM :: forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> (Int, a) -> m b)
-> b -> MutableSparseSet v (PrimState m) a -> m b
ifoldM b -> (Int, a) -> m b
f b
initAcc MutableSparseSet{MutVar (PrimState m) (GrowVec v (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} = do
  GrowVec v (PrimState m) a
denseGV <- MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> m (GrowVec v (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense
  GrowVec MVector (PrimState m) Int
indicesGV <- MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> m (GrowVec MVector (PrimState m) Int)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssIndices
  let !len :: Int
len = GrowVec v (PrimState m) a -> Int
forall a (v :: * -> * -> *) s. GrowVec v s a -> Int
GrowVec.length GrowVec v (PrimState m) a
denseGV
      go :: Int -> b -> m b
go !Int
idx !b
acc
        | Int
idx Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
len = b -> m b
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure b
acc
        | Bool
otherwise = do
            Int
entity <- GrowVec MVector (PrimState m) Int -> Int -> m Int
forall a (m :: * -> *) (v :: * -> * -> *).
(PrimMonad m, MVector v a) =>
GrowVec v (PrimState m) a -> Int -> m a
GrowVec.unsafeRead GrowVec MVector (PrimState m) Int
indicesGV Int
idx
            a
component <- GrowVec v (PrimState m) a -> Int -> m a
forall a (m :: * -> *) (v :: * -> * -> *).
(PrimMonad m, MVector v a) =>
GrowVec v (PrimState m) a -> Int -> m a
GrowVec.unsafeRead GrowVec v (PrimState m) a
denseGV Int
idx
            b
newAcc <- b -> (Int, a) -> m b
f b
acc (Int
entity, a
component)
            Int -> b -> m b
go (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) b
newAcc

  Int -> b -> m b
go Int
0 b
initAcc
{-# INLINE ifoldM #-}

-- | O(n) Iterate over the values of the set.
--
-- @since 0.1.0.0
mapM_
  :: (PrimMonad m, MVG.MVector v a)
  => (a -> m ())
  -> MutableSparseSet v (PrimState m) a
  -> m ()
mapM_ :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
(a -> m ()) -> MutableSparseSet v (PrimState m) a -> m ()
mapM_ a -> m ()
f MutableSparseSet{MutVar (PrimState m) (GrowVec v (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} = do
  GrowVec v (PrimState m) a
denseGV <- MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> m (GrowVec v (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense
  let !len :: Int
len = GrowVec v (PrimState m) a -> Int
forall a (v :: * -> * -> *) s. GrowVec v s a -> Int
GrowVec.length GrowVec v (PrimState m) a
denseGV
      go :: Int -> m ()
go !Int
idx
        | Int
idx Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
len = () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
        | Bool
otherwise = do
            a
component <- GrowVec v (PrimState m) a -> Int -> m a
forall a (m :: * -> *) (v :: * -> * -> *).
(PrimMonad m, MVector v a) =>
GrowVec v (PrimState m) a -> Int -> m a
GrowVec.unsafeRead GrowVec v (PrimState m) a
denseGV Int
idx
            a -> m ()
f a
component
            Int -> m ()
go (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  Int -> m ()
go Int
0
{-# INLINE mapM_ #-}

-- | O(n) Iterate over the keys and values of the set.
--
-- @since 0.1.0.0
imapM_
  :: (PrimMonad m, MVG.MVector v a)
  => ((Int, a) -> m ())
  -> MutableSparseSet v (PrimState m) a
  -> m ()
imapM_ :: forall (m :: * -> *) (v :: * -> * -> *) a.
(PrimMonad m, MVector v a) =>
((Int, a) -> m ()) -> MutableSparseSet v (PrimState m) a -> m ()
imapM_ (Int, a) -> m ()
f MutableSparseSet{MutVar (PrimState m) (GrowVec v (PrimState m) a)
MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
MutVar (PrimState m) (MutableSparseArray (PrimState m))
ssDense :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec v s a)
ssIndices :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (GrowVec MVector s Int)
ssSparse :: forall (v :: * -> * -> *) s a.
MutableSparseSet v s a -> MutVar s (MutableSparseArray s)
ssDense :: MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssIndices :: MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssSparse :: MutVar (PrimState m) (MutableSparseArray (PrimState m))
..} = do
  GrowVec v (PrimState m) a
denseGV <- MutVar (PrimState m) (GrowVec v (PrimState m) a)
-> m (GrowVec v (PrimState m) a)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec v (PrimState m) a)
ssDense
  GrowVec MVector (PrimState m) Int
indicesGV <- MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
-> m (GrowVec MVector (PrimState m) Int)
forall (m :: * -> *) a.
PrimMonad m =>
MutVar (PrimState m) a -> m a
readMutVar MutVar (PrimState m) (GrowVec MVector (PrimState m) Int)
ssIndices
  let !len :: Int
len = GrowVec v (PrimState m) a -> Int
forall a (v :: * -> * -> *) s. GrowVec v s a -> Int
GrowVec.length GrowVec v (PrimState m) a
denseGV
      go :: Int -> m ()
go !Int
idx
        | Int
idx Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
len = () -> m ()
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ()
        | Bool
otherwise = do
            Int
entity <- GrowVec MVector (PrimState m) Int -> Int -> m Int
forall a (m :: * -> *) (v :: * -> * -> *).
(PrimMonad m, MVector v a) =>
GrowVec v (PrimState m) a -> Int -> m a
GrowVec.unsafeRead GrowVec MVector (PrimState m) Int
indicesGV Int
idx
            a
component <- GrowVec v (PrimState m) a -> Int -> m a
forall a (m :: * -> *) (v :: * -> * -> *).
(PrimMonad m, MVector v a) =>
GrowVec v (PrimState m) a -> Int -> m a
GrowVec.unsafeRead GrowVec v (PrimState m) a
denseGV Int
idx
            (Int, a) -> m ()
f (Int
entity, a
component)
            Int -> m ()
go (Int
idx Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)
  Int -> m ()
go Int
0
{-# INLINE imapM_ #-}

-- | O(min(n, m)) Iterate over the intersection of two sets with an accumulator.
--
-- The order of the arguments does not matter - the smaller of the two sets is
-- selected as the iteratee.
--
-- @since 0.1.0.0
ifoldIntersectionM
  :: (PrimMonad m, MVG.MVector v a, MVG.MVector v b)
  => (c -> Int -> a -> b -> m c)
  -- ^ Accumulator
  -> c
  -- ^ Initial value
  -> MutableSparseSet v (PrimState m) a
  -- ^ Set A
  -> MutableSparseSet v (PrimState m) b
  -- ^ Set B
  -> m c
ifoldIntersectionM :: forall (m :: * -> *) (v :: * -> * -> *) a b c.
(PrimMonad m, MVector v a, MVector v b) =>
(c -> Int -> a -> b -> m c)
-> c
-> MutableSparseSet v (PrimState m) a
-> MutableSparseSet v (PrimState m) b
-> m c
ifoldIntersectionM c -> Int -> a -> b -> m c
f c
c MutableSparseSet v (PrimState m) a
a MutableSparseSet v (PrimState m) b
b = do
  Int
la <- MutableSparseSet v (PrimState m) a -> m Int
forall a (v :: * -> * -> *) (m :: * -> *).
PrimMonad m =>
MutableSparseSet v (PrimState m) a -> m Int
length MutableSparseSet v (PrimState m) a
a
  Int
lb <- MutableSparseSet v (PrimState m) b -> m Int
forall a (v :: * -> * -> *) (m :: * -> *).
PrimMonad m =>
MutableSparseSet v (PrimState m) a -> m Int
length MutableSparseSet v (PrimState m) b
b

  if Int
la Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
lb
    then (c -> (Int, a) -> m c)
-> c -> MutableSparseSet v (PrimState m) a -> m c
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> (Int, a) -> m b)
-> b -> MutableSparseSet v (PrimState m) a -> m b
ifoldM (MutableSparseSet v (PrimState m) b -> c -> (Int, a) -> m c
forall {v :: * -> * -> *}.
MVector v b =>
MutableSparseSet v (PrimState m) b -> c -> (Int, a) -> m c
goLookupB MutableSparseSet v (PrimState m) b
b) c
c MutableSparseSet v (PrimState m) a
a
    else (c -> (Int, b) -> m c)
-> c -> MutableSparseSet v (PrimState m) b -> m c
forall (m :: * -> *) (v :: * -> * -> *) a b.
(PrimMonad m, MVector v a) =>
(b -> (Int, a) -> m b)
-> b -> MutableSparseSet v (PrimState m) a -> m b
ifoldM (MutableSparseSet v (PrimState m) a -> c -> (Int, b) -> m c
forall {v :: * -> * -> *}.
MVector v a =>
MutableSparseSet v (PrimState m) a -> c -> (Int, b) -> m c
goLookupA MutableSparseSet v (PrimState m) a
a) c
c MutableSparseSet v (PrimState m) b
b
 where
  goLookupB :: MutableSparseSet v (PrimState m) b -> c -> (Int, a) -> m c
goLookupB MutableSparseSet v (PrimState m) b
otherSetB c
acc (Int
entity, a
componentA) =
    MutableSparseSet v (PrimState m) b -> Int -> m (Maybe b)
forall a (v :: * -> * -> *) (m :: * -> *).
(PrimMonad m, MVector v a) =>
MutableSparseSet v (PrimState m) a -> Int -> m (Maybe a)
lookup MutableSparseSet v (PrimState m) b
otherSetB Int
entity m (Maybe b) -> (Maybe b -> m c) -> m c
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
      Maybe b
Nothing -> c -> m c
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure c
acc
      Just b
componentB -> c -> Int -> a -> b -> m c
f c
acc Int
entity a
componentA b
componentB

  goLookupA :: MutableSparseSet v (PrimState m) a -> c -> (Int, b) -> m c
goLookupA MutableSparseSet v (PrimState m) a
otherSetA c
acc (Int
entity, b
componentB) =
    MutableSparseSet v (PrimState m) a -> Int -> m (Maybe a)
forall a (v :: * -> * -> *) (m :: * -> *).
(PrimMonad m, MVector v a) =>
MutableSparseSet v (PrimState m) a -> Int -> m (Maybe a)
lookup MutableSparseSet v (PrimState m) a
otherSetA Int
entity m (Maybe a) -> (Maybe a -> m c) -> m c
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case
      Maybe a
Nothing -> c -> m c
forall a. a -> m a
forall (f :: * -> *) a. Applicative f => a -> f a
pure c
acc
      Just a
componentA -> c -> Int -> a -> b -> m c
f c
acc Int
entity a
componentA b
componentB
{-# INLINE ifoldIntersectionM #-}