{-# LANGUAGE DeriveFunctor, DeriveFoldable, DeriveTraversable #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE DeriveGeneric #-}

-- | This module provides an efficient implementation of maps from 'Word' keys to values.
-- It uses a Patricia trie with hash-consing to enable fast structural sharing and
-- O(1) equality checks. The 'HashCons' type wraps the internal nodes to take advantage
-- of O(1) 'Eq' and 'Ord' operations provided by hash-consing.
--
-- Note: This is an internal module. Users should prefer the public interface provided
-- by 'Data.HashCons.WordMap'.

module Data.HashCons.WordMap.Internal where

import Prelude hiding (lookup, map)
import Data.Bits
import Data.Hashable
import Data.HashCons
import GHC.Generics

-- | The main 'WordMap' data type.
data WordMap a
    = Empty
    | NonEmptyMap !(HashCons (NonEmptyWordMap a))
    deriving (Int -> WordMap a -> ShowS
[WordMap a] -> ShowS
WordMap a -> String
(Int -> WordMap a -> ShowS)
-> (WordMap a -> String)
-> ([WordMap a] -> ShowS)
-> Show (WordMap a)
forall a. Show a => Int -> WordMap a -> ShowS
forall a. Show a => [WordMap a] -> ShowS
forall a. Show a => WordMap a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> WordMap a -> ShowS
showsPrec :: Int -> WordMap a -> ShowS
$cshow :: forall a. Show a => WordMap a -> String
show :: WordMap a -> String
$cshowList :: forall a. Show a => [WordMap a] -> ShowS
showList :: [WordMap a] -> ShowS
Show, WordMap a -> WordMap a -> Bool
(WordMap a -> WordMap a -> Bool)
-> (WordMap a -> WordMap a -> Bool) -> Eq (WordMap a)
forall a. Eq a => WordMap a -> WordMap a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => WordMap a -> WordMap a -> Bool
== :: WordMap a -> WordMap a -> Bool
$c/= :: forall a. Eq a => WordMap a -> WordMap a -> Bool
/= :: WordMap a -> WordMap a -> Bool
Eq, Eq (WordMap a)
Eq (WordMap a) =>
(WordMap a -> WordMap a -> Ordering)
-> (WordMap a -> WordMap a -> Bool)
-> (WordMap a -> WordMap a -> Bool)
-> (WordMap a -> WordMap a -> Bool)
-> (WordMap a -> WordMap a -> Bool)
-> (WordMap a -> WordMap a -> WordMap a)
-> (WordMap a -> WordMap a -> WordMap a)
-> Ord (WordMap a)
WordMap a -> WordMap a -> Bool
WordMap a -> WordMap a -> Ordering
WordMap a -> WordMap a -> WordMap a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (WordMap a)
forall a. Ord a => WordMap a -> WordMap a -> Bool
forall a. Ord a => WordMap a -> WordMap a -> Ordering
forall a. Ord a => WordMap a -> WordMap a -> WordMap a
$ccompare :: forall a. Ord a => WordMap a -> WordMap a -> Ordering
compare :: WordMap a -> WordMap a -> Ordering
$c< :: forall a. Ord a => WordMap a -> WordMap a -> Bool
< :: WordMap a -> WordMap a -> Bool
$c<= :: forall a. Ord a => WordMap a -> WordMap a -> Bool
<= :: WordMap a -> WordMap a -> Bool
$c> :: forall a. Ord a => WordMap a -> WordMap a -> Bool
> :: WordMap a -> WordMap a -> Bool
$c>= :: forall a. Ord a => WordMap a -> WordMap a -> Bool
>= :: WordMap a -> WordMap a -> Bool
$cmax :: forall a. Ord a => WordMap a -> WordMap a -> WordMap a
max :: WordMap a -> WordMap a -> WordMap a
$cmin :: forall a. Ord a => WordMap a -> WordMap a -> WordMap a
min :: WordMap a -> WordMap a -> WordMap a
Ord, (forall x. WordMap a -> Rep (WordMap a) x)
-> (forall x. Rep (WordMap a) x -> WordMap a)
-> Generic (WordMap a)
forall x. Rep (WordMap a) x -> WordMap a
forall x. WordMap a -> Rep (WordMap a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (WordMap a) x -> WordMap a
forall a x. WordMap a -> Rep (WordMap a) x
$cfrom :: forall a x. WordMap a -> Rep (WordMap a) x
from :: forall x. WordMap a -> Rep (WordMap a) x
$cto :: forall a x. Rep (WordMap a) x -> WordMap a
to :: forall x. Rep (WordMap a) x -> WordMap a
Generic)

instance Hashable a => Hashable (WordMap a)

-- | Non-empty trie nodes.
data NonEmptyWordMap a
    = Leaf !Word a
    | Bin !Word !Word (WordMap a) (WordMap a)
    deriving (Int -> NonEmptyWordMap a -> ShowS
[NonEmptyWordMap a] -> ShowS
NonEmptyWordMap a -> String
(Int -> NonEmptyWordMap a -> ShowS)
-> (NonEmptyWordMap a -> String)
-> ([NonEmptyWordMap a] -> ShowS)
-> Show (NonEmptyWordMap a)
forall a. Show a => Int -> NonEmptyWordMap a -> ShowS
forall a. Show a => [NonEmptyWordMap a] -> ShowS
forall a. Show a => NonEmptyWordMap a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall a. Show a => Int -> NonEmptyWordMap a -> ShowS
showsPrec :: Int -> NonEmptyWordMap a -> ShowS
$cshow :: forall a. Show a => NonEmptyWordMap a -> String
show :: NonEmptyWordMap a -> String
$cshowList :: forall a. Show a => [NonEmptyWordMap a] -> ShowS
showList :: [NonEmptyWordMap a] -> ShowS
Show, NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
(NonEmptyWordMap a -> NonEmptyWordMap a -> Bool)
-> (NonEmptyWordMap a -> NonEmptyWordMap a -> Bool)
-> Eq (NonEmptyWordMap a)
forall a. Eq a => NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
== :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
$c/= :: forall a. Eq a => NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
/= :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
Eq, Eq (NonEmptyWordMap a)
Eq (NonEmptyWordMap a) =>
(NonEmptyWordMap a -> NonEmptyWordMap a -> Ordering)
-> (NonEmptyWordMap a -> NonEmptyWordMap a -> Bool)
-> (NonEmptyWordMap a -> NonEmptyWordMap a -> Bool)
-> (NonEmptyWordMap a -> NonEmptyWordMap a -> Bool)
-> (NonEmptyWordMap a -> NonEmptyWordMap a -> Bool)
-> (NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a)
-> (NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a)
-> Ord (NonEmptyWordMap a)
NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
NonEmptyWordMap a -> NonEmptyWordMap a -> Ordering
NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a
forall a.
Eq a =>
(a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (NonEmptyWordMap a)
forall a. Ord a => NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
forall a.
Ord a =>
NonEmptyWordMap a -> NonEmptyWordMap a -> Ordering
forall a.
Ord a =>
NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a
$ccompare :: forall a.
Ord a =>
NonEmptyWordMap a -> NonEmptyWordMap a -> Ordering
compare :: NonEmptyWordMap a -> NonEmptyWordMap a -> Ordering
$c< :: forall a. Ord a => NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
< :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
$c<= :: forall a. Ord a => NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
<= :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
$c> :: forall a. Ord a => NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
> :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
$c>= :: forall a. Ord a => NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
>= :: NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
$cmax :: forall a.
Ord a =>
NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a
max :: NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a
$cmin :: forall a.
Ord a =>
NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a
min :: NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a
Ord, (forall x. NonEmptyWordMap a -> Rep (NonEmptyWordMap a) x)
-> (forall x. Rep (NonEmptyWordMap a) x -> NonEmptyWordMap a)
-> Generic (NonEmptyWordMap a)
forall x. Rep (NonEmptyWordMap a) x -> NonEmptyWordMap a
forall x. NonEmptyWordMap a -> Rep (NonEmptyWordMap a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall a x. Rep (NonEmptyWordMap a) x -> NonEmptyWordMap a
forall a x. NonEmptyWordMap a -> Rep (NonEmptyWordMap a) x
$cfrom :: forall a x. NonEmptyWordMap a -> Rep (NonEmptyWordMap a) x
from :: forall x. NonEmptyWordMap a -> Rep (NonEmptyWordMap a) x
$cto :: forall a x. Rep (NonEmptyWordMap a) x -> NonEmptyWordMap a
to :: forall x. Rep (NonEmptyWordMap a) x -> NonEmptyWordMap a
Generic)

instance Hashable a => Hashable (NonEmptyWordMap a)

-- | /O(1)/. Create an empty map.
empty :: WordMap a
empty :: forall a. WordMap a
empty = WordMap a
forall a. WordMap a
Empty

-- | /O(1)/. Create a map with a single key-value pair.
singleton :: Hashable a => Word -> a -> WordMap a
singleton :: forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k a
v = HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons (Word -> a -> NonEmptyWordMap a
forall a. Word -> a -> NonEmptyWordMap a
Leaf Word
k a
v))

-- | /O(1)/. Create a map with a single key-value pair.
singletonNonEmpty :: Hashable a => Word -> a -> NonEmptyWordMap a
singletonNonEmpty :: forall a. Hashable a => Word -> a -> NonEmptyWordMap a
singletonNonEmpty = Word -> a -> NonEmptyWordMap a
forall a. Word -> a -> NonEmptyWordMap a
Leaf

-- | /O(log n)/. Insert a key-value pair into the map.
-- If the key is already present, the value is replaced.
insert :: Hashable a => Word -> a -> WordMap a -> WordMap a
insert :: forall a. Hashable a => Word -> a -> WordMap a -> WordMap a
insert Word
k a
v WordMap a
Empty = Word -> a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k a
v
insert Word
k a
v (NonEmptyMap HashCons (NonEmptyWordMap a)
hc) =
    let t :: NonEmptyWordMap a
t = HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc
        t' :: NonEmptyWordMap a
t' = Word -> a -> NonEmptyWordMap a -> NonEmptyWordMap a
forall a.
Hashable a =>
Word -> a -> NonEmptyWordMap a -> NonEmptyWordMap a
insertNonEmpty Word
k a
v NonEmptyWordMap a
t
    in if NonEmptyWordMap a
t' NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
forall a. Eq a => a -> a -> Bool
== NonEmptyWordMap a
t  -- Exploit O(1) 'Eq' from 'HashCons'
       then HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap HashCons (NonEmptyWordMap a)
hc  -- No change needed
       else HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t')

insertNonEmpty :: Hashable a => Word -> a -> NonEmptyWordMap a -> NonEmptyWordMap a
insertNonEmpty :: forall a.
Hashable a =>
Word -> a -> NonEmptyWordMap a -> NonEmptyWordMap a
insertNonEmpty Word
k a
v t :: NonEmptyWordMap a
t@(Leaf Word
k' a
_)
  | Word
k Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
k'   = Word -> a -> NonEmptyWordMap a
forall a. Word -> a -> NonEmptyWordMap a
Leaf Word
k a
v  -- Replace the existing value
  | Bool
otherwise = Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
forall a.
Hashable a =>
Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
join Word
k (Word -> a -> NonEmptyWordMap a
forall a. Word -> a -> NonEmptyWordMap a
Leaf Word
k a
v) Word
k' NonEmptyWordMap a
t
insertNonEmpty Word
k a
v t :: NonEmptyWordMap a
t@(Bin Word
p Word
m WordMap a
l WordMap a
r)
  | Word -> Word -> Word -> Bool
match Word
k Word
p Word
m = if Word -> Word -> Bool
zero Word
k Word
m
                  then
                    let l' :: WordMap a
l' = Word -> a -> WordMap a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a -> WordMap a
insert Word
k a
v WordMap a
l
                    in if WordMap a
l' WordMap a -> WordMap a -> Bool
forall a. Eq a => a -> a -> Bool
== WordMap a
l then NonEmptyWordMap a
t else Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p Word
m WordMap a
l' WordMap a
r
                  else
                    let r' :: WordMap a
r' = Word -> a -> WordMap a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a -> WordMap a
insert Word
k a
v WordMap a
r
                    in if WordMap a
r' WordMap a -> WordMap a -> Bool
forall a. Eq a => a -> a -> Bool
== WordMap a
r then NonEmptyWordMap a
t else Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p Word
m WordMap a
l WordMap a
r'
  | Bool
otherwise   = Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
forall a.
Hashable a =>
Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
join Word
k (Word -> a -> NonEmptyWordMap a
forall a. Word -> a -> NonEmptyWordMap a
Leaf Word
k a
v) Word
p NonEmptyWordMap a
t

-- | /O(log n)/. Lookup the value at a key in the map.
lookup :: Word -> WordMap a -> Maybe a
lookup :: forall a. Word -> WordMap a -> Maybe a
lookup Word
_ WordMap a
Empty = Maybe a
forall a. Maybe a
Nothing
lookup Word
k (NonEmptyMap HashCons (NonEmptyWordMap a)
hc) = Word -> NonEmptyWordMap a -> Maybe a
forall a. Word -> NonEmptyWordMap a -> Maybe a
lookupNonEmpty Word
k (HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc)

lookupNonEmpty :: Word -> NonEmptyWordMap a -> Maybe a
lookupNonEmpty :: forall a. Word -> NonEmptyWordMap a -> Maybe a
lookupNonEmpty Word
k (Leaf Word
k' a
v)
  | Word
k Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
k'   = a -> Maybe a
forall a. a -> Maybe a
Just a
v
  | Bool
otherwise = Maybe a
forall a. Maybe a
Nothing
lookupNonEmpty Word
k (Bin Word
p Word
m WordMap a
l WordMap a
r)
  | Word -> Word -> Word -> Bool
match Word
k Word
p Word
m = if Word -> Word -> Bool
zero Word
k Word
m then Word -> WordMap a -> Maybe a
forall a. Word -> WordMap a -> Maybe a
lookup Word
k WordMap a
l else Word -> WordMap a -> Maybe a
forall a. Word -> WordMap a -> Maybe a
lookup Word
k WordMap a
r
  | Bool
otherwise   = Maybe a
forall a. Maybe a
Nothing

-- | /O(n)/. Map a function over all values in the map.
map :: Hashable b => (a -> b) -> WordMap a -> WordMap b
map :: forall b a. Hashable b => (a -> b) -> WordMap a -> WordMap b
map a -> b
_ WordMap a
Empty = WordMap b
forall a. WordMap a
Empty
map a -> b
f (NonEmptyMap HashCons (NonEmptyWordMap a)
hc) = HashCons (NonEmptyWordMap b) -> WordMap b
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap b -> HashCons (NonEmptyWordMap b)
forall a. Hashable a => a -> HashCons a
hashCons ((a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b
forall b a.
Hashable b =>
(a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b
mapNonEmpty a -> b
f (HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc)))

mapNonEmpty :: Hashable b => (a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b
mapNonEmpty :: forall b a.
Hashable b =>
(a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b
mapNonEmpty a -> b
f (Leaf Word
k a
v) = Word -> b -> NonEmptyWordMap b
forall a. Word -> a -> NonEmptyWordMap a
Leaf Word
k (a -> b
f a
v)
mapNonEmpty a -> b
f (Bin Word
p Word
m WordMap a
l WordMap a
r) = Word -> Word -> WordMap b -> WordMap b -> NonEmptyWordMap b
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p Word
m ((a -> b) -> WordMap a -> WordMap b
forall b a. Hashable b => (a -> b) -> WordMap a -> WordMap b
map a -> b
f WordMap a
l) ((a -> b) -> WordMap a -> WordMap b
forall b a. Hashable b => (a -> b) -> WordMap a -> WordMap b
map a -> b
f WordMap a
r)

-- | /O(n)/. Map a function over all key-value pairs in the map.
mapWithKey :: Hashable b => (Word -> a -> b) -> WordMap a -> WordMap b
mapWithKey :: forall b a.
Hashable b =>
(Word -> a -> b) -> WordMap a -> WordMap b
mapWithKey Word -> a -> b
_ WordMap a
Empty = WordMap b
forall a. WordMap a
Empty
mapWithKey Word -> a -> b
f (NonEmptyMap HashCons (NonEmptyWordMap a)
hc) = HashCons (NonEmptyWordMap b) -> WordMap b
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap b -> HashCons (NonEmptyWordMap b)
forall a. Hashable a => a -> HashCons a
hashCons ((Word -> a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b
forall b a.
Hashable b =>
(Word -> a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b
mapWithKeyNonEmpty Word -> a -> b
f (HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc)))

mapWithKeyNonEmpty :: Hashable b => (Word -> a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b
mapWithKeyNonEmpty :: forall b a.
Hashable b =>
(Word -> a -> b) -> NonEmptyWordMap a -> NonEmptyWordMap b
mapWithKeyNonEmpty Word -> a -> b
f (Leaf Word
k a
v) = Word -> b -> NonEmptyWordMap b
forall a. Word -> a -> NonEmptyWordMap a
Leaf Word
k (Word -> a -> b
f Word
k a
v)
mapWithKeyNonEmpty Word -> a -> b
f (Bin Word
p Word
m WordMap a
l WordMap a
r) = Word -> Word -> WordMap b -> WordMap b -> NonEmptyWordMap b
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p Word
m ((Word -> a -> b) -> WordMap a -> WordMap b
forall b a.
Hashable b =>
(Word -> a -> b) -> WordMap a -> WordMap b
mapWithKey Word -> a -> b
f WordMap a
l) ((Word -> a -> b) -> WordMap a -> WordMap b
forall b a.
Hashable b =>
(Word -> a -> b) -> WordMap a -> WordMap b
mapWithKey Word -> a -> b
f WordMap a
r)

-- | /O(n)/. Traverse the map with a function that accesses keys.
traverseWithKey :: (Applicative t, Hashable b) => (Word -> a -> t b) -> WordMap a -> t (WordMap b)
traverseWithKey :: forall (t :: * -> *) b a.
(Applicative t, Hashable b) =>
(Word -> a -> t b) -> WordMap a -> t (WordMap b)
traverseWithKey Word -> a -> t b
_ WordMap a
Empty = WordMap b -> t (WordMap b)
forall a. a -> t a
forall (f :: * -> *) a. Applicative f => a -> f a
pure WordMap b
forall a. WordMap a
Empty
traverseWithKey Word -> a -> t b
f (NonEmptyMap HashCons (NonEmptyWordMap a)
hc) = HashCons (NonEmptyWordMap b) -> WordMap b
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (HashCons (NonEmptyWordMap b) -> WordMap b)
-> (NonEmptyWordMap b -> HashCons (NonEmptyWordMap b))
-> NonEmptyWordMap b
-> WordMap b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmptyWordMap b -> HashCons (NonEmptyWordMap b)
forall a. Hashable a => a -> HashCons a
hashCons (NonEmptyWordMap b -> WordMap b)
-> t (NonEmptyWordMap b) -> t (WordMap b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Word -> a -> t b) -> NonEmptyWordMap a -> t (NonEmptyWordMap b)
forall (t :: * -> *) b a.
(Applicative t, Hashable b) =>
(Word -> a -> t b) -> NonEmptyWordMap a -> t (NonEmptyWordMap b)
traverseWithKeyNonEmpty Word -> a -> t b
f (HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc)

traverseWithKeyNonEmpty :: (Applicative t, Hashable b) => (Word -> a -> t b) -> NonEmptyWordMap a -> t (NonEmptyWordMap b)
traverseWithKeyNonEmpty :: forall (t :: * -> *) b a.
(Applicative t, Hashable b) =>
(Word -> a -> t b) -> NonEmptyWordMap a -> t (NonEmptyWordMap b)
traverseWithKeyNonEmpty Word -> a -> t b
f (Leaf Word
k a
v) = Word -> b -> NonEmptyWordMap b
forall a. Word -> a -> NonEmptyWordMap a
Leaf Word
k (b -> NonEmptyWordMap b) -> t b -> t (NonEmptyWordMap b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Word -> a -> t b
f Word
k a
v
traverseWithKeyNonEmpty Word -> a -> t b
f (Bin Word
p Word
m WordMap a
l WordMap a
r) = Word -> Word -> WordMap b -> WordMap b -> NonEmptyWordMap b
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p Word
m (WordMap b -> WordMap b -> NonEmptyWordMap b)
-> t (WordMap b) -> t (WordMap b -> NonEmptyWordMap b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Word -> a -> t b) -> WordMap a -> t (WordMap b)
forall (t :: * -> *) b a.
(Applicative t, Hashable b) =>
(Word -> a -> t b) -> WordMap a -> t (WordMap b)
traverseWithKey Word -> a -> t b
f WordMap a
l t (WordMap b -> NonEmptyWordMap b)
-> t (WordMap b) -> t (NonEmptyWordMap b)
forall a b. t (a -> b) -> t a -> t b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> (Word -> a -> t b) -> WordMap a -> t (WordMap b)
forall (t :: * -> *) b a.
(Applicative t, Hashable b) =>
(Word -> a -> t b) -> WordMap a -> t (WordMap b)
traverseWithKey Word -> a -> t b
f WordMap a
r

-- | /O(n)/. The union of two maps. If a key occurs in both maps, the value from the left map is used.
union :: Hashable a => WordMap a -> WordMap a -> WordMap a
union :: forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
union WordMap a
t1 WordMap a
Empty = WordMap a
t1
union WordMap a
Empty WordMap a
t2 = WordMap a
t2
union t1 :: WordMap a
t1@(NonEmptyMap HashCons (NonEmptyWordMap a)
hc1) t2 :: WordMap a
t2@(NonEmptyMap HashCons (NonEmptyWordMap a)
hc2)
  | HashCons (NonEmptyWordMap a)
hc1 HashCons (NonEmptyWordMap a)
-> HashCons (NonEmptyWordMap a) -> Bool
forall a. Eq a => a -> a -> Bool
== HashCons (NonEmptyWordMap a)
hc2 = WordMap a
t1  -- O(1) comparison via 'HashCons'
union (NonEmptyMap HashCons (NonEmptyWordMap a)
hc1) WordMap a
t2 =
    HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons (NonEmptyWordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Hashable a =>
NonEmptyWordMap a -> WordMap a -> NonEmptyWordMap a
unionNonEmpty (HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc1) WordMap a
t2))

unionNonEmpty :: Hashable a => NonEmptyWordMap a -> WordMap a -> NonEmptyWordMap a
unionNonEmpty :: forall a.
Hashable a =>
NonEmptyWordMap a -> WordMap a -> NonEmptyWordMap a
unionNonEmpty NonEmptyWordMap a
t1 WordMap a
Empty = NonEmptyWordMap a
t1
unionNonEmpty NonEmptyWordMap a
t1 (NonEmptyMap HashCons (NonEmptyWordMap a)
hc2) = NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a
forall a.
Hashable a =>
NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a
unionNonEmptyNonEmpty NonEmptyWordMap a
t1 (HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc2)

unionNonEmptyNonEmpty :: Hashable a => NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a
unionNonEmptyNonEmpty :: forall a.
Hashable a =>
NonEmptyWordMap a -> NonEmptyWordMap a -> NonEmptyWordMap a
unionNonEmptyNonEmpty NonEmptyWordMap a
t1 NonEmptyWordMap a
t2
  | NonEmptyWordMap a
t1 NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
forall a. Eq a => a -> a -> Bool
== NonEmptyWordMap a
t2  = NonEmptyWordMap a
t1  -- O(1) comparison via 'HashCons'
unionNonEmptyNonEmpty t1 :: NonEmptyWordMap a
t1@(Leaf Word
k1 a
v1) t2 :: NonEmptyWordMap a
t2@(Leaf Word
k2 a
_)
  | Word
k1 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
k2  = NonEmptyWordMap a
t1  -- Prefer left map's value
  | Bool
otherwise = Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
forall a.
Hashable a =>
Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
join Word
k1 NonEmptyWordMap a
t1 Word
k2 NonEmptyWordMap a
t2
unionNonEmptyNonEmpty t1 :: NonEmptyWordMap a
t1@(Leaf Word
k1 a
v1) t2 :: NonEmptyWordMap a
t2@(Bin Word
p2 Word
m2 WordMap a
l2 WordMap a
r2)
  | Word -> Word -> Word -> Bool
match Word
k1 Word
p2 Word
m2 = if Word -> Word -> Bool
zero Word
k1 Word
m2
                     then Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p2 Word
m2 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
union (Word -> a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k1 a
v1) WordMap a
l2) WordMap a
r2
                     else Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p2 Word
m2 WordMap a
l2 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
union (Word -> a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k1 a
v1) WordMap a
r2)
  | Bool
otherwise      = Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
forall a.
Hashable a =>
Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
join Word
k1 NonEmptyWordMap a
t1 Word
p2 NonEmptyWordMap a
t2
unionNonEmptyNonEmpty t1 :: NonEmptyWordMap a
t1@(Bin Word
p1 Word
m1 WordMap a
l1 WordMap a
r1) t2 :: NonEmptyWordMap a
t2@(Leaf Word
k2 a
v2)
  | Word -> Word -> Word -> Bool
match Word
k2 Word
p1 Word
m1 = if Word -> Word -> Bool
zero Word
k2 Word
m1
                     then Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p1 Word
m1 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
union WordMap a
l1 (Word -> a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k2 a
v2)) WordMap a
r1
                     else Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p1 Word
m1 WordMap a
l1 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
union WordMap a
r1 (Word -> a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k2 a
v2))
  | Bool
otherwise      = Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
forall a.
Hashable a =>
Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
join Word
p1 NonEmptyWordMap a
t1 Word
k2 NonEmptyWordMap a
t2
unionNonEmptyNonEmpty t1 :: NonEmptyWordMap a
t1@(Bin Word
p1 Word
m1 WordMap a
l1 WordMap a
r1) t2 :: NonEmptyWordMap a
t2@(Bin Word
p2 Word
m2 WordMap a
l2 WordMap a
r2)
  | NonEmptyWordMap a
t1 NonEmptyWordMap a -> NonEmptyWordMap a -> Bool
forall a. Eq a => a -> a -> Bool
== NonEmptyWordMap a
t2  = NonEmptyWordMap a
t1  -- O(1) comparison via 'HashCons'
  | Word -> Word -> Bool
shorter Word
m1 Word
m2 =
      if Word -> Word -> Word -> Bool
match Word
p2 Word
p1 Word
m1
      then if Word -> Word -> Bool
zero Word
p2 Word
m1
           then Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p1 Word
m1 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
union WordMap a
l1 (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t2))) WordMap a
r1
           else Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p1 Word
m1 WordMap a
l1 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
union WordMap a
r1 (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t2)))
      else Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
