{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE UndecidableInstances #-}
{-# OPTIONS_GHC -Wall #-}
module Data.Set.Internal
( Set(..)
, empty
, null
, singleton
, doubleton
, tripleton
, difference
, intersection
, intersects
, append
, member
, lookupIndex
, showsPrec
, equals
, compare
, fromListN
, fromList
, toList
, toArray
, size
, concat
, subset
, enumFromTo
, foldr
, foldMap
, foldl'
, foldr'
, foldMap'
, foldlM'
, liftHashWithSalt
, traverse_
, itraverse_
, map
) where
import Prelude hiding (compare,showsPrec,concat,foldr,foldMap,null,map,enumFromTo)
import Control.Monad.ST (ST,runST)
import Data.Hashable (Hashable)
import Data.Primitive.Contiguous (ContiguousU,Contiguous,Mutable,Element)
import qualified Prelude as P
import qualified Data.Primitive.Contiguous as A
import qualified Data.Concatenation as C
newtype Set arr a = Set (arr a)
append :: (ContiguousU arr, Element arr a, Ord a) => Set arr a -> Set arr a -> Set arr a
append :: forall (arr :: * -> *) a.
(ContiguousU arr, Element arr a, Ord a) =>
Set arr a -> Set arr a -> Set arr a
append (Set arr a
x) (Set arr a
y) = forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr :: * -> *) a.
(ContiguousU arr, Element arr a, Ord a) =>
arr a -> arr a -> arr a
unionArr arr a
x arr a
y)
null :: Contiguous arr => Set arr a -> Bool
null :: forall (arr :: * -> *) a. Contiguous arr => Set arr a -> Bool
null (Set arr a
x) = forall (arr :: * -> *) b. Contiguous arr => arr b -> Bool
A.null arr a
x
empty :: Contiguous arr => Set arr a
empty :: forall (arr :: * -> *) a. Contiguous arr => Set arr a
empty = forall (arr :: * -> *) a. arr a -> Set arr a
Set forall (arr :: * -> *) a. Contiguous arr => arr a
A.empty
equals :: (Contiguous arr, Element arr a, Eq a) => Set arr a -> Set arr a -> Bool
equals :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Eq a) =>
Set arr a -> Set arr a -> Bool
equals (Set arr a
x) (Set arr a
y) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b, Eq b) =>
arr b -> arr b -> Bool
A.equals arr a
x arr a
y
compare :: (Contiguous arr, Element arr a, Ord a) => Set arr a -> Set arr a -> Ordering
compare :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
Set arr a -> Set arr a -> Ordering
compare (Set arr a
x) (Set arr a
y) = forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
arr a -> arr a -> Ordering
compareArr arr a
x arr a
y
map :: (Contiguous arr, Element arr a, Element arr b) => (a -> b) -> Set arr a -> Set arr b
map :: forall (arr :: * -> *) a b.
(Contiguous arr, Element arr a, Element arr b) =>
(a -> b) -> Set arr a -> Set arr b
map a -> b
f (Set arr a
x) = forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr1 :: * -> *) b (arr2 :: * -> *) c.
(Contiguous arr1, Element arr1 b, Contiguous arr2,
Element arr2 c) =>
(b -> c) -> arr1 b -> arr2 c
A.map a -> b
f arr a
x)
fromListN :: (ContiguousU arr, Element arr a, Ord a) => Int -> [a] -> Set arr a
fromListN :: forall (arr :: * -> *) a.
(ContiguousU arr, Element arr a, Ord a) =>
Int -> [a] -> Set arr a
fromListN Int
n [a]
xs =
case [a]
xs of
[] -> forall (arr :: * -> *) a. Contiguous arr => Set arr a
empty
a
y : [a]
ys ->
let ([a]
leftovers, Set arr a
result) = forall (arr :: * -> *) a.
(ContiguousU arr, Element arr a, Ord a) =>
Int -> a -> [a] -> ([a], Set arr a)
fromAscList (forall a. Ord a => a -> a -> a
max Int
1 Int
n) a
y [a]
ys
in forall (arr :: * -> *) a.
(ContiguousU arr, Element arr a, Ord a) =>
[Set arr a] -> Set arr a
concat (Set arr a
result forall a. a -> [a] -> [a]
: forall a b. (a -> b) -> [a] -> [b]
P.map forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> Set arr a
singleton [a]
leftovers)
fromList :: (ContiguousU arr, Element arr a, Ord a) => [a] -> Set arr a
fromList :: forall (arr :: * -> *) a.
(ContiguousU arr, Element arr a, Ord a) =>
[a] -> Set arr a
fromList = forall (arr :: * -> *) a.
(ContiguousU arr, Element arr a, Ord a) =>
Int -> [a] -> Set arr a
fromListN Int
1
enumFromTo :: (Contiguous arr, Element arr a, Enum a, Ord a, Num a)
=> a
-> a
-> Set arr a
enumFromTo :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Enum a, Ord a, Num a) =>
a -> a -> Set arr a
enumFromTo !a
lo !a
hi = if a
hi forall a. Ord a => a -> a -> Bool
>= a
lo
then forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
let go :: Mutable arr (PrimState f) a -> Int -> a -> a -> f (Set arr a)
go !Mutable arr (PrimState f) a
arr !Int
ix !a
a !a
old = if Int
ix forall a. Ord a => a -> a -> Bool
>= Int
0
then if a
a forall a. Ord a => a -> a -> Bool
< a
old
then forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
A.write Mutable arr (PrimState f) a
arr Int
ix a
a forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
*> Mutable arr (PrimState f) a -> Int -> a -> a -> f (Set arr a)
go Mutable arr (PrimState f) a
arr (Int
ix forall a. Num a => a -> a -> a
- Int
1) (a
a forall a. Num a => a -> a -> a
- a
1) a
a
else forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall (arr :: * -> *) a. arr a -> Set arr a
Set forall (arr :: * -> *) a. Contiguous arr => arr a
A.empty)
else do
arr a
r <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
A.unsafeFreeze Mutable arr (PrimState f) a
arr
forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall (arr :: * -> *) a. arr a -> Set arr a
Set arr a
r)
let total :: Int
total = forall a. Enum a => a -> Int
fromEnum (a
hi forall a. Num a => a -> a -> a
- a
lo)
if Int
total forall a. Ord a => a -> a -> Bool
>= Int
0
then do
Mutable arr s a
arr <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
A.new (Int
total forall a. Num a => a -> a -> a
+ Int
1)
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
A.write Mutable arr s a
arr Int
total a
hi
forall {arr :: * -> *} {a} {f :: * -> *}.
(Element arr a, Ord a, Contiguous arr, PrimMonad f, Num a) =>
Mutable arr (PrimState f) a -> Int -> a -> a -> f (Set arr a)
go Mutable arr s a
arr (Int
total forall a. Num a => a -> a -> a
- Int
1) (a
hi forall a. Num a => a -> a -> a
- a
1) a
hi
else forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall (arr :: * -> *) a. arr a -> Set arr a
Set forall (arr :: * -> *) a. Contiguous arr => arr a
A.empty)
else forall (arr :: * -> *) a. arr a -> Set arr a
Set forall (arr :: * -> *) a. Contiguous arr => arr a
A.empty
difference :: forall a arr. (ContiguousU arr, Element arr a, Ord a)
=> Set arr a
-> Set arr a
-> Set arr a
difference :: forall a (arr :: * -> *).
(ContiguousU arr, Element arr a, Ord a) =>
Set arr a -> Set arr a -> Set arr a
difference s1 :: Set arr a
s1@(Set arr a
arr1) s2 :: Set arr a
s2@(Set arr a
arr2)
| Int
sz1 forall a. Eq a => a -> a -> Bool
== Int
0 = forall (arr :: * -> *) a. Contiguous arr => Set arr a
empty
| Int
sz2 forall a. Eq a => a -> a -> Bool
== Int
0 = Set arr a
s1
| Bool
otherwise = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
Mutable arr s a
dst <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
A.new Int
sz1
let go :: Int -> Int -> Int -> ST s Int
go !Int
ix1 !Int
ix2 !Int
dstIx = if Int
ix2 forall a. Ord a => a -> a -> Bool
< Int
sz2
then if Int
ix1 forall a. Ord a => a -> a -> Bool
< Int
sz1
then do
a
v1 <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
A.indexM arr a
arr1 Int
ix1
a
v2 <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
A.indexM arr a
arr2 Int
ix2
case forall a. Ord a => a -> a -> Ordering
P.compare a
v1 a
v2 of
Ordering
EQ -> Int -> Int -> Int -> ST s Int
go (Int
ix1 forall a. Num a => a -> a -> a
+ Int
1) (Int
ix2 forall a. Num a => a -> a -> a
+ Int
1) Int
dstIx
Ordering
LT -> do
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
A.write Mutable arr s a
dst Int
dstIx a
v1
Int -> Int -> Int -> ST s Int
go (Int
ix1 forall a. Num a => a -> a -> a
+ Int
1) Int
ix2 (Int
dstIx forall a. Num a => a -> a -> a
+ Int
1)
Ordering
GT -> Int -> Int -> Int -> ST s Int
go Int
ix1 (Int
ix2 forall a. Num a => a -> a -> a
+ Int
1) Int
dstIx
else forall (m :: * -> *) a. Monad m => a -> m a
return Int
dstIx
else do
let !remaining :: Int
remaining = Int
sz1 forall a. Num a => a -> a -> a
- Int
ix1
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> Sliced arr b -> m ()
A.copy Mutable arr s a
dst Int
dstIx (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
A.slice arr a
arr1 Int
ix1 Int
remaining)
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
dstIx forall a. Num a => a -> a -> a
+ Int
remaining)
Int
dstSz <- Int -> Int -> Int -> ST s Int
go Int
0 Int
0 Int
0
arr a
dstFrozen <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
A.resize Mutable arr s a
dst Int
dstSz forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
A.unsafeFreeze
forall (m :: * -> *) a. Monad m => a -> m a
return (forall (arr :: * -> *) a. arr a -> Set arr a
Set arr a
dstFrozen)
where
!sz1 :: Int
sz1 = forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
Set arr a -> Int
size Set arr a
s1
!sz2 :: Int
sz2 = forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
Set arr a -> Int
size Set arr a
s2
intersects :: forall a arr. (Contiguous arr, Element arr a, Ord a)
=> Set arr a
-> Set arr a
-> Bool
intersects :: forall a (arr :: * -> *).
(Contiguous arr, Element arr a, Ord a) =>
Set arr a -> Set arr a -> Bool
intersects Set arr a
s1 Set arr a
s2
| Int
sz1 forall a. Eq a => a -> a -> Bool
== Int
0 = Bool
False
| Int
sz2 forall a. Eq a => a -> a -> Bool
== Int
0 = Bool
False
| Bool
otherwise =
let (smaller :: Set arr a
smaller@(Set arr a
arr1),larger :: Set arr a
larger@(Set arr a
arr2)) = if Int
sz1 forall a. Ord a => a -> a -> Bool
<= Int
sz2
then (Set arr a
s1,Set arr a
s2)
else (Set arr a
s2,Set arr a
s1)
!szSmaller :: Int
szSmaller = forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
Set arr a -> Int
size Set arr a
smaller
go :: Int -> ST s Bool
go :: forall s. Int -> ST s Bool
go !Int
ix = if Int
ix forall a. Ord a => a -> a -> Bool
< Int
szSmaller
then do
a
v <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
A.indexM arr a
arr1 Int
ix
if forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
a -> Set arr a -> Bool
member a
v Set arr a
larger
then forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True
else forall s. Int -> ST s Bool
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1)
else forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
in forall a. (forall s. ST s a) -> a
runST (forall s. Int -> ST s Bool
go Int
0)
where
!sz1 :: Int
sz1 = forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
Set arr a -> Int
size Set arr a
s1
!sz2 :: Int
sz2 = forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
Set arr a -> Int
size Set arr a
s2
{-# INLINEABLE intersects #-}
intersection :: forall a arr. (ContiguousU arr, Element arr a, Ord a)
=> Set arr a
-> Set arr a
-> Set arr a
intersection :: forall a (arr :: * -> *).
(ContiguousU arr, Element arr a, Ord a) =>
Set arr a -> Set arr a -> Set arr a
intersection s1 :: Set arr a
s1@(Set arr a
arr1) s2 :: Set arr a
s2@(Set arr a
arr2)
| Int
sz1 forall a. Eq a => a -> a -> Bool
== Int
0 = forall (arr :: * -> *) a. Contiguous arr => Set arr a
empty
| Int
sz2 forall a. Eq a => a -> a -> Bool
== Int
0 = forall (arr :: * -> *) a. Contiguous arr => Set arr a
empty
| Bool
otherwise = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
Mutable arr s a
dst <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
A.new (forall a. Ord a => a -> a -> a
min Int
sz1 Int
sz2)
let go :: Int -> Int -> Int -> ST s Int
go !Int
ix1 !Int
ix2 !Int
dstIx = if Int
ix2 forall a. Ord a => a -> a -> Bool
< Int
sz2 Bool -> Bool -> Bool
&& Int
ix1 forall a. Ord a => a -> a -> Bool
< Int
sz1
then do
a
v1 <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
A.indexM arr a
arr1 Int
ix1
a
v2 <- forall (arr :: * -> *) b (m :: * -> *).
(Contiguous arr, Element arr b, Monad m) =>
arr b -> Int -> m b
A.indexM arr a
arr2 Int
ix2
case forall a. Ord a => a -> a -> Ordering
P.compare a
v1 a
v2 of
Ordering
EQ -> do
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
A.write Mutable arr s a
dst Int
dstIx a
v1
Int -> Int -> Int -> ST s Int
go (Int
ix1 forall a. Num a => a -> a -> a
+ Int
1) (Int
ix2 forall a. Num a => a -> a -> a
+ Int
1) (Int
dstIx forall a. Num a => a -> a -> a
+ Int
1)
Ordering
LT -> Int -> Int -> Int -> ST s Int
go (Int
ix1 forall a. Num a => a -> a -> a
+ Int
1) Int
ix2 Int
dstIx
Ordering
GT -> Int -> Int -> Int -> ST s Int
go Int
ix1 (Int
ix2 forall a. Num a => a -> a -> a
+ Int
1) Int
dstIx
else forall (m :: * -> *) a. Monad m => a -> m a
return Int
dstIx
Int
dstSz <- Int -> Int -> Int -> ST s Int
go Int
0 Int
0 Int
0
arr a
dstFrozen <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
A.resize Mutable arr s a
dst Int
dstSz forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
A.unsafeFreeze
forall (m :: * -> *) a. Monad m => a -> m a
return (forall (arr :: * -> *) a. arr a -> Set arr a
Set arr a
dstFrozen)
where
!sz1 :: Int
sz1 = forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
Set arr a -> Int
size Set arr a
s1
!sz2 :: Int
sz2 = forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
Set arr a -> Int
size Set arr a
s2
fromAscList :: forall arr a. (ContiguousU arr, Element arr a, Ord a)
=> Int
-> a
-> [a]
-> ([a], Set arr a)
fromAscList :: forall (arr :: * -> *) a.
(ContiguousU arr, Element arr a, Ord a) =>
Int -> a -> [a] -> ([a], Set arr a)
fromAscList !Int
n a
x0 [a]
xs0 = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
Mutable arr s a
marr0 <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
A.new Int
n
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
A.write Mutable arr s a
marr0 Int
0 a
x0
let go :: forall s. Int -> a -> Int -> Mutable arr s a -> [a] -> ST s ([a], Set arr a)
go :: forall s.
Int -> a -> Int -> Mutable arr s a -> [a] -> ST s ([a], Set arr a)
go !Int
ix !a
_ !Int
sz !Mutable arr s a
marr [] = if Int
ix forall a. Eq a => a -> a -> Bool
== Int
sz
then do
arr a
arr <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
A.unsafeFreeze Mutable arr s a
marr
forall (m :: * -> *) a. Monad m => a -> m a
return ([],forall (arr :: * -> *) a. arr a -> Set arr a
Set arr a
arr)
else do
Mutable arr s a
marr' <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
A.resize Mutable arr s a
marr Int
ix
arr a
arr <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
A.unsafeFreeze Mutable arr s a
marr'
forall (m :: * -> *) a. Monad m => a -> m a
return ([],forall (arr :: * -> *) a. arr a -> Set arr a
Set arr a
arr)
go !Int
ix !a
old !Int
sz !Mutable arr s a
marr (a
x : [a]
xs) = if Int
ix forall a. Ord a => a -> a -> Bool
< Int
sz
then case forall a. Ord a => a -> a -> Ordering
P.compare a
x a
old of
Ordering
GT -> do
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
A.write Mutable arr s a
marr Int
ix a
x
forall s.
Int -> a -> Int -> Mutable arr s a -> [a] -> ST s ([a], Set arr a)
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1) a
x Int
sz Mutable arr s a
marr [a]
xs
Ordering
EQ -> forall s.
Int -> a -> Int -> Mutable arr s a -> [a] -> ST s ([a], Set arr a)
go Int
ix a
x Int
sz Mutable arr s a
marr [a]
xs
Ordering
LT -> do
Mutable arr s a
marr' <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
A.resize Mutable arr s a
marr Int
ix
arr a
arr <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
A.unsafeFreeze Mutable arr s a
marr'
forall (m :: * -> *) a. Monad m => a -> m a
return (a
x forall a. a -> [a] -> [a]
: [a]
xs,forall (arr :: * -> *) a. arr a -> Set arr a
Set arr a
arr)
else do
let sz' :: Int
sz' = Int
sz forall a. Num a => a -> a -> a
* Int
2
Mutable arr s a
marr' <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
A.resize Mutable arr s a
marr Int
sz'
forall s.
Int -> a -> Int -> Mutable arr s a -> [a] -> ST s ([a], Set arr a)
go Int
ix a
old Int
sz' Mutable arr s a
marr' (a
x forall a. a -> [a] -> [a]
: [a]
xs)
forall s.
Int -> a -> Int -> Mutable arr s a -> [a] -> ST s ([a], Set arr a)
go Int
1 a
x0 Int
n Mutable arr s a
marr0 [a]
xs0
showsPrec :: (Contiguous arr, Element arr a, Show a) => Int -> Set arr a -> ShowS
showsPrec :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Show a) =>
Int -> Set arr a -> ShowS
showsPrec Int
p Set arr a
xs = Bool -> ShowS -> ShowS
showParen (Int
p forall a. Ord a => a -> a -> Bool
> Int
10) forall a b. (a -> b) -> a -> b
$
String -> ShowS
showString String
"fromList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => a -> ShowS
shows (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
Set arr a -> [a]
toList Set arr a
xs)
toList :: (Contiguous arr, Element arr a) => Set arr a -> [a]
toList :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
Set arr a -> [a]
toList = forall (arr :: * -> *) a b.
(Contiguous arr, Element arr a) =>
(a -> b -> b) -> b -> Set arr a -> b
foldr (:) []
toArray :: Set arr a -> arr a
toArray :: forall (arr :: * -> *) a. Set arr a -> arr a
toArray (Set arr a
a) = arr a
a
member :: forall arr a. (Contiguous arr, Element arr a, Ord a) => a -> Set arr a -> Bool
member :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
a -> Set arr a -> Bool
member a
a (Set arr a
arr) = Int -> Int -> Bool
go Int
0 (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
A.size arr a
arr forall a. Num a => a -> a -> a
- Int
1) where
go :: Int -> Int -> Bool
go :: Int -> Int -> Bool
go !Int
start !Int
end = if Int
end forall a. Ord a => a -> a -> Bool
< Int
start
then Bool
False
else
let !mid :: Int
mid = forall a. Integral a => a -> a -> a
div (Int
end forall a. Num a => a -> a -> a
+ Int
start) Int
2
!v :: a
v = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
A.index arr a
arr Int
mid
in case forall a. Ord a => a -> a -> Ordering
P.compare a
a a
v of
Ordering
LT -> Int -> Int -> Bool
go Int
start (Int
mid forall a. Num a => a -> a -> a
- Int
1)
Ordering
EQ -> Bool
True
Ordering
GT -> Int -> Int -> Bool
go (Int
mid forall a. Num a => a -> a -> a
+ Int
1) Int
end
{-# INLINEABLE member #-}
lookupIndex :: forall arr a. (Contiguous arr, Element arr a, Ord a) => a -> Set arr a -> Maybe Int
lookupIndex :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
a -> Set arr a -> Maybe Int
lookupIndex a
a (Set arr a
arr) = Int -> Int -> Maybe Int
go Int
0 (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
A.size arr a
arr forall a. Num a => a -> a -> a
- Int
1) where
go :: Int -> Int -> Maybe Int
go :: Int -> Int -> Maybe Int
go !Int
start !Int
end = if Int
end forall a. Ord a => a -> a -> Bool
< Int
start
then forall a. Maybe a
Nothing
else
let !mid :: Int
mid = forall a. Integral a => a -> a -> a
div (Int
end forall a. Num a => a -> a -> a
+ Int
start) Int
2
!v :: a
v = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
A.index arr a
arr Int
mid
in case forall a. Ord a => a -> a -> Ordering
P.compare a
a a
v of
Ordering
LT -> Int -> Int -> Maybe Int
go Int
start (Int
mid forall a. Num a => a -> a -> a
- Int
1)
Ordering
EQ -> forall a. a -> Maybe a
Just Int
mid
Ordering
GT -> Int -> Int -> Maybe Int
go (Int
mid forall a. Num a => a -> a -> a
+ Int
1) Int
end
{-# INLINEABLE lookupIndex #-}
concat :: forall arr a. (ContiguousU arr, Element arr a, Ord a) => [Set arr a] -> Set arr a
concat :: forall (arr :: * -> *) a.
(ContiguousU arr, Element arr a, Ord a) =>
[Set arr a] -> Set arr a
concat = forall m. (m -> Int) -> m -> (m -> m -> m) -> [m] -> m
C.concatSized forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
Set arr a -> Int
size forall (arr :: * -> *) a. Contiguous arr => Set arr a
empty forall (arr :: * -> *) a.
(ContiguousU arr, Element arr a, Ord a) =>
Set arr a -> Set arr a -> Set arr a
append
compareArr :: (Contiguous arr, Element arr a, Ord a)
=> arr a
-> arr a
-> Ordering
{-# INLINEABLE compareArr #-}
compareArr :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
arr a -> arr a -> Ordering
compareArr arr a
arrA arr a
arrB = Int -> Ordering
go Int
0 where
go :: Int -> Ordering
go :: Int -> Ordering
go !Int
ix = if Int
ix forall a. Ord a => a -> a -> Bool
< forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
A.size arr a
arrA
then if Int
ix forall a. Ord a => a -> a -> Bool
< forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
A.size arr a
arrB
then forall a. Monoid a => a -> a -> a
mappend (forall a. Ord a => a -> a -> Ordering
P.compare (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
A.index arr a
arrA Int
ix) (forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
A.index arr a
arrB Int
ix)) (Int -> Ordering
go (Int
ix forall a. Num a => a -> a -> a
+ Int
1))
else Ordering
GT
else if Int
ix forall a. Ord a => a -> a -> Bool
< forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
A.size arr a
arrB
then Ordering
LT
else Ordering
EQ
singleton :: (Contiguous arr, Element arr a) => a -> Set arr a
{-# INLINEABLE singleton #-}
singleton :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> Set arr a
singleton a
a = forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> arr a
A.singleton a
a)
doubleton :: (Contiguous arr, Element arr a, Ord a) => a -> a -> Set arr a
{-# INLINEABLE doubleton #-}
doubleton :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
a -> a -> Set arr a
doubleton a
a a
b = case forall a. Ord a => a -> a -> Ordering
P.compare a
a a
b of
Ordering
LT -> forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> a -> arr a
A.doubleton a
a a
b)
Ordering
GT -> forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> a -> arr a
A.doubleton a
b a
a)
Ordering
EQ -> forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> arr a
A.singleton a
a)
tripleton :: (Contiguous arr, Element arr a, Ord a) => a -> a -> a -> Set arr a
{-# INLINEABLE tripleton #-}
tripleton :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
a -> a -> a -> Set arr a
tripleton a
a a
b a
c = case forall a. Ord a => a -> a -> Ordering
P.compare a
a a
b of
Ordering
LT -> case forall a. Ord a => a -> a -> Ordering
P.compare a
b a
c of
Ordering
LT -> forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> a -> a -> arr a
A.tripleton a
a a
b a
c)
Ordering
EQ -> forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
a -> a -> Set arr a
doubleton a
a a
b
Ordering
GT -> case forall a. Ord a => a -> a -> Ordering
P.compare a
a a
c of
Ordering
LT -> forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> a -> a -> arr a
A.tripleton a
a a
c a
b)
Ordering
EQ -> forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
a -> a -> Set arr a
doubleton a
a a
b
Ordering
GT -> forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> a -> a -> arr a
A.tripleton a
c a
a a
b)
Ordering
GT -> case forall a. Ord a => a -> a -> Ordering
P.compare a
b a
c of
Ordering
LT -> case forall a. Ord a => a -> a -> Ordering
P.compare a
a a
c of
Ordering
LT -> forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> a -> a -> arr a
A.tripleton a
b a
a a
c)
Ordering
EQ -> forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
a -> a -> Set arr a
doubleton a
b a
a
Ordering
GT -> forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> a -> a -> arr a
A.tripleton a
b a
c a
a)
Ordering
EQ -> forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
a -> a -> Set arr a
doubleton a
b a
a
Ordering
GT -> forall (arr :: * -> *) a. arr a -> Set arr a
Set (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
a -> a -> a -> arr a
A.tripleton a
c a
b a
a)
Ordering
EQ -> forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
a -> a -> Set arr a
doubleton a
b a
c
unionArr :: forall arr a. (ContiguousU arr, Element arr a, Ord a)
=> arr a
-> arr a
-> arr a
{-# INLINEABLE unionArr #-}
unionArr :: forall (arr :: * -> *) a.
(ContiguousU arr, Element arr a, Ord a) =>
arr a -> arr a -> arr a
unionArr arr a
arrA arr a
arrB
| Int
szA forall a. Ord a => a -> a -> Bool
< Int
1 = arr a
arrB
| Int
szB forall a. Ord a => a -> a -> Bool
< Int
1 = arr a
arrA
| forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
A.index arr a
arrA (Int
szA forall a. Num a => a -> a -> a
- Int
1) forall a. Ord a => a -> a -> Bool
< forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
A.index arr a
arrB Int
0 = forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> arr a -> arr a
A.append arr a
arrA arr a
arrB
| Bool
otherwise = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
!(Mutable arr s a
arrDst :: Mutable arr s a) <- forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Int -> m (Mutable arr (PrimState m) b)
A.new (Int
szA forall a. Num a => a -> a -> a
+ Int
szB)
let go :: Int -> Int -> Int -> ST s Int
go !Int
ixA !Int
ixB !Int
ixDst = if Int
ixA forall a. Ord a => a -> a -> Bool
< Int
szA
then if Int
ixB forall a. Ord a => a -> a -> Bool
< Int
szB
then do
let !a :: a
a = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
A.index arr a
arrA Int
ixA
!b :: a
b = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> b
A.index arr a
arrB Int
ixB
case forall a. Ord a => a -> a -> Ordering
P.compare a
a a
b of
Ordering
EQ -> do
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
A.write Mutable arr s a
arrDst Int
ixDst a
a
Int -> Int -> Int -> ST s Int
go (Int
ixA forall a. Num a => a -> a -> a
+ Int
1) (Int
ixB forall a. Num a => a -> a -> a
+ Int
1) (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
Ordering
LT -> do
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
A.write Mutable arr s a
arrDst Int
ixDst a
a
Int -> Int -> Int -> ST s Int
go (Int
ixA forall a. Num a => a -> a -> a
+ Int
1) Int
ixB (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
Ordering
GT -> do
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> b -> m ()
A.write Mutable arr s a
arrDst Int
ixDst a
b
Int -> Int -> Int -> ST s Int
go Int
ixA (Int
ixB forall a. Num a => a -> a -> a
+ Int
1) (Int
ixDst forall a. Num a => a -> a -> a
+ Int
1)
else do
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> Sliced arr b -> m ()
A.copy Mutable arr s a
arrDst Int
ixDst (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
A.slice arr a
arrA Int
ixA (Int
szA forall a. Num a => a -> a -> a
- Int
ixA))
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst forall a. Num a => a -> a -> a
+ (Int
szA forall a. Num a => a -> a -> a
- Int
ixA))
else if Int
ixB forall a. Ord a => a -> a -> Bool
< Int
szB
then do
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> Int -> Sliced arr b -> m ()
A.copy Mutable arr s a
arrDst Int
ixDst (forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
arr a -> Int -> Int -> Sliced arr a
A.slice arr a
arrB Int
ixB (Int
szB forall a. Num a => a -> a -> a
- Int
ixB))
forall (m :: * -> *) a. Monad m => a -> m a
return (Int
ixDst forall a. Num a => a -> a -> a
+ (Int
szB forall a. Num a => a -> a -> a
- Int
ixB))
else forall (m :: * -> *) a. Monad m => a -> m a
return Int
ixDst
Int
total <- Int -> Int -> Int -> ST s Int
go Int
0 Int
0 Int
0
Mutable arr s a
arrFinal <- forall (arr :: * -> *) (m :: * -> *) b.
(ContiguousU arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b
-> Int -> m (Mutable arr (PrimState m) b)
A.resize Mutable arr s a
arrDst Int
total
forall (arr :: * -> *) (m :: * -> *) b.
(Contiguous arr, PrimMonad m, Element arr b) =>
Mutable arr (PrimState m) b -> m (arr b)
A.unsafeFreeze Mutable arr s a
arrFinal
where
!szA :: Int
szA = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
A.size arr a
arrA
!szB :: Int
szB = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
A.size arr a
arrB
size :: (Contiguous arr, Element arr a) => Set arr a -> Int
size :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
Set arr a -> Int
size (Set arr a
arr) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
A.size arr a
arr
foldr :: (Contiguous arr, Element arr a)
=> (a -> b -> b)
-> b
-> Set arr a
-> b
foldr :: forall (arr :: * -> *) a b.
(Contiguous arr, Element arr a) =>
(a -> b -> b) -> b -> Set arr a -> b
foldr a -> b -> b
f b
b0 (Set arr a
arr) = forall (arr :: * -> *) a b.
(Contiguous arr, Element arr a) =>
(a -> b -> b) -> b -> arr a -> b
A.foldr a -> b -> b
f b
b0 arr a
arr
{-# INLINEABLE foldr #-}
foldMap :: (Contiguous arr, Element arr a, Monoid m)
=> (a -> m)
-> Set arr a
-> m
foldMap :: forall (arr :: * -> *) a m.
(Contiguous arr, Element arr a, Monoid m) =>
(a -> m) -> Set arr a -> m
foldMap a -> m
f (Set arr a
arr) = forall (arr :: * -> *) a m.
(Contiguous arr, Element arr a, Monoid m) =>
(a -> m) -> arr a -> m
A.foldMap a -> m
f arr a
arr
{-# INLINEABLE foldMap #-}
foldl' :: (Contiguous arr, Element arr a)
=> (b -> a -> b)
-> b
-> Set arr a
-> b
foldl' :: forall (arr :: * -> *) a b.
(Contiguous arr, Element arr a) =>
(b -> a -> b) -> b -> Set arr a -> b
foldl' b -> a -> b
f b
b0 (Set arr a
arr) = forall (arr :: * -> *) a b.
(Contiguous arr, Element arr a) =>
(b -> a -> b) -> b -> arr a -> b
A.foldl' b -> a -> b
f b
b0 arr a
arr
{-# INLINEABLE foldl' #-}
foldr' :: (Contiguous arr, Element arr a)
=> (a -> b -> b)
-> b
-> Set arr a
-> b
foldr' :: forall (arr :: * -> *) a b.
(Contiguous arr, Element arr a) =>
(a -> b -> b) -> b -> Set arr a -> b
foldr' a -> b -> b
f b
b0 (Set arr a
arr) = forall (arr :: * -> *) a b.
(Contiguous arr, Element arr a) =>
(a -> b -> b) -> b -> arr a -> b
A.foldr' a -> b -> b
f b
b0 arr a
arr
{-# INLINEABLE foldr' #-}
foldMap' :: (Contiguous arr, Element arr a, Monoid m)
=> (a -> m)
-> Set arr a
-> m
foldMap' :: forall (arr :: * -> *) a m.
(Contiguous arr, Element arr a, Monoid m) =>
(a -> m) -> Set arr a -> m
foldMap' a -> m
f (Set arr a
arr) = forall (arr :: * -> *) a m.
(Contiguous arr, Element arr a, Monoid m) =>
(a -> m) -> arr a -> m
A.foldMap' a -> m
f arr a
arr
{-# INLINEABLE foldMap' #-}
foldlM' :: (Contiguous arr, Element arr a, Monad m)
=> (b -> a -> m b)
-> b
-> Set arr a
-> m b
foldlM' :: forall (arr :: * -> *) a (m :: * -> *) b.
(Contiguous arr, Element arr a, Monad m) =>
(b -> a -> m b) -> b -> Set arr a -> m b
foldlM' b -> a -> m b
f b
b0 (Set arr a
arr) = forall (arr :: * -> *) a (m :: * -> *) b.
(Contiguous arr, Element arr a, Monad m) =>
(b -> a -> m b) -> b -> arr a -> m b
A.foldlM' b -> a -> m b
f b
b0 arr a
arr
{-# INLINEABLE foldlM' #-}
traverse_ :: (Contiguous arr, Element arr a, Applicative m)
=> (a -> m b)
-> Set arr a
-> m ()
traverse_ :: forall (arr :: * -> *) a (m :: * -> *) b.
(Contiguous arr, Element arr a, Applicative m) =>
(a -> m b) -> Set arr a -> m ()
traverse_ a -> m b
f (Set arr a
arr) = forall (arr :: * -> *) a (f :: * -> *) b.
(Contiguous arr, Element arr a, Applicative f) =>
(a -> f b) -> arr a -> f ()
A.traverse_ a -> m b
f arr a
arr
{-# INLINEABLE traverse_ #-}
itraverse_ :: (Contiguous arr, Element arr a, Applicative m)
=> (Int -> a -> m b)
-> Set arr a
-> m ()
itraverse_ :: forall (arr :: * -> *) a (m :: * -> *) b.
(Contiguous arr, Element arr a, Applicative m) =>
(Int -> a -> m b) -> Set arr a -> m ()
itraverse_ Int -> a -> m b
f (Set arr a
arr) = forall (arr :: * -> *) a (f :: * -> *) b.
(Contiguous arr, Element arr a, Applicative f) =>
(Int -> a -> f b) -> arr a -> f ()
A.itraverse_ Int -> a -> m b
f arr a
arr
{-# INLINEABLE itraverse_ #-}
liftHashWithSalt :: (Contiguous arr, Element arr a)
=> (Int -> a -> Int)
-> Int
-> Set arr a
-> Int
liftHashWithSalt :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
(Int -> a -> Int) -> Int -> Set arr a -> Int
liftHashWithSalt Int -> a -> Int
f Int
s (Set arr a
arr) = forall (arr :: * -> *) a.
(Contiguous arr, Element arr a) =>
(Int -> a -> Int) -> Int -> arr a -> Int
A.liftHashWithSalt Int -> a -> Int
f Int
s arr a
arr
{-# INLINEABLE liftHashWithSalt #-}
subset :: (Contiguous arr, Element arr a, Ord a)
=> Set arr a
-> Set arr a
-> Bool
{-# INLINEABLE subset #-}
subset :: forall (arr :: * -> *) a.
(Contiguous arr, Element arr a, Ord a) =>
Set arr a -> Set arr a -> Bool
subset (Set arr a
arrA) (Set arr a
arrB) = Int -> Int -> Bool
go Int
0 Int
0
where
!szA :: Int
szA = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
A.size arr a
arrA
!szB :: Int
szB = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int
A.size arr a
arrB
go :: Int -> Int -> Bool
go !Int
ixA !Int
ixB = if Int
ixA forall a. Ord a => a -> a -> Bool
< Int
szA
then if Int
ixB forall a. Ord a => a -> a -> Bool
< Int
szB
then
let !(# a
a #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
A.index# arr a
arrA Int
ixA
!(# a
b #) = forall (arr :: * -> *) b.
(Contiguous arr, Element arr b) =>
arr b -> Int -> (# b #)
A.index# arr a
arrB Int
ixB
in case forall a. Ord a => a -> a -> Ordering
P.compare a
a a
b of
Ordering
LT -> Bool
False
Ordering
EQ -> Int -> Int -> Bool
go (Int
ixA forall a. Num a => a -> a -> a
+ Int
1) (Int
ixB forall a. Num a => a -> a -> a
+ Int
1)
Ordering
GT -> Int -> Int -> Bool
go Int
ixA (Int
ixB forall a. Num a => a -> a -> a
+ Int
1)
else Bool
False
else Bool
True