{-# LANGUAGE RecordWildCards #-}
module PureSAT.SparseSet (
    SparseSet (..),
    sizeofSparseSet,
    indexSparseSet,
    newSparseSet,
    memberSparseSet,
    insertSparseSet,
    deleteSparseSet,
    popSparseSet,
    popSparseSet_,
    elemsSparseSet,
    clearSparseSet,
) where

import Data.Primitive.PrimVar

import PureSAT.Prim
import PureSAT.Base

-- $setup
-- >>> import Control.Monad.ST (runST)

-- | https://research.swtch.com/sparse
--
-- An 'Int' set which support efficient popping ('popSparseSet').
--
data SparseSet s = SS
    { forall s. SparseSet s -> PrimVar s Int
size   :: {-# UNPACK #-} !(PrimVar s Int)
    , forall s. SparseSet s -> MutablePrimArray s Int
dense  :: {-# UNPACK #-} !(MutablePrimArray s Int)
    , forall s. SparseSet s -> MutablePrimArray s Int
sparse :: {-# UNPACK #-} !(MutablePrimArray s Int)
    }

_invariant :: SparseSet s -> ST s ()
_invariant :: forall s. SparseSet s -> ST s ()
_invariant SS {PrimVar s Int
MutablePrimArray s Int
size :: forall s. SparseSet s -> PrimVar s Int
dense :: forall s. SparseSet s -> MutablePrimArray s Int
sparse :: forall s. SparseSet s -> MutablePrimArray s Int
size :: PrimVar s Int
dense :: MutablePrimArray s Int
sparse :: MutablePrimArray s Int
..} = do
    Int
n         <- PrimVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimVar (PrimState m) a -> m a
readPrimVar PrimVar s Int
PrimVar (PrimState (ST s)) Int
size
    Int
capacity  <- MutablePrimArray (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> m Int
getSizeofMutablePrimArray MutablePrimArray s Int
MutablePrimArray (PrimState (ST s)) Int
dense
    Int
capacity' <- MutablePrimArray (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> m Int
getSizeofMutablePrimArray MutablePrimArray s Int
MutablePrimArray (PrimState (ST s)) Int
sparse

    String -> Bool -> ST s ()
forall s. HasCallStack => String -> Bool -> ST s ()
assertST String
"capacities" (Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
capacity Bool -> Bool -> Bool
&& Int
capacity Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
capacity')

    Int -> Int -> Int -> ST s ()
go Int
capacity Int
n Int
0
  where
    go :: Int -> Int -> Int -> ST s ()
go Int
capacity Int
n Int
i =
        if Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
n
        then () -> ST s ()
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return ()
        else do
            Int
x <- MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
dense Int
i
            String -> Bool -> ST s ()
forall s. HasCallStack => String -> Bool -> ST s ()
assertST String
"x < capacity" (Bool -> ST s ()) -> Bool -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
x Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
capacity
            Int
j <- MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
sparse Int
x
            String -> Bool -> ST s ()
forall s. HasCallStack => String -> Bool -> ST s ()
assertST String
"i == j" (Bool -> ST s ()) -> Bool -> ST s ()
forall a b. (a -> b) -> a -> b
$ Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j

            Int -> Int -> Int -> ST s ()
go Int
capacity Int
n (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)

checkInvariant :: SparseSet s -> ST s ()
-- checkInvariant = _invariant
checkInvariant :: forall s. SparseSet s -> ST s ()
checkInvariant SparseSet s
_ = () -> ST s ()
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return ()

-- | Create new sparse set
--
-- >>> runST $ newSparseSet 100 >>= elemsSparseSet
-- []
newSparseSet
    :: Int -- ^ max integer
    -> ST s (SparseSet s)
newSparseSet :: forall s. Int -> ST s (SparseSet s)
newSparseSet Int
capacity = do
    PrimVar s Int
size <- Int -> ST s (PrimVar (PrimState (ST s)) Int)
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
a -> m (PrimVar (PrimState m) a)
newPrimVar Int
0
    MutablePrimArray s Int
dense <- Int -> ST s (MutablePrimArray (PrimState (ST s)) Int)
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
Int -> m (MutablePrimArray (PrimState m) a)
newPrimArray Int
capacity
    MutablePrimArray s Int
sparse <- Int -> ST s (MutablePrimArray (PrimState (ST s)) Int)
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
Int -> m (MutablePrimArray (PrimState m) a)
newPrimArray Int
capacity
    SparseSet s -> ST s (SparseSet s)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return SS {PrimVar s Int
MutablePrimArray s Int
size :: PrimVar s Int
dense :: MutablePrimArray s Int
sparse :: MutablePrimArray s Int
size :: PrimVar s Int
dense :: MutablePrimArray s Int
sparse :: MutablePrimArray s Int
..}
    
indexSparseSet :: SparseSet s -> Int -> ST s Int
indexSparseSet :: forall s. SparseSet s -> Int -> ST s Int
indexSparseSet SS {PrimVar s Int
MutablePrimArray s Int
size :: forall s. SparseSet s -> PrimVar s Int
dense :: forall s. SparseSet s -> MutablePrimArray s Int
sparse :: forall s. SparseSet s -> MutablePrimArray s Int
size :: PrimVar s Int
dense :: MutablePrimArray s Int
sparse :: MutablePrimArray s Int
..} Int
i = MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
dense Int
i

-- | Size of sparse set.
--
-- >>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; sizeofSparseSet set }
-- 5
--
sizeofSparseSet :: SparseSet s -> ST s Int
sizeofSparseSet :: forall s. SparseSet s -> ST s Int
sizeofSparseSet SS {PrimVar s Int
MutablePrimArray s Int
size :: forall s. SparseSet s -> PrimVar s Int
dense :: forall s. SparseSet s -> MutablePrimArray s Int
sparse :: forall s. SparseSet s -> MutablePrimArray s Int
size :: PrimVar s Int
dense :: MutablePrimArray s Int
sparse :: MutablePrimArray s Int
..} = PrimVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimVar (PrimState m) a -> m a
readPrimVar PrimVar s Int
PrimVar (PrimState (ST s)) Int
size

-- | Test for membership
--
-- >>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; memberSparseSet set 10 }
-- False
--
-- >>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; memberSparseSet set 13 }
-- True
--
memberSparseSet :: SparseSet s -> Int -> ST s Bool
memberSparseSet :: forall s. SparseSet s -> Int -> ST s Bool
memberSparseSet set :: SparseSet s
set@SS {PrimVar s Int
MutablePrimArray s Int
size :: forall s. SparseSet s -> PrimVar s Int
dense :: forall s. SparseSet s -> MutablePrimArray s Int
sparse :: forall s. SparseSet s -> MutablePrimArray s Int
size :: PrimVar s Int
dense :: MutablePrimArray s Int
sparse :: MutablePrimArray s Int
..} Int
x = do
    SparseSet s -> ST s ()
forall s. SparseSet s -> ST s ()
checkInvariant SparseSet s
set

    Int
n <- PrimVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimVar (PrimState m) a -> m a
readPrimVar PrimVar s Int
PrimVar (PrimState (ST s)) Int
size
    Int
i <- MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
sparse Int
x
    if Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n
    then do
        Int
x' <- MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
dense Int
i
        Bool -> ST s Bool
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
x' Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
x)
    else Bool -> ST s Bool
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False

-- | Insert into set
--
-- >>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; elemsSparseSet set }
-- [3,5,7,11,13]
--
insertSparseSet :: SparseSet s -> Int -> ST s ()
insertSparseSet :: forall s. SparseSet s -> Int -> ST s ()
insertSparseSet set :: SparseSet s
set@SS {PrimVar s Int
MutablePrimArray s Int
size :: forall s. SparseSet s -> PrimVar s Int
dense :: forall s. SparseSet s -> MutablePrimArray s Int
sparse :: forall s. SparseSet s -> MutablePrimArray s Int
size :: PrimVar s Int
dense :: MutablePrimArray s Int
sparse :: MutablePrimArray s Int
..} Int
x = do
    SparseSet s -> ST s ()
forall s. SparseSet s -> ST s ()
checkInvariant SparseSet s
set

    Int
n <- PrimVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimVar (PrimState m) a -> m a
readPrimVar PrimVar s Int
PrimVar (PrimState (ST s)) Int
size
    Int
i <- MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
sparse Int
x
    if Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n
    then do
        Int
x' <- MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
dense Int
i
        if Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
x' then () -> ST s ()
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return () else Int -> ST s ()
insert Int
n
    else Int -> ST s ()
insert Int
n
  where
    {-# INLINE insert #-}
    insert :: Int -> ST s ()
insert Int
n = do
        MutablePrimArray s Int -> Int -> Int -> ST s ()
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> a -> ST s ()
writePrimArray MutablePrimArray s Int
dense Int
n Int
x
        MutablePrimArray s Int -> Int -> Int -> ST s ()
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> a -> ST s ()
writePrimArray MutablePrimArray s Int
sparse Int
x Int
n
        PrimVar (PrimState (ST s)) Int -> Int -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimVar (PrimState m) a -> a -> m ()
writePrimVar PrimVar s Int
PrimVar (PrimState (ST s)) Int
size (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1)

-- | Delete from set
--
-- >>> runST $ do { set <- newSparseSet 100; deleteSparseSet set 10; elemsSparseSet set }
-- []
--
-- >>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; deleteSparseSet set 10; elemsSparseSet set }
-- [3,5,7,11,13]
--
-- >>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; deleteSparseSet set 13; elemsSparseSet set }
-- [3,5,7,11]
--
-- >>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; deleteSparseSet set 11; elemsSparseSet set }
-- [3,5,7,13]
--
deleteSparseSet :: SparseSet s -> Int -> ST s ()
deleteSparseSet :: forall s. SparseSet s -> Int -> ST s ()
deleteSparseSet set :: SparseSet s
set@SS {PrimVar s Int
MutablePrimArray s Int
size :: forall s. SparseSet s -> PrimVar s Int
dense :: forall s. SparseSet s -> MutablePrimArray s Int
sparse :: forall s. SparseSet s -> MutablePrimArray s Int
size :: PrimVar s Int
dense :: MutablePrimArray s Int
sparse :: MutablePrimArray s Int
..} Int
x = do
    SparseSet s -> ST s ()