forall a.
Hashable a =>
Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
join Word
p1 NonEmptyWordMap a
t1 Word
p2 NonEmptyWordMap a
t2
  | Word -> Word -> Bool
shorter Word
m2 Word
m1 =
      if Word -> Word -> Word -> Bool
match Word
p1 Word
p2 Word
m2
      then if Word -> Word -> Bool
zero Word
p1 Word
m2
           then Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p2 Word
m2 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
union (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)) WordMap a
l2) WordMap a
r2
           else Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p2 Word
m2 WordMap a
l2 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
union (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)) WordMap a
r2)
      else Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
forall a.
Hashable a =>
Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
join Word
p1 NonEmptyWordMap a
t1 Word
p2 NonEmptyWordMap a
t2
  | Word
p1 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
p2      = Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p1 Word
m1 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
union WordMap a
l1 WordMap a
l2) (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
union WordMap a
r1 WordMap a
r2)
  | Bool
otherwise     = Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
forall a.
Hashable a =>
Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
join Word
p1 NonEmptyWordMap a
t1 Word
p2 NonEmptyWordMap a
t2

-- | /O(n)/. Intersection of two maps. Only keys present in both maps are included.
intersection :: Hashable a => WordMap a -> WordMap a -> WordMap a
intersection :: forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
intersection WordMap a
Empty WordMap a
_ = WordMap a
forall a. WordMap a
Empty
intersection WordMap a
_ WordMap a
Empty = WordMap a
forall a. WordMap a
Empty
intersection t1 :: WordMap a
t1@(NonEmptyMap HashCons (NonEmptyWordMap a)
hc1) t2 :: WordMap a
t2@(NonEmptyMap HashCons (NonEmptyWordMap a)
hc2)
  | HashCons (NonEmptyWordMap a)
