{-# LANGUAGE CPP #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE TypeFamilies #-}

{-# OPTIONS_HADDOCK not-home #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Word64Set.Internal
-- Copyright   :  (c) Daan Leijen 2002
--                (c) Joachim Breitner 2011
-- License     :  BSD-style
-- Maintainer  :  libraries@haskell.org
-- Portability :  portable
--
-- = WARNING
--
-- This module is considered __internal__.
--
-- The Package Versioning Policy __does not apply__.
--
-- The contents of this module may change __in any way whatsoever__
-- and __without any warning__ between minor versions of this package.
--
-- Authors importing this module are expected to track development
-- closely.
--
-- = Description
--
-- An efficient implementation of integer sets.
--
-- These modules are intended to be imported qualified, to avoid name
-- clashes with Prelude functions, e.g.
--
-- >  import Data.Word64Set (Word64Set)
-- >  import qualified Data.Word64Set as Word64Set
--
-- The implementation is based on /big-endian patricia trees/.  This data
-- structure performs especially well on binary operations like 'union'
-- and 'intersection'.  However, my benchmarks show that it is also
-- (much) faster on insertions and deletions when compared to a generic
-- size-balanced set implementation (see "Data.Set").
--
--    * Chris Okasaki and Andy Gill,  \"/Fast Mergeable Integer Maps/\",
--      Workshop on ML, September 1998, pages 77-86,
--      <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452>
--
--    * D.R. Morrison, \"/PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric/\",
--      Journal of the ACM, 15(4), October 1968, pages 514-534.
--
-- Additionally, this implementation places bitmaps in the leaves of the tree.
-- Their size is the natural size of a machine word (32 or 64 bits) and greatly
-- reduce memory footprint and execution times for dense sets, e.g. sets where
-- it is likely that many values lie close to each other. The asymptotics are
-- not affected by this optimization.
--
-- Many operations have a worst-case complexity of \(O(\min(n,W))\).
-- This means that the operation can become linear in the number of
-- elements with a maximum of \(W\) -- the number of bits in an 'Int'
-- (32 or 64).
--
-- @since 0.5.9
-----------------------------------------------------------------------------

-- [Note: INLINE bit fiddling]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- It is essential that the bit fiddling functions like mask, zero, branchMask
-- etc are inlined. If they do not, the memory allocation skyrockets. The GHC
-- usually gets it right, but it is disastrous if it does not. Therefore we
-- explicitly mark these functions INLINE.


-- [Note: Local 'go' functions and capturing]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- Care must be taken when using 'go' function which captures an argument.
-- Sometimes (for example when the argument is passed to a data constructor,
-- as in insert), GHC heap-allocates more than necessary. Therefore C-- code
-- must be checked for increased allocation when creating and modifying such
-- functions.


-- [Note: Order of constructors]
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-- The order of constructors of Word64Set matters when considering performance.
-- Currently in GHC 7.0, when type has 3 constructors, they are matched from
-- the first to the last -- the best performance is achieved when the
-- constructors are ordered by frequency.
-- On GHC 7.0, reordering constructors from Nil | Tip | Bin to Bin | Tip | Nil
-- improves the benchmark by circa 10%.

module GHC.Data.Word64Set.Internal (
    -- * Set type
      Word64Set(..), Key -- instance Eq,Show
    , Prefix, Mask, BitMap

    -- * Operators
    , (\\)

    -- * Query
    , null
    , size
    , member
    , notMember
    , lookupLT
    , lookupGT
    , lookupLE
    , lookupGE
    , isSubsetOf
    , isProperSubsetOf
    , disjoint

    -- * Construction
    , empty
    , singleton
    , insert
    , delete
    , alterF

    -- * Combine
    , union
    , unions
    , difference
    , intersection

    -- * Filter
    , filter
    , partition

    , takeWhileAntitone
    , dropWhileAntitone
    , spanAntitone

    , split
    , splitMember
    , splitRoot

    -- * Map
    , map
    , mapMonotonic

    -- * Folds
    , foldr
    , foldl
    -- ** Strict folds
    , foldr'
    , foldl'
    -- ** Legacy folds
    , fold

    -- * Min\/Max
    , findMin
    , findMax
    , deleteMin
    , deleteMax
    , deleteFindMin
    , deleteFindMax
    , maxView
    , minView

    -- * Conversion

    -- ** List
    , elems
    , toList
    , fromList

    -- ** Ordered list
    , toAscList
    , toDescList
    , fromAscList
    , fromDistinctAscList

    -- * Debugging
    , showTree
    , showTreeWith

    -- * Internals
    , match
    , suffixBitMask
    , prefixBitMask
    , bitmapOf
    , zero
    ) where

import Control.Applicative (Const(..))
import Control.DeepSeq (NFData(rnf))
import Data.Bits
import qualified Data.List as List
import Data.Maybe (fromMaybe)
import Data.Semigroup (Semigroup(stimes, (<>)), stimesIdempotentMonoid)
import GHC.Prelude.Basic hiding
  (filter, foldr, foldl, foldl', null, map)
import Data.Word ( Word64 )

import GHC.Utils.Containers.Internal.BitUtil
import GHC.Utils.Containers.Internal.StrictPair

#if __GLASGOW_HASKELL__
import Data.Data (Data(..), Constr, mkConstr, constrIndex, DataType, mkDataType)
import qualified Data.Data
import Text.Read
#endif

#if __GLASGOW_HASKELL__
import qualified GHC.Exts
#endif

import Data.Functor.Identity (Identity(..))

infixl 9 \\{-This comment teaches CPP correct behaviour -}

-- A "Nat" is a 64 bit machine word
type Nat = Word64

natFromInt :: Word64 -> Nat
natFromInt :: Mask -> Mask
natFromInt = Mask -> Mask
forall a. a -> a
id
{-# INLINE natFromInt #-}

intFromNat :: Nat -> Word64
intFromNat :: Mask -> Mask
intFromNat = Mask -> Mask
forall a. a -> a
id
{-# INLINE intFromNat #-}

{--------------------------------------------------------------------
  Operators
--------------------------------------------------------------------}
-- | \(O(n+m)\). See 'difference'.
(\\) :: Word64Set -> Word64Set -> Word64Set
Word64Set
m1 \\ :: Word64Set -> Word64Set -> Word64Set
\\ Word64Set
m2 = Word64Set -> Word64Set -> Word64Set
difference Word64Set
m1 Word64Set
m2

{--------------------------------------------------------------------
  Types
--------------------------------------------------------------------}

-- | A set of integers.

-- See Note: Order of constructors
data Word64Set = Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !Word64Set !Word64Set
-- Invariant: Nil is never found as a child of Bin.
-- Invariant: The Mask is a power of 2.  It is the largest bit position at which
--            two elements of the set differ.
-- Invariant: Prefix is the common high-order bits that all elements share to
--            the left of the Mask bit.
-- Invariant: In Bin prefix mask left right, left consists of the elements that
--            don't have the mask bit set; right is all the elements that do.
            | Tip {-# UNPACK #-} !Prefix {-# UNPACK #-} !BitMap
-- Invariant: The Prefix is zero for the last 6 bits. The values of the set
--            represented by a tip are the prefix plus the indices of the set
--            bits in the bit map.
            | Nil

-- A number stored in a set is stored as
-- * Prefix (all but last 6 bits) and
-- * BitMap (last 6 bits stored as a bitmask)
--   Last 6 bits are called a Suffix.

type Prefix = Word64
type Mask   = Word64
type BitMap = Word64
type Key    = Word64

instance Monoid Word64Set where
    mempty :: Word64Set
mempty  = Word64Set
empty
    mconcat :: [Word64Set] -> Word64Set
mconcat = [Word64Set] -> Word64Set
unions
    mappend :: Word64Set -> Word64Set -> Word64Set
mappend = Word64Set -> Word64Set -> Word64Set
forall a. Semigroup a => a -> a -> a
(<>)

-- | @since 0.5.7
instance Semigroup Word64Set where
    <> :: Word64Set -> Word64Set -> Word64Set
(<>)    = Word64Set -> Word64Set -> Word64Set
union
    stimes :: forall b. Integral b => b -> Word64Set -> Word64Set
stimes  = b -> Word64Set -> Word64Set
forall b a. (Integral b, Monoid a) => b -> a -> a
stimesIdempotentMonoid

#if __GLASGOW_HASKELL__

{--------------------------------------------------------------------
  A Data instance
--------------------------------------------------------------------}

-- This instance preserves data abstraction at the cost of inefficiency.
-- We provide limited reflection services for the sake of data abstraction.

instance Data Word64Set where
  gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Word64Set -> c Word64Set
gfoldl forall d b. Data d => c (d -> b) -> d -> c b
f forall g. g -> c g
z Word64Set
is = ([Mask] -> Word64Set) -> c ([Mask] -> Word64Set)
forall g. g -> c g
z [Mask] -> Word64Set
fromList c ([Mask] -> Word64Set) -> [Mask] -> c Word64Set
forall d b. Data d => c (d -> b) -> d -> c b
`f` (Word64Set -> [Mask]
toList Word64Set
is)
  toConstr :: Word64Set -> Constr
toConstr Word64Set
_     = Constr
fromListConstr
  gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c Word64Set
gunfold forall b r. Data b => c (b -> r) -> c r
k forall r. r -> c r
z Constr
c  = case Constr -> Int
constrIndex Constr
c of
    Int
1 -> c ([Mask] -> Word64Set) -> c Word64Set
forall b r. Data b => c (b -> r) -> c r
k (([Mask] -> Word64Set) -> c ([Mask] -> Word64Set)
forall r. r -> c r
z [Mask] -> Word64Set
fromList)
    Int
_ -> [Char] -> c Word64Set
forall a. HasCallStack => [Char] -> a
error [Char]
"gunfold"
  dataTypeOf :: Word64Set -> DataType
dataTypeOf Word64Set
_   = DataType
intSetDataType

fromListConstr :: Constr
fromListConstr :: Constr
fromListConstr = DataType -> [Char] -> [[Char]] -> Fixity -> Constr
mkConstr DataType
intSetDataType [Char]
"fromList" [] Fixity
Data.Data.Prefix

intSetDataType :: DataType
intSetDataType :: DataType
intSetDataType = [Char] -> [Constr] -> DataType
mkDataType [Char]
"Data.Word64Set.Internal.Word64Set" [Constr
fromListConstr]

#endif

{--------------------------------------------------------------------
  Query
--------------------------------------------------------------------}
-- | \(O(1)\). Is the set empty?
null :: Word64Set -> Bool
null :: Word64Set -> Bool
null Word64Set
Nil = Bool
True
null Word64Set
_   = Bool
False
{-# INLINE null #-}

-- | \(O(n)\). Cardinality of the set.
size :: Word64Set -> Int
size :: Word64Set -> Int
size = Int -> Word64Set -> Int
go Int
0
  where
    go :: Int -> Word64Set -> Int
go !Int
acc (Bin Mask
_ Mask
_ Word64Set
l Word64Set
r) = Int -> Word64Set -> Int
go (Int -> Word64Set -> Int
go Int
acc Word64Set
l) Word64Set
r
    go Int
acc (Tip Mask
_ Mask
bm) = Int
acc Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int -> Mask -> Int
bitcount Int
0 Mask
bm
    go Int
acc Word64Set
Nil = Int
acc

-- | \(O(\min(n,W))\). Is the value a member of the set?

-- See Note: Local 'go' functions and capturing.
member :: Key -> Word64Set -> Bool
member :: Mask -> Word64Set -> Bool
member !Mask
x = Word64Set -> Bool
go
  where
    go :: Word64Set -> Bool
go (Bin Mask
p Mask
m Word64Set
l Word64Set
r)
      | Mask -> Mask -> Mask -> Bool
nomatch Mask
x Mask
p Mask
m = Bool
False
      | Mask -> Mask -> Bool
zero Mask
x Mask
m      = Word64Set -> Bool
go Word64Set
l
      | Bool
otherwise     = Word64Set -> Bool
go Word64Set
r
    go (Tip Mask
y Mask
bm) = Mask -> Mask
prefixOf Mask
x Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
y Bool -> Bool -> Bool
&& Mask -> Mask
bitmapOf Mask
x Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
bm Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
0
    go Word64Set
Nil = Bool
False

-- | \(O(\min(n,W))\). Is the element not in the set?
notMember :: Key -> Word64Set -> Bool
notMember :: Mask -> Word64Set -> Bool
notMember Mask
k = Bool -> Bool
not (Bool -> Bool) -> (Word64Set -> Bool) -> Word64Set -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Mask -> Word64Set -> Bool
member Mask
k

-- | \(O(\min(n,W))\). Find largest element smaller than the given one.
--
-- > lookupLT 3 (fromList [3, 5]) == Nothing
-- > lookupLT 5 (fromList [3, 5]) == Just 3

-- See Note: Local 'go' functions and capturing.
lookupLT :: Key -> Word64Set -> Maybe Key
lookupLT :: Mask -> Word64Set -> Maybe Mask
lookupLT !Mask
x Word64Set
t = case Word64Set
t of
    Bin Mask
_ Mask
m Word64Set
l Word64Set
r | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 -> if Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
>= Mask
0 then Word64Set -> Word64Set -> Maybe Mask
go Word64Set
r Word64Set
l else Word64Set -> Word64Set -> Maybe Mask
go Word64Set
Nil Word64Set
r
    Word64Set
_ -> Word64Set -> Word64Set -> Maybe Mask
go Word64Set
Nil Word64Set
t
  where
    go :: Word64Set -> Word64Set -> Maybe Mask
go Word64Set
def (Bin Mask
p Mask
m Word64Set
l Word64Set
r) | Mask -> Mask -> Mask -> Bool
nomatch Mask
x Mask
p Mask
m = if Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
p then Word64Set -> Maybe Mask
unsafeFindMax Word64Set
def else Word64Set -> Maybe Mask
unsafeFindMax Word64Set
r
                         | Mask -> Mask -> Bool
zero Mask
x Mask
m  = Word64Set -> Word64Set -> Maybe Mask
go Word64Set
def Word64Set
l
                         | Bool
otherwise = Word64Set -> Word64Set -> Maybe Mask
go Word64Set
l Word64Set
r
    go Word64Set
def (Tip Mask
kx Mask
bm) | Mask -> Mask
prefixOf Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
> Mask
kx = Mask -> Maybe Mask
forall a. a -> Maybe a
Just (Mask -> Maybe Mask) -> Mask -> Maybe Mask
forall a b. (a -> b) -> a -> b
$ Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
highestBitSet Mask
bm
                       | Mask -> Mask
prefixOf Mask
x Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx Bool -> Bool -> Bool
&& Mask
maskLT Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
0 = Mask -> Maybe Mask
forall a. a -> Maybe a
Just (Mask -> Maybe Mask) -> Mask -> Maybe Mask
forall a b. (a -> b) -> a -> b
$ Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
highestBitSet Mask
maskLT
                       | Bool
otherwise = Word64Set -> Maybe Mask
unsafeFindMax Word64Set
def
                       where maskLT :: Mask
maskLT = (Mask -> Mask
bitmapOf Mask
x Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
- Mask
1) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
bm
    go Word64Set
def Word64Set
Nil = Word64Set -> Maybe Mask
unsafeFindMax Word64Set
def


-- | \(O(\min(n,W))\). Find smallest element greater than the given one.
--
-- > lookupGT 4 (fromList [3, 5]) == Just 5
-- > lookupGT 5 (fromList [3, 5]) == Nothing

-- See Note: Local 'go' functions and capturing.
lookupGT :: Key -> Word64Set -> Maybe Key
lookupGT :: Mask -> Word64Set -> Maybe Mask
lookupGT !Mask
x Word64Set
t = case Word64Set
t of
    Bin Mask
_ Mask
m Word64Set
l Word64Set
r | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 -> if Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
>= Mask
0 then Word64Set -> Word64Set -> Maybe Mask
go Word64Set
Nil Word64Set
l else Word64Set -> Word64Set -> Maybe Mask
go Word64Set
l Word64Set
r
    Word64Set
_ -> Word64Set -> Word64Set -> Maybe Mask
go Word64Set
Nil Word64Set
t
  where
    go :: Word64Set -> Word64Set -> Maybe Mask
go Word64Set
def (Bin Mask
p Mask
m Word64Set
l Word64Set
r) | Mask -> Mask -> Mask -> Bool
nomatch Mask
x Mask
p Mask
m = if Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
p then Word64Set -> Maybe Mask
unsafeFindMin Word64Set
l else Word64Set -> Maybe Mask
unsafeFindMin Word64Set
def
                         | Mask -> Mask -> Bool
zero Mask
x Mask
m  = Word64Set -> Word64Set -> Maybe Mask
go Word64Set
r Word64Set
l
                         | Bool
otherwise = Word64Set -> Word64Set -> Maybe Mask
go Word64Set
def Word64Set
r
    go Word64Set
def (Tip Mask
kx Mask
bm) | Mask -> Mask
prefixOf Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
kx = Mask -> Maybe Mask
forall a. a -> Maybe a
Just (Mask -> Maybe Mask) -> Mask -> Maybe Mask
forall a b. (a -> b) -> a -> b
$ Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
lowestBitSet Mask
bm
                       | Mask -> Mask
prefixOf Mask
x Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx Bool -> Bool -> Bool
&& Mask
maskGT Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
0 = Mask -> Maybe Mask
forall a. a -> Maybe a
Just (Mask -> Maybe Mask) -> Mask -> Maybe Mask
forall a b. (a -> b) -> a -> b
$ Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
lowestBitSet Mask
maskGT
                       | Bool
otherwise = Word64Set -> Maybe Mask
unsafeFindMin Word64Set
def
                       where maskGT :: Mask
maskGT = (- ((Mask -> Mask
bitmapOf Mask
x) Mask -> Int -> Mask
`shiftLL` Int
1)) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
bm
    go Word64Set
def Word64Set
Nil = Word64Set -> Maybe Mask
unsafeFindMin Word64Set
def


-- | \(O(\min(n,W))\). Find largest element smaller or equal to the given one.
--
-- > lookupLE 2 (fromList [3, 5]) == Nothing
-- > lookupLE 4 (fromList [3, 5]) == Just 3
-- > lookupLE 5 (fromList [3, 5]) == Just 5

-- See Note: Local 'go' functions and capturing.
lookupLE :: Key -> Word64Set -> Maybe Key
lookupLE :: Mask -> Word64Set -> Maybe Mask
lookupLE !Mask
x Word64Set
t = case Word64Set
t of
    Bin Mask
_ Mask
m Word64Set
l Word64Set
r | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 -> if Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
>= Mask
0 then Word64Set -> Word64Set -> Maybe Mask
go Word64Set
r Word64Set
l else Word64Set -> Word64Set -> Maybe Mask
go Word64Set
Nil Word64Set
r
    Word64Set
_ -> Word64Set -> Word64Set -> Maybe Mask
go Word64Set
Nil Word64Set
t
  where
    go :: Word64Set -> Word64Set -> Maybe Mask
go Word64Set
def (Bin Mask
p Mask
m Word64Set
l Word64Set
r) | Mask -> Mask -> Mask -> Bool
nomatch Mask
x Mask
p Mask
m = if Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
p then Word64Set -> Maybe Mask
unsafeFindMax Word64Set
def else Word64Set -> Maybe Mask
unsafeFindMax Word64Set
r
                         | Mask -> Mask -> Bool
zero Mask
x Mask
m  = Word64Set -> Word64Set -> Maybe Mask
go Word64Set
def Word64Set
l
                         | Bool
otherwise = Word64Set -> Word64Set -> Maybe Mask
go Word64Set
l Word64Set
r
    go Word64Set
def (Tip Mask
kx Mask
bm) | Mask -> Mask
prefixOf Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
> Mask
kx = Mask -> Maybe Mask
forall a. a -> Maybe a
Just (Mask -> Maybe Mask) -> Mask -> Maybe Mask
forall a b. (a -> b) -> a -> b
$ Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
highestBitSet Mask
bm
                       | Mask -> Mask
prefixOf Mask
x Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx Bool -> Bool -> Bool
&& Mask
maskLE Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
0 = Mask -> Maybe Mask
forall a. a -> Maybe a
Just (Mask -> Maybe Mask) -> Mask -> Maybe Mask
forall a b. (a -> b) -> a -> b
$ Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
highestBitSet Mask
maskLE
                       | Bool
otherwise = Word64Set -> Maybe Mask
unsafeFindMax Word64Set
def
                       where maskLE :: Mask
maskLE = (((Mask -> Mask
bitmapOf Mask
x) Mask -> Int -> Mask
`shiftLL` Int
1) Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
- Mask
1) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
bm
    go Word64Set
def Word64Set
Nil = Word64Set -> Maybe Mask
unsafeFindMax Word64Set
def


-- | \(O(\min(n,W))\). Find smallest element greater or equal to the given one.
--
-- > lookupGE 3 (fromList [3, 5]) == Just 3
-- > lookupGE 4 (fromList [3, 5]) == Just 5
-- > lookupGE 6 (fromList [3, 5]) == Nothing

-- See Note: Local 'go' functions and capturing.
lookupGE :: Key -> Word64Set -> Maybe Key
lookupGE :: Mask -> Word64Set -> Maybe Mask
lookupGE !Mask
x Word64Set
t = case Word64Set
t of
    Bin Mask
_ Mask
m Word64Set
l Word64Set
r | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 -> if Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
>= Mask
0 then Word64Set -> Word64Set -> Maybe Mask
go Word64Set
Nil Word64Set
l else Word64Set -> Word64Set -> Maybe Mask
go Word64Set
l Word64Set
r
    Word64Set
_ -> Word64Set -> Word64Set -> Maybe Mask
go Word64Set
Nil Word64Set
t
  where
    go :: Word64Set -> Word64Set -> Maybe Mask
go Word64Set
def (Bin Mask
p Mask
m Word64Set
l Word64Set
r) | Mask -> Mask -> Mask -> Bool
nomatch Mask
x Mask
p Mask
m = if Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
p then Word64Set -> Maybe Mask
unsafeFindMin Word64Set
l else Word64Set -> Maybe Mask
unsafeFindMin Word64Set
def
                         | Mask -> Mask -> Bool
zero Mask
x Mask
m  = Word64Set -> Word64Set -> Maybe Mask
go Word64Set
r Word64Set
l
                         | Bool
otherwise = Word64Set -> Word64Set -> Maybe Mask
go Word64Set
def Word64Set
r
    go Word64Set
def (Tip Mask
kx Mask
bm) | Mask -> Mask
prefixOf Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
kx = Mask -> Maybe Mask
forall a. a -> Maybe a
Just (Mask -> Maybe Mask) -> Mask -> Maybe Mask
forall a b. (a -> b) -> a -> b
$ Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
lowestBitSet Mask
bm
                       | Mask -> Mask
prefixOf Mask
x Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx Bool -> Bool -> Bool
&& Mask
maskGE Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
0 = Mask -> Maybe Mask
forall a. a -> Maybe a
Just (Mask -> Maybe Mask) -> Mask -> Maybe Mask
forall a b. (a -> b) -> a -> b
$ Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
lowestBitSet Mask
maskGE
                       | Bool
otherwise = Word64Set -> Maybe Mask
unsafeFindMin Word64Set
def
                       where maskGE :: Mask
maskGE = (- (Mask -> Mask
bitmapOf Mask
x)) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
bm
    go Word64Set
def Word64Set
Nil = Word64Set -> Maybe Mask
unsafeFindMin Word64Set
def



-- Helper function for lookupGE and lookupGT. It assumes that if a Bin node is
-- given, it has m > 0.
unsafeFindMin :: Word64Set -> Maybe Key
unsafeFindMin :: Word64Set -> Maybe Mask
unsafeFindMin Word64Set
Nil = Maybe Mask
forall a. Maybe a
Nothing
unsafeFindMin (Tip Mask
kx Mask
bm) = Mask -> Maybe Mask
forall a. a -> Maybe a
Just (Mask -> Maybe Mask) -> Mask -> Maybe Mask
forall a b. (a -> b) -> a -> b
$ Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
lowestBitSet Mask
bm
unsafeFindMin (Bin Mask
_ Mask
_ Word64Set
l Word64Set
_) = Word64Set -> Maybe Mask
unsafeFindMin Word64Set
l

-- Helper function for lookupLE and lookupLT. It assumes that if a Bin node is
-- given, it has m > 0.
unsafeFindMax :: Word64Set -> Maybe Key
unsafeFindMax :: Word64Set -> Maybe Mask
unsafeFindMax Word64Set
Nil = Maybe Mask
forall a. Maybe a
Nothing
unsafeFindMax (Tip Mask
kx Mask
bm) = Mask -> Maybe Mask
forall a. a -> Maybe a
Just (Mask -> Maybe Mask) -> Mask -> Maybe Mask
forall a b. (a -> b) -> a -> b
$ Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
highestBitSet Mask
bm
unsafeFindMax (Bin Mask
_ Mask
_ Word64Set
_ Word64Set
r) = Word64Set -> Maybe Mask
unsafeFindMax Word64Set
r

{--------------------------------------------------------------------
  Construction
--------------------------------------------------------------------}
-- | \(O(1)\). The empty set.
empty :: Word64Set
empty :: Word64Set
empty
  = Word64Set
Nil
{-# INLINE empty #-}

-- | \(O(1)\). A set of one element.
singleton :: Key -> Word64Set
singleton :: Mask -> Word64Set
singleton Mask
x
  = Mask -> Mask -> Word64Set
Tip (Mask -> Mask
prefixOf Mask
x) (Mask -> Mask
bitmapOf Mask
x)
{-# INLINE singleton #-}

{--------------------------------------------------------------------
  Insert
--------------------------------------------------------------------}
-- | \(O(\min(n,W))\). Add a value to the set. There is no left- or right bias for
-- Word64Sets.
insert :: Key -> Word64Set -> Word64Set
insert :: Mask -> Word64Set -> Word64Set
insert !Mask
x = Mask -> Mask -> Word64Set -> Word64Set
insertBM (Mask -> Mask
prefixOf Mask
x) (Mask -> Mask
bitmapOf Mask
x)

-- Helper function for insert and union.
insertBM :: Prefix -> BitMap -> Word64Set -> Word64Set
insertBM :: Mask -> Mask -> Word64Set -> Word64Set
insertBM !Mask
kx !Mask
bm t :: Word64Set
t@(Bin Mask
p Mask
m Word64Set
l Word64Set
r)
  | Mask -> Mask -> Mask -> Bool
nomatch Mask
kx Mask
p Mask
m = Mask -> Word64Set -> Mask -> Word64Set -> Word64Set
link Mask
kx (Mask -> Mask -> Word64Set
Tip Mask
kx Mask
bm) Mask
p Word64Set
t
  | Mask -> Mask -> Bool
zero Mask
kx Mask
m      = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
Bin Mask
p Mask
m (Mask -> Mask -> Word64Set -> Word64Set
insertBM Mask
kx Mask
bm Word64Set
l) Word64Set
r
  | Bool
otherwise      = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
Bin Mask
p Mask
m Word64Set
l (Mask -> Mask -> Word64Set -> Word64Set
insertBM Mask
kx Mask
bm Word64Set
r)
insertBM Mask
kx Mask
bm t :: Word64Set
t@(Tip Mask
kx' Mask
bm')
  | Mask
kx' Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx = Mask -> Mask -> Word64Set
Tip Mask
kx' (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.|. Mask
bm')
  | Bool
otherwise = Mask -> Word64Set -> Mask -> Word64Set -> Word64Set
link Mask
kx (Mask -> Mask -> Word64Set
Tip Mask
kx Mask
bm) Mask
kx' Word64Set
t
insertBM Mask
kx Mask
bm Word64Set
Nil = Mask -> Mask -> Word64Set
Tip Mask
kx Mask
bm

-- | \(O(\min(n,W))\). Delete a value in the set. Returns the
-- original set when the value was not present.
delete :: Key -> Word64Set -> Word64Set
delete :: Mask -> Word64Set -> Word64Set
delete !Mask
x = Mask -> Mask -> Word64Set -> Word64Set
deleteBM (Mask -> Mask
prefixOf Mask
x) (Mask -> Mask
bitmapOf Mask
x)

-- Deletes all values mentioned in the BitMap from the set.
-- Helper function for delete and difference.
deleteBM :: Prefix -> BitMap -> Word64Set -> Word64Set
deleteBM :: Mask -> Mask -> Word64Set -> Word64Set
deleteBM !Mask
kx !Mask
bm t :: Word64Set
t@(Bin Mask
p Mask
m Word64Set
l Word64Set
r)
  | Mask -> Mask -> Mask -> Bool
nomatch Mask
kx Mask
p Mask
m = Word64Set
t
  | Mask -> Mask -> Bool
zero Mask
kx Mask
m      = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m (Mask -> Mask -> Word64Set -> Word64Set
deleteBM Mask
kx Mask
bm Word64Set
l) Word64Set
r
  | Bool
otherwise      = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l (Mask -> Mask -> Word64Set -> Word64Set
deleteBM Mask
kx Mask
bm Word64Set
r)
deleteBM Mask
kx Mask
bm t :: Word64Set
t@(Tip Mask
kx' Mask
bm')
  | Mask
kx' Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx = Mask -> Mask -> Word64Set
tip Mask
kx (Mask
bm' Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask -> Mask
forall a. Bits a => a -> a
complement Mask
bm)
  | Bool
otherwise = Word64Set
t
deleteBM Mask
_ Mask
_ Word64Set
Nil = Word64Set
Nil

-- | \(O(\min(n,W))\). @('alterF' f x s)@ can delete or insert @x@ in @s@ depending
-- on whether it is already present in @s@.
--
-- In short:
--
-- @
-- 'member' x \<$\> 'alterF' f x s = f ('member' x s)
-- @
--
-- Note: 'alterF' is a variant of the @at@ combinator from "Control.Lens.At".
--
-- @since 0.6.3.1
alterF :: Functor f => (Bool -> f Bool) -> Key -> Word64Set -> f Word64Set
alterF :: forall (f :: * -> *).
Functor f =>
(Bool -> f Bool) -> Mask -> Word64Set -> f Word64Set
alterF Bool -> f Bool
f Mask
k Word64Set
s = (Bool -> Word64Set) -> f Bool -> f Word64Set
forall a b. (a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Bool -> Word64Set
choose (Bool -> f Bool
f Bool
member_)
  where
    member_ :: Bool
member_ = Mask -> Word64Set -> Bool
member Mask
k Word64Set
s

    (Word64Set
inserted, Word64Set
deleted)
      | Bool
member_   = (Word64Set
s         , Mask -> Word64Set -> Word64Set
delete Mask
k Word64Set
s)
      | Bool
otherwise = (Mask -> Word64Set -> Word64Set
insert Mask
k Word64Set
s, Word64Set
s         )

    choose :: Bool -> Word64Set
choose Bool
True  = Word64Set
inserted
    choose Bool
False = Word64Set
deleted
#ifndef __GLASGOW_HASKELL__
{-# INLINE alterF #-}
#else
{-# INLINABLE [2] alterF #-}

{-# RULES
"alterF/Const" forall k (f :: Bool -> Const a Bool) . alterF f k = \s -> Const . getConst . f $ member k s
 #-}
#endif

{-# SPECIALIZE alterF :: (Bool -> Identity Bool) -> Key -> Word64Set -> Identity Word64Set #-}

{--------------------------------------------------------------------
  Union
--------------------------------------------------------------------}
-- | The union of a list of sets.

{-# INLINABLE unions #-}
unions :: [Word64Set] -> Word64Set
unions :: [Word64Set] -> Word64Set
unions = (Word64Set -> Word64Set -> Word64Set)
-> Word64Set -> [Word64Set] -> Word64Set
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' Word64Set -> Word64Set -> Word64Set
union Word64Set
empty

-- | \(O(n+m)\). The union of two sets.
union :: Word64Set -> Word64Set -> Word64Set
union :: Word64Set -> Word64Set -> Word64Set
union t1 :: Word64Set
t1@(Bin Mask
p1 Mask
m1 Word64Set
l1 Word64Set
r1) t2 :: Word64Set
t2@(Bin Mask
p2 Mask
m2 Word64Set
l2 Word64Set
r2)
  | Mask -> Mask -> Bool
shorter Mask
m1 Mask
m2  = Word64Set
union1
  | Mask -> Mask -> Bool
shorter Mask
m2 Mask
m1  = Word64Set
union2
  | Mask
p1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
p2       = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
Bin Mask
p1 Mask
m1 (Word64Set -> Word64Set -> Word64Set
union Word64Set
l1 Word64Set
l2) (Word64Set -> Word64Set -> Word64Set
union Word64Set
r1 Word64Set
r2)
  | Bool
otherwise      = Mask -> Word64Set -> Mask -> Word64Set -> Word64Set
link Mask
p1 Word64Set
t1 Mask
p2 Word64Set
t2
  where
    union1 :: Word64Set
union1  | Mask -> Mask -> Mask -> Bool
nomatch Mask
p2 Mask
p1 Mask
m1  = Mask -> Word64Set -> Mask -> Word64Set -> Word64Set
link Mask
p1 Word64Set
t1 Mask
p2 Word64Set
t2
            | Mask -> Mask -> Bool
zero Mask
p2 Mask
m1        = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
Bin Mask
p1 Mask
m1 (Word64Set -> Word64Set -> Word64Set
union Word64Set
l1 Word64Set
t2) Word64Set
r1
            | Bool
otherwise         = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
Bin Mask
p1 Mask
m1 Word64Set
l1 (Word64Set -> Word64Set -> Word64Set
union Word64Set
r1 Word64Set
t2)

    union2 :: Word64Set
union2  | Mask -> Mask -> Mask -> Bool
nomatch Mask
p1 Mask
p2 Mask
m2  = Mask -> Word64Set -> Mask -> Word64Set -> Word64Set
link Mask
p1 Word64Set
t1 Mask
p2 Word64Set
t2
            | Mask -> Mask -> Bool
zero Mask
p1 Mask
m2        = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
Bin Mask
p2 Mask
m2 (Word64Set -> Word64Set -> Word64Set
union Word64Set
t1 Word64Set
l2) Word64Set
r2
            | Bool
otherwise         = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
Bin Mask
p2 Mask
m2 Word64Set
l2 (Word64Set -> Word64Set -> Word64Set
union Word64Set
t1 Word64Set
r2)

union t :: Word64Set
t@(Bin Mask
_ Mask
_ Word64Set
_ Word64Set
_) (Tip Mask
kx Mask
bm) = Mask -> Mask -> Word64Set -> Word64Set
insertBM Mask
kx Mask
bm Word64Set
t
union t :: Word64Set
t@(Bin Mask
_ Mask
_ Word64Set
_ Word64Set
_) Word64Set
Nil = Word64Set
t
union (Tip Mask
kx Mask
bm) Word64Set
t = Mask -> Mask -> Word64Set -> Word64Set
insertBM Mask
kx Mask
bm Word64Set
t
union Word64Set
Nil Word64Set
t = Word64Set
t


{--------------------------------------------------------------------
  Difference
--------------------------------------------------------------------}
-- | \(O(n+m)\). Difference between two sets.
difference :: Word64Set -> Word64Set -> Word64Set
difference :: Word64Set -> Word64Set -> Word64Set
difference t1 :: Word64Set
t1@(Bin Mask
p1 Mask
m1 Word64Set
l1 Word64Set
r1) t2 :: Word64Set
t2@(Bin Mask
p2 Mask
m2 Word64Set
l2 Word64Set
r2)
  | Mask -> Mask -> Bool
shorter Mask
m1 Mask
m2  = Word64Set
difference1
  | Mask -> Mask -> Bool
shorter Mask
m2 Mask
m1  = Word64Set
difference2
  | Mask
p1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
p2       = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p1 Mask
m1 (Word64Set -> Word64Set -> Word64Set
difference Word64Set
l1 Word64Set
l2) (Word64Set -> Word64Set -> Word64Set
difference Word64Set
r1 Word64Set
r2)
  | Bool
otherwise      = Word64Set
t1
  where
    difference1 :: Word64Set
difference1 | Mask -> Mask -> Mask -> Bool
nomatch Mask
p2 Mask
p1 Mask
m1  = Word64Set
t1
                | Mask -> Mask -> Bool
zero Mask
p2 Mask
m1        = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p1 Mask
m1 (Word64Set -> Word64Set -> Word64Set
difference Word64Set
l1 Word64Set
t2) Word64Set
r1
                | Bool
otherwise         = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p1 Mask
m1 Word64Set
l1 (Word64Set -> Word64Set -> Word64Set
difference Word64Set
r1 Word64Set
t2)

    difference2 :: Word64Set
difference2 | Mask -> Mask -> Mask -> Bool
nomatch Mask
p1 Mask
p2 Mask
m2  = Word64Set
t1
                | Mask -> Mask -> Bool
zero Mask
p1 Mask
m2        = Word64Set -> Word64Set -> Word64Set
difference Word64Set
t1 Word64Set
l2
                | Bool
otherwise         = Word64Set -> Word64Set -> Word64Set
difference Word64Set
t1 Word64Set
r2

difference t :: Word64Set
t@(Bin Mask
_ Mask
_ Word64Set
_ Word64Set
_) (Tip Mask
kx Mask
bm) = Mask -> Mask -> Word64Set -> Word64Set
deleteBM Mask
kx Mask
bm Word64Set
t
difference t :: Word64Set
t@(Bin Mask
_ Mask
_ Word64Set
_ Word64Set
_) Word64Set
Nil = Word64Set
t

difference t1 :: Word64Set
t1@(Tip Mask
kx Mask
bm) Word64Set
t2 = Word64Set -> Word64Set
differenceTip Word64Set
t2
  where differenceTip :: Word64Set -> Word64Set
differenceTip (Bin Mask
p2 Mask
m2 Word64Set
l2 Word64Set
r2) | Mask -> Mask -> Mask -> Bool
nomatch Mask
kx Mask
p2 Mask
m2 = Word64Set
t1
                                        | Mask -> Mask -> Bool
zero Mask
kx Mask
m2 = Word64Set -> Word64Set
differenceTip Word64Set
l2
                                        | Bool
otherwise = Word64Set -> Word64Set
differenceTip Word64Set
r2
        differenceTip (Tip Mask
kx2 Mask
bm2) | Mask
kx Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx2 = Mask -> Mask -> Word64Set
tip Mask
kx (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask -> Mask
forall a. Bits a => a -> a
complement Mask
bm2)
                                    | Bool
otherwise = Word64Set
t1
        differenceTip Word64Set
Nil = Word64Set
t1

difference Word64Set
Nil Word64Set
_     = Word64Set
Nil



{--------------------------------------------------------------------
  Intersection
--------------------------------------------------------------------}
-- | \(O(n+m)\). The intersection of two sets.
intersection :: Word64Set -> Word64Set -> Word64Set
intersection :: Word64Set -> Word64Set -> Word64Set
intersection t1 :: Word64Set
t1@(Bin Mask
p1 Mask
m1 Word64Set
l1 Word64Set
r1) t2 :: Word64Set
t2@(Bin Mask
p2 Mask
m2 Word64Set
l2 Word64Set
r2)
  | Mask -> Mask -> Bool
shorter Mask
m1 Mask
m2  = Word64Set
intersection1
  | Mask -> Mask -> Bool
shorter Mask
m2 Mask
m1  = Word64Set
intersection2
  | Mask
p1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
p2       = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p1 Mask
m1 (Word64Set -> Word64Set -> Word64Set
intersection Word64Set
l1 Word64Set
l2) (Word64Set -> Word64Set -> Word64Set
intersection Word64Set
r1 Word64Set
r2)
  | Bool
otherwise      = Word64Set
Nil
  where
    intersection1 :: Word64Set
intersection1 | Mask -> Mask -> Mask -> Bool
nomatch Mask
p2 Mask
p1 Mask
m1  = Word64Set
Nil
                  | Mask -> Mask -> Bool
zero Mask
p2 Mask
m1        = Word64Set -> Word64Set -> Word64Set
intersection Word64Set
l1 Word64Set
t2
                  | Bool
otherwise         = Word64Set -> Word64Set -> Word64Set
intersection Word64Set
r1 Word64Set
t2

    intersection2 :: Word64Set
intersection2 | Mask -> Mask -> Mask -> Bool
nomatch Mask
p1 Mask
p2 Mask
m2  = Word64Set
Nil
                  | Mask -> Mask -> Bool
zero Mask
p1 Mask
m2        = Word64Set -> Word64Set -> Word64Set
intersection Word64Set
t1 Word64Set
l2
                  | Bool
otherwise         = Word64Set -> Word64Set -> Word64Set
intersection Word64Set
t1 Word64Set
r2

intersection t1 :: Word64Set
t1@(Bin Mask
_ Mask
_ Word64Set
_ Word64Set
_) (Tip Mask
kx2 Mask
bm2) = Word64Set -> Word64Set
intersectBM Word64Set
t1
  where intersectBM :: Word64Set -> Word64Set
intersectBM (Bin Mask
p1 Mask
m1 Word64Set
l1 Word64Set
r1) | Mask -> Mask -> Mask -> Bool
nomatch Mask
kx2 Mask
p1 Mask
m1 = Word64Set
Nil
                                      | Mask -> Mask -> Bool
zero Mask
kx2 Mask
m1       = Word64Set -> Word64Set
intersectBM Word64Set
l1
                                      | Bool
otherwise         = Word64Set -> Word64Set
intersectBM Word64Set
r1
        intersectBM (Tip Mask
kx1 Mask
bm1) | Mask
kx1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx2 = Mask -> Mask -> Word64Set
tip Mask
kx1 (Mask
bm1 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
bm2)
                                  | Bool
otherwise = Word64Set
Nil
        intersectBM Word64Set
Nil = Word64Set
Nil

intersection (Bin Mask
_ Mask
_ Word64Set
_ Word64Set
_) Word64Set
Nil = Word64Set
Nil

intersection (Tip Mask
kx1 Mask
bm1) Word64Set
t2 = Word64Set -> Word64Set
intersectBM Word64Set
t2
  where intersectBM :: Word64Set -> Word64Set
intersectBM (Bin Mask
p2 Mask
m2 Word64Set
l2 Word64Set
r2) | Mask -> Mask -> Mask -> Bool
nomatch Mask
kx1 Mask
p2 Mask
m2 = Word64Set
Nil
                                      | Mask -> Mask -> Bool
zero Mask
kx1 Mask
m2       = Word64Set -> Word64Set
intersectBM Word64Set
l2
                                      | Bool
otherwise         = Word64Set -> Word64Set
intersectBM Word64Set
r2
        intersectBM (Tip Mask
kx2 Mask
bm2) | Mask
kx1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx2 = Mask -> Mask -> Word64Set
tip Mask
kx1 (Mask
bm1 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
bm2)
                                  | Bool
otherwise = Word64Set
Nil
        intersectBM Word64Set
Nil = Word64Set
Nil

intersection Word64Set
Nil Word64Set
_ = Word64Set
Nil

{--------------------------------------------------------------------
  Subset
--------------------------------------------------------------------}
-- | \(O(n+m)\). Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: Word64Set -> Word64Set -> Bool
isProperSubsetOf :: Word64Set -> Word64Set -> Bool
isProperSubsetOf Word64Set
t1 Word64Set
t2
  = case Word64Set -> Word64Set -> Ordering
subsetCmp Word64Set
t1 Word64Set
t2 of
      Ordering
LT -> Bool
True
      Ordering
_  -> Bool
False

subsetCmp :: Word64Set -> Word64Set -> Ordering
subsetCmp :: Word64Set -> Word64Set -> Ordering
subsetCmp t1 :: Word64Set
t1@(Bin Mask
p1 Mask
m1 Word64Set
l1 Word64Set
r1) (Bin Mask
p2 Mask
m2 Word64Set
l2 Word64Set
r2)
  | Mask -> Mask -> Bool
shorter Mask
m1 Mask
m2  = Ordering
GT
  | Mask -> Mask -> Bool
shorter Mask
m2 Mask
m1  = case Ordering
subsetCmpLt of
                       Ordering
GT -> Ordering
GT
                       Ordering
_  -> Ordering
LT
  | Mask
p1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
p2       = Ordering
subsetCmpEq
  | Bool
otherwise      = Ordering
GT  -- disjoint
  where
    subsetCmpLt :: Ordering
subsetCmpLt | Mask -> Mask -> Mask -> Bool
nomatch Mask
p1 Mask
p2 Mask
m2  = Ordering
GT
                | Mask -> Mask -> Bool
zero Mask
p1 Mask
m2        = Word64Set -> Word64Set -> Ordering
subsetCmp Word64Set
t1 Word64Set
l2
                | Bool
otherwise         = Word64Set -> Word64Set -> Ordering
subsetCmp Word64Set
t1 Word64Set
r2
    subsetCmpEq :: Ordering
subsetCmpEq = case (Word64Set -> Word64Set -> Ordering
subsetCmp Word64Set
l1 Word64Set
l2, Word64Set -> Word64Set -> Ordering
subsetCmp Word64Set
r1 Word64Set
r2) of
                    (Ordering
GT,Ordering
_ ) -> Ordering
GT
                    (Ordering
_ ,Ordering
GT) -> Ordering
GT
                    (Ordering
EQ,Ordering
EQ) -> Ordering
EQ
                    (Ordering, Ordering)
_       -> Ordering
LT

subsetCmp (Bin Mask
_ Mask
_ Word64Set
_ Word64Set
_) Word64Set
_  = Ordering
GT
subsetCmp (Tip Mask
kx1 Mask
bm1) (Tip Mask
kx2 Mask
bm2)
  | Mask
kx1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
kx2                  = Ordering
GT -- disjoint
  | Mask
bm1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
bm2                  = Ordering
EQ
  | Mask
bm1 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask -> Mask
forall a. Bits a => a -> a
complement Mask
bm2 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
0 = Ordering
LT
  | Bool
otherwise                   = Ordering
GT
subsetCmp t1 :: Word64Set
t1@(Tip Mask
kx Mask
_) (Bin Mask
p Mask
m Word64Set
l Word64Set
r)
  | Mask -> Mask -> Mask -> Bool
nomatch Mask
kx Mask
p Mask
m = Ordering
GT
  | Mask -> Mask -> Bool
zero Mask
kx Mask
m      = case Word64Set -> Word64Set -> Ordering
subsetCmp Word64Set
t1 Word64Set
l of Ordering
GT -> Ordering
GT ; Ordering
_ -> Ordering
LT
  | Bool
otherwise      = case Word64Set -> Word64Set -> Ordering
subsetCmp Word64Set
t1 Word64Set
r of Ordering
GT -> Ordering
GT ; Ordering
_ -> Ordering
LT
subsetCmp (Tip Mask
_ Mask
_) Word64Set
Nil = Ordering
GT -- disjoint
subsetCmp Word64Set
Nil Word64Set
Nil = Ordering
EQ
subsetCmp Word64Set
Nil Word64Set
_   = Ordering
LT

-- | \(O(n+m)\). Is this a subset?
-- @(s1 \`isSubsetOf\` s2)@ tells whether @s1@ is a subset of @s2@.

isSubsetOf :: Word64Set -> Word64Set -> Bool
isSubsetOf :: Word64Set -> Word64Set -> Bool
isSubsetOf t1 :: Word64Set
t1@(Bin Mask
p1 Mask
m1 Word64Set
l1 Word64Set
r1) (Bin Mask
p2 Mask
m2 Word64Set
l2 Word64Set
r2)
  | Mask -> Mask -> Bool
shorter Mask
m1 Mask
m2  = Bool
False
  | Mask -> Mask -> Bool
shorter Mask
m2 Mask
m1  = Mask -> Mask -> Mask -> Bool
match Mask
p1 Mask
p2 Mask
m2 Bool -> Bool -> Bool
&& (if Mask -> Mask -> Bool
zero Mask
p1 Mask
m2 then Word64Set -> Word64Set -> Bool
isSubsetOf Word64Set
t1 Word64Set
l2
                                                      else Word64Set -> Word64Set -> Bool
isSubsetOf Word64Set
t1 Word64Set
r2)
  | Bool
otherwise      = (Mask
p1Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
==Mask
p2) Bool -> Bool -> Bool
&& Word64Set -> Word64Set -> Bool
isSubsetOf Word64Set
l1 Word64Set
l2 Bool -> Bool -> Bool
&& Word64Set -> Word64Set -> Bool
isSubsetOf Word64Set
r1 Word64Set
r2
isSubsetOf (Bin Mask
_ Mask
_ Word64Set
_ Word64Set
_) Word64Set
_  = Bool
False
isSubsetOf (Tip Mask
kx1 Mask
bm1) (Tip Mask
kx2 Mask
bm2) = Mask
kx1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx2 Bool -> Bool -> Bool
&& Mask
bm1 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask -> Mask
forall a. Bits a => a -> a
complement Mask
bm2 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
0
isSubsetOf t1 :: Word64Set
t1@(Tip Mask
kx Mask
_) (Bin Mask
p Mask
m Word64Set
l Word64Set
r)
  | Mask -> Mask -> Mask -> Bool
nomatch Mask
kx Mask
p Mask
m = Bool
False
  | Mask -> Mask -> Bool
zero Mask
kx Mask
m      = Word64Set -> Word64Set -> Bool
isSubsetOf Word64Set
t1 Word64Set
l
  | Bool
otherwise      = Word64Set -> Word64Set -> Bool
isSubsetOf Word64Set
t1 Word64Set
r
isSubsetOf (Tip Mask
_ Mask
_) Word64Set
Nil = Bool
False
isSubsetOf Word64Set
Nil Word64Set
_         = Bool
True


{--------------------------------------------------------------------
  Disjoint
--------------------------------------------------------------------}
-- | \(O(n+m)\). Check whether two sets are disjoint (i.e. their intersection
--   is empty).
--
-- > disjoint (fromList [2,4,6])   (fromList [1,3])     == True
-- > disjoint (fromList [2,4,6,8]) (fromList [2,3,5,7]) == False
-- > disjoint (fromList [1,2])     (fromList [1,2,3,4]) == False
-- > disjoint (fromList [])        (fromList [])        == True
--
-- @since 0.5.11
disjoint :: Word64Set -> Word64Set -> Bool
disjoint :: Word64Set -> Word64Set -> Bool
disjoint t1 :: Word64Set
t1@(Bin Mask
p1 Mask
m1 Word64Set
l1 Word64Set
r1) t2 :: Word64Set
t2@(Bin Mask
p2 Mask
m2 Word64Set
l2 Word64Set
r2)
  | Mask -> Mask -> Bool
shorter Mask
m1 Mask
m2  = Bool
disjoint1
  | Mask -> Mask -> Bool
shorter Mask
m2 Mask
m1  = Bool
disjoint2
  | Mask
p1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
p2       = Word64Set -> Word64Set -> Bool
disjoint Word64Set
l1 Word64Set
l2 Bool -> Bool -> Bool
&& Word64Set -> Word64Set -> Bool
disjoint Word64Set
r1 Word64Set
r2
  | Bool
otherwise      = Bool
True
  where
    disjoint1 :: Bool
disjoint1 | Mask -> Mask -> Mask -> Bool
nomatch Mask
p2 Mask
p1 Mask
m1  = Bool
True
              | Mask -> Mask -> Bool
zero Mask
p2 Mask
m1        = Word64Set -> Word64Set -> Bool
disjoint Word64Set
l1 Word64Set
t2
              | Bool
otherwise         = Word64Set -> Word64Set -> Bool
disjoint Word64Set
r1 Word64Set
t2

    disjoint2 :: Bool
disjoint2 | Mask -> Mask -> Mask -> Bool
nomatch Mask
p1 Mask
p2 Mask
m2  = Bool
True
              | Mask -> Mask -> Bool
zero Mask
p1 Mask
m2        = Word64Set -> Word64Set -> Bool
disjoint Word64Set
t1 Word64Set
l2
              | Bool
otherwise         = Word64Set -> Word64Set -> Bool
disjoint Word64Set
t1 Word64Set
r2

disjoint t1 :: Word64Set
t1@(Bin Mask
_ Mask
_ Word64Set
_ Word64Set
_) (Tip Mask
kx2 Mask
bm2) = Word64Set -> Bool
disjointBM Word64Set
t1
  where disjointBM :: Word64Set -> Bool
disjointBM (Bin Mask
p1 Mask
m1 Word64Set
l1 Word64Set
r1) | Mask -> Mask -> Mask -> Bool
nomatch Mask
kx2 Mask
p1 Mask
m1 = Bool
True
                                     | Mask -> Mask -> Bool
zero Mask
kx2 Mask
m1       = Word64Set -> Bool
disjointBM Word64Set
l1
                                     | Bool
otherwise         = Word64Set -> Bool
disjointBM Word64Set
r1
        disjointBM (Tip Mask
kx1 Mask
bm1) | Mask
kx1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx2 = (Mask
bm1 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
bm2) Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
0
                                 | Bool
otherwise = Bool
True
        disjointBM Word64Set
Nil = Bool
True

disjoint (Bin Mask
_ Mask
_ Word64Set
_ Word64Set
_) Word64Set
Nil = Bool
True

disjoint (Tip Mask
kx1 Mask
bm1) Word64Set
t2 = Word64Set -> Bool
disjointBM Word64Set
t2
  where disjointBM :: Word64Set -> Bool
disjointBM (Bin Mask
p2 Mask
m2 Word64Set
l2 Word64Set
r2) | Mask -> Mask -> Mask -> Bool
nomatch Mask
kx1 Mask
p2 Mask
m2 = Bool
True
                                     | Mask -> Mask -> Bool
zero Mask
kx1 Mask
m2       = Word64Set -> Bool
disjointBM Word64Set
l2
                                     | Bool
otherwise         = Word64Set -> Bool
disjointBM Word64Set
r2
        disjointBM (Tip Mask
kx2 Mask
bm2) | Mask
kx1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx2 = (Mask
bm1 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
bm2) Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
0
                                 | Bool
otherwise = Bool
True
        disjointBM Word64Set
Nil = Bool
True

disjoint Word64Set
Nil Word64Set
_ = Bool
True


{--------------------------------------------------------------------
  Filter
--------------------------------------------------------------------}
-- | \(O(n)\). Filter all elements that satisfy some predicate.
filter :: (Key -> Bool) -> Word64Set -> Word64Set
filter :: (Mask -> Bool) -> Word64Set -> Word64Set
filter Mask -> Bool
predicate Word64Set
t
  = case Word64Set
t of
      Bin Mask
p Mask
m Word64Set
l Word64Set
r
        -> Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m ((Mask -> Bool) -> Word64Set -> Word64Set
filter Mask -> Bool
predicate Word64Set
l) ((Mask -> Bool) -> Word64Set -> Word64Set
filter Mask -> Bool
predicate Word64Set
r)
      Tip Mask
kx Mask
bm
        -> Mask -> Mask -> Word64Set
tip Mask
kx (Mask -> (Mask -> Mask -> Mask) -> Mask -> Mask -> Mask
forall a. Mask -> (a -> Mask -> a) -> a -> Mask -> a
foldl'Bits Mask
0 (Mask -> Mask -> Mask -> Mask
bitPred Mask
kx) Mask
0 Mask
bm)
      Word64Set
Nil -> Word64Set
Nil
  where bitPred :: Mask -> Mask -> Mask -> Mask
bitPred Mask
kx Mask
bm Mask
bi | Mask -> Bool
predicate (Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask
bi) = Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.|. Mask -> Mask
bitmapOfSuffix Mask
bi
                         | Bool
otherwise           = Mask
bm
        {-# INLINE bitPred #-}

-- | \(O(n)\). partition the set according to some predicate.
partition :: (Key -> Bool) -> Word64Set -> (Word64Set,Word64Set)
partition :: (Mask -> Bool) -> Word64Set -> (Word64Set, Word64Set)
partition Mask -> Bool
predicate0 Word64Set
t0 = StrictPair Word64Set Word64Set -> (Word64Set, Word64Set)
forall a b. StrictPair a b -> (a, b)
toPair (StrictPair Word64Set Word64Set -> (Word64Set, Word64Set))
-> StrictPair Word64Set Word64Set -> (Word64Set, Word64Set)
forall a b. (a -> b) -> a -> b
$ (Mask -> Bool) -> Word64Set -> StrictPair Word64Set Word64Set
go Mask -> Bool
predicate0 Word64Set
t0
  where
    go :: (Mask -> Bool) -> Word64Set -> StrictPair Word64Set Word64Set
go Mask -> Bool
predicate Word64Set
t
      = case Word64Set
t of
          Bin Mask
p Mask
m Word64Set
l Word64Set
r
            -> let (Word64Set
l1 :*: Word64Set
l2) = (Mask -> Bool) -> Word64Set -> StrictPair Word64Set Word64Set
go Mask -> Bool
predicate Word64Set
l
                   (Word64Set
r1 :*: Word64Set
r2) = (Mask -> Bool) -> Word64Set -> StrictPair Word64Set Word64Set
go Mask -> Bool
predicate Word64Set
r
               in Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l1 Word64Set
r1 Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l2 Word64Set
r2
          Tip Mask
kx Mask
bm
            -> let bm1 :: Mask
bm1 = Mask -> (Mask -> Mask -> Mask) -> Mask -> Mask -> Mask
forall a. Mask -> (a -> Mask -> a) -> a -> Mask -> a
foldl'Bits Mask
0 (Mask -> Mask -> Mask -> Mask
bitPred Mask
kx) Mask
0 Mask
bm
               in  Mask -> Mask -> Word64Set
tip Mask
kx Mask
bm1 Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Mask -> Mask -> Word64Set
tip Mask
kx (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
`xor` Mask
bm1)
          Word64Set
Nil -> (Word64Set
Nil Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Word64Set
Nil)
      where bitPred :: Mask -> Mask -> Mask -> Mask
bitPred Mask
kx Mask
bm Mask
bi | Mask -> Bool
predicate (Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask
bi) = Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.|. Mask -> Mask
bitmapOfSuffix Mask
bi
                             | Bool
otherwise           = Mask
bm
            {-# INLINE bitPred #-}

-- | \(O(\min(n,W))\). Take while a predicate on the elements holds.
-- The user is responsible for ensuring that for all @Int@s, @j \< k ==\> p j \>= p k@.
-- See note at 'spanAntitone'.
--
-- @
-- takeWhileAntitone p = 'fromDistinctAscList' . 'Data.List.takeWhile' p . 'toList'
-- takeWhileAntitone p = 'filter' p
-- @
--
-- @since 0.6.7
takeWhileAntitone :: (Key -> Bool) -> Word64Set -> Word64Set
takeWhileAntitone :: (Mask -> Bool) -> Word64Set -> Word64Set
takeWhileAntitone Mask -> Bool
predicate Word64Set
t =
  case Word64Set
t of
    Bin Mask
p Mask
m Word64Set
l Word64Set
r
      | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 ->
        if Mask -> Bool
predicate Mask
0 -- handle negative numbers.
        then Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m ((Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate Word64Set
l) Word64Set
r
        else (Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate Word64Set
r
    Word64Set
_ -> (Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate Word64Set
t
  where
    go :: (Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate' (Bin Mask
p Mask
m Word64Set
l Word64Set
r)
      | Mask -> Bool
predicate' (Mask -> Bool) -> Mask -> Bool
forall a b. (a -> b) -> a -> b
$! Mask
pMask -> Mask -> Mask
forall a. Num a => a -> a -> a
+Mask
m = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l ((Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate' Word64Set
r)
      | Bool
otherwise         = (Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate' Word64Set
l
    go Mask -> Bool
predicate' (Tip Mask
kx Mask
bm) = Mask -> Mask -> Word64Set
tip Mask
kx (Mask -> (Mask -> Bool) -> Mask -> Mask
takeWhileAntitoneBits Mask
kx Mask -> Bool
predicate' Mask
bm)
    go Mask -> Bool
_ Word64Set
Nil = Word64Set
Nil

-- | \(O(\min(n,W))\). Drop while a predicate on the elements holds.
-- The user is responsible for ensuring that for all @Int@s, @j \< k ==\> p j \>= p k@.
-- See note at 'spanAntitone'.
--
-- @
-- dropWhileAntitone p = 'fromDistinctAscList' . 'Data.List.dropWhile' p . 'toList'
-- dropWhileAntitone p = 'filter' (not . p)
-- @
--
-- @since 0.6.7
dropWhileAntitone :: (Key -> Bool) -> Word64Set -> Word64Set
dropWhileAntitone :: (Mask -> Bool) -> Word64Set -> Word64Set
dropWhileAntitone Mask -> Bool
predicate Word64Set
t =
  case Word64Set
t of
    Bin Mask
p Mask
m Word64Set
l Word64Set
r
      | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 ->
        if Mask -> Bool
predicate Mask
0 -- handle negative numbers.
        then (Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate Word64Set
l
        else Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l ((Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate Word64Set
r)
    Word64Set
_ -> (Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate Word64Set
t
  where
    go :: (Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate' (Bin Mask
p Mask
m Word64Set
l Word64Set
r)
      | Mask -> Bool
predicate' (Mask -> Bool) -> Mask -> Bool
forall a b. (a -> b) -> a -> b
$! Mask
pMask -> Mask -> Mask
forall a. Num a => a -> a -> a
+Mask
m = (Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate' Word64Set
r
      | Bool
otherwise         = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m ((Mask -> Bool) -> Word64Set -> Word64Set
go Mask -> Bool
predicate' Word64Set
l) Word64Set
r
    go Mask -> Bool
predicate' (Tip Mask
kx Mask
bm) = Mask -> Mask -> Word64Set
tip Mask
kx (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
`xor` Mask -> (Mask -> Bool) -> Mask -> Mask
takeWhileAntitoneBits Mask
kx Mask -> Bool
predicate' Mask
bm)
    go Mask -> Bool
_ Word64Set
Nil = Word64Set
Nil

-- | \(O(\min(n,W))\). Divide a set at the point where a predicate on the elements stops holding.
-- The user is responsible for ensuring that for all @Int@s, @j \< k ==\> p j \>= p k@.
--
-- @
-- spanAntitone p xs = ('takeWhileAntitone' p xs, 'dropWhileAntitone' p xs)
-- spanAntitone p xs = 'partition' p xs
-- @
--
-- Note: if @p@ is not actually antitone, then @spanAntitone@ will split the set
-- at some /unspecified/ point.
--
-- @since 0.6.7
spanAntitone :: (Key -> Bool) -> Word64Set -> (Word64Set, Word64Set)
spanAntitone :: (Mask -> Bool) -> Word64Set -> (Word64Set, Word64Set)
spanAntitone Mask -> Bool
predicate Word64Set
t =
  case Word64Set
t of
    Bin Mask
p Mask
m Word64Set
l Word64Set
r
      | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 ->
        if Mask -> Bool
predicate Mask
0 -- handle negative numbers.
        then
          case (Mask -> Bool) -> Word64Set -> StrictPair Word64Set Word64Set
go Mask -> Bool
predicate Word64Set
l of
            (Word64Set
lt :*: Word64Set
gt) ->
              let !lt' :: Word64Set
lt' = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
lt Word64Set
r
              in (Word64Set
lt', Word64Set
gt)
        else
          case (Mask -> Bool) -> Word64Set -> StrictPair Word64Set Word64Set
go Mask -> Bool
predicate Word64Set
r of
            (Word64Set
lt :*: Word64Set
gt) ->
              let !gt' :: Word64Set
gt' = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l Word64Set
gt
              in (Word64Set
lt, Word64Set
gt')
    Word64Set
_ -> case (Mask -> Bool) -> Word64Set -> StrictPair Word64Set Word64Set
go Mask -> Bool
predicate Word64Set
t of
          (Word64Set
lt :*: Word64Set
gt) -> (Word64Set
lt, Word64Set
gt)
  where
    go :: (Mask -> Bool) -> Word64Set -> StrictPair Word64Set Word64Set
go Mask -> Bool
predicate' (Bin Mask
p Mask
m Word64Set
l Word64Set
r)
      | Mask -> Bool
predicate' (Mask -> Bool) -> Mask -> Bool
forall a b. (a -> b) -> a -> b
$! Mask
pMask -> Mask -> Mask
forall a. Num a => a -> a -> a
+Mask
m = case (Mask -> Bool) -> Word64Set -> StrictPair Word64Set Word64Set
go Mask -> Bool
predicate' Word64Set
r of (Word64Set
lt :*: Word64Set
gt) -> Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l Word64Set
lt Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Word64Set
gt
      | Bool
otherwise         = case (Mask -> Bool) -> Word64Set -> StrictPair Word64Set Word64Set
go Mask -> Bool
predicate' Word64Set
l of (Word64Set
lt :*: Word64Set
gt) -> Word64Set
lt Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
gt Word64Set
r
    go Mask -> Bool
predicate' (Tip Mask
kx Mask
bm) = let bm' :: Mask
bm' = Mask -> (Mask -> Bool) -> Mask -> Mask
takeWhileAntitoneBits Mask
kx Mask -> Bool
predicate' Mask
bm
                                in (Mask -> Mask -> Word64Set
tip Mask
kx Mask
bm' Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Mask -> Mask -> Word64Set
tip Mask
kx (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
`xor` Mask
bm'))
    go Mask -> Bool
_ Word64Set
Nil = (Word64Set
Nil Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Word64Set
Nil)

-- | \(O(\min(n,W))\). The expression (@'split' x set@) is a pair @(set1,set2)@
-- where @set1@ comprises the elements of @set@ less than @x@ and @set2@
-- comprises the elements of @set@ greater than @x@.
--
-- > split 3 (fromList [1..5]) == (fromList [1,2], fromList [4,5])
split :: Key -> Word64Set -> (Word64Set,Word64Set)
split :: Mask -> Word64Set -> (Word64Set, Word64Set)
split Mask
x Word64Set
t =
  case Word64Set
t of
    Bin Mask
p Mask
m Word64Set
l Word64Set
r
      | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 ->
        if Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
>= Mask
0  -- handle negative numbers.
        then
          case Mask -> Word64Set -> StrictPair Word64Set Word64Set
go Mask
x Word64Set
l of
            (Word64Set
lt :*: Word64Set
gt) ->
              let !lt' :: Word64Set
lt' = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
lt Word64Set
r
              in (Word64Set
lt', Word64Set
gt)
        else
          case Mask -> Word64Set -> StrictPair Word64Set Word64Set
go Mask
x Word64Set
r of
            (Word64Set
lt :*: Word64Set
gt) ->
              let !gt' :: Word64Set
gt' = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l Word64Set
gt
              in (Word64Set
lt, Word64Set
gt')
    Word64Set
_ -> case Mask -> Word64Set -> StrictPair Word64Set Word64Set
go Mask
x Word64Set
t of
          (Word64Set
lt :*: Word64Set
gt) -> (Word64Set
lt, Word64Set
gt)
  where
    go :: Mask -> Word64Set -> StrictPair Word64Set Word64Set
go !Mask
x' t' :: Word64Set
t'@(Bin Mask
p Mask
m Word64Set
l Word64Set
r)
        | Mask -> Mask -> Mask -> Bool
nomatch Mask
x' Mask
p Mask
m = if Mask
x' Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
p then (Word64Set
Nil Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Word64Set
t') else (Word64Set
t' Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Word64Set
Nil)
        | Mask -> Mask -> Bool
zero Mask
x' Mask
m      = case Mask -> Word64Set -> StrictPair Word64Set Word64Set
go Mask
x' Word64Set
l of (Word64Set
lt :*: Word64Set
gt) -> Word64Set
lt Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
gt Word64Set
r
        | Bool
otherwise      = case Mask -> Word64Set -> StrictPair Word64Set Word64Set
go Mask
x' Word64Set
r of (Word64Set
lt :*: Word64Set
gt) -> Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l Word64Set
lt Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Word64Set
gt
    go Mask
x' t' :: Word64Set
t'@(Tip Mask
kx' Mask
bm)
        | Mask
kx' Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
> Mask
x'          = (Word64Set
Nil Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Word64Set
t')
          -- equivalent to kx' > prefixOf x'
        | Mask
kx' Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask -> Mask
prefixOf Mask
x' = (Word64Set
t' Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Word64Set
Nil)
        | Bool
otherwise = Mask -> Mask -> Word64Set
tip Mask
kx' (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
lowerBitmap) Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Mask -> Mask -> Word64Set
tip Mask
kx' (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
higherBitmap)
            where lowerBitmap :: Mask
lowerBitmap = Mask -> Mask
bitmapOf Mask
x' Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
- Mask
1
                  higherBitmap :: Mask
higherBitmap = Mask -> Mask
forall a. Bits a => a -> a
complement (Mask
lowerBitmap Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
bitmapOf Mask
x')
    go Mask
_ Word64Set
Nil = (Word64Set
Nil Word64Set -> Word64Set -> StrictPair Word64Set Word64Set
forall a b. a -> b -> StrictPair a b
:*: Word64Set
Nil)

-- | \(O(\min(n,W))\). Performs a 'split' but also returns whether the pivot
-- element was found in the original set.
splitMember :: Key -> Word64Set -> (Word64Set,Bool,Word64Set)
splitMember :: Mask -> Word64Set -> (Word64Set, Bool, Word64Set)
splitMember Mask
x Word64Set
t =
  case Word64Set
t of
    Bin Mask
p Mask
m Word64Set
l Word64Set
r
      | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 ->
        if Mask
x Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
>= Mask
0 -- handle negative numbers.
        then
          case Mask -> Word64Set -> (Word64Set, Bool, Word64Set)
go Mask
x Word64Set
l of
            (Word64Set
lt, Bool
fnd, Word64Set
gt) ->
              let !lt' :: Word64Set
lt' = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
lt Word64Set
r
              in (Word64Set
lt', Bool
fnd, Word64Set
gt)
        else
          case Mask -> Word64Set -> (Word64Set, Bool, Word64Set)
go Mask
x Word64Set
r of
            (Word64Set
lt, Bool
fnd, Word64Set
gt) ->
              let !gt' :: Word64Set
gt' = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l Word64Set
gt
              in (Word64Set
lt, Bool
fnd, Word64Set
gt')
    Word64Set
_ -> Mask -> Word64Set -> (Word64Set, Bool, Word64Set)
go Mask
x Word64Set
t
  where
    go :: Mask -> Word64Set -> (Word64Set, Bool, Word64Set)
go Mask
x' t' :: Word64Set
t'@(Bin Mask
p Mask
m Word64Set
l Word64Set
r)
        | Mask -> Mask -> Mask -> Bool
nomatch Mask
x' Mask
p Mask
m = if Mask
x' Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
p then (Word64Set
Nil, Bool
False, Word64Set
t') else (Word64Set
t', Bool
False, Word64Set
Nil)
        | Mask -> Mask -> Bool
zero Mask
x' Mask
m =
          case Mask -> Word64Set -> (Word64Set, Bool, Word64Set)
go Mask
x' Word64Set
l of
            (Word64Set
lt, Bool
fnd, Word64Set
gt) ->
              let !gt' :: Word64Set
gt' = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
gt Word64Set
r
              in (Word64Set
lt, Bool
fnd, Word64Set
gt')
        | Bool
otherwise =
          case Mask -> Word64Set -> (Word64Set, Bool, Word64Set)
go Mask
x' Word64Set
r of
            (Word64Set
lt, Bool
fnd, Word64Set
gt) ->
              let !lt' :: Word64Set
lt' = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l Word64Set
lt
              in (Word64Set
lt', Bool
fnd, Word64Set
gt)
    go Mask
x' t' :: Word64Set
t'@(Tip Mask
kx' Mask
bm)
        | Mask
kx' Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
> Mask
x'          = (Word64Set
Nil, Bool
False, Word64Set
t')
          -- equivalent to kx' > prefixOf x'
        | Mask
kx' Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask -> Mask
prefixOf Mask
x' = (Word64Set
t', Bool
False, Word64Set
Nil)
        | Bool
otherwise = let !lt :: Word64Set
lt = Mask -> Mask -> Word64Set
tip Mask
kx' (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
lowerBitmap)
                          !found :: Bool
found = (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
bitmapOfx') Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
0
                          !gt :: Word64Set
gt = Mask -> Mask -> Word64Set
tip Mask
kx' (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
higherBitmap)
                      in (Word64Set
lt, Bool
found, Word64Set
gt)
            where bitmapOfx' :: Mask
bitmapOfx' = Mask -> Mask
bitmapOf Mask
x'
                  lowerBitmap :: Mask
lowerBitmap = Mask
bitmapOfx' Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
- Mask
1
                  higherBitmap :: Mask
higherBitmap = Mask -> Mask
forall a. Bits a => a -> a
complement (Mask
lowerBitmap Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask
bitmapOfx')
    go Mask
_ Word64Set
Nil = (Word64Set
Nil, Bool
False, Word64Set
Nil)

{----------------------------------------------------------------------
  Min/Max
----------------------------------------------------------------------}

-- | \(O(\min(n,W))\). Retrieves the maximal key of the set, and the set
-- stripped of that element, or 'Nothing' if passed an empty set.
maxView :: Word64Set -> Maybe (Key, Word64Set)
maxView :: Word64Set -> Maybe (Mask, Word64Set)
maxView Word64Set
t =
  case Word64Set
t of Word64Set
Nil -> Maybe (Mask, Word64Set)
forall a. Maybe a
Nothing
            Bin Mask
p Mask
m Word64Set
l Word64Set
r | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 -> case Word64Set -> (Mask, Word64Set)
go Word64Set
l of (Mask
result, Word64Set
l') -> (Mask, Word64Set) -> Maybe (Mask, Word64Set)
forall a. a -> Maybe a
Just (Mask
result, Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l' Word64Set
r)
            Word64Set
_ -> (Mask, Word64Set) -> Maybe (Mask, Word64Set)
forall a. a -> Maybe a
Just (Word64Set -> (Mask, Word64Set)
go Word64Set
t)
  where
    go :: Word64Set -> (Mask, Word64Set)
go (Bin Mask
p Mask
m Word64Set
l Word64Set
r) = case Word64Set -> (Mask, Word64Set)
go Word64Set
r of (Mask
result, Word64Set
r') -> (Mask
result, Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l Word64Set
r')
    go (Tip Mask
kx Mask
bm) = case Mask -> Mask
highestBitSet Mask
bm of Mask
bi -> (Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask
bi, Mask -> Mask -> Word64Set
tip Mask
kx (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask -> Mask
forall a. Bits a => a -> a
complement (Mask -> Mask
bitmapOfSuffix Mask
bi)))
    go Word64Set
Nil = [Char] -> (Mask, Word64Set)
forall a. HasCallStack => [Char] -> a
error [Char]
"maxView Nil"

-- | \(O(\min(n,W))\). Retrieves the minimal key of the set, and the set
-- stripped of that element, or 'Nothing' if passed an empty set.
minView :: Word64Set -> Maybe (Key, Word64Set)
minView :: Word64Set -> Maybe (Mask, Word64Set)
minView Word64Set
t =
  case Word64Set
t of Word64Set
Nil -> Maybe (Mask, Word64Set)
forall a. Maybe a
Nothing
            Bin Mask
p Mask
m Word64Set
l Word64Set
r | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 -> case Word64Set -> (Mask, Word64Set)
go Word64Set
r of (Mask
result, Word64Set
r') -> (Mask, Word64Set) -> Maybe (Mask, Word64Set)
forall a. a -> Maybe a
Just (Mask
result, Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l Word64Set
r')
            Word64Set
_ -> (Mask, Word64Set) -> Maybe (Mask, Word64Set)
forall a. a -> Maybe a
Just (Word64Set -> (Mask, Word64Set)
go Word64Set
t)
  where
    go :: Word64Set -> (Mask, Word64Set)
go (Bin Mask
p Mask
m Word64Set
l Word64Set
r) = case Word64Set -> (Mask, Word64Set)
go Word64Set
l of (Mask
result, Word64Set
l') -> (Mask
result, Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
p Mask
m Word64Set
l' Word64Set
r)
    go (Tip Mask
kx Mask
bm) = case Mask -> Mask
lowestBitSet Mask
bm of Mask
bi -> (Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask
bi, Mask -> Mask -> Word64Set
tip Mask
kx (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask -> Mask
forall a. Bits a => a -> a
complement (Mask -> Mask
bitmapOfSuffix Mask
bi)))
    go Word64Set
Nil = [Char] -> (Mask, Word64Set)
forall a. HasCallStack => [Char] -> a
error [Char]
"minView Nil"

-- | \(O(\min(n,W))\). Delete and find the minimal element.
--
-- > deleteFindMin set = (findMin set, deleteMin set)
deleteFindMin :: Word64Set -> (Key, Word64Set)
deleteFindMin :: Word64Set -> (Mask, Word64Set)
deleteFindMin = (Mask, Word64Set) -> Maybe (Mask, Word64Set) -> (Mask, Word64Set)
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> (Mask, Word64Set)
forall a. HasCallStack => [Char] -> a
error [Char]
"deleteFindMin: empty set has no minimal element") (Maybe (Mask, Word64Set) -> (Mask, Word64Set))
-> (Word64Set -> Maybe (Mask, Word64Set))
-> Word64Set
-> (Mask, Word64Set)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word64Set -> Maybe (Mask, Word64Set)
minView

-- | \(O(\min(n,W))\). Delete and find the maximal element.
--
-- > deleteFindMax set = (findMax set, deleteMax set)
deleteFindMax :: Word64Set -> (Key, Word64Set)
deleteFindMax :: Word64Set -> (Mask, Word64Set)
deleteFindMax = (Mask, Word64Set) -> Maybe (Mask, Word64Set) -> (Mask, Word64Set)
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> (Mask, Word64Set)
forall a. HasCallStack => [Char] -> a
error [Char]
"deleteFindMax: empty set has no maximal element") (Maybe (Mask, Word64Set) -> (Mask, Word64Set))
-> (Word64Set -> Maybe (Mask, Word64Set))
-> Word64Set
-> (Mask, Word64Set)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word64Set -> Maybe (Mask, Word64Set)
maxView


-- | \(O(\min(n,W))\). The minimal element of the set.
findMin :: Word64Set -> Key
findMin :: Word64Set -> Mask
findMin Word64Set
Nil = [Char] -> Mask
forall a. HasCallStack => [Char] -> a
error [Char]
"findMin: empty set has no minimal element"
findMin (Tip Mask
kx Mask
bm) = Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
lowestBitSet Mask
bm
findMin (Bin Mask
_ Mask
m Word64Set
l Word64Set
r)
  |   Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0   = Word64Set -> Mask
find Word64Set
r
  | Bool
otherwise = Word64Set -> Mask
find Word64Set
l
    where find :: Word64Set -> Mask
find (Tip Mask
kx Mask
bm) = Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
lowestBitSet Mask
bm
          find (Bin Mask
_ Mask
_ Word64Set
l' Word64Set
_) = Word64Set -> Mask
find Word64Set
l'
          find Word64Set
Nil            = [Char] -> Mask
forall a. HasCallStack => [Char] -> a
error [Char]
"findMin Nil"

-- | \(O(\min(n,W))\). The maximal element of a set.
findMax :: Word64Set -> Key
findMax :: Word64Set -> Mask
findMax Word64Set
Nil = [Char] -> Mask
forall a. HasCallStack => [Char] -> a
error [Char]
"findMax: empty set has no maximal element"
findMax (Tip Mask
kx Mask
bm) = Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
highestBitSet Mask
bm
findMax (Bin Mask
_ Mask
m Word64Set
l Word64Set
r)
  |   Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0   = Word64Set -> Mask
find Word64Set
l
  | Bool
otherwise = Word64Set -> Mask
find Word64Set
r
    where find :: Word64Set -> Mask
find (Tip Mask
kx Mask
bm) = Mask
kx Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Mask -> Mask
highestBitSet Mask
bm
          find (Bin Mask
_ Mask
_ Word64Set
_ Word64Set
r') = Word64Set -> Mask
find Word64Set
r'
          find Word64Set
Nil            = [Char] -> Mask
forall a. HasCallStack => [Char] -> a
error [Char]
"findMax Nil"


-- | \(O(\min(n,W))\). Delete the minimal element. Returns an empty set if the set is empty.
--
-- Note that this is a change of behaviour for consistency with 'Data.Set.Set' &#8211;
-- versions prior to 0.5 threw an error if the 'Word64Set' was already empty.
deleteMin :: Word64Set -> Word64Set
deleteMin :: Word64Set -> Word64Set
deleteMin = Word64Set
-> ((Mask, Word64Set) -> Word64Set)
-> Maybe (Mask, Word64Set)
-> Word64Set
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Word64Set
Nil (Mask, Word64Set) -> Word64Set
forall a b. (a, b) -> b
snd (Maybe (Mask, Word64Set) -> Word64Set)
-> (Word64Set -> Maybe (Mask, Word64Set)) -> Word64Set -> Word64Set
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word64Set -> Maybe (Mask, Word64Set)
minView

-- | \(O(\min(n,W))\). Delete the maximal element. Returns an empty set if the set is empty.
--
-- Note that this is a change of behaviour for consistency with 'Data.Set.Set' &#8211;
-- versions prior to 0.5 threw an error if the 'Word64Set' was already empty.
deleteMax :: Word64Set -> Word64Set
deleteMax :: Word64Set -> Word64Set
deleteMax = Word64Set
-> ((Mask, Word64Set) -> Word64Set)
-> Maybe (Mask, Word64Set)
-> Word64Set
forall b a. b -> (a -> b) -> Maybe a -> b
maybe Word64Set
Nil (Mask, Word64Set) -> Word64Set
forall a b. (a, b) -> b
snd (Maybe (Mask, Word64Set) -> Word64Set)
-> (Word64Set -> Maybe (Mask, Word64Set)) -> Word64Set -> Word64Set
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word64Set -> Maybe (Mask, Word64Set)
maxView

{----------------------------------------------------------------------
  Map
----------------------------------------------------------------------}

-- | \(O(n \min(n,W))\).
-- @'map' f s@ is the set obtained by applying @f@ to each element of @s@.
--
-- It's worth noting that the size of the result may be smaller if,
-- for some @(x,y)@, @x \/= y && f x == f y@

map :: (Key -> Key) -> Word64Set -> Word64Set
map :: (Mask -> Mask) -> Word64Set -> Word64Set
map Mask -> Mask
f = [Mask] -> Word64Set
fromList ([Mask] -> Word64Set)
-> (Word64Set -> [Mask]) -> Word64Set -> Word64Set
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Mask -> Mask) -> [Mask] -> [Mask]
forall a b. (a -> b) -> [a] -> [b]
List.map Mask -> Mask
f ([Mask] -> [Mask]) -> (Word64Set -> [Mask]) -> Word64Set -> [Mask]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word64Set -> [Mask]
toList

-- | \(O(n)\). The
--
-- @'mapMonotonic' f s == 'map' f s@, but works only when @f@ is strictly increasing.
-- /The precondition is not checked./
-- Semi-formally, we have:
--
-- > and [x < y ==> f x < f y | x <- ls, y <- ls]
-- >                     ==> mapMonotonic f s == map f s
-- >     where ls = toList s
--
-- @since 0.6.3.1

-- Note that for now the test is insufficient to support any fancier implementation.
mapMonotonic :: (Key -> Key) -> Word64Set -> Word64Set
mapMonotonic :: (Mask -> Mask) -> Word64Set -> Word64Set
mapMonotonic Mask -> Mask
f = [Mask] -> Word64Set
fromDistinctAscList ([Mask] -> Word64Set)
-> (Word64Set -> [Mask]) -> Word64Set -> Word64Set
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Mask -> Mask) -> [Mask] -> [Mask]
forall a b. (a -> b) -> [a] -> [b]
List.map Mask -> Mask
f ([Mask] -> [Mask]) -> (Word64Set -> [Mask]) -> Word64Set -> [Mask]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word64Set -> [Mask]
toAscList


{--------------------------------------------------------------------
  Fold
--------------------------------------------------------------------}
-- | \(O(n)\). Fold the elements in the set using the given right-associative
-- binary operator. This function is an equivalent of 'foldr' and is present
-- for compatibility only.
--
-- /Please note that fold will be deprecated in the future and removed./
fold :: (Key -> b -> b) -> b -> Word64Set -> b
fold :: forall b. (Mask -> b -> b) -> b -> Word64Set -> b
fold = (Mask -> b -> b) -> b -> Word64Set -> b
forall b. (Mask -> b -> b) -> b -> Word64Set -> b
foldr
{-# INLINE fold #-}

-- | \(O(n)\). Fold the elements in the set using the given right-associative
-- binary operator, such that @'foldr' f z == 'Prelude.foldr' f z . 'toAscList'@.
--
-- For example,
--
-- > toAscList set = foldr (:) [] set
foldr :: (Key -> b -> b) -> b -> Word64Set -> b
foldr :: forall b. (Mask -> b -> b) -> b -> Word64Set -> b
foldr Mask -> b -> b
f b
z = \Word64Set
t ->      -- Use lambda t to be inlinable with two arguments only.
  case Word64Set
t of Bin Mask
_ Mask
m Word64Set
l Word64Set
r | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 -> b -> Word64Set -> b
go (b -> Word64Set -> b
go b
z Word64Set
l) Word64Set
r -- put negative numbers before
                        | Bool
otherwise -> b -> Word64Set -> b
go (b -> Word64Set -> b
go b
z Word64Set
r) Word64Set
l
            Word64Set
_ -> b -> Word64Set -> b
go b
z Word64Set
t
  where
    go :: b -> Word64Set -> b
go b
z' Word64Set
Nil           = b
z'
    go b
z' (Tip Mask
kx Mask
bm)   = Mask -> (Mask -> b -> b) -> b -> Mask -> b
forall a. Mask -> (Mask -> a -> a) -> a -> Mask -> a
foldrBits Mask
kx Mask -> b -> b
f b
z' Mask
bm
    go b
z' (Bin Mask
_ Mask
_ Word64Set
l Word64Set
r) = b -> Word64Set -> b
go (b -> Word64Set -> b
go b
z' Word64Set
r) Word64Set
l
{-# INLINE foldr #-}

-- | \(O(n)\). A strict version of 'foldr'. Each application of the operator is
-- evaluated before using the result in the next application. This
-- function is strict in the starting value.
foldr' :: (Key -> b -> b) -> b -> Word64Set -> b
foldr' :: forall b. (Mask -> b -> b) -> b -> Word64Set -> b
foldr' Mask -> b -> b
f b
z = \Word64Set
t ->      -- Use lambda t to be inlinable with two arguments only.
  case Word64Set
t of Bin Mask
_ Mask
m Word64Set
l Word64Set
r | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 -> b -> Word64Set -> b
go (b -> Word64Set -> b
go b
z Word64Set
l) Word64Set
r -- put negative numbers before
                        | Bool
otherwise -> b -> Word64Set -> b
go (b -> Word64Set -> b
go b
z Word64Set
r) Word64Set
l
            Word64Set
_ -> b -> Word64Set -> b
go b
z Word64Set
t
  where
    go :: b -> Word64Set -> b
go !b
z' Word64Set
Nil           = b
z'
    go b
z' (Tip Mask
kx Mask
bm)   = Mask -> (Mask -> b -> b) -> b -> Mask -> b
forall a. Mask -> (Mask -> a -> a) -> a -> Mask -> a
foldr'Bits Mask
kx Mask -> b -> b
f b
z' Mask
bm
    go b
z' (Bin Mask
_ Mask
_ Word64Set
l Word64Set
r) = b -> Word64Set -> b
go (b -> Word64Set -> b
go b
z' Word64Set
r) Word64Set
l
{-# INLINE foldr' #-}

-- | \(O(n)\). Fold the elements in the set using the given left-associative
-- binary operator, such that @'foldl' f z == 'Prelude.foldl' f z . 'toAscList'@.
--
-- For example,
--
-- > toDescList set = foldl (flip (:)) [] set
foldl :: (a -> Key -> a) -> a -> Word64Set -> a
foldl :: forall a. (a -> Mask -> a) -> a -> Word64Set -> a
foldl a -> Mask -> a
f a
z = \Word64Set
t ->      -- Use lambda t to be inlinable with two arguments only.
  case Word64Set
t of Bin Mask
_ Mask
m Word64Set
l Word64Set
r | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 -> a -> Word64Set -> a
go (a -> Word64Set -> a
go a
z Word64Set
r) Word64Set
l -- put negative numbers before
                        | Bool
otherwise -> a -> Word64Set -> a
go (a -> Word64Set -> a
go a
z Word64Set
l) Word64Set
r
            Word64Set
_ -> a -> Word64Set -> a
go a
z Word64Set
t
  where
    go :: a -> Word64Set -> a
go a
z' Word64Set
Nil           = a
z'
    go a
z' (Tip Mask
kx Mask
bm)   = Mask -> (a -> Mask -> a) -> a -> Mask -> a
forall a. Mask -> (a -> Mask -> a) -> a -> Mask -> a
foldlBits Mask
kx a -> Mask -> a
f a
z' Mask
bm
    go a
z' (Bin Mask
_ Mask
_ Word64Set
l Word64Set
r) = a -> Word64Set -> a
go (a -> Word64Set -> a
go a
z' Word64Set
l) Word64Set
r
{-# INLINE foldl #-}

-- | \(O(n)\). A strict version of 'foldl'. Each application of the operator is
-- evaluated before using the result in the next application. This
-- function is strict in the starting value.
foldl' :: (a -> Key -> a) -> a -> Word64Set -> a
foldl' :: forall a. (a -> Mask -> a) -> a -> Word64Set -> a
foldl' a -> Mask -> a
f a
z = \Word64Set
t ->      -- Use lambda t to be inlinable with two arguments only.
  case Word64Set
t of Bin Mask
_ Mask
m Word64Set
l Word64Set
r | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 -> a -> Word64Set -> a
go (a -> Word64Set -> a
go a
z Word64Set
r) Word64Set
l -- put negative numbers before
                        | Bool
otherwise -> a -> Word64Set -> a
go (a -> Word64Set -> a
go a
z Word64Set
l) Word64Set
r
            Word64Set
_ -> a -> Word64Set -> a
go a
z Word64Set
t
  where
    go :: a -> Word64Set -> a
go !a
z' Word64Set
Nil           = a
z'
    go a
z' (Tip Mask
kx Mask
bm)   = Mask -> (a -> Mask -> a) -> a -> Mask -> a
forall a. Mask -> (a -> Mask -> a) -> a -> Mask -> a
foldl'Bits Mask
kx a -> Mask -> a
f a
z' Mask
bm
    go a
z' (Bin Mask
_ Mask
_ Word64Set
l Word64Set
r) = a -> Word64Set -> a
go (a -> Word64Set -> a
go a
z' Word64Set
l) Word64Set
r
{-# INLINE foldl' #-}

{--------------------------------------------------------------------
  List variations
--------------------------------------------------------------------}
-- | \(O(n)\). An alias of 'toAscList'. The elements of a set in ascending order.
-- Subject to list fusion.
elems :: Word64Set -> [Key]
elems :: Word64Set -> [Mask]
elems
  = Word64Set -> [Mask]
toAscList

{--------------------------------------------------------------------
  Lists
--------------------------------------------------------------------}

#ifdef __GLASGOW_HASKELL__
-- | @since 0.5.6.2
instance GHC.Exts.IsList Word64Set where
  type Item Word64Set = Key
  fromList :: [Item Word64Set] -> Word64Set
fromList = [Mask] -> Word64Set
[Item Word64Set] -> Word64Set
fromList
  toList :: Word64Set -> [Item Word64Set]
toList   = Word64Set -> [Mask]
Word64Set -> [Item Word64Set]
toList
#endif

-- | \(O(n)\). Convert the set to a list of elements. Subject to list fusion.
toList :: Word64Set -> [Key]
toList :: Word64Set -> [Mask]
toList
  = Word64Set -> [Mask]
toAscList

-- | \(O(n)\). Convert the set to an ascending list of elements. Subject to list
-- fusion.
toAscList :: Word64Set -> [Key]
toAscList :: Word64Set -> [Mask]
toAscList = (Mask -> [Mask] -> [Mask]) -> [Mask] -> Word64Set -> [Mask]
forall b. (Mask -> b -> b) -> b -> Word64Set -> b
foldr (:) []

-- | \(O(n)\). Convert the set to a descending list of elements. Subject to list
-- fusion.
toDescList :: Word64Set -> [Key]
toDescList :: Word64Set -> [Mask]
toDescList = ([Mask] -> Mask -> [Mask]) -> [Mask] -> Word64Set -> [Mask]
forall a. (a -> Mask -> a) -> a -> Word64Set -> a
foldl ((Mask -> [Mask] -> [Mask]) -> [Mask] -> Mask -> [Mask]
forall a b c. (a -> b -> c) -> b -> a -> c
flip (:)) []

-- List fusion for the list generating functions.
#if __GLASGOW_HASKELL__
-- The foldrFB and foldlFB are foldr and foldl equivalents, used for list fusion.
-- They are important to convert unfused to{Asc,Desc}List back, see mapFB in prelude.
foldrFB :: (Key -> b -> b) -> b -> Word64Set -> b
foldrFB :: forall b. (Mask -> b -> b) -> b -> Word64Set -> b
foldrFB = (Mask -> b -> b) -> b -> Word64Set -> b
forall b. (Mask -> b -> b) -> b -> Word64Set -> b
foldr
{-# INLINE[0] foldrFB #-}
foldlFB :: (a -> Key -> a) -> a -> Word64Set -> a
foldlFB :: forall a. (a -> Mask -> a) -> a -> Word64Set -> a
foldlFB = (a -> Mask -> a) -> a -> Word64Set -> a
forall a. (a -> Mask -> a) -> a -> Word64Set -> a
foldl
{-# INLINE[0] foldlFB #-}

-- Inline elems and toList, so that we need to fuse only toAscList.
{-# INLINE elems #-}
{-# INLINE toList #-}

-- The fusion is enabled up to phase 2 included. If it does not succeed,
-- convert in phase 1 the expanded to{Asc,Desc}List calls back to
-- to{Asc,Desc}List.  In phase 0, we inline fold{lr}FB (which were used in
-- a list fusion, otherwise it would go away in phase 1), and let compiler do
-- whatever it wants with to{Asc,Desc}List -- it was forbidden to inline it
-- before phase 0, otherwise the fusion rules would not fire at all.
{-# NOINLINE[0] toAscList #-}
{-# NOINLINE[0] toDescList #-}
{-# RULES "Word64Set.toAscList" [~1] forall s . toAscList s = GHC.Exts.build (\c n -> foldrFB c n s) #-}
{-# RULES "Word64Set.toAscListBack" [1] foldrFB (:) [] = toAscList #-}
{-# RULES "Word64Set.toDescList" [~1] forall s . toDescList s = GHC.Exts.build (\c n -> foldlFB (\xs x -> c x xs) n s) #-}
{-# RULES "Word64Set.toDescListBack" [1] foldlFB (\xs x -> x : xs) [] = toDescList #-}
#endif


-- | \(O(n \min(n,W))\). Create a set from a list of integers.
{-# INLINABLE fromList #-}
fromList :: [Key] -> Word64Set
fromList :: [Mask] -> Word64Set
fromList = (Word64Set -> Mask -> Word64Set)
-> Word64Set -> [Mask] -> Word64Set
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
List.foldl' Word64Set -> Mask -> Word64Set
ins Word64Set
empty
  where
    ins :: Word64Set -> Mask -> Word64Set
ins Word64Set
t Mask
x  = Mask -> Word64Set -> Word64Set
insert Mask
x Word64Set
t

-- | \(O(n)\). Build a set from an ascending list of elements.
-- /The precondition (input list is ascending) is not checked./
fromAscList :: [Key] -> Word64Set
fromAscList :: [Mask] -> Word64Set
fromAscList = [Mask] -> Word64Set
fromMonoList
{-# NOINLINE fromAscList #-}

-- | \(O(n)\). Build a set from an ascending list of distinct elements.
-- /The precondition (input list is strictly ascending) is not checked./
fromDistinctAscList :: [Key] -> Word64Set
fromDistinctAscList :: [Mask] -> Word64Set
fromDistinctAscList = [Mask] -> Word64Set
fromAscList
{-# INLINE fromDistinctAscList #-}

-- | \(O(n)\). Build a set from a monotonic list of elements.
--
-- The precise conditions under which this function works are subtle:
-- For any branch mask, keys with the same prefix w.r.t. the branch
-- mask must occur consecutively in the list.
fromMonoList :: [Key] -> Word64Set
fromMonoList :: [Mask] -> Word64Set
fromMonoList []         = Word64Set
Nil
fromMonoList (Mask
kx : [Mask]
zs1) = Mask -> Mask -> [Mask] -> Word64Set
addAll' (Mask -> Mask
prefixOf Mask
kx) (Mask -> Mask
bitmapOf Mask
kx) [Mask]
zs1
  where
    -- `addAll'` collects all keys with the prefix `px` into a single
    -- bitmap, and then proceeds with `addAll`.
    addAll' :: Mask -> Mask -> [Mask] -> Word64Set
addAll' !Mask
px !Mask
bm []
        = Mask -> Mask -> Word64Set
Tip Mask
px Mask
bm
    addAll' !Mask
px !Mask
bm (Mask
ky : [Mask]
zs)
        | Mask
px Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask -> Mask
prefixOf Mask
ky
        = Mask -> Mask -> [Mask] -> Word64Set
addAll' Mask
px (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.|. Mask -> Mask
bitmapOf Mask
ky) [Mask]
zs
        -- inlined: | otherwise = addAll px (Tip px bm) (ky : zs)
        | Mask
py <- Mask -> Mask
prefixOf Mask
ky
        , Mask
m <- Mask -> Mask -> Mask
branchMask Mask
px Mask
py
        , Inserted Word64Set
ty [Mask]
zs' <- Mask -> Mask -> Mask -> [Mask] -> Inserted
addMany' Mask
m Mask
py (Mask -> Mask
bitmapOf Mask
ky) [Mask]
zs
        = Mask -> Word64Set -> [Mask] -> Word64Set
addAll Mask
px (Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
linkWithMask Mask
m Mask
py Word64Set
ty {-px-} (Mask -> Mask -> Word64Set
Tip Mask
px Mask
bm)) [Mask]
zs'

    -- for `addAll` and `addMany`, px is /a/ prefix inside the tree `tx`
    -- `addAll` consumes the rest of the list, adding to the tree `tx`
    addAll :: Mask -> Word64Set -> [Mask] -> Word64Set
addAll !Mask
_px !Word64Set
tx []
        = Word64Set
tx
    addAll !Mask
px !Word64Set
tx (Mask
ky : [Mask]
zs)
        | Mask
py <- Mask -> Mask
prefixOf Mask
ky
        , Mask
m <- Mask -> Mask -> Mask
branchMask Mask
px Mask
py
        , Inserted Word64Set
ty [Mask]
zs' <- Mask -> Mask -> Mask -> [Mask] -> Inserted
addMany' Mask
m Mask
py (Mask -> Mask
bitmapOf Mask
ky) [Mask]
zs
        = Mask -> Word64Set -> [Mask] -> Word64Set
addAll Mask
px (Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
linkWithMask Mask
m Mask
py Word64Set
ty {-px-} Word64Set
tx) [Mask]
zs'

    -- `addMany'` is similar to `addAll'`, but proceeds with `addMany'`.
    addMany' :: Mask -> Mask -> Mask -> [Mask] -> Inserted
addMany' !Mask
_m !Mask
px !Mask
bm []
        = Word64Set -> [Mask] -> Inserted
Inserted (Mask -> Mask -> Word64Set
Tip Mask
px Mask
bm) []
    addMany' !Mask
m !Mask
px !Mask
bm zs0 :: [Mask]
zs0@(Mask
ky : [Mask]
zs)
        | Mask
px Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask -> Mask
prefixOf Mask
ky
        = Mask -> Mask -> Mask -> [Mask] -> Inserted
addMany' Mask
m Mask
px (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.|. Mask -> Mask
bitmapOf Mask
ky) [Mask]
zs
        -- inlined: | otherwise = addMany m px (Tip px bm) (ky : zs)
        | Mask -> Mask -> Mask
mask Mask
px Mask
m Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask -> Mask -> Mask
mask Mask
ky Mask
m
        = Word64Set -> [Mask] -> Inserted
Inserted (Mask -> Mask -> Word64Set
Tip (Mask -> Mask
prefixOf Mask
px) Mask
bm) [Mask]
zs0
        | Mask
py <- Mask -> Mask
prefixOf Mask
ky
        , Mask
mxy <- Mask -> Mask -> Mask
branchMask Mask
px Mask
py
        , Inserted Word64Set
ty [Mask]
zs' <- Mask -> Mask -> Mask -> [Mask] -> Inserted
addMany' Mask
mxy Mask
py (Mask -> Mask
bitmapOf Mask
ky) [Mask]
zs
        = Mask -> Mask -> Word64Set -> [Mask] -> Inserted
addMany Mask
m Mask
px (Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
linkWithMask Mask
mxy Mask
py Word64Set
ty {-px-} (Mask -> Mask -> Word64Set
Tip Mask
px Mask
bm)) [Mask]
zs'

    -- `addAll` adds to `tx` all keys whose prefix w.r.t. `m` agrees with `px`.
    addMany :: Mask -> Mask -> Word64Set -> [Mask] -> Inserted
addMany !Mask
_m !Mask
_px Word64Set
tx []
        = Word64Set -> [Mask] -> Inserted
Inserted Word64Set
tx []
    addMany !Mask
m !Mask
px Word64Set
tx zs0 :: [Mask]
zs0@(Mask
ky : [Mask]
zs)
        | Mask -> Mask -> Mask
mask Mask
px Mask
m Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask -> Mask -> Mask
mask Mask
ky Mask
m
        = Word64Set -> [Mask] -> Inserted
Inserted Word64Set
tx [Mask]
zs0
        | Mask
py <- Mask -> Mask
prefixOf Mask
ky
        , Mask
mxy <- Mask -> Mask -> Mask
branchMask Mask
px Mask
py
        , Inserted Word64Set
ty [Mask]
zs' <- Mask -> Mask -> Mask -> [Mask] -> Inserted
addMany' Mask
mxy Mask
py (Mask -> Mask
bitmapOf Mask
ky) [Mask]
zs
        = Mask -> Mask -> Word64Set -> [Mask] -> Inserted
addMany Mask
m Mask
px (Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
linkWithMask Mask
mxy Mask
py Word64Set
ty {-px-} Word64Set
tx) [Mask]
zs'
{-# INLINE fromMonoList #-}

data Inserted = Inserted !Word64Set ![Key]

{--------------------------------------------------------------------
  Eq
--------------------------------------------------------------------}
instance Eq Word64Set where
  Word64Set
t1 == :: Word64Set -> Word64Set -> Bool
== Word64Set
t2  = Word64Set -> Word64Set -> Bool
equal Word64Set
t1 Word64Set
t2
  Word64Set
t1 /= :: Word64Set -> Word64Set -> Bool
/= Word64Set
t2  = Word64Set -> Word64Set -> Bool
nequal Word64Set
t1 Word64Set
t2

equal :: Word64Set -> Word64Set -> Bool
equal :: Word64Set -> Word64Set -> Bool
equal (Bin Mask
p1 Mask
m1 Word64Set
l1 Word64Set
r1) (Bin Mask
p2 Mask
m2 Word64Set
l2 Word64Set
r2)
  = (Mask
m1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
m2) Bool -> Bool -> Bool
&& (Mask
p1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
p2) Bool -> Bool -> Bool
&& (Word64Set -> Word64Set -> Bool
equal Word64Set
l1 Word64Set
l2) Bool -> Bool -> Bool
&& (Word64Set -> Word64Set -> Bool
equal Word64Set
r1 Word64Set
r2)
equal (Tip Mask
kx1 Mask
bm1) (Tip Mask
kx2 Mask
bm2)
  = Mask
kx1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
kx2 Bool -> Bool -> Bool
&& Mask
bm1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
bm2
equal Word64Set
Nil Word64Set
Nil = Bool
True
equal Word64Set
_   Word64Set
_   = Bool
False

nequal :: Word64Set -> Word64Set -> Bool
nequal :: Word64Set -> Word64Set -> Bool
nequal (Bin Mask
p1 Mask
m1 Word64Set
l1 Word64Set
r1) (Bin Mask
p2 Mask
m2 Word64Set
l2 Word64Set
r2)
  = (Mask
m1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
m2) Bool -> Bool -> Bool
|| (Mask
p1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
p2) Bool -> Bool -> Bool
|| (Word64Set -> Word64Set -> Bool
nequal Word64Set
l1 Word64Set
l2) Bool -> Bool -> Bool
|| (Word64Set -> Word64Set -> Bool
nequal Word64Set
r1 Word64Set
r2)
nequal (Tip Mask
kx1 Mask
bm1) (Tip Mask
kx2 Mask
bm2)
  = Mask
kx1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
kx2 Bool -> Bool -> Bool
|| Mask
bm1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
bm2
nequal Word64Set
Nil Word64Set
Nil = Bool
False
nequal Word64Set
_   Word64Set
_   = Bool
True

{--------------------------------------------------------------------
  Ord
--------------------------------------------------------------------}

instance Ord Word64Set where
    compare :: Word64Set -> Word64Set -> Ordering
compare Word64Set
s1 Word64Set
s2 = [Mask] -> [Mask] -> Ordering
forall a. Ord a => a -> a -> Ordering
compare (Word64Set -> [Mask]
toAscList Word64Set
s1) (Word64Set -> [Mask]
toAscList Word64Set
s2)
    -- tentative implementation. See if more efficient exists.

{--------------------------------------------------------------------
  Show
--------------------------------------------------------------------}
instance Show Word64Set where
  showsPrec :: Int -> Word64Set -> ShowS
showsPrec Int
p Word64Set
xs = Bool -> ShowS -> ShowS
showParen (Int
p Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
    [Char] -> ShowS
showString [Char]
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Mask] -> ShowS
forall a. Show a => a -> ShowS
shows (Word64Set -> [Mask]
toList Word64Set
xs)

{--------------------------------------------------------------------
  Read
--------------------------------------------------------------------}
instance Read Word64Set where
#ifdef __GLASGOW_HASKELL__
  readPrec :: ReadPrec Word64Set
readPrec = ReadPrec Word64Set -> ReadPrec Word64Set
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec Word64Set -> ReadPrec Word64Set)
-> ReadPrec Word64Set -> ReadPrec Word64Set
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec Word64Set -> ReadPrec Word64Set
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec Word64Set -> ReadPrec Word64Set)
-> ReadPrec Word64Set -> ReadPrec Word64Set
forall a b. (a -> b) -> a -> b
$ do
    Ident "fromList" <- ReadPrec Lexeme
lexP
    xs <- readPrec
    return (fromList xs)

  readListPrec :: ReadPrec [Word64Set]
readListPrec = ReadPrec [Word64Set]
forall a. Read a => ReadPrec [a]
readListPrecDefault
#else
  readsPrec p = readParen (p > 10) $ \ r -> do
    ("fromList",s) <- lex r
    (xs,t) <- reads s
    return (fromList xs,t)
#endif

{--------------------------------------------------------------------
  NFData
--------------------------------------------------------------------}

-- The Word64Set constructors consist only of strict fields of Ints and
-- Word64Sets, thus the default NFData instance which evaluates to whnf
-- should suffice
instance NFData Word64Set where rnf :: Word64Set -> ()
rnf Word64Set
x = Word64Set -> () -> ()
forall a b. a -> b -> b
seq Word64Set
x ()

{--------------------------------------------------------------------
  Debugging
--------------------------------------------------------------------}
-- | \(O(n \min(n,W))\). Show the tree that implements the set. The tree is shown
-- in a compressed, hanging format.
showTree :: Word64Set -> String
showTree :: Word64Set -> [Char]
showTree Word64Set
s
  = Bool -> Bool -> Word64Set -> [Char]
showTreeWith Bool
True Bool
False Word64Set
s


{- | \(O(n \min(n,W))\). The expression (@'showTreeWith' hang wide map@) shows
 the tree that implements the set. If @hang@ is
 'True', a /hanging/ tree is shown otherwise a rotated tree is shown. If
 @wide@ is 'True', an extra wide version is shown.
-}
showTreeWith :: Bool -> Bool -> Word64Set -> String
showTreeWith :: Bool -> Bool -> Word64Set -> [Char]
showTreeWith Bool
hang Bool
wide Word64Set
t
  | Bool
hang      = (Bool -> [[Char]] -> Word64Set -> ShowS
showsTreeHang Bool
wide [] Word64Set
t) [Char]
""
  | Bool
otherwise = (Bool -> [[Char]] -> [[Char]] -> Word64Set -> ShowS
showsTree Bool
wide [] [] Word64Set
t) [Char]
""

showsTree :: Bool -> [String] -> [String] -> Word64Set -> ShowS
showsTree :: Bool -> [[Char]] -> [[Char]] -> Word64Set -> ShowS
showsTree Bool
wide [[Char]]
lbars [[Char]]
rbars Word64Set
t
  = case Word64Set
t of
      Bin Mask
p Mask
m Word64Set
l Word64Set
r
          -> Bool -> [[Char]] -> [[Char]] -> Word64Set -> ShowS
showsTree Bool
wide ([[Char]] -> [[Char]]
withBar [[Char]]
rbars) ([[Char]] -> [[Char]]
withEmpty [[Char]]
rbars) Word64Set
r ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             Bool -> [[Char]] -> ShowS
showWide Bool
wide [[Char]]
rbars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             [[Char]] -> ShowS
showsBars [[Char]]
lbars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString (Mask -> Mask -> [Char]
showBin Mask
p Mask
m) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"\n" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             Bool -> [[Char]] -> ShowS
showWide Bool
wide [[Char]]
lbars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             Bool -> [[Char]] -> [[Char]] -> Word64Set -> ShowS
showsTree Bool
wide ([[Char]] -> [[Char]]
withEmpty [[Char]]
lbars) ([[Char]] -> [[Char]]
withBar [[Char]]
lbars) Word64Set
l
      Tip Mask
kx Mask
bm
          -> [[Char]] -> ShowS
showsBars [[Char]]
lbars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
" " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Mask -> ShowS
forall a. Show a => a -> ShowS
shows Mask
kx ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
" + " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
                                                Mask -> ShowS
showsBitMap Mask
bm ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"\n"
      Word64Set
Nil -> [[Char]] -> ShowS
showsBars [[Char]]
lbars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"|\n"

showsTreeHang :: Bool -> [String] -> Word64Set -> ShowS
showsTreeHang :: Bool -> [[Char]] -> Word64Set -> ShowS
showsTreeHang Bool
wide [[Char]]
bars Word64Set
t
  = case Word64Set
t of
      Bin Mask
p Mask
m Word64Set
l Word64Set
r
          -> [[Char]] -> ShowS
showsBars [[Char]]
bars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString (Mask -> Mask -> [Char]
showBin Mask
p Mask
m) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"\n" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             Bool -> [[Char]] -> ShowS
showWide Bool
wide [[Char]]
bars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             Bool -> [[Char]] -> Word64Set -> ShowS
showsTreeHang Bool
wide ([[Char]] -> [[Char]]
withBar [[Char]]
bars) Word64Set
l ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             Bool -> [[Char]] -> ShowS
showWide Bool
wide [[Char]]
bars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
             Bool -> [[Char]] -> Word64Set -> ShowS
showsTreeHang Bool
wide ([[Char]] -> [[Char]]
withEmpty [[Char]]
bars) Word64Set
r
      Tip Mask
kx Mask
bm
          -> [[Char]] -> ShowS
showsBars [[Char]]
bars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
" " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Mask -> ShowS
forall a. Show a => a -> ShowS
shows Mask
kx ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
" + " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
                                               Mask -> ShowS
showsBitMap Mask
bm ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"\n"
      Word64Set
Nil -> [[Char]] -> ShowS
showsBars [[Char]]
bars ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"|\n"

showBin :: Prefix -> Mask -> String
showBin :: Mask -> Mask -> [Char]
showBin Mask
_ Mask
_
  = [Char]
"*" -- ++ show (p,m)

showWide :: Bool -> [String] -> String -> String
showWide :: Bool -> [[Char]] -> ShowS
showWide Bool
wide [[Char]]
bars
  | Bool
wide      = [Char] -> ShowS
showString ([[Char]] -> [Char]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([[Char]] -> [[Char]]
forall a. [a] -> [a]
reverse [[Char]]
bars)) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
"|\n"
  | Bool
otherwise = ShowS
forall a. a -> a
id

showsBars :: [String] -> ShowS
showsBars :: [[Char]] -> ShowS
showsBars [] = ShowS
forall a. a -> a
id
showsBars ([Char]
_ : [[Char]]
tl) = [Char] -> ShowS
showString ([[Char]] -> [Char]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([[Char]] -> [[Char]]
forall a. [a] -> [a]
reverse [[Char]]
tl)) ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Char] -> ShowS
showString [Char]
node

showsBitMap :: Word64 -> ShowS
showsBitMap :: Mask -> ShowS
showsBitMap = [Char] -> ShowS
showString ([Char] -> ShowS) -> (Mask -> [Char]) -> Mask -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Mask -> [Char]
showBitMap

showBitMap :: Word64 -> String
showBitMap :: Mask -> [Char]
showBitMap Mask
w = [Mask] -> [Char]
forall a. Show a => a -> [Char]
show ([Mask] -> [Char]) -> [Mask] -> [Char]
forall a b. (a -> b) -> a -> b
$ Mask -> (Mask -> [Mask] -> [Mask]) -> [Mask] -> Mask -> [Mask]
forall a. Mask -> (Mask -> a -> a) -> a -> Mask -> a
foldrBits Mask
0 (:) [] Mask
w

node :: String
node :: [Char]
node           = [Char]
"+--"

withBar, withEmpty :: [String] -> [String]
withBar :: [[Char]] -> [[Char]]
withBar [[Char]]
bars   = [Char]
"|  "[Char] -> [[Char]] -> [[Char]]
forall a. a -> [a] -> [a]
:[[Char]]
bars
withEmpty :: [[Char]] -> [[Char]]
withEmpty [[Char]]
bars = [Char]
"   "[Char] -> [[Char]] -> [[Char]]
forall a. a -> [a] -> [a]
:[[Char]]
bars


{--------------------------------------------------------------------
  Helpers
--------------------------------------------------------------------}
{--------------------------------------------------------------------
  Link
--------------------------------------------------------------------}
link :: Prefix -> Word64Set -> Prefix -> Word64Set -> Word64Set
link :: Mask -> Word64Set -> Mask -> Word64Set -> Word64Set
link Mask
p1 Word64Set
t1 Mask
p2 Word64Set
t2 = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
linkWithMask (Mask -> Mask -> Mask
branchMask Mask
p1 Mask
p2) Mask
p1 Word64Set
t1 {-p2-} Word64Set
t2
{-# INLINE link #-}

-- `linkWithMask` is useful when the `branchMask` has already been computed
linkWithMask :: Mask -> Prefix -> Word64Set -> Word64Set -> Word64Set
linkWithMask :: Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
linkWithMask Mask
m Mask
p1 Word64Set
t1 {-p2-} Word64Set
t2
  | Mask -> Mask -> Bool
zero Mask
p1 Mask
m = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
Bin Mask
p Mask
m Word64Set
t1 Word64Set
t2
  | Bool
otherwise = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
Bin Mask
p Mask
m Word64Set
t2 Word64Set
t1
  where
    p :: Mask
p = Mask -> Mask -> Mask
mask Mask
p1 Mask
m
{-# INLINE linkWithMask #-}

{--------------------------------------------------------------------
  @bin@ assures that we never have empty trees within a tree.
--------------------------------------------------------------------}
bin :: Prefix -> Mask -> Word64Set -> Word64Set -> Word64Set
bin :: Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
bin Mask
_ Mask
_ Word64Set
l Word64Set
Nil = Word64Set
l
bin Mask
_ Mask
_ Word64Set
Nil Word64Set
r = Word64Set
r
bin Mask
p Mask
m Word64Set
l Word64Set
r   = Mask -> Mask -> Word64Set -> Word64Set -> Word64Set
Bin Mask
p Mask
m Word64Set
l Word64Set
r
{-# INLINE bin #-}

{--------------------------------------------------------------------
  @tip@ assures that we never have empty bitmaps within a tree.
--------------------------------------------------------------------}
tip :: Prefix -> BitMap -> Word64Set
tip :: Mask -> Mask -> Word64Set
tip Mask
_ Mask
0 = Word64Set
Nil
tip Mask
kx Mask
bm = Mask -> Mask -> Word64Set
Tip Mask
kx Mask
bm
{-# INLINE tip #-}


{----------------------------------------------------------------------
  Functions that generate Prefix and BitMap of a Key or a Suffix.
----------------------------------------------------------------------}

suffixBitMask :: Word64
suffixBitMask :: Mask
suffixBitMask = Int -> Mask
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Mask -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize (Mask
forall a. HasCallStack => a
undefined::Word64)) Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
- Mask
1
{-# INLINE suffixBitMask #-}

prefixBitMask :: Word64
prefixBitMask :: Mask
prefixBitMask = Mask -> Mask
forall a. Bits a => a -> a
complement Mask
suffixBitMask
{-# INLINE prefixBitMask #-}

prefixOf :: Word64 -> Prefix
prefixOf :: Mask -> Mask
prefixOf Mask
x = Mask
x Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
prefixBitMask
{-# INLINE prefixOf #-}

suffixOf :: Word64 -> Word64
suffixOf :: Mask -> Mask
suffixOf Mask
x = Mask
x Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
suffixBitMask
{-# INLINE suffixOf #-}

bitmapOfSuffix :: Word64 -> BitMap
bitmapOfSuffix :: Mask -> Mask
bitmapOfSuffix Mask
s = Mask
1 Mask -> Int -> Mask
`shiftLL` Mask -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Mask
s
{-# INLINE bitmapOfSuffix #-}

bitmapOf :: Word64 -> BitMap
bitmapOf :: Mask -> Mask
bitmapOf Mask
x = Mask -> Mask
bitmapOfSuffix (Mask -> Mask
suffixOf Mask
x)
{-# INLINE bitmapOf #-}


{--------------------------------------------------------------------
  Endian independent bit twiddling
--------------------------------------------------------------------}
-- Returns True iff the bits set in i and the Mask m are disjoint.
zero :: Word64 -> Mask -> Bool
zero :: Mask -> Mask -> Bool
zero Mask
i Mask
m
  = (Mask -> Mask
natFromInt Mask
i) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. (Mask -> Mask
natFromInt Mask
m) Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
0
{-# INLINE zero #-}

nomatch,match :: Word64 -> Prefix -> Mask -> Bool
nomatch :: Mask -> Mask -> Mask -> Bool
nomatch Mask
i Mask
p Mask
m
  = (Mask -> Mask -> Mask
mask Mask
i Mask
m) Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
p
{-# INLINE nomatch #-}

match :: Mask -> Mask -> Mask -> Bool
match Mask
i Mask
p Mask
m
  = (Mask -> Mask -> Mask
mask Mask
i Mask
m) Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
== Mask
p
{-# INLINE match #-}

-- Suppose a is largest such that 2^a divides 2*m.
-- Then mask i m is i with the low a bits zeroed out.
mask :: Word64 -> Mask -> Prefix
mask :: Mask -> Mask -> Mask
mask Mask
i Mask
m
  = Mask -> Mask -> Mask
maskW (Mask -> Mask
natFromInt Mask
i) (Mask -> Mask
natFromInt Mask
m)
{-# INLINE mask #-}

{--------------------------------------------------------------------
  Big endian operations
--------------------------------------------------------------------}
maskW :: Nat -> Nat -> Prefix
maskW :: Mask -> Mask -> Mask
maskW Mask
i Mask
m
  = Mask -> Mask
intFromNat (Mask
i Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. (Mask -> Mask
forall a. Bits a => a -> a
complement (Mask
mMask -> Mask -> Mask
forall a. Num a => a -> a -> a
-Mask
1) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
`xor` Mask
m))
{-# INLINE maskW #-}

shorter :: Mask -> Mask -> Bool
shorter :: Mask -> Mask -> Bool
shorter Mask
m1 Mask
m2
  = (Mask -> Mask
natFromInt Mask
m1) Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
> (Mask -> Mask
natFromInt Mask
m2)
{-# INLINE shorter #-}

branchMask :: Prefix -> Prefix -> Mask
branchMask :: Mask -> Mask -> Mask
branchMask Mask
p1 Mask
p2
  = Mask -> Mask
intFromNat (Mask -> Mask
highestBitMask (Mask -> Mask
natFromInt Mask
p1 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
`xor` Mask -> Mask
natFromInt Mask
p2))
{-# INLINE branchMask #-}

{----------------------------------------------------------------------
  To get best performance, we provide fast implementations of
  lowestBitSet, highestBitSet and fold[lr][l]Bits for GHC.
  If the intel bsf and bsr instructions ever become GHC primops,
  this code should be reimplemented using these.

  Performance of this code is crucial for folds, toList, filter, partition.

  The signatures of methods in question are placed after this comment.
----------------------------------------------------------------------}

lowestBitSet :: Nat -> Word64
highestBitSet :: Nat -> Word64
foldlBits :: Word64 -> (a -> Word64 -> a) -> a -> Nat -> a
foldl'Bits :: Word64 -> (a -> Word64 -> a) -> a -> Nat -> a
foldrBits :: Word64 -> (Word64 -> a -> a) -> a -> Nat -> a
foldr'Bits :: Word64 -> (Word64 -> a -> a) -> a -> Nat -> a
takeWhileAntitoneBits :: Word64 -> (Word64 -> Bool) -> Nat -> Nat

{-# INLINE lowestBitSet #-}
{-# INLINE highestBitSet #-}
{-# INLINE foldlBits #-}
{-# INLINE foldl'Bits #-}
{-# INLINE foldrBits #-}
{-# INLINE foldr'Bits #-}
{-# INLINE takeWhileAntitoneBits #-}

#if defined(__GLASGOW_HASKELL__)
indexOfTheOnlyBit :: Nat -> Word64
{-# INLINE indexOfTheOnlyBit #-}
indexOfTheOnlyBit :: Mask -> Mask
indexOfTheOnlyBit Mask
bitmask = Int -> Mask
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Mask) -> Int -> Mask
forall a b. (a -> b) -> a -> b
$ Mask -> Int
forall b. FiniteBits b => b -> Int
countTrailingZeros Mask
bitmask

lowestBitSet :: Mask -> Mask
lowestBitSet Mask
x = Int -> Mask
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Mask) -> Int -> Mask
forall a b. (a -> b) -> a -> b
$ Mask -> Int
forall b. FiniteBits b => b -> Int
countTrailingZeros Mask
x

highestBitSet :: Mask -> Mask
highestBitSet Mask
x = Int -> Mask
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Mask) -> Int -> Mask
forall a b. (a -> b) -> a -> b
$ Int
63 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Mask -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros Mask
x

lowestBitMask :: Nat -> Nat
lowestBitMask :: Mask -> Mask
lowestBitMask Mask
x = Mask
x Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask -> Mask
forall a. Num a => a -> a
negate Mask
x
{-# INLINE lowestBitMask #-}

-- Reverse the order of bits in the Nat.
revNat :: Nat -> Nat
revNat :: Mask -> Mask
revNat Mask
x1 = case ((Mask
x1 Mask -> Int -> Mask
`shiftRL` Int
1) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
0x5555555555555555) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.|. ((Mask
x1 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
0x5555555555555555) Mask -> Int -> Mask
`shiftLL` Int
1) of
              Mask
x2 -> case ((Mask
x2 Mask -> Int -> Mask
`shiftRL` Int
2) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
0x3333333333333333) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.|. ((Mask
x2 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
0x3333333333333333) Mask -> Int -> Mask
`shiftLL` Int
2) of
                 Mask
x3 -> case ((Mask
x3 Mask -> Int -> Mask
`shiftRL` Int
4) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
0x0F0F0F0F0F0F0F0F) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.|. ((Mask
x3 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
0x0F0F0F0F0F0F0F0F) Mask -> Int -> Mask
`shiftLL` Int
4) of
                   Mask
x4 -> case ((Mask
x4 Mask -> Int -> Mask
`shiftRL` Int
8) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
0x00FF00FF00FF00FF) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.|. ((Mask
x4 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
0x00FF00FF00FF00FF) Mask -> Int -> Mask
`shiftLL` Int
8) of
                     Mask
x5 -> case ((Mask
x5 Mask -> Int -> Mask
`shiftRL` Int
16) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
0x0000FFFF0000FFFF) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.|. ((Mask
x5 Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
0x0000FFFF0000FFFF) Mask -> Int -> Mask
`shiftLL` Int
16) of
                       Mask
x6 -> ( Mask
x6 Mask -> Int -> Mask
`shiftRL` Int
32             ) Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.|. ( Mask
x6               Mask -> Int -> Mask
`shiftLL` Int
32);

foldlBits :: forall a. Mask -> (a -> Mask -> a) -> a -> Mask -> a
foldlBits Mask
prefix a -> Mask -> a
f a
z Mask
bitmap = Mask -> a -> a
go Mask
bitmap a
z
  where go :: Mask -> a -> a
go Mask
0 a
acc = a
acc
        go Mask
bm a
acc = Mask -> a -> a
go (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
`xor` Mask
bitmask) ((a -> Mask -> a
f a
acc) (Mask -> a) -> Mask -> a
forall a b. (a -> b) -> a -> b
$! (Mask
prefixMask -> Mask -> Mask
forall a. Num a => a -> a -> a
+Mask
bi))
          where
            !bitmask :: Mask
bitmask = Mask -> Mask
lowestBitMask Mask
bm
            !bi :: Mask
bi = Mask -> Mask
indexOfTheOnlyBit Mask
bitmask

foldl'Bits :: forall a. Mask -> (a -> Mask -> a) -> a -> Mask -> a
foldl'Bits Mask
prefix a -> Mask -> a
f a
z Mask
bitmap = Mask -> a -> a
go Mask
bitmap a
z
  where go :: Mask -> a -> a
go Mask
0 a
acc = a
acc
        go Mask
bm !a
acc = Mask -> a -> a
go (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
`xor` Mask
bitmask) ((a -> Mask -> a
f a
acc) (Mask -> a) -> Mask -> a
forall a b. (a -> b) -> a -> b
$! (Mask
prefixMask -> Mask -> Mask
forall a. Num a => a -> a -> a
+Mask
bi))
          where !bitmask :: Mask
bitmask = Mask -> Mask
lowestBitMask Mask
bm
                !bi :: Mask
bi = Mask -> Mask
indexOfTheOnlyBit Mask
bitmask

foldrBits :: forall a. Mask -> (Mask -> a -> a) -> a -> Mask -> a
foldrBits Mask
prefix Mask -> a -> a
f a
z Mask
bitmap = Mask -> a -> a
go (Mask -> Mask
revNat Mask
bitmap) a
z
  where go :: Mask -> a -> a
go Mask
0 a
acc = a
acc
        go Mask
bm a
acc = Mask -> a -> a
go (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
`xor` Mask
bitmask) ((Mask -> a -> a
f (Mask -> a -> a) -> Mask -> a -> a
forall a b. (a -> b) -> a -> b
$! (Mask
prefixMask -> Mask -> Mask
forall a. Num a => a -> a -> a
+Mask
63Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
-Mask
bi)) a
acc)
          where !bitmask :: Mask
bitmask = Mask -> Mask
lowestBitMask Mask
bm
                !bi :: Mask
bi = Mask -> Mask
indexOfTheOnlyBit Mask
bitmask


foldr'Bits :: forall a. Mask -> (Mask -> a -> a) -> a -> Mask -> a
foldr'Bits Mask
prefix Mask -> a -> a
f a
z Mask
bitmap = Mask -> a -> a
go (Mask -> Mask
revNat Mask
bitmap) a
z
  where go :: Mask -> a -> a
go Mask
0 a
acc = a
acc
        go Mask
bm !a
acc = Mask -> a -> a
go (Mask
bm Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
`xor` Mask
bitmask) ((Mask -> a -> a
f (Mask -> a -> a) -> Mask -> a -> a
forall a b. (a -> b) -> a -> b
$! (Mask
prefixMask -> Mask -> Mask
forall a. Num a => a -> a -> a
+Mask
63Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
-Mask
bi)) a
acc)
          where !bitmask :: Mask
bitmask = Mask -> Mask
lowestBitMask Mask
bm
                !bi :: Mask
bi = Mask -> Mask
indexOfTheOnlyBit Mask
bitmask

takeWhileAntitoneBits :: Mask -> (Mask -> Bool) -> Mask -> Mask
takeWhileAntitoneBits Mask
prefix Mask -> Bool
predicate Mask
bitmap =
  -- Binary search for the first index where the predicate returns false, but skip a predicate
  -- call if the high half of the current range is empty. This ensures
  -- min (log2 64 + 1 = 7) (popcount bitmap) predicate calls.
  let next :: Int -> Mask -> (Mask, Int) -> (Mask, Int)
next Int
d Mask
h (Mask
n',Int
b') =
        if Mask
n' Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
h Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
0 Bool -> Bool -> Bool
&& (Mask -> Bool
predicate (Mask -> Bool) -> Mask -> Bool
forall a b. (a -> b) -> a -> b
$! Mask
prefix Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
+ Int -> Mask
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
b'Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
d)) then (Mask
n' Mask -> Int -> Mask
`shiftRL` Int
d, Int
b'Int -> Int -> Int
forall a. Num a => a -> a -> a
+Int
d) else (Mask
n',Int
b')
      {-# INLINE next #-}
      (Mask
_,Int
b) = Int -> Mask -> (Mask, Int) -> (Mask, Int)
next Int
1  Mask
0x2 ((Mask, Int) -> (Mask, Int)) -> (Mask, Int) -> (Mask, Int)
forall a b. (a -> b) -> a -> b
$
              Int -> Mask -> (Mask, Int) -> (Mask, Int)
next Int
2  Mask
0xC ((Mask, Int) -> (Mask, Int)) -> (Mask, Int) -> (Mask, Int)
forall a b. (a -> b) -> a -> b
$
              Int -> Mask -> (Mask, Int) -> (Mask, Int)
next Int
4  Mask
0xF0 ((Mask, Int) -> (Mask, Int)) -> (Mask, Int) -> (Mask, Int)
forall a b. (a -> b) -> a -> b
$
              Int -> Mask -> (Mask, Int) -> (Mask, Int)
next Int
8  Mask
0xFF00 ((Mask, Int) -> (Mask, Int)) -> (Mask, Int) -> (Mask, Int)
forall a b. (a -> b) -> a -> b
$
              Int -> Mask -> (Mask, Int) -> (Mask, Int)
next Int
16 Mask
0xFFFF0000 ((Mask, Int) -> (Mask, Int)) -> (Mask, Int) -> (Mask, Int)
forall a b. (a -> b) -> a -> b
$
              Int -> Mask -> (Mask, Int) -> (Mask, Int)
next Int
32 Mask
0xFFFFFFFF00000000 ((Mask, Int) -> (Mask, Int)) -> (Mask, Int) -> (Mask, Int)
forall a b. (a -> b) -> a -> b
$
              (Mask
bitmap,Int
0)
      m :: Mask
m = if Int
b Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
/= Int
0 Bool -> Bool -> Bool
|| (Mask
bitmap Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
0x1 Mask -> Mask -> Bool
forall a. Eq a => a -> a -> Bool
/= Mask
0 Bool -> Bool -> Bool
&& Mask -> Bool
predicate Mask
prefix)
          then ((Mask
2 Mask -> Int -> Mask
`shiftLL` Int
b) Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
- Mask
1)
          else ((Mask
1 Mask -> Int -> Mask
`shiftLL` Int
b) Mask -> Mask -> Mask
forall a. Num a => a -> a -> a
- Mask
1)
  in Mask
bitmap Mask -> Mask -> Mask
forall a. Bits a => a -> a -> a
.&. Mask
m

#else
{----------------------------------------------------------------------
  In general case we use logarithmic implementation of
  lowestBitSet and highestBitSet, which works up to bit sizes of 64.

  Folds are linear scans.
----------------------------------------------------------------------}

lowestBitSet n0 =
    let (n1,b1) = if n0 .&. 0xFFFFFFFF /= 0 then (n0,0)  else (n0 `shiftRL` 32, 32)
        (n2,b2) = if n1 .&. 0xFFFF /= 0     then (n1,b1) else (n1 `shiftRL` 16, 16+b1)
        (n3,b3) = if n2 .&. 0xFF /= 0       then (n2,b2) else (n2 `shiftRL` 8,  8+b2)
        (n4,b4) = if n3 .&. 0xF /= 0        then (n3,b3) else (n3 `shiftRL` 4,  4+b3)
        (n5,b5) = if n4 .&. 0x3 /= 0        then (n4,b4) else (n4 `shiftRL` 2,  2+b4)
        b6      = if n5 .&. 0x1 /= 0        then     b5  else                   1+b5
    in b6

highestBitSet n0 =
    let (n1,b1) = if n0 .&. 0xFFFFFFFF00000000 /= 0 then (n0 `shiftRL` 32, 32)    else (n0,0)
        (n2,b2) = if n1 .&. 0xFFFF0000 /= 0         then (n1 `shiftRL` 16, 16+b1) else (n1,b1)
        (n3,b3) = if n2 .&. 0xFF00 /= 0             then (n2 `shiftRL` 8,  8+b2)  else (n2,b2)
        (n4,b4) = if n3 .&. 0xF0 /= 0               then (n3 `shiftRL` 4,  4+b3)  else (n3,b3)
        (n5,b5) = if n4 .&. 0xC /= 0                then (n4 `shiftRL` 2,  2+b4)  else (n4,b4)
        b6      = if n5 .&. 0x2 /= 0                then                   1+b5   else     b5
    in b6

foldlBits prefix f z bm = let lb = lowestBitSet bm
                          in  go (prefix+lb) z (bm `shiftRL` lb)
  where go !_ acc 0 = acc
        go bi acc n | n `testBit` 0 = go (bi + 1) (f acc bi) (n `shiftRL` 1)
                    | otherwise     = go (bi + 1)    acc     (n `shiftRL` 1)

foldl'Bits prefix f z bm = let lb = lowestBitSet bm
                           in  go (prefix+lb) z (bm `shiftRL` lb)
  where go !_ !acc 0 = acc
        go bi acc n | n `testBit` 0 = go (bi + 1) (f acc bi) (n `shiftRL` 1)
                    | otherwise     = go (bi + 1)    acc     (n `shiftRL` 1)

foldrBits prefix f z bm = let lb = lowestBitSet bm
                          in  go (prefix+lb) (bm `shiftRL` lb)
  where go !_ 0 = z
        go bi n | n `testBit` 0 = f bi (go (bi + 1) (n `shiftRL` 1))
                | otherwise     =       go (bi + 1) (n `shiftRL` 1)

foldr'Bits prefix f z bm = let lb = lowestBitSet bm
                           in  go (prefix+lb) (bm `shiftRL` lb)
  where
        go !_ 0 = z
        go bi n | n `testBit` 0 = f bi $! go (bi + 1) (n `shiftRL` 1)
                | otherwise     =         go (bi + 1) (n `shiftRL` 1)

takeWhileAntitoneBits prefix predicate = foldl'Bits prefix f 0 -- Does not use antitone property
  where
    f acc bi | predicate bi = acc .|. bitmapOf bi
             | otherwise    = acc

#endif


{--------------------------------------------------------------------
  Utilities
--------------------------------------------------------------------}

-- | \(O(1)\).  Decompose a set into pieces based on the structure of the underlying
-- tree.  This function is useful for consuming a set in parallel.
--
-- No guarantee is made as to the sizes of the pieces; an internal, but
-- deterministic process determines this.  However, it is guaranteed that the
-- pieces returned will be in ascending order (all elements in the first submap
-- less than all elements in the second, and so on).
--
-- Examples:
--
-- > splitRoot (fromList [1..120]) == [fromList [1..63],fromList [64..120]]
-- > splitRoot empty == []
--
--  Note that the current implementation does not return more than two subsets,
--  but you should not depend on this behaviour because it can change in the
--  future without notice. Also, the current version does not continue
--  splitting all the way to individual singleton sets -- it stops at some
--  point.
splitRoot :: Word64Set -> [Word64Set]
splitRoot :: Word64Set -> [Word64Set]
splitRoot Word64Set
Nil = []
-- NOTE: we don't currently split below Tip, but we could.
splitRoot x :: Word64Set
x@(Tip Mask
_ Mask
_) = [Word64Set
x]
splitRoot (Bin Mask
_ Mask
m Word64Set
l Word64Set
r) | Mask
m Mask -> Mask -> Bool
forall a. Ord a => a -> a -> Bool
< Mask
0 = [Word64Set
r, Word64Set
l]
                        | Bool
otherwise = [Word64Set
l, Word64Set
r]
{-# INLINE splitRoot #-}