forall s. SparseSet s -> ST s ()
checkInvariant SparseSet s
set

    Int
n <- PrimVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimVar (PrimState m) a -> m a
readPrimVar PrimVar s Int
PrimVar (PrimState (ST s)) Int
size
    Int
i <- MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
sparse Int
x
    if Int
0 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
i Bool -> Bool -> Bool
&& Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n
    then do
        Int
x' <- MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
dense Int
i
        if Int
x Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
x' then Int -> Int -> ST s ()
delete Int
i Int
n else () -> ST s ()
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return ()
    else () -> ST s ()
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return ()
  where
    {-# INLINE delete #-}
    delete :: Int -> Int -> ST s ()
delete Int
i Int
n = do
        PrimVar (PrimState (ST s)) Int -> Int -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimVar (PrimState m) a -> a -> m ()
writePrimVar PrimVar s Int
PrimVar (PrimState (ST s)) Int
size (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)
        MutablePrimArray s Int
-> MutablePrimArray s Int -> Int -> Int -> Int -> ST s ()
forall s.
MutablePrimArray s Int
-> MutablePrimArray s Int -> Int -> Int -> Int -> ST s ()
swap MutablePrimArray s Int
dense MutablePrimArray s Int
sparse Int
i Int
x (Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)

{-# INLINE swap #-}
swap :: MutablePrimArray s Int -> MutablePrimArray s Int -> Int -> Int -> Int -> ST s ()
swap :: forall s.
MutablePrimArray s Int
-> MutablePrimArray s Int -> Int -> Int -> Int -> ST s ()
swap !MutablePrimArray s Int
dense !MutablePrimArray s Int
sparse !Int
i !Int
x !Int
j
    | Int
i Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
j
    = () -> ST s ()
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return ()

    | Bool
otherwise = do
        -- x <- readPrimArray dense i
        Int
y <- MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
dense Int
j

        MutablePrimArray s Int -> Int -> Int -> ST s ()
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> a -> ST s ()
writePrimArray MutablePrimArray s Int
dense Int
j Int
x
        MutablePrimArray s Int -> Int -> Int -> ST s ()
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> a -> ST s ()
writePrimArray MutablePrimArray s Int
dense Int
i Int
y
        MutablePrimArray s Int -> Int -> Int -> ST s ()
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> a -> ST s ()
writePrimArray MutablePrimArray s Int
sparse Int
x Int
j
        MutablePrimArray s Int -> Int -> Int -> ST s ()
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> a -> ST s ()
writePrimArray MutablePrimArray s Int
sparse Int
y Int
i

-- | Pop element from the set.
--
-- >>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; popSparseSet set }
-- Just 13
--
popSparseSet :: SparseSet s -> ST s (Maybe Int)
popSparseSet :: forall s. SparseSet s -> ST s (Maybe Int)
popSparseSet SparseSet s
set = SparseSet s
-> ST s (Maybe Int)
-> (Int -> ST s (Maybe Int))
-> ST s (Maybe Int)
forall s r. SparseSet s -> ST s r -> (Int -> ST s r) -> ST s r
popSparseSet_ SparseSet s
set (Maybe Int -> ST s (Maybe Int)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return Maybe Int
forall a. Maybe a
Nothing) (Maybe Int -> ST s (Maybe Int)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return (Maybe Int -> ST s (Maybe Int))
-> (Int -> Maybe Int) -> Int -> ST s (Maybe Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> Maybe Int
forall a. a -> Maybe a
Just)

-- by using continuation passing style we can avoid allocating Just constructor.
{-# INLINE popSparseSet_ #-}
popSparseSet_ :: SparseSet s -> ST s r -> (Int -> ST s r) -> ST s r
popSparseSet_ :: forall s r. SparseSet s -> ST s r -> (Int -> ST s r) -> ST s r
popSparseSet_ set :: SparseSet s
set@SS {PrimVar s Int
MutablePrimArray s Int
size :: forall s. SparseSet s -> PrimVar s Int
dense :: forall s. SparseSet s -> MutablePrimArray s Int
sparse :: forall s. SparseSet s -> MutablePrimArray s Int
size :: PrimVar s Int
dense :: MutablePrimArray s Int
sparse :: MutablePrimArray s Int
..} ST s r
no Int -> ST s r
yes = do
    SparseSet s -> ST s ()
forall s. SparseSet s -> ST s ()
checkInvariant SparseSet s
set

    Int
n <- PrimVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimVar (PrimState m) a -> m a
readPrimVar PrimVar s Int
PrimVar (PrimState (ST s)) Int
size
    if Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
<= Int
0
    then ST s r
no
    else do
        let !n' :: Int
n' = Int
n Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1
        Int
x <- MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
dense Int
n'
        PrimVar (PrimState (ST s)) Int -> Int -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimVar (PrimState m) a -> a -> m ()
writePrimVar PrimVar s Int
PrimVar (PrimState (ST s)) Int
size Int
n'
        Int -> ST s r
yes Int
x
--
-- | Clear sparse set.
--
-- >>> runST $ do { set <- newSparseSet 100; mapM_ (insertSparseSet set) [3,5,7,11,13,11]; clearSparseSet set; elemsSparseSet set }
-- []
--
clearSparseSet :: SparseSet s -> ST s ()
clearSparseSet :: forall s. SparseSet s -> ST s ()
clearSparseSet SS {PrimVar s Int
MutablePrimArray s Int
size :: forall s. SparseSet s -> PrimVar s Int
dense :: forall s. SparseSet s -> MutablePrimArray s Int
sparse :: forall s. SparseSet s -> MutablePrimArray s Int
size :: PrimVar s Int
dense :: MutablePrimArray s Int
sparse :: MutablePrimArray s Int
..} = do
    PrimVar (PrimState (ST s)) Int -> Int -> ST s ()
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimVar (PrimState m) a -> a -> m ()
writePrimVar PrimVar s Int
PrimVar (PrimState (ST s)) Int
size Int
0

-- | Elements of the set
elemsSparseSet :: SparseSet s -> ST s [Int]
elemsSparseSet :: forall s. SparseSet s -> ST s [Int]
elemsSparseSet SS {PrimVar s Int
MutablePrimArray s Int
size :: forall s. SparseSet s -> PrimVar s Int
dense :: forall s. SparseSet s -> MutablePrimArray s Int
sparse :: forall s. SparseSet s -> MutablePrimArray s Int
size :: PrimVar s Int
dense :: MutablePrimArray s Int
sparse :: MutablePrimArray s Int
..} = do
    Int
n <- PrimVar (PrimState (ST s)) Int -> ST s Int
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
PrimVar (PrimState m) a -> m a
readPrimVar PrimVar s Int
PrimVar (PrimState (ST s)) Int
size
    [Int] -> Int -> Int -> ST s [Int]
go [] Int
0 Int
n
  where
    go :: [Int] -> Int -> Int -> ST s [Int]
go ![Int]
acc !Int
i !Int
n
        | Int
i Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
n
        = do
            Int
x <- MutablePrimArray s Int -> Int -> ST s Int
forall a s.
(HasCallStack, Prim a) =>
MutablePrimArray s a -> Int -> ST s a
readPrimArray MutablePrimArray s Int
dense Int
i
            [Int] -> Int -> Int -> ST s [Int]
go (Int
x Int -> [Int] -> [Int]
forall a. a -> [a] -> [a]
: [Int]
acc) (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int
n

        | Bool
otherwise
        = [Int] -> ST s [Int]
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return ([Int] -> [Int]
forall a. [a] -> [a]
reverse [Int]
acc)