hc1 HashCons (NonEmptyWordMap a)
-> HashCons (NonEmptyWordMap a) -> Bool
forall a. Eq a => a -> a -> Bool
== HashCons (NonEmptyWordMap a)
hc2 = WordMap a
t1  -- O(1) comparison via 'HashCons'
intersection (NonEmptyMap HashCons (NonEmptyWordMap a)
hc1) WordMap a
t2 =
    NonEmptyWordMap a -> WordMap a -> WordMap a
forall a. Hashable a => NonEmptyWordMap a -> WordMap a -> WordMap a
intersectionNonEmpty (HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc1) WordMap a
t2

intersectionNonEmpty :: Hashable a => NonEmptyWordMap a -> WordMap a -> WordMap a
intersectionNonEmpty :: forall a. Hashable a => NonEmptyWordMap a -> WordMap a -> WordMap a
intersectionNonEmpty NonEmptyWordMap a
_ WordMap a
Empty = WordMap a
forall a. WordMap a
Empty
intersectionNonEmpty NonEmptyWordMap a
t1 (NonEmptyMap HashCons (NonEmptyWordMap a)
hc2) =
    case NonEmptyWordMap a
t1 of
      Leaf Word
k1 a
v1 -> if Word -> WordMap a -> Bool
forall a. Word -> WordMap a -> Bool
member Word
k1 (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap HashCons (NonEmptyWordMap a)
hc2)
                    then Word -> a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k1 a
