{-# 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
    -- * Folds
  , foldr
  , foldMap
  , foldl'
  , foldr'
  , foldMap'
  , foldlM'
  , liftHashWithSalt
    -- * Traversals
  , 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

-- Only correct if the function is a monotone.
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 = -- fromList 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

-- This is intended to be used with things like Word8,Int8,Word16,Int16,etc.
-- It does the minimal number of allocations. It does some extra checks
-- just in case someone write a bad Num instance for something. If
-- you have a Num instance that doesn't satisfy the laws one would
-- intuitively expect, this function will bail out and return
-- the empty set.
enumFromTo :: (Contiguous arr, Element arr a, Enum a, Ord a, Num a)
  => a -- Low
  -> a -- High
  -> 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 -- initial size of buffer, must be 1 or higher
  -> a -- first element
  -> [a] -- elements
  -> ([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

-- The shortcuts help when:
-- 
-- * One of the arrays is empty. In this situation, we can just return
--   the other array instead of reconstructing it.
-- * All elements in one array are smaller than all elements in the
--   other. In this case, we can append the arrays, which uses memcpy.
unionArr :: forall arr a. (ContiguousU arr, Element arr a, Ord a)
  => arr a -- array x
  -> arr a -- array y
  -> 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 #-}

-- | Monoidal fold over the elements in the set. This is lazy in the accumulator.
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 -- ^ salt
  -> Set arr a -- ^ set
  -> 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 #-}

-- Returns true if the first set is a subset of the second set.
-- This algorithm could be improved by performing some kind of
-- galloping.
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

-- This relies on a sensible @Num@ instance for correctness. It is not totally
-- correcty yet because of the existence of zero
-- scale :: (Contiguous arr, Element arr a, Num a)
--   => a
--   -> Set arr a
--   -> Set arr a
-- scale x (Set arr) = Set (A.map' (x *)  arr)
-- {-# INLINEABLE scale #-}

-- Take the cross product of the two sets. That is, combine every
-- element in @A@ with every element in @B@ using the provided function.
-- If the combining function @f@ is an inequality morphism satisfying
-- @forall x y w z. x >= y ==> f x w >= f y z@, then this algorithm runs
-- in /O(n*m)/. Otherwise, it runs in @/O(n*m*log(n*m)/@.
-- cross :: (Contiguous arr, Element arr a, Element arr b, Element arr c)
--   => (a -> b -> c)
--   -> Set arr a
--   -> Set arr b
--   -> Set arr c
-- cross f (Set as) (Set bs) = runST $ do
--   let !maxSz = A.size as * A.size bs
--   !m <- A.new maxSz
--   let go !ixA !ixB !ixCount !ixDst !morphism = if ixCount < maxSz
--         then