{-# LANGUAGE CPP #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE UnboxedTuples #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE PatternGuards #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE Trustworthy #-}
{-# OPTIONS_GHC -Wall -funbox-strict-fields -fno-warn-orphans -fno-warn-type-defaults -O2 #-}
#ifdef ST_HACK
{-# OPTIONS_GHC -fno-full-laziness #-}
#endif
--------------------------------------------------------------------------------
-- |
-- Copyright   : (c) Edward Kmett 2015
-- License     : BSD-style
-- Maintainer  : Edward Kmett <ekmett@gmail.com>
-- Portability : non-portable
--
-- This module suppose a Word64-based array-mapped PATRICIA Trie.
--
-- The most significant nybble is isolated by using techniques based on
-- <https://www.fpcomplete.com/user/edwardk/revisiting-matrix-multiplication/part-4>
-- but modified to work nybble-by-nybble rather than bit-by-bit.
--
--------------------------------------------------------------------------------
module Data.Discrimination.Internal.WordMap
  ( WordMap
  , singleton
  , empty
  , insert
  , lookup
  , member
  , fromList
  ) where

import Control.Applicative hiding (empty)
import Control.DeepSeq
import Control.Monad.ST hiding (runST)
import Data.Bits
import Data.Discrimination.Internal.SmallArray
import Data.Foldable
import Data.Functor
import Data.Monoid
import Data.Traversable
import Data.Word
import qualified GHC.Exts as Exts
import Prelude hiding (lookup, length, foldr)
import GHC.Types
import GHC.ST

type Key = Word64
type Mask = Word16
type Offset = Int

ptrEq :: a -> a -> Bool
ptrEq :: forall a. a -> a -> Bool
ptrEq a
x a
y = Int# -> Bool
isTrue# (forall a. a -> a -> Int#
Exts.reallyUnsafePtrEquality# a
x a
y Int# -> Int# -> Int#
Exts.==# Int#
1#)
{-# INLINEABLE ptrEq #-}

ptrNeq :: a -> a -> Bool
ptrNeq :: forall a. a -> a -> Bool
ptrNeq a
x a
y = Int# -> Bool
isTrue# (forall a. a -> a -> Int#
Exts.reallyUnsafePtrEquality# a
x a
y Int# -> Int# -> Int#
Exts./=# Int#
1#)
{-# INLINEABLE ptrNeq #-}

data WordMap v
  = Full !Key !Offset !(SmallArray (WordMap v))
  | Node !Key !Offset !Mask !(SmallArray (WordMap v))
  | Tip  !Key v
  | Nil
  deriving Int -> WordMap v -> ShowS
forall v. Show v => Int -> WordMap v -> ShowS
forall v. Show v => [WordMap v] -> ShowS
forall v. Show v => WordMap v -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [WordMap v] -> ShowS
$cshowList :: forall v. Show v => [WordMap v] -> ShowS
show :: WordMap v -> String
$cshow :: forall v. Show v => WordMap v -> String
showsPrec :: Int -> WordMap v -> ShowS
$cshowsPrec :: forall v. Show v => Int -> WordMap v -> ShowS
Show

node :: Key -> Offset -> Mask -> SmallArray (WordMap v) -> WordMap v
node :: forall v.
Key -> Int -> Word16 -> SmallArray (WordMap v) -> WordMap v
node Key
k Int
o Word16
0xffff SmallArray (WordMap v)
a = forall v. Key -> Int -> SmallArray (WordMap v) -> WordMap v
Full Key
k Int
o SmallArray (WordMap v)
a
node Key
k Int
o Word16
m SmallArray (WordMap v)
a      = forall v.
Key -> Int -> Word16 -> SmallArray (WordMap v) -> WordMap v
Node Key
k Int
o Word16
m SmallArray (WordMap v)
a
{-# INLINE node #-}

instance NFData v => NFData (WordMap v) where
  rnf :: WordMap v -> ()
rnf (Full Key
_ Int
_ SmallArray (WordMap v)
a)   = forall a. NFData a => a -> ()
rnf SmallArray (WordMap v)
a
  rnf (Node Key
_ Int
_ Word16
_ SmallArray (WordMap v)
a) = forall a. NFData a => a -> ()
rnf SmallArray (WordMap v)
a
  rnf (Tip Key
_ v
v) = forall a. NFData a => a -> ()
rnf v
v
  rnf WordMap v
Nil = ()

instance Functor WordMap where
  fmap :: forall a b. (a -> b) -> WordMap a -> WordMap b
fmap a -> b
f = WordMap a -> WordMap b
go where
    go :: WordMap a -> WordMap b
go (Full Key
k Int
o SmallArray (WordMap a)
a) = forall v. Key -> Int -> SmallArray (WordMap v) -> WordMap v
Full Key
k Int
o (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap WordMap a -> WordMap b
go SmallArray (WordMap a)
a)
    go (Node Key
k Int
o Word16
m SmallArray (WordMap a)
a) = forall v.
Key -> Int -> Word16 -> SmallArray (WordMap v) -> WordMap v
Node Key
k Int
o Word16
m (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap WordMap a -> WordMap b
go SmallArray (WordMap a)
a)
    go (Tip Key
k a
v) = forall v. Key -> v -> WordMap v
Tip Key
k (a -> b
f a
v)
    go WordMap a
Nil = forall v. WordMap v
Nil
  {-# INLINEABLE fmap #-}

instance Foldable WordMap where
  foldMap :: forall m a. Monoid m => (a -> m) -> WordMap a -> m
foldMap a -> m
f = WordMap a -> m
go where
    go :: WordMap a -> m
go (Full Key
_ Int
_ SmallArray (WordMap a)
a) = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap WordMap a -> m
go SmallArray (WordMap a)
a
    go (Node Key
_ Int
_ Word16
_ SmallArray (WordMap a)
a) = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap WordMap a -> m
go SmallArray (WordMap a)
a
    go (Tip Key
_ a
v) = a -> m
f a
v
    go WordMap a
Nil = forall a. Monoid a => a
mempty
  {-# INLINEABLE foldMap #-}

instance Traversable WordMap where
  traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> WordMap a -> f (WordMap b)
traverse a -> f b
f = WordMap a -> f (WordMap b)
go where
    go :: WordMap a -> f (WordMap b)
go (Full Key
k Int
o SmallArray (WordMap a)
a) = forall v. Key -> Int -> SmallArray (WordMap v) -> WordMap v
Full Key
k Int
o forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse WordMap a -> f (WordMap b)
go SmallArray (WordMap a)
a
    go (Node Key
k Int
o Word16
m SmallArray (WordMap a)
a) = forall v.
Key -> Int -> Word16 -> SmallArray (WordMap v) -> WordMap v
Node Key
k Int
o Word16
m forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse WordMap a -> f (WordMap b)
go SmallArray (WordMap a)
a
    go (Tip Key
k a
v) = forall v. Key -> v -> WordMap v
Tip Key
k forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> f b
f a
v
    go WordMap a
Nil = forall (f :: * -> *) a. Applicative f => a -> f a
pure forall v. WordMap v
Nil
  {-# INLINEABLE traverse #-}

-- Note: 'level 0' will return a negative shift, don't use it
level :: Key -> Int
level :: Key -> Int
level Key
w = Int
60 forall a. Num a => a -> a -> a
- (forall b. FiniteBits b => b -> Int
countLeadingZeros Key
w forall a. Bits a => a -> a -> a
.&. Int
0x7c)
{-# INLINE level #-}

maskBit :: Key -> Offset -> Int
maskBit :: Key -> Int -> Int
maskBit Key
k Int
o = forall a b. (Integral a, Num b) => a -> b
fromIntegral (forall a. Bits a => a -> Int -> a
unsafeShiftR Key
k Int
o forall a. Bits a => a -> a -> a
.&. Key
0xf)
{-# INLINE maskBit #-}

mask :: Key -> Offset -> Word16
mask :: Key -> Int -> Word16
mask Key
k Int
o = forall a. Bits a => a -> Int -> a
unsafeShiftL Word16
1 (Key -> Int -> Int
maskBit Key
k Int
o)
{-# INLINE mask #-}

-- offset :: Int -> Word16 -> Int
-- offset k w = popCount $ w .&. (unsafeShiftL 1 k - 1)
-- {-# INLINE offset #-}

fork :: Int -> Key -> WordMap v -> Key -> WordMap v -> WordMap v
fork :: forall v. Int -> Key -> WordMap v -> Key -> WordMap v -> WordMap v
fork Int
o Key
k WordMap v
n Key
ok WordMap v
on = forall v.
Key -> Int -> Word16 -> SmallArray (WordMap v) -> WordMap v
Node (Key
k forall a. Bits a => a -> a -> a
.&. forall a. Bits a => a -> Int -> a
unsafeShiftL Key
0xfffffffffffffff0 Int
o) Int
o (Key -> Int -> Word16
mask Key
k Int
o forall a. Bits a => a -> a -> a
.|. Key -> Int -> Word16
mask Key
ok Int
o) forall a b. (a -> b) -> a -> b
$ forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
  SmallMutableArray s (WordMap v)
arr <- forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (SmallMutableArray (PrimState m) a)
newSmallArray Int
2 WordMap v
n
  forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s (WordMap v)
arr (forall a. Enum a => a -> Int
fromEnum (Key
k forall a. Ord a => a -> a -> Bool
< Key
ok)) WordMap v
on
  forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> m (SmallArray a)
unsafeFreezeSmallArray SmallMutableArray s (WordMap v)
arr

insert :: Key -> v -> WordMap v -> WordMap v
insert :: forall v. Key -> v -> WordMap v -> WordMap v
insert !Key
k v
v WordMap v
xs0 = WordMap v -> WordMap v
go WordMap v
xs0 where
  go :: WordMap v -> WordMap v
go on :: WordMap v
on@(Full Key
ok Int
n SmallArray (WordMap v)
as)
    | Key
wd forall a. Ord a => a -> a -> Bool
> Key
0xf = forall v. Int -> Key -> WordMap v -> Key -> WordMap v -> WordMap v
fork (Key -> Int
level Key
okk) Key
k (forall v. Key -> v -> WordMap v
Tip Key
k v
v) Key
ok WordMap v
on
    | !WordMap v
oz <- forall a. SmallArray a -> Int -> a
indexSmallArray SmallArray (WordMap v)
as Int
d
    , !WordMap v
z <- WordMap v -> WordMap v
go WordMap v
oz
    , forall a. a -> a -> Bool
ptrNeq WordMap v
z WordMap v
oz = forall v. Key -> Int -> SmallArray (WordMap v) -> WordMap v
Full Key
ok Int
n (forall a. Int -> a -> SmallArray a -> SmallArray a
update16 Int
d WordMap v
z SmallArray (WordMap v)
as)
    | Bool
otherwise = WordMap v
on
    where
      okk :: Key
okk = forall a. Bits a => a -> a -> a
xor Key
ok Key
k
      wd :: Key
wd  = forall a. Bits a => a -> Int -> a
unsafeShiftR Key
okk Int
n
      d :: Int
d   = forall a b. (Integral a, Num b) => a -> b
fromIntegral Key
wd
  go on :: WordMap v
on@(Node Key
ok Int
n Word16
m SmallArray (WordMap v)
as)
    | Key
wd forall a. Ord a => a -> a -> Bool
> Key
0xf = forall v. Int -> Key -> WordMap v -> Key -> WordMap v -> WordMap v
fork (Key -> Int
level Key
okk) Key
k (forall v. Key -> v -> WordMap v
Tip Key
k v
v) Key
ok WordMap v
on
    | Word16
m forall a. Bits a => a -> a -> a
.&. Word16
b forall a. Eq a => a -> a -> Bool
== Word16
0 = forall v.
Key -> Int -> Word16 -> SmallArray (WordMap v) -> WordMap v
node Key
ok Int
n (Word16
m forall a. Bits a => a -> a -> a
.|. Word16
b) (forall a. Int -> a -> SmallArray a -> SmallArray a
insertSmallArray Int
odm (forall v. Key -> v -> WordMap v
Tip Key
k v
v) SmallArray (WordMap v)
as)
    | !WordMap v
oz <- forall a. SmallArray a -> Int -> a
indexSmallArray SmallArray (WordMap v)
as Int
odm
    , !WordMap v
z <- WordMap v -> WordMap v
go WordMap v
oz
    , forall a. a -> a -> Bool
ptrNeq WordMap v
z WordMap v
oz = forall v.
Key -> Int -> Word16 -> SmallArray (WordMap v) -> WordMap v
Node Key
ok Int
n Word16
m (forall a. Int -> a -> SmallArray a -> SmallArray a
updateSmallArray Int
odm WordMap v
z SmallArray (WordMap v)
as)
    | Bool
otherwise = WordMap v
on
    where
      okk :: Key
okk = forall a. Bits a => a -> a -> a
xor Key
ok Key
k
      wd :: Key
wd  = forall a. Bits a => a -> Int -> a
unsafeShiftR Key
okk Int
n
      d :: Int
d   = forall a b. (Integral a, Num b) => a -> b
fromIntegral Key
wd
      b :: Word16
b   = forall a. Bits a => a -> Int -> a
unsafeShiftL Word16
1 Int
d
      odm :: Int
odm = forall a. Bits a => a -> Int
popCount forall a b. (a -> b) -> a -> b
$ Word16
m forall a. Bits a => a -> a -> a
.&. (Word16
b forall a. Num a => a -> a -> a
- Word16
1)
  go on :: WordMap v
on@(Tip Key
ok v
ov)
    | Key
k forall a. Eq a => a -> a -> Bool
/= Key
ok    = forall v. Int -> Key -> WordMap v -> Key -> WordMap v -> WordMap v
fork (Key -> Int
level (forall a. Bits a => a -> a -> a
xor Key
ok Key
k)) Key
k (forall v. Key -> v -> WordMap v
Tip Key
k v
v) Key
ok WordMap v
on
    | forall a. a -> a -> Bool
ptrEq v
v v
ov = WordMap v
on
    | Bool
otherwise  = forall v. Key -> v -> WordMap v
Tip Key
k v
v
  go WordMap v
Nil = forall v. Key -> v -> WordMap v
Tip Key
k v
v
{-# INLINEABLE insert #-}


lookup :: Key -> WordMap v -> Maybe v
lookup :: forall v. Key -> WordMap v -> Maybe v
lookup !Key
k (Full Key
ok Int
o SmallArray (WordMap v)
a)
  | Key
z <- forall a. Bits a => a -> Int -> a
unsafeShiftR (forall a. Bits a => a -> a -> a
xor Key
k Key
ok) Int
o, Key
z forall a. Ord a => a -> a -> Bool
<= Key
0xf = forall v. Key -> WordMap v -> Maybe v
lookup Key
k forall a b. (a -> b) -> a -> b
$ forall a. SmallArray a -> Int -> a
indexSmallArray SmallArray (WordMap v)
a (forall a b. (Integral a, Num b) => a -> b
fromIntegral Key
z)
  | Bool
otherwise = forall a. Maybe a
Nothing
lookup Key
k (Node Key
ok Int
o Word16
m SmallArray (WordMap v)
a)
  | Key
z forall a. Ord a => a -> a -> Bool
<= Key
0xf Bool -> Bool -> Bool
&& Word16
m forall a. Bits a => a -> a -> a
.&. Word16
b forall a. Eq a => a -> a -> Bool
/= Word16
0 = forall v. Key -> WordMap v -> Maybe v
lookup Key
k (forall a. SmallArray a -> Int -> a
indexSmallArray SmallArray (WordMap v)
a (forall a. Bits a => a -> Int
popCount (Word16
m forall a. Bits a => a -> a -> a
.&. (Word16
b forall a. Num a => a -> a -> a
- Word16
1))))
  | Bool
otherwise = forall a. Maybe a
Nothing
  where
    z :: Key
z = forall a. Bits a => a -> Int -> a
unsafeShiftR (forall a. Bits a => a -> a -> a
xor Key
k Key
ok) Int
o
    b :: Word16
b = forall a. Bits a => a -> Int -> a
unsafeShiftL Word16
1 (forall a b. (Integral a, Num b) => a -> b
fromIntegral Key
z)
lookup Key
k (Tip Key
ok v
ov)
  | Key
k forall a. Eq a => a -> a -> Bool
== Key
ok   = forall a. a -> Maybe a
Just v
ov
  | Bool
otherwise = forall a. Maybe a
Nothing
lookup Key
_ WordMap v
Nil = forall a. Maybe a
Nothing
{-# INLINEABLE lookup #-}

member :: Key -> WordMap v -> Bool
member :: forall v. Key -> WordMap v -> Bool
member !Key
k (Full Key
ok Int
o SmallArray (WordMap v)
a)
  | Key
z <- forall a. Bits a => a -> Int -> a
unsafeShiftR (forall a. Bits a => a -> a -> a
xor Key
k Key
ok) Int
o = Key
z forall a. Ord a => a -> a -> Bool
<= Key
0xf Bool -> Bool -> Bool
&& forall v. Key -> WordMap v -> Bool
member Key
k (forall a. SmallArray a -> Int -> a
indexSmallArray SmallArray (WordMap v)
a (forall a b. (Integral a, Num b) => a -> b
fromIntegral Key
z))
member Key
k (Node Key
ok Int
o Word16
m SmallArray (WordMap v)
a)
  | Key
z <- forall a. Bits a => a -> Int -> a
unsafeShiftR (forall a. Bits a => a -> a -> a
xor Key
k Key
ok) Int
o
  = Key
z forall a. Ord a => a -> a -> Bool
<= Key
0xf Bool -> Bool -> Bool
&& let b :: Word16
b = forall a. Bits a => a -> Int -> a
unsafeShiftL Word16
1 (forall a b. (Integral a, Num b) => a -> b
fromIntegral Key
z) in
    Word16
m forall a. Bits a => a -> a -> a
.&. Word16
b forall a. Eq a => a -> a -> Bool
/= Word16
0 Bool -> Bool -> Bool
&& forall v. Key -> WordMap v -> Bool
member Key
k (forall a. SmallArray a -> Int -> a
indexSmallArray SmallArray (WordMap v)
a (forall a. Bits a => a -> Int
popCount (Word16
m forall a. Bits a => a -> a -> a
.&. (Word16
b forall a. Num a => a -> a -> a
- Word16
1))))
member Key
k (Tip Key
ok v
_) = Key
k forall a. Eq a => a -> a -> Bool
== Key
ok
member Key
_ WordMap v
Nil = Bool
False
{-# INLINEABLE member #-}

updateSmallArray :: Int -> a -> SmallArray a -> SmallArray a
updateSmallArray :: forall a. Int -> a -> SmallArray a -> SmallArray a
updateSmallArray !Int
k a
a SmallArray a
i = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
  let n :: Int
n = forall (t :: * -> *) a. Foldable t => t a -> Int
length SmallArray a
i
  SmallMutableArray s a
o <- forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (SmallMutableArray (PrimState m) a)
newSmallArray Int
n forall a. HasCallStack => a
undefined
  forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a
-> Int -> SmallArray a -> Int -> Int -> m ()
copySmallArray SmallMutableArray s a
o Int
0 SmallArray a
i Int
0 Int
n
  forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
k a
a
  forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> m (SmallArray a)
unsafeFreezeSmallArray SmallMutableArray s a
o
{-# INLINEABLE updateSmallArray #-}

update16 :: Int -> a -> SmallArray a -> SmallArray a
update16 :: forall a. Int -> a -> SmallArray a -> SmallArray a
update16 !Int
k a
a SmallArray a
i = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
  SmallMutableArray s a
o <- forall a s. SmallArray a -> ST s (SmallMutableArray s a)
clone16 SmallArray a
i
  forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
k a
a
  forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> m (SmallArray a)
unsafeFreezeSmallArray SmallMutableArray s a
o
{-# INLINEABLE update16 #-}

insertSmallArray :: Int -> a -> SmallArray a -> SmallArray a
insertSmallArray :: forall a. Int -> a -> SmallArray a -> SmallArray a
insertSmallArray !Int
k a
a SmallArray a
i = forall a. (forall s. ST s a) -> a
runST forall a b. (a -> b) -> a -> b
$ do
  let n :: Int
n = forall (t :: * -> *) a. Foldable t => t a -> Int
length SmallArray a
i
  SmallMutableArray s a
o <- forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (SmallMutableArray (PrimState m) a)
newSmallArray (Int
n forall a. Num a => a -> a -> a
+ Int
1) a
a
  forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a
-> Int -> SmallArray a -> Int -> Int -> m ()
copySmallArray  SmallMutableArray s a
o Int
0 SmallArray a
i Int
0 Int
k
  forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a
-> Int -> SmallArray a -> Int -> Int -> m ()
copySmallArray  SmallMutableArray s a
o (Int
kforall a. Num a => a -> a -> a
+Int
1) SmallArray a
i Int
k (Int
nforall a. Num a => a -> a -> a
-Int
k)
  forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> m (SmallArray a)
unsafeFreezeSmallArray SmallMutableArray s a
o
{-# INLINEABLE insertSmallArray #-}

clone16 :: SmallArray a -> ST s (SmallMutableArray s a)
clone16 :: forall a s. SmallArray a -> ST s (SmallMutableArray s a)
clone16 SmallArray a
i = do
  SmallMutableArray s a
o <- forall (m :: * -> *) a.
PrimMonad m =>
Int -> a -> m (SmallMutableArray (PrimState m) a)
newSmallArray Int
16 forall a. HasCallStack => a
undefined
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
0 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
0
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
1 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
1
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
2 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
2
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
3 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
3
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
4 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
4
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
5 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
5
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
6 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
6
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
7 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
7
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
8 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
8
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
9 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
9
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
10 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
10
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
11 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
11
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
12 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
12
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
13 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
13
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
14 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
14
  forall (m :: * -> *) a. Monad m => SmallArray a -> Int -> m a
indexSmallArrayM SmallArray a
i Int
15 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall (m :: * -> *) a.
PrimMonad m =>
SmallMutableArray (PrimState m) a -> Int -> a -> m ()
writeSmallArray SmallMutableArray s a
o Int
15
  forall (m :: * -> *) a. Monad m => a -> m a
return SmallMutableArray s a
o
{-# INLINE clone16 #-}

-- | Build a singleton WordMap
singleton :: Key -> v -> WordMap v
singleton :: forall v. Key -> v -> WordMap v
singleton !Key
k v
v = forall v. Key -> v -> WordMap v
Tip Key
k v
v
{-# INLINE singleton #-}

fromList :: [(Word64,v)] -> WordMap v
fromList :: forall v. [(Key, v)] -> WordMap v
fromList [(Key, v)]
xs = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (\WordMap v
r (Key
k,v
v) -> forall v. Key -> v -> WordMap v -> WordMap v
insert Key
k v
v WordMap v
r) forall v. WordMap v
Nil [(Key, v)]
xs
{-# INLINE fromList #-}

empty :: WordMap a
empty :: forall v. WordMap v
empty = forall v. WordMap v
Nil
{-# INLINE empty #-}