v1
                    else WordMap a
forall a. WordMap a
Empty
      Bin Word
p1 Word
m1 WordMap a
l1 WordMap a
r1 -> case HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc2 of
        Leaf Word
k2 a
a2
          | Word -> Word -> Word -> Bool
match Word
k2 Word
p1 Word
m1 -> if Word -> Word -> Bool
zero Word
k2 Word
m1
                               then WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
intersection WordMap a
l1 (Word -> a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k2 a
a2)
                               else WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
intersection WordMap a
r1 (Word -> a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k2 a
a2)
          | Bool
otherwise      -> WordMap a
forall a. WordMap a
Empty
        Bin Word
p2 Word
m2 WordMap a
l2 WordMap a
r2
          | Word -> Word -> Bool
shorter Word
m1 Word
m2 ->
              if Word -> Word -> Word -> Bool
match Word
p2 Word
p1 Word
m1
              then if Word -> Word -> Bool
zero Word
p2 Word
m1
                   then WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
intersection WordMap a
l1 (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap HashCons (NonEmptyWordMap a)
hc2)
                   else WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
intersection WordMap a
r1 (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap HashCons (NonEmptyWordMap a)
hc2)
              else WordMap a
forall a. WordMap a
Empty
          | Word -> Word -> Bool
shorter Word
m2 Word
m1 ->
              if Word -> Word -> Word -> Bool
match Word
p1 Word
p2 Word
m2
              then if Word -> Word -> Bool
zero Word
p1 Word
m2
                   then WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
intersection (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)) WordMap a
l2
                   else WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
intersection (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)) WordMap a
r2
              else WordMap a
forall a. WordMap a
Empty
          | Word
p1 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
p2      -> let l :: WordMap a
l = WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
intersection WordMap a
l1 WordMap a
l2
                                 r :: WordMap a
r = WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
intersection WordMap a
r1 WordMap a
r2
                             in Word -> Word -> WordMap a -> WordMap a -> WordMap a
forall a.
Hashable a =>
Word -> Word -> WordMap a -> WordMap a -> WordMap a
combine Word
p1 Word
m1 WordMap a
l WordMap a
r
          | Bool
otherwise     -> WordMap a
forall a. WordMap a
Empty

-- | /O(n)/. Difference of two maps. Keys in the first map but not in the second are included.
difference :: Hashable a => WordMap a -> WordMap a -> WordMap a
difference :: forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
difference WordMap a
Empty WordMap a
_ = WordMap a
forall a. WordMap a
Empty
difference WordMap a
t1 WordMap a
Empty = WordMap a
t1
difference t1 :: WordMap a
t1@(NonEmptyMap HashCons (NonEmptyWordMap a)
hc1) t2 :: WordMap a
t2@(NonEmptyMap HashCons (NonEmptyWordMap a)
hc2)
  | HashCons (NonEmptyWordMap a)
hc1 HashCons (NonEmptyWordMap a)
-> HashCons (NonEmptyWordMap a) -> Bool
forall a. Eq a => a -> a -> Bool
== HashCons (NonEmptyWordMap a)
hc2 = WordMap a
forall a. WordMap a
Empty  -- O(1) comparison via 'HashCons'
difference (NonEmptyMap HashCons (NonEmptyWordMap a)
hc1) WordMap a
t2 =
    NonEmptyWordMap a -> WordMap a -> WordMap a
forall a. Hashable a => NonEmptyWordMap a -> WordMap a -> WordMap a
differenceNonEmpty (HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc1) WordMap a
t2

differenceNonEmpty :: Hashable a => NonEmptyWordMap a -> WordMap a -> WordMap a
differenceNonEmpty :: forall a. Hashable a => NonEmptyWordMap a -> WordMap a -> WordMap a
differenceNonEmpty NonEmptyWordMap a
t1 WordMap a
Empty = HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)
differenceNonEmpty NonEmptyWordMap a
t1 (NonEmptyMap HashCons (NonEmptyWordMap a)
hc2) =
    case NonEmptyWordMap a
t1 of
      Leaf Word
k1 a
v1 -> if Word -> WordMap a -> Bool
forall a. Word -> WordMap a -> Bool
member Word
k1 (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap HashCons (NonEmptyWordMap a)
hc2)
                    then WordMap a
forall a. WordMap a
Empty
                    else Word -> a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k1 a
v1
      Bin Word
p1 Word
m1 WordMap a
l1 WordMap a
r1 -> case HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc2 of
        Leaf Word
k2 a
a2
          | Word -> Word -> Word -> Bool
match Word
k2 Word
p1 Word
m1 -> if Word -> Word -> Bool
zero Word
k2 Word
m1
                               then Word -> Word -> WordMap a -> WordMap a -> WordMap a
forall a.
Hashable a =>
Word -> Word -> WordMap a -> WordMap a -> WordMap a
combine Word
p1 Word
m1 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
difference WordMap a
l1 (Word -> a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k2 a
a2)) WordMap a
r1
                               else Word -> Word -> WordMap a -> WordMap a -> WordMap a
forall a.
Hashable a =>
Word -> Word -> WordMap a -> WordMap a -> WordMap a
combine Word
p1 Word
m1 WordMap a
l1 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
difference WordMap a
r1 (Word -> a -> WordMap a
forall a. Hashable a => Word -> a -> WordMap a
singleton Word
k2 a
a2))
          | Bool
otherwise      -> HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)
        Bin Word
p2 Word
m2 WordMap a
l2 WordMap a
r2
          | Word -> Word -> Bool
shorter Word
m1 Word
m2 ->
              if Word -> Word -> Word -> Bool
match Word
p2 Word
p1 Word
m1
              then if Word -> Word -> Bool
zero Word
p2 Word
m1
                   then Word -> Word -> WordMap a -> WordMap a -> WordMap a
forall a.
Hashable a =>
Word -> Word -> WordMap a -> WordMap a -> WordMap a
combine Word
p1 Word
m1 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
difference WordMap a
l1 (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap HashCons (NonEmptyWordMap a)
hc2)) WordMap a
r1
                   else Word -> Word -> WordMap a -> WordMap a -> WordMap a
forall a.
Hashable a =>
Word -> Word -> WordMap a -> WordMap a -> WordMap a
combine Word
p1 Word
m1 WordMap a
l1 (WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
difference WordMap a
r1 (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap HashCons (NonEmptyWordMap a)
hc2))
              else HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)
          | Word -> Word -> Bool
shorter Word
m2 Word
m1 ->
              if Word -> Word -> Word -> Bool
match Word
p1 Word
p2 Word
m2
              then if Word -> Word -> Bool
zero Word
p1 Word
m2
                   then WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
difference (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)) WordMap a
l2
                   else WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
difference (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)) WordMap a
r2
              else HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)
          | Word
p1 Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
p2      -> let l :: WordMap a
l = WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
difference WordMap a
l1 WordMap a
l2
                                 r :: WordMap a
r = WordMap a -> WordMap a -> WordMap a
forall a. Hashable a => WordMap a -> WordMap a -> WordMap a
difference WordMap a
r1 WordMap a
r2
                             in Word -> Word -> WordMap a -> WordMap a -> WordMap a
forall a.
Hashable a =>
Word -> Word -> WordMap a -> WordMap a -> WordMap a
combine Word
p1 Word
m1 WordMap a
l WordMap a
r
          | Bool
otherwise     -> HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)

-- | Check if a key is present in the map.
member :: Word -> WordMap a -> Bool
member :: forall a. Word -> WordMap a -> Bool
member Word
_ WordMap a
Empty = Bool
False
member Word
k (NonEmptyMap HashCons (NonEmptyWordMap a)
hc) = Word -> NonEmptyWordMap a -> Bool
forall a. Word -> NonEmptyWordMap a -> Bool
memberNonEmpty Word
k (HashCons (NonEmptyWordMap a) -> NonEmptyWordMap a
forall a. HashCons a -> a
unHashCons HashCons (NonEmptyWordMap a)
hc)

memberNonEmpty :: Word -> NonEmptyWordMap a -> Bool
memberNonEmpty :: forall a. Word -> NonEmptyWordMap a -> Bool
memberNonEmpty Word
k (Leaf Word
k' a
_)
  | Word
k Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
k'   = Bool
True
  | Bool
otherwise = Bool
False
memberNonEmpty Word
k (Bin Word
p Word
m WordMap a
l WordMap a
r)
  | Word -> Word -> Word -> Bool
match Word
k Word
p Word
m = if Word -> Word -> Bool
zero Word
k Word
m then Word -> WordMap a -> Bool
forall a. Word -> WordMap a -> Bool
member Word
k WordMap a
l else Word -> WordMap a -> Bool
forall a. Word -> WordMap a -> Bool
member Word
k WordMap a
r
  | Bool
otherwise   = Bool
False

-- | Helper function to combine two subtrees.
combine :: Hashable a => Word -> Word -> WordMap a -> WordMap a -> WordMap a
combine :: forall a.
Hashable a =>
Word -> Word -> WordMap a -> WordMap a -> WordMap a
combine Word
_ Word
_ WordMap a
Empty WordMap a
Empty = WordMap a
forall a. WordMap a
Empty
combine Word
p Word
m WordMap a
l WordMap a
r = HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons (Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p Word
m WordMap a
l WordMap a
r))

-- | Helper functions.

join :: Hashable a => Word -> NonEmptyWordMap a -> Word -> NonEmptyWordMap a -> NonEmptyWordMap a
join :: forall a.
Hashable a =>
Word
-> NonEmptyWordMap a
-> Word
-> NonEmptyWordMap a
-> NonEmptyWordMap a
join Word
p1 NonEmptyWordMap a
t1 Word
p2 NonEmptyWordMap a
t2 =
  let m :: Word
m = Word -> Word -> Word
branchingBit Word
p1 Word
p2
      p :: Word
p = Word -> Word -> Word
mask Word
p1 Word
m
  in if Word -> Word -> Bool
zero Word
p1 Word
m
     then Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p Word
m (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1)) (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t2))
     else Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
forall a.
Word -> Word -> WordMap a -> WordMap a -> NonEmptyWordMap a
Bin Word
p Word
m (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t2)) (HashCons (NonEmptyWordMap a) -> WordMap a
forall a. HashCons (NonEmptyWordMap a) -> WordMap a
NonEmptyMap (NonEmptyWordMap a -> HashCons (NonEmptyWordMap a)
forall a. Hashable a => a -> HashCons a
hashCons NonEmptyWordMap a
t1))

match :: Word -> Word -> Word -> Bool
match :: Word -> Word -> Word -> Bool
match Word
k Word
p Word
m = Word -> Word -> Word
mask Word
k Word
m Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
p

mask :: Word -> Word -> Word
mask :: Word -> Word -> Word
mask Word
k Word
m = Word
k Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. (Word -> Word
forall a. Bits a => a -> a
complement (Word
m Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
1) Word -> Word -> Word
forall a. Bits a => a -> a -> a
`xor` Word
m)

zero :: Word -> Word -> Bool
zero :: Word -> Word -> Bool
zero Word
k Word
m = (Word
k Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word
m) Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
0

branchingBit :: Word -> Word -> Word
branchingBit :: Word -> Word -> Word
branchingBit Word
p1 Word
p2 = Word -> Word
highestBitMask (Word
p1 Word -> Word -> Word
forall a. Bits a => a -> a -> a
`xor` Word
p2)

highestBitMask :: Word -> Word
highestBitMask :: Word -> Word
highestBitMask Word
x
  | Word
x Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
0    = Word
0
  | Bool
otherwise = Int -> Word
forall a. Bits a => Int -> a
bit (Word -> Int
forall b. FiniteBits b => b -> Int
finiteBitSize Word
x Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1 Int -> Int -> Int
forall a. Num a => a -> a -> a
- Word -> Int
forall b. FiniteBits b => b -> Int
countLeadingZeros Word
x)

shorter :: Word -> Word -> Bool
shorter :: Word -> Word -> Bool
shorter Word
m1 Word
m2 = Word
m1 Word -> Word -> Bool
forall a. Ord a => a -> a -> Bool
> Word
m2