-- | A map of `String` keys represented by a radix tree.
module MCSP.Data.RadixTree.Map (
    -- * Data Types
    RadixTreeMap (..),
    Edge (..),
    EdgeSet,
    debug,

    -- * Construction
    empty,
    construct,

    -- * Query
    lookup,
    lookupMin,
    lookupMinWithKey,
    lookupMax,
    lookupMaxWithKey,
    member,

    -- * Modification
    insert,
    insertWith,
    union,
    unionWith,
    delete,
    updatePath,
) where

import Control.Applicative (liftA2, pure)
import Control.Monad ((<$!>))
import Data.Bool (Bool (False, True))
import Data.Char (Char)
import Data.Eq (Eq ((==)))
import Data.Foldable (foldMap, foldMap', foldl, foldl', foldr, foldr', toList)
import Data.Foldable qualified as Foldable (Foldable (..))
import Data.Foldable1 qualified as Foldable1 (Foldable1 (..), foldl1, foldr1)
import Data.Function (const, flip, id, ($), (.))
import Data.Functor (Functor (fmap, (<$)), (<$>))
import Data.Int (Int)
import Data.List.Extra (map)
import Data.List.NonEmpty (nonEmpty)
import Data.Maybe (Maybe (Just, Nothing), isJust, maybe)
import Data.Monoid (mempty, (<>))
import Data.Ord (Ord, (>))
import Data.String qualified as Text (String)
import Data.Traversable (Traversable (..))
import Data.Tuple (snd, uncurry)
import Data.Word (Word8)
import GHC.Base (($!))
import GHC.Err (error, errorWithoutStackTrace)
import GHC.Num ((+), (-))
import Text.Show (Show (showsPrec), showChar, showParen, showString, shows)

import Data.Map.Strict qualified as Map
import Data.Map.Strict.Internal (Map (Bin))

import MCSP.Data.String (ShowString, String (..), Unbox, (++))
import MCSP.Data.String.Extra.Radix (splitCommonPrefix, stripPrefix)

-- --------------- --
-- Data definition --
-- --------------- --

-- | A map of `String` keys represented by a [radix tree](https://en.wikipedia.org/wiki/Radix_tree).
--
-- The tree structure uses the maximal substring possible to label edges so that each internal node
-- has at least two children. Even though a substrings are used, the trie property is maintained,
-- that is, a node has at most @r@ children, where @r@ is the number of possible values for @a@.
-- Given this property, substring are stored using a sorted `Map.Map` which may improve performance.
data RadixTreeMap a v
    = -- | A subtree or node in the map.
      --
      -- Each node may contain a value and is considered a terminating node in that case, or it may
      -- be only a radix for its children. Note that all leaves must be terminating, except for
      -- empty tree maps.
      Tree
      { -- | The value for a terminating node.
        forall a v. RadixTreeMap a v -> Maybe v
value :: {-# UNPACK #-} !(Maybe v),
        -- | The set of labelled edges to its children.
        forall a v. RadixTreeMap a v -> EdgeSet a v
edges :: {-# UNPACK #-} !(EdgeSet a v)
      }
    deriving stock (RadixTreeMap a v -> RadixTreeMap a v -> Bool
(RadixTreeMap a v -> RadixTreeMap a v -> Bool)
-> (RadixTreeMap a v -> RadixTreeMap a v -> Bool)
-> Eq (RadixTreeMap a v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall a v.
(Eq v, Eq a) =>
RadixTreeMap a v -> RadixTreeMap a v -> Bool
$c== :: forall a v.
(Eq v, Eq a) =>
RadixTreeMap a v -> RadixTreeMap a v -> Bool
== :: RadixTreeMap a v -> RadixTreeMap a v -> Bool
$c/= :: forall a v.
(Eq v, Eq a) =>
RadixTreeMap a v -> RadixTreeMap a v -> Bool
/= :: RadixTreeMap a v -> RadixTreeMap a v -> Bool
Eq, Eq (RadixTreeMap a v)
Eq (RadixTreeMap a v) =>
(RadixTreeMap a v -> RadixTreeMap a v -> Ordering)
-> (RadixTreeMap a v -> RadixTreeMap a v -> Bool)
-> (RadixTreeMap a v -> RadixTreeMap a v -> Bool)
-> (RadixTreeMap a v -> RadixTreeMap a v -> Bool)
-> (RadixTreeMap a v -> RadixTreeMap a v -> Bool)
-> (RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v)
-> (RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v)
-> Ord (RadixTreeMap a v)
RadixTreeMap a v -> RadixTreeMap a v -> Bool
RadixTreeMap a v -> RadixTreeMap a v -> Ordering
RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
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 v. (Ord v, Ord a) => Eq (RadixTreeMap a v)
forall a v.
(Ord v, Ord a) =>
RadixTreeMap a v -> RadixTreeMap a v -> Bool
forall a v.
(Ord v, Ord a) =>
RadixTreeMap a v -> RadixTreeMap a v -> Ordering
forall a v.
(Ord v, Ord a) =>
RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
$ccompare :: forall a v.
(Ord v, Ord a) =>
RadixTreeMap a v -> RadixTreeMap a v -> Ordering
compare :: RadixTreeMap a v -> RadixTreeMap a v -> Ordering
$c< :: forall a v.
(Ord v, Ord a) =>
RadixTreeMap a v -> RadixTreeMap a v -> Bool
< :: RadixTreeMap a v -> RadixTreeMap a v -> Bool
$c<= :: forall a v.
(Ord v, Ord a) =>
RadixTreeMap a v -> RadixTreeMap a v -> Bool
<= :: RadixTreeMap a v -> RadixTreeMap a v -> Bool
$c> :: forall a v.
(Ord v, Ord a) =>
RadixTreeMap a v -> RadixTreeMap a v -> Bool
> :: RadixTreeMap a v -> RadixTreeMap a v -> Bool
$c>= :: forall a v.
(Ord v, Ord a) =>
RadixTreeMap a v -> RadixTreeMap a v -> Bool
>= :: RadixTreeMap a v -> RadixTreeMap a v -> Bool
$cmax :: forall a v.
(Ord v, Ord a) =>
RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
max :: RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
$cmin :: forall a v.
(Ord v, Ord a) =>
RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
min :: RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
Ord)

{-# COMPLETE Leaf, Empty, WithSomeKey #-}

-- | /O(1)/ Matches a tree node with value but no edges.
pattern Leaf :: v -> RadixTreeMap a v
pattern $mLeaf :: forall {r} {v} {a}.
RadixTreeMap a v -> (v -> r) -> ((# #) -> r) -> r
$bLeaf :: forall v a. v -> RadixTreeMap a v
Leaf x = Tree (Just x) NullSet
{-# INLINE CONLIKE Leaf #-}

-- | /O(1)/ Matches an empty `RadixTreeMap`.
pattern Empty :: RadixTreeMap a v
pattern $mEmpty :: forall {r} {a} {v}.
RadixTreeMap a v -> ((# #) -> r) -> ((# #) -> r) -> r
$bEmpty :: forall a v. RadixTreeMap a v
Empty = Tree Nothing NullSet
{-# INLINE CONLIKE Empty #-}

-- | /O(1)/ Matches any key inside a `RadixTreeMap`.
pattern WithSomeKey :: () => Unbox a => String a -> RadixTreeMap a v
pattern $mWithSomeKey :: forall {r} {a} {v}.
RadixTreeMap a v -> (Unbox a => String a -> r) -> ((# #) -> r) -> r
WithSomeKey s <- (edges -> Bin _ _ (s@Unboxed :~> _) _ _)
{-# INLINE CONLIKE WithSomeKey #-}

-- | A collection of uniquely labelled edges.
--
-- This could be @`Map.Map` (`String` a) (`Edge` a v)@, using the entire label as key, but the
-- [trie property](https://en.wikipedia.org/wiki/Trie) ensures that the first character of the
-- label must also be unique. This enables us to use a faster implementation and also helps to
-- ensure the trie property.
type EdgeSet a v = Map.Map a (Edge a v)

-- | /O(1)/ Matches an empty `EdgeSet`.
pattern NullSet :: EdgeSet a v
pattern $mNullSet :: forall {r} {a} {v}.
EdgeSet a v -> ((# #) -> r) -> ((# #) -> r) -> r
$bNullSet :: forall a v. EdgeSet a v
NullSet <- (Map.null -> True)
    where
        NullSet = Map a (Edge a v)
forall k a. Map k a
Map.empty
{-# INLINE CONLIKE NullSet #-}

-- | /O(1)/ Matches an `EdgeSet` with a single edge.
pattern Single :: () => Unbox a => Edge a v -> EdgeSet a v
pattern $mSingle :: forall {r} {a} {v}.
EdgeSet a v -> (Unbox a => Edge a v -> r) -> ((# #) -> r) -> r
Single e <- (id -> Bin 1 _ e@(Unboxed :~> _) _ _)
{-# INLINE CONLIKE Single #-}

-- | A labelled edge.
--
-- A simple pair @(label `:~>` subtree)@ representing an edge of a `RadixTreeMap`.
--
-- Note that the subtre pointed by an edge must never be empty!
data Edge a v = {-# UNPACK #-} !(String a) :~> {-# UNPACK #-} !(RadixTreeMap a v)
    deriving stock (Edge a v -> Edge a v -> Bool
(Edge a v -> Edge a v -> Bool)
-> (Edge a v -> Edge a v -> Bool) -> Eq (Edge a v)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall a v. (Eq a, Eq v) => Edge a v -> Edge a v -> Bool
$c== :: forall a v. (Eq a, Eq v) => Edge a v -> Edge a v -> Bool
== :: Edge a v -> Edge a v -> Bool
$c/= :: forall a v. (Eq a, Eq v) => Edge a v -> Edge a v -> Bool
/= :: Edge a v -> Edge a v -> Bool
Eq, Eq (Edge a v)
Eq (Edge a v) =>
(Edge a v -> Edge a v -> Ordering)
-> (Edge a v -> Edge a v -> Bool)
-> (Edge a v -> Edge a v -> Bool)
-> (Edge a v -> Edge a v -> Bool)
-> (Edge a v -> Edge a v -> Bool)
-> (Edge a v -> Edge a v -> Edge a v)
-> (Edge a v -> Edge a v -> Edge a v)
-> Ord (Edge a v)
Edge a v -> Edge a v -> Bool
Edge a v -> Edge a v -> Ordering
Edge a v -> Edge a v -> Edge a v
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 v. (Ord a, Ord v) => Eq (Edge a v)
forall a v. (Ord a, Ord v) => Edge a v -> Edge a v -> Bool
forall a v. (Ord a, Ord v) => Edge a v -> Edge a v -> Ordering
forall a v. (Ord a, Ord v) => Edge a v -> Edge a v -> Edge a v
$ccompare :: forall a v. (Ord a, Ord v) => Edge a v -> Edge a v -> Ordering
compare :: Edge a v -> Edge a v -> Ordering
$c< :: forall a v. (Ord a, Ord v) => Edge a v -> Edge a v -> Bool
< :: Edge a v -> Edge a v -> Bool
$c<= :: forall a v. (Ord a, Ord v) => Edge a v -> Edge a v -> Bool
<= :: Edge a v -> Edge a v -> Bool
$c> :: forall a v. (Ord a, Ord v) => Edge a v -> Edge a v -> Bool
> :: Edge a v -> Edge a v -> Bool
$c>= :: forall a v. (Ord a, Ord v) => Edge a v -> Edge a v -> Bool
>= :: Edge a v -> Edge a v -> Bool
$cmax :: forall a v. (Ord a, Ord v) => Edge a v -> Edge a v -> Edge a v
max :: Edge a v -> Edge a v -> Edge a v
$cmin :: forall a v. (Ord a, Ord v) => Edge a v -> Edge a v -> Edge a v
min :: Edge a v -> Edge a v -> Edge a v
Ord)

-- -------------- --
-- Map operations --
-- -------------- --

-- ------------ --
-- Construction --

-- | /O(1)/ The empty map.
--
-- >>> import Prelude (Char, Int)
-- >>> empty @Char @Int
-- Tree []
empty :: RadixTreeMap a v
empty :: forall a v. RadixTreeMap a v
empty = RadixTreeMap a v
forall a v. RadixTreeMap a v
Empty
{-# INLINE empty #-}

-- | /O(?)/ Build a map from a list of key/value pairs.
--
-- >>> import Prelude (Char, Int)
-- >>> construct [("abc", 1), ("def", 3), ("abb", 5)]
-- Tree [ab :~> Tree [b :~> Tree (5) [],c :~> Tree (1) []],def :~> Tree (3) []]
construct :: Ord a => [(String a, v)] -> RadixTreeMap a v
construct :: forall a v. Ord a => [(String a, v)] -> RadixTreeMap a v
construct = (RadixTreeMap a v -> (String a, v) -> RadixTreeMap a v)
-> RadixTreeMap a v -> [(String a, v)] -> RadixTreeMap a v
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (((String a, v) -> RadixTreeMap a v -> RadixTreeMap a v)
-> RadixTreeMap a v -> (String a, v) -> RadixTreeMap a v
forall a b c. (a -> b -> c) -> b -> a -> c
flip (((String a, v) -> RadixTreeMap a v -> RadixTreeMap a v)
 -> RadixTreeMap a v -> (String a, v) -> RadixTreeMap a v)
-> ((String a, v) -> RadixTreeMap a v -> RadixTreeMap a v)
-> RadixTreeMap a v
-> (String a, v)
-> RadixTreeMap a v
forall a b. (a -> b) -> a -> b
$ (String a -> v -> RadixTreeMap a v -> RadixTreeMap a v)
-> (String a, v) -> RadixTreeMap a v -> RadixTreeMap a v
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry String a -> v -> RadixTreeMap a v -> RadixTreeMap a v
forall a v.
Ord a =>
String a -> v -> RadixTreeMap a v -> RadixTreeMap a v
insert) RadixTreeMap a v
forall a v. RadixTreeMap a v
empty
{-# INLINEABLE construct #-}

-- ----- --
-- Query --

-- | /O(n log r)/ Lookup the value at a key in the map.
--
-- >>> import Prelude (Int)
-- >>> lookup "abc" (construct [("abc", 1), ("def", 3), ("abb", 5)])
-- Just 1
--
-- >>> lookup "xyz" (construct [("abc", 1), ("def", 3), ("abb", 5)])
-- Nothing
--
-- >>> lookupMax (construct [("abc", 1), ("def", 3), ("abb", 5)])
-- Just 3
lookup :: Ord a => String a -> RadixTreeMap a v -> Maybe v
lookup :: forall a v. Ord a => String a -> RadixTreeMap a v -> Maybe v
lookup String a
Null RadixTreeMap a v
t = RadixTreeMap a v -> Maybe v
forall a v. RadixTreeMap a v -> Maybe v
value RadixTreeMap a v
t
lookup k :: String a
k@(Head a
h) RadixTreeMap a v
t = do
    String a
prefix :~> RadixTreeMap a v
subt <- a -> Map a (Edge a v) -> Maybe (Edge a v)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup a
h (RadixTreeMap a v -> Map a (Edge a v)
forall a v. RadixTreeMap a v -> EdgeSet a v
edges RadixTreeMap a v
t)
    String a
rest <- String a -> String a -> Maybe (String a)
forall a. Eq a => String a -> String a -> Maybe (String a)
stripPrefix String a
prefix String a
k
    String a -> RadixTreeMap a v -> Maybe v
forall a v. Ord a => String a -> RadixTreeMap a v -> Maybe v
lookup String a
rest RadixTreeMap a v
subt
{-# INLINEABLE lookup #-}

-- | /O(n log r)/ Extract the minimal key in the map.
--
-- >>> lookupMinWithKey (construct [("abc", 1), ("def", 3), ("abb", 5)])
-- Just (abb,5)
--
-- >>> lookupMinWithKey @Char @Int empty
-- Nothing
lookupMinWithKey :: Unbox a => RadixTreeMap a v -> Maybe (String a, v)
lookupMinWithKey :: forall a v. Unbox a => RadixTreeMap a v -> Maybe (String a, v)
lookupMinWithKey (Tree (Just !v
x) EdgeSet a v
_) = (String a, v) -> Maybe (String a, v)
forall a. a -> Maybe a
Just (String a
forall a. Monoid a => a
mempty, v
x)
lookupMinWithKey (Tree Maybe v
Nothing EdgeSet a v
es) = do
    (a
_, String a
prefix :~> RadixTreeMap a v
t) <- EdgeSet a v -> Maybe (a, Edge a v)
forall k a. Map k a -> Maybe (k, a)
Map.lookupMin EdgeSet a v
es
    (String a
suffix, v
val) <- RadixTreeMap a v -> Maybe (String a, v)
forall a v. Unbox a => RadixTreeMap a v -> Maybe (String a, v)
lookupMinWithKey RadixTreeMap a v
t
    (String a, v) -> Maybe (String a, v)
forall a. a -> Maybe a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (String a
prefix String a -> String a -> String a
forall a. String a -> String a -> String a
++ String a
suffix, v
val)
{-# INLINEABLE lookupMinWithKey #-}

-- | /O(n log r)/ Extract the maximal key in the map.
--
-- >>> lookupMaxWithKey (construct [("abc", 1), ("def", 3), ("abb", 5)])
-- Just (def,3)
--
-- >>> lookupMaxWithKey @Char @Int empty
-- Nothing
lookupMaxWithKey :: Unbox a => RadixTreeMap a v -> Maybe (String a, v)
lookupMaxWithKey :: forall a v. Unbox a => RadixTreeMap a v -> Maybe (String a, v)
lookupMaxWithKey (Leaf v
x) = (String a, v) -> Maybe (String a, v)
forall a. a -> Maybe a
Just (String a
forall a. Monoid a => a
mempty, v
x)
lookupMaxWithKey (Tree Maybe v
_ EdgeSet a v
es) = do
    (a
_, String a
prefix :~> RadixTreeMap a v
t) <- EdgeSet a v -> Maybe (a, Edge a v)
forall k a. Map k a -> Maybe (k, a)
Map.lookupMax EdgeSet a v
es
    (String a
suffix, v
val) <- RadixTreeMap a v -> Maybe (String a, v)
forall a v. Unbox a => RadixTreeMap a v -> Maybe (String a, v)
lookupMaxWithKey RadixTreeMap a v
t
    (String a, v) -> Maybe (String a, v)
forall a. a -> Maybe a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (String a
prefix String a -> String a -> String a
forall a. String a -> String a -> String a
++ String a
suffix, v
val)
{-# INLINEABLE lookupMaxWithKey #-}

-- | /O(n log r)/ Extract the value associated with the minimal key in the map.
--
-- >>> lookupMin @Char @Int (construct [("abc", 1), ("def", 3), ("abb", 5)])
-- Just 5
--
-- >>> lookupMin @Char @Int empty
-- Nothing
lookupMin :: RadixTreeMap a v -> Maybe v
lookupMin :: forall a v. RadixTreeMap a v -> Maybe v
lookupMin (Tree (Just !v
x) EdgeSet a v
_) = v -> Maybe v
forall a. a -> Maybe a
Just v
x
lookupMin (Tree Maybe v
Nothing EdgeSet a v
es) = do
    (a
_, String a
_ :~> RadixTreeMap a v
t) <- EdgeSet a v -> Maybe (a, Edge a v)
forall k a. Map k a -> Maybe (k, a)
Map.lookupMin EdgeSet a v
es
    RadixTreeMap a v -> Maybe v
forall a v. RadixTreeMap a v -> Maybe v
lookupMin RadixTreeMap a v
t
{-# INLINEABLE lookupMin #-}

-- | /O(n log r)/ Extract the value associated with the maximal key in the map.
--
-- >>> lookupMax @Char @Int (construct [("abc", 1), ("def", 3), ("abb", 5)])
-- Just 3
--
-- >>> lookupMax @Char @Int empty
-- Nothing
lookupMax :: RadixTreeMap a v -> Maybe v
lookupMax :: forall a v. RadixTreeMap a v -> Maybe v
lookupMax (Leaf !v
x) = v -> Maybe v
forall a. a -> Maybe a
Just v
x
lookupMax (Tree Maybe v
_ EdgeSet a v
es) = do
    (a
_, String a
_ :~> RadixTreeMap a v
t) <- EdgeSet a v -> Maybe (a, Edge a v)
forall k a. Map k a -> Maybe (k, a)
Map.lookupMax EdgeSet a v
es
    RadixTreeMap a v -> Maybe v
forall a v. RadixTreeMap a v -> Maybe v
lookupMax RadixTreeMap a v
t
{-# INLINEABLE lookupMax #-}

-- | /O(n log r)/ Check if there is an associated value for the key.
--
-- >>> member "abc" (construct [("abc", 1), ("def", 3), ("abb", 5)])
-- True
--
-- >>> member "xyz" (construct [("abc", 1), ("def", 3), ("abb", 5)])
-- False
member :: Ord a => String a -> RadixTreeMap a v -> Bool
member :: forall a v. Ord a => String a -> RadixTreeMap a v -> Bool
member String a
k RadixTreeMap a v
t = Maybe v -> Bool
forall a. Maybe a -> Bool
isJust (String a -> RadixTreeMap a v -> Maybe v
forall a v. Ord a => String a -> RadixTreeMap a v -> Maybe v
lookup String a
k RadixTreeMap a v
t)
{-# INLINE member #-}

-- --------- --
-- Insertion --

-- | /O(?)/ Merge two edges into a single edge by their common prefix.
--
-- There are basically three situations:
-- * both edge labels are distinct, but share a common prefix; then the edge is replaced by a
-- new edge with both subtrees as children.
-- * one label is a prefix of the other; then the other subtree is inserted into the prefix edge.
-- * both label are equal; then the edge is replaced by the union of the subtrees.
mergeWith :: Ord a => (v -> v -> v) -> Edge a v -> Edge a v -> Edge a v
mergeWith :: forall a v.
Ord a =>
(v -> v -> v) -> Edge a v -> Edge a v -> Edge a v
mergeWith v -> v -> v
f (String a
kx :~> tx :: RadixTreeMap a v
tx@(Tree Maybe v
vx EdgeSet a v
ex)) (String a
ky :~> ty :: RadixTreeMap a v
ty@(Tree Maybe v
vy EdgeSet a v
ey)) =
    String a
prefix String a -> RadixTreeMap a v -> Edge a v
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> case (String a
rkx, String a
rky) of
        -- kx == prefix == ky
        (String a
Null, String a
Null) -> (v -> v -> v)
-> RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
forall a v.
Ord a =>
(v -> v -> v)
-> RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
unionWith v -> v -> v
f RadixTreeMap a v
tx RadixTreeMap a v
ty
        -- prefix + rky == kx + rky == ky
        (String a
Null, Head a
hy) -> Maybe v -> EdgeSet a v -> RadixTreeMap a v
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree Maybe v
vx ((Edge a v -> Edge a v -> Edge a v)
-> a -> Edge a v -> EdgeSet a v -> EdgeSet a v
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
Map.insertWith ((v -> v -> v) -> Edge a v -> Edge a v -> Edge a v
forall a v.
Ord a =>
(v -> v -> v) -> Edge a v -> Edge a v -> Edge a v
mergeWith v -> v -> v
f) a
hy (String a
rky String a -> RadixTreeMap a v -> Edge a v
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap a v
ty) EdgeSet a v
ex)
        -- prefix + rkx == kx == ky + rkx
        (Head a
hx, String a
Null) -> Maybe v -> EdgeSet a v -> RadixTreeMap a v
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree Maybe v
vy ((Edge a v -> Edge a v -> Edge a v)
-> a -> Edge a v -> EdgeSet a v -> EdgeSet a v
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
Map.insertWith ((v -> v -> v) -> Edge a v -> Edge a v -> Edge a v
forall a v.
Ord a =>
(v -> v -> v) -> Edge a v -> Edge a v -> Edge a v
mergeWith v -> v -> v
f) a
hx (String a
rkx String a -> RadixTreeMap a v -> Edge a v
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap a v
tx) EdgeSet a v
ey)
        -- rkx != rky
        (Head a
hx, Head a
hy) -> Maybe v -> EdgeSet a v -> RadixTreeMap a v
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree Maybe v
forall a. Maybe a
Nothing ([(a, Edge a v)] -> EdgeSet a v
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList [(a
hx, String a
rkx String a -> RadixTreeMap a v -> Edge a v
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap a v
tx), (a
hy, String a
rky String a -> RadixTreeMap a v -> Edge a v
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap a v
ty)])
  where
    (String a
prefix, String a
rkx, String a
rky) = String a -> String a -> (String a, String a, String a)
forall a.
Eq a =>
String a -> String a -> (String a, String a, String a)
splitCommonPrefix String a
kx String a
ky

-- | Insert with a function, combining new value and old value.
--
-- @`insertWith` f key value tree@ will insert the pair @(key, value)@ into @tree@ if key does
-- not exist in the map. If the key does exist, the function will insert the pair
-- @(key, f new_value old_value)@.
insertWith :: Ord a => (v -> v -> v) -> String a -> v -> RadixTreeMap a v -> RadixTreeMap a v
insertWith :: forall a v.
Ord a =>
(v -> v -> v)
-> String a -> v -> RadixTreeMap a v -> RadixTreeMap a v
insertWith v -> v -> v
f String a
Null v
x (Tree Maybe v
val EdgeSet a v
es) = Maybe v -> EdgeSet a v -> RadixTreeMap a v
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree (v -> Maybe v
forall a. a -> Maybe a
Just (v -> (v -> v) -> Maybe v -> v
forall b a. b -> (a -> b) -> Maybe a -> b
maybe v
x (v -> v -> v
f v
x) Maybe v
val)) EdgeSet a v
es
insertWith v -> v -> v
f kx :: String a
kx@(Head a
h) v
x (Tree Maybe v
val EdgeSet a v
es) = Maybe v -> EdgeSet a v -> RadixTreeMap a v
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree Maybe v
val ((Edge a v -> Edge a v -> Edge a v)
-> a -> Edge a v -> EdgeSet a v -> EdgeSet a v
forall k a. Ord k => (a -> a -> a) -> k -> a -> Map k a -> Map k a
Map.insertWith ((v -> v -> v) -> Edge a v -> Edge a v -> Edge a v
forall a v.
Ord a =>
(v -> v -> v) -> Edge a v -> Edge a v -> Edge a v
mergeWith v -> v -> v
f) a
h (String a
kx String a -> RadixTreeMap a v -> Edge a v
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> v -> RadixTreeMap a v
forall v a. v -> RadixTreeMap a v
Leaf v
x) EdgeSet a v
es)
{-# INLINE insertWith #-}

-- | /O(?)/ Insert a new key and value in the map.
--
--  If the key is already present in the map, the associated value is replaced with the supplied
-- value.
insert :: Ord a => String a -> v -> RadixTreeMap a v -> RadixTreeMap a v
insert :: forall a v.
Ord a =>
String a -> v -> RadixTreeMap a v -> RadixTreeMap a v
insert = (v -> v -> v)
-> String a -> v -> RadixTreeMap a v -> RadixTreeMap a v
forall a v.
Ord a =>
(v -> v -> v)
-> String a -> v -> RadixTreeMap a v -> RadixTreeMap a v
insertWith v -> v -> v
forall a b. a -> b -> a
const
{-# INLINE insert #-}

-- | /O(?)/  Union with a combining function.
unionWith :: Ord a => (v -> v -> v) -> RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
unionWith :: forall a v.
Ord a =>
(v -> v -> v)
-> RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
unionWith v -> v -> v
f (Tree Maybe v
vx EdgeSet a v
ex) (Tree Maybe v
vy EdgeSet a v
ey) = Maybe v -> EdgeSet a v -> RadixTreeMap a v
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree ((v -> v -> v) -> Maybe v -> Maybe v -> Maybe v
forall {a}. (a -> a -> a) -> Maybe a -> Maybe a -> Maybe a
mergeMaybe v -> v -> v
f Maybe v
vx Maybe v
vy) ((Edge a v -> Edge a v -> Edge a v)
-> EdgeSet a v -> EdgeSet a v -> EdgeSet a v
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith ((v -> v -> v) -> Edge a v -> Edge a v -> Edge a v
forall a v.
Ord a =>
(v -> v -> v) -> Edge a v -> Edge a v -> Edge a v
mergeWith v -> v -> v
f) EdgeSet a v
ex EdgeSet a v
ey)
  where
    mergeMaybe :: (a -> a -> a) -> Maybe a -> Maybe a -> Maybe a
mergeMaybe a -> a -> a
g (Just a
x) (Just a
y) = a -> Maybe a
forall a. a -> Maybe a
Just (a -> a -> a
g a
x a
y)
    mergeMaybe a -> a -> a
_ Maybe a
mx Maybe a
Nothing = Maybe a
mx
    mergeMaybe a -> a -> a
_ Maybe a
Nothing Maybe a
my = Maybe a
my
{-# INLINE unionWith #-}

-- | /O(?)/ The expression @union t1 t2@ takes the left-biased union of @t1@ and @t2@.
--
-- It prefers @t1@ when duplicate keys are encountered.
union :: Ord a => RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
union :: forall a v.
Ord a =>
RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
union = (v -> v -> v)
-> RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
forall a v.
Ord a =>
(v -> v -> v)
-> RadixTreeMap a v -> RadixTreeMap a v -> RadixTreeMap a v
unionWith v -> v -> v
forall a b. a -> b -> a
const
{-# INLINE union #-}

-- | /O(n log r)/ Update values for all prefixes of key in the map, present or not.
updatePath ::
    Ord a => (String a -> Maybe v -> Maybe v) -> String a -> RadixTreeMap a v -> RadixTreeMap a v
updatePath :: forall a v.
Ord a =>
(String a -> Maybe v -> Maybe v)
-> String a -> RadixTreeMap a v -> RadixTreeMap a v
updatePath String a -> Maybe v -> Maybe v
f k :: String a
k@String a
Null (Tree Maybe v
val EdgeSet a v
es) = Maybe v -> EdgeSet a v -> RadixTreeMap a v
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree (String a -> Maybe v -> Maybe v
f String a
k Maybe v
val) EdgeSet a v
es
updatePath String a -> Maybe v -> Maybe v
f k :: String a
k@(Head a
h) (Tree Maybe v
val EdgeSet a v
es) = Maybe v -> EdgeSet a v -> RadixTreeMap a v
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree (String a -> Maybe v -> Maybe v
f String a
k Maybe v
val) ((Edge a v -> Edge a v) -> a -> EdgeSet a v -> EdgeSet a v
forall k a. Ord k => (a -> a) -> k -> Map k a -> Map k a
Map.adjust Edge a v -> Edge a v
updateEdgeOnPath a
h EdgeSet a v
es)
  where
    updateEdgeOnPath :: Edge a v -> Edge a v
updateEdgeOnPath (String a
kx :~> RadixTreeMap a v
tx) = String a
kx String a -> RadixTreeMap a v -> Edge a v
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> (RadixTreeMap a v -> RadixTreeMap a v)
-> (String a -> RadixTreeMap a v -> RadixTreeMap a v)
-> Maybe (String a)
-> RadixTreeMap a v
-> RadixTreeMap a v
forall b a. b -> (a -> b) -> Maybe a -> b
maybe RadixTreeMap a v -> RadixTreeMap a v
forall a. a -> a
id ((String a -> Maybe v -> Maybe v)
-> String a -> RadixTreeMap a v -> RadixTreeMap a v
forall a v.
Ord a =>
(String a -> Maybe v -> Maybe v)
-> String a -> RadixTreeMap a v -> RadixTreeMap a v
updatePath String a -> Maybe v -> Maybe v
f) (String a -> String a -> Maybe (String a)
forall a. Eq a => String a -> String a -> Maybe (String a)
stripPrefix String a
kx String a
k) RadixTreeMap a v
tx
{-# INLINEABLE updatePath #-}

-- -------- --
-- Deletion --

-- | /O(?)/ Remove a key from a subtree.
--
-- Returns `Just` the updated subtree or `Nothing` if the edge should be removed.
remove :: Ord a => String a -> Edge a v -> Maybe (Edge a v)
remove :: forall a v. Ord a => String a -> Edge a v -> Maybe (Edge a v)
remove String a
k (String a
label :~> t :: RadixTreeMap a v
t@(Tree Maybe v
val EdgeSet a v
es)) = case String a -> String a -> Maybe (String a)
forall a. Eq a => String a -> String a -> Maybe (String a)
stripPrefix String a
label String a
k of
    -- k == label, remove the current value
    Just String a
Null -> Maybe v -> EdgeSet a v -> Maybe (Edge a v)
nonEmptyEdge Maybe v
forall a. Maybe a
Nothing EdgeSet a v
es
    -- k == label + rk, continue searching in rk
    Just rk :: String a
rk@(Head a
h) -> Maybe v -> EdgeSet a v -> Maybe (Edge a v)
nonEmptyEdge Maybe v
val ((Edge a v -> Maybe (Edge a v)) -> a -> EdgeSet a v -> EdgeSet a v
forall k a. Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
Map.update (String a -> Edge a v -> Maybe (Edge a v)
forall a v. Ord a => String a -> Edge a v -> Maybe (Edge a v)
remove String a
rk) a
h EdgeSet a v
es)
    -- k != label, key is not present in map
    Maybe (String a)
Nothing -> Edge a v -> Maybe (Edge a v)
forall a. a -> Maybe a
Just (String a
label String a -> RadixTreeMap a v -> Edge a v
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap a v
t)
  where
    -- remove edges to empty subtrees
    nonEmptyEdge :: Maybe v -> EdgeSet a v -> Maybe (Edge a v)
nonEmptyEdge Maybe v
Nothing EdgeSet a v
NullSet = Maybe (Edge a v)
forall a. Maybe a
Nothing
    -- merge edges with a single child
    nonEmptyEdge Maybe v
Nothing (Single (String a
ln :~> RadixTreeMap a v
tn)) = Edge a v -> Maybe (Edge a v)
forall a. a -> Maybe a
Just (String a
label String a -> String a -> String a
forall a. String a -> String a -> String a
++ String a
ln String a -> RadixTreeMap a v -> Edge a v
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap a v
tn)
    -- just reconstruct the edge otherwise
    nonEmptyEdge Maybe v
vn EdgeSet a v
en = Edge a v -> Maybe (Edge a v)
forall a. a -> Maybe a
Just (String a
label String a -> RadixTreeMap a v -> Edge a v
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> Maybe v -> EdgeSet a v -> RadixTreeMap a v
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree Maybe v
vn EdgeSet a v
en)

-- | /O(?)/ Delete a key and its value from the map.
--
-- When the key is not a member of the map, the original map is returned.
delete :: Ord a => String a -> RadixTreeMap a v -> RadixTreeMap a v
delete :: forall a v.
Ord a =>
String a -> RadixTreeMap a v -> RadixTreeMap a v
delete String a
Null (Tree Maybe v
_ EdgeSet a v
es) = Maybe v -> EdgeSet a v -> RadixTreeMap a v
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree Maybe v
forall a. Maybe a
Nothing EdgeSet a v
es
delete k :: String a
k@(Head a
h) (Tree Maybe v
val EdgeSet a v
es) = Maybe v -> EdgeSet a v -> RadixTreeMap a v
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree Maybe v
val ((Edge a v -> Maybe (Edge a v)) -> a -> EdgeSet a v -> EdgeSet a v
forall k a. Ord k => (a -> Maybe a) -> k -> Map k a -> Map k a
Map.update (String a -> Edge a v -> Maybe (Edge a v)
forall a v. Ord a => String a -> Edge a v -> Maybe (Edge a v)
remove String a
k) a
h EdgeSet a v
es)
{-# INLINE delete #-}

-- ---------------- --
-- Text conversions --
-- ---------------- --

instance (ShowString a, Show v) => Show (RadixTreeMap a v) where
    showsPrec :: Size -> RadixTreeMap a v -> ShowS
showsPrec Size
d (Tree Maybe v
val EdgeSet a v
e) = Bool -> ShowS -> ShowS
showParen (Size
d Size -> Size -> Bool
forall a. Ord a => a -> a -> Bool
> Size
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ case Maybe v
val of
        Just v
x -> String -> ShowS
showString String
"Tree" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
showSpace ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. v -> ShowS
forall {a}. Show a => a -> ShowS
showVal v
x ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
showSpace ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
showEdges
        Maybe v
Nothing -> String -> ShowS
showString String
"Tree" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
showSpace ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
showEdges
      where
        showSpace :: ShowS
showSpace = Char -> ShowS
showChar Char
' '
        showVal :: a -> ShowS
showVal a
x = Bool -> ShowS -> ShowS
showParen Bool
True (a -> ShowS
forall {a}. Show a => a -> ShowS
shows a
x)
        showEdges :: ShowS
showEdges = [Edge a v] -> ShowS
forall {a}. Show a => a -> ShowS
shows (((a, Edge a v) -> Edge a v) -> [(a, Edge a v)] -> [Edge a v]
forall a b. (a -> b) -> [a] -> [b]
map (a, Edge a v) -> Edge a v
forall a b. (a, b) -> b
snd ([(a, Edge a v)] -> [Edge a v]) -> [(a, Edge a v)] -> [Edge a v]
forall a b. (a -> b) -> a -> b
$ EdgeSet a v -> [(a, Edge a v)]
forall k a. Map k a -> [(k, a)]
Map.toAscList EdgeSet a v
e)

instance (ShowString a, Show v) => Show (Edge a v) where
    showsPrec :: Size -> Edge a v -> ShowS
showsPrec Size
_ (String a
s :~> RadixTreeMap a v
t) = String a -> ShowS
forall {a}. Show a => a -> ShowS
shows String a
s ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" :~> " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. RadixTreeMap a v -> ShowS
forall {a}. Show a => a -> ShowS
shows RadixTreeMap a v
t

-- | Show `RadixTreeMap` in a readable, idented format.
debug :: (ShowString a, Show v) => RadixTreeMap a v -> Text.String
debug :: forall a v. (ShowString a, Show v) => RadixTreeMap a v -> String
debug RadixTreeMap a v
root = Size -> RadixTreeMap a v -> ShowS
forall {a} {t} {a}.
(Show a, Num t, Eq t, ShowString a) =>
t -> RadixTreeMap a a -> ShowS
go (Size
0 :: Int) RadixTreeMap a v
root String
""
  where
    -- recursive printers
    go :: t -> RadixTreeMap a a -> ShowS
go t
n (Tree Maybe a
val EdgeSet a a
es) = String -> ShowS
showString String
"Tree" ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
showSpace ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Maybe a -> ShowS
forall {a}. Show a => Maybe a -> ShowS
showVal Maybe a
val ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
showLn ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> EdgeSet a a -> ShowS
showEdges t
n EdgeSet a a
es
    showEdges :: t -> EdgeSet a a -> ShowS
showEdges t
n EdgeSet a a
es = ((a, Edge a a) -> ShowS -> ShowS)
-> ShowS -> [(a, Edge a a)] -> ShowS
forall a b. (a -> b -> b) -> b -> [a] -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\(a
_, Edge a a
e) ShowS
s -> t -> Edge a a -> ShowS
showEdge (t
n t -> t -> t
forall a. Num a => a -> a -> a
+ t
1) Edge a a
e ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ShowS
s) ShowS
forall a. a -> a
id ([(a, Edge a a)] -> ShowS) -> [(a, Edge a a)] -> ShowS
forall a b. (a -> b) -> a -> b
$ EdgeSet a a -> [(a, Edge a a)]
forall k a. Map k a -> [(k, a)]
Map.toAscList EdgeSet a a
es
    showEdge :: t -> Edge a a -> ShowS
showEdge t
n (String a
s :~> RadixTreeMap a a
t) = t -> ShowS
forall {t}. (Eq t, Num t) => t -> ShowS
ident t
n ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String a -> ShowS
forall {a}. Show a => a -> ShowS
shows String a
s ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" :~> " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> RadixTreeMap a a -> ShowS
go t
n RadixTreeMap a a
t
    -- additional printers
    showSpace :: ShowS
showSpace = Char -> ShowS
showChar Char
' '
    showLn :: ShowS
showLn = Char -> ShowS
showChar Char
'\n'
    showVal :: Maybe a -> ShowS
showVal Maybe a
v = Bool -> ShowS -> ShowS
showParen (Maybe a -> Bool
forall a. Maybe a -> Bool
isJust Maybe a
v) (Maybe a -> ShowS
forall {a}. Show a => a -> ShowS
shows Maybe a
v)
    -- identation for each edge
    ident :: t -> ShowS
ident t
0 = ShowS
forall a. a -> a
id
    ident t
n = String -> ShowS
showString String
"    " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t -> ShowS
ident (t
n t -> t -> t
forall a. Num a => a -> a -> a
- t
1)

-- ------------------ --
-- Foldable instances --
-- ------------------ --

-- | Extracts the element out of a `Just` and throws an error if its argument is `Nothing`.
--
-- This is an adaptation of `Data.Maybe.fromJust` without capturing the call stack for traces. It
-- should only be used when the error should never happen, like an `Edge` pointing to a an empty
-- subtree.
unwrap :: Text.String -> Maybe a -> a
unwrap :: forall a. String -> Maybe a -> a
unwrap String
_ (Just a
x) = a
x
unwrap String
message Maybe a
Nothing = String -> a
forall a. String -> a
errorWithoutStackTrace String
message
{-# INLINEABLE unwrap #-}

-- | Strict version of @unwrap@.
unwrap' :: Text.String -> Maybe a -> a
unwrap' :: forall a. String -> Maybe a -> a
unwrap' !String
_ (Just !a
x) = a
x
unwrap' !String
message Maybe a
Nothing = String -> a
forall a. String -> a
errorWithoutStackTrace String
message
{-# INLINEABLE unwrap' #-}

-- | Strict version of `fmap` for `Maybe`.
fmap' :: (a -> b) -> Maybe a -> Maybe b
fmap' :: forall a b. (a -> b) -> Maybe a -> Maybe b
fmap' = (a -> b) -> Maybe a -> Maybe b
forall (m :: * -> *) a b. Monad m => (a -> b) -> m a -> m b
(<$!>)
{-# INLINE fmap' #-}

-- | Delegate `Foldable.Foldabe` to its `Edge`s.
instance Foldable.Foldable (RadixTreeMap s) where
    {-# SPECIALIZE instance Foldable.Foldable (RadixTreeMap Char) #-}
    {-# SPECIALIZE instance Foldable.Foldable (RadixTreeMap Int) #-}
    {-# SPECIALIZE instance Foldable.Foldable (RadixTreeMap Word8) #-}
    fold :: forall m. Monoid m => RadixTreeMap s m -> m
fold RadixTreeMap s m
Empty = m
forall a. Monoid a => a
mempty
    fold (Leaf m
v) = m
v
    fold t :: RadixTreeMap s m
t@(WithSomeKey String s
k) = Edge s m -> m
forall m. Semigroup m => Edge s m -> m
forall (t :: * -> *) m. (Foldable1 t, Semigroup m) => t m -> m
Foldable1.fold1 (String s
k String s -> RadixTreeMap s m -> Edge s m
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s m
t)
    {-# INLINEABLE fold #-}
    foldMap :: forall m a. Monoid m => (a -> m) -> RadixTreeMap s a -> m
foldMap a -> m
_ RadixTreeMap s a
Empty = m
forall a. Monoid a => a
mempty
    foldMap a -> m
f (Leaf a
v) = a -> m
f a
v
    foldMap a -> m
f t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = (a -> m) -> Edge s a -> m
forall m a. Semigroup m => (a -> m) -> Edge s a -> m
forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
Foldable1.foldMap1 a -> m
f (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE foldMap #-}
    foldMap' :: forall m a. Monoid m => (a -> m) -> RadixTreeMap s a -> m
foldMap' a -> m
_ RadixTreeMap s a
Empty = m
forall a. Monoid a => a
mempty
    foldMap' a -> m
f (Leaf !a
v) = a -> m
f a
v
    foldMap' a -> m
f t :: RadixTreeMap s a
t@(WithSomeKey !String s
k) = (a -> m) -> Edge s a -> m
forall m a. Semigroup m => (a -> m) -> Edge s a -> m
forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
Foldable1.foldMap1' a -> m
f (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE foldMap' #-}
    foldr :: forall a b. (a -> b -> b) -> b -> RadixTreeMap s a -> b
foldr a -> b -> b
_ b
x RadixTreeMap s a
Empty = b
x
    foldr a -> b -> b
f b
x (Leaf a
v) = a -> b -> b
f a
v b
x
    foldr a -> b -> b
f b
x t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = (a -> b -> b) -> b -> Edge s a -> b
forall a b. (a -> b -> b) -> b -> Edge s a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f b
x (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE foldr #-}
    foldr' :: forall a b. (a -> b -> b) -> b -> RadixTreeMap s a -> b
foldr' a -> b -> b
_ !b
x RadixTreeMap s a
Empty = b
x
    foldr' a -> b -> b
f !b
x (Leaf !a
v) = a -> b -> b
f a
v b
x
    foldr' a -> b -> b
f !b
x t :: RadixTreeMap s a
t@(WithSomeKey !String s
k) = (a -> b -> b) -> b -> Edge s a -> b
forall a b. (a -> b -> b) -> b -> Edge s a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' a -> b -> b
f b
x (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE foldr' #-}
    foldl :: forall b a. (b -> a -> b) -> b -> RadixTreeMap s a -> b
foldl b -> a -> b
_ b
x RadixTreeMap s a
Empty = b
x
    foldl b -> a -> b
f b
x (Leaf a
v) = b -> a -> b
f b
x a
v
    foldl b -> a -> b
f b
x t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = (b -> a -> b) -> b -> Edge s a -> b
forall b a. (b -> a -> b) -> b -> Edge s a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl b -> a -> b
f b
x (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE foldl #-}
    foldl' :: forall b a. (b -> a -> b) -> b -> RadixTreeMap s a -> b
foldl' b -> a -> b
_ b
x RadixTreeMap s a
Empty = b
x
    foldl' b -> a -> b
f !b
x (Leaf !a
v) = b -> a -> b
f b
x a
v
    foldl' b -> a -> b
f !b
x t :: RadixTreeMap s a
t@(WithSomeKey !String s
k) = (b -> a -> b) -> b -> Edge s a -> b
forall b a. (b -> a -> b) -> b -> Edge s a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
f b
x (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE foldl' #-}
    foldr1 :: forall a. (a -> a -> a) -> RadixTreeMap s a -> a
foldr1 a -> a -> a
_ RadixTreeMap s a
Empty = String -> a
forall a. HasCallStack => String -> a
error String
"foldr1.RadixTreeMap: empty tree"
    foldr1 a -> a -> a
_ (Leaf a
v) = a
v
    foldr1 a -> a -> a
f t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = (a -> a -> a) -> Edge s a -> a
forall (t :: * -> *) a. Foldable1 t => (a -> a -> a) -> t a -> a
Foldable1.foldr1 a -> a -> a
f (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE foldr1 #-}
    foldl1 :: forall a. (a -> a -> a) -> RadixTreeMap s a -> a
foldl1 a -> a -> a
_ RadixTreeMap s a
Empty = String -> a
forall a. HasCallStack => String -> a
error String
"foldl1.RadixTreeMap: empty tree"
    foldl1 a -> a -> a
_ (Leaf a
v) = a
v
    foldl1 a -> a -> a
f t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = (a -> a -> a) -> Edge s a -> a
forall (t :: * -> *) a. Foldable1 t => (a -> a -> a) -> t a -> a
Foldable1.foldl1 a -> a -> a
f (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE foldl1 #-}
    toList :: forall a. RadixTreeMap s a -> [a]
toList RadixTreeMap s a
Empty = []
    toList (Leaf a
v) = [a
Item [a]
v]
    toList t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = Edge s a -> [a]
forall a. Edge s a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE toList #-}
    null :: forall a. RadixTreeMap s a -> Bool
null RadixTreeMap s a
Empty = Bool
True
    null RadixTreeMap s a
_ = Bool
False
    {-# INLINE null #-}
    length :: forall a. RadixTreeMap s a -> Size
length RadixTreeMap s a
Empty = Size
0
    length (Leaf a
_) = Size
1
    length t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = Edge s a -> Size
forall a. Edge s a -> Size
forall (t :: * -> *) a. Foldable t => t a -> Size
Foldable.length (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE length #-}
    elem :: forall a. Eq a => a -> RadixTreeMap s a -> Bool
elem a
_ RadixTreeMap s a
Empty = Bool
False
    elem a
x (Leaf a
v) = a
x a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
v
    elem a
x t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = a -> Edge s a -> Bool
forall a. Eq a => a -> Edge s a -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
Foldable.elem a
x (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE elem #-}
    maximum :: forall a. Ord a => RadixTreeMap s a -> a
maximum RadixTreeMap s a
Empty = String -> a
forall a. HasCallStack => String -> a
error String
"maximum.RadixTreeMap: empty tree"
    maximum (Leaf a
v) = a
v
    maximum t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = Edge s a -> a
forall a. Ord a => Edge s a -> a
forall (t :: * -> *) a. (Foldable1 t, Ord a) => t a -> a
Foldable1.maximum (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE maximum #-}
    minimum :: forall a. Ord a => RadixTreeMap s a -> a
minimum RadixTreeMap s a
Empty = String -> a
forall a. HasCallStack => String -> a
error String
"minimum.RadixTreeMap: empty tree"
    minimum (Leaf a
v) = a
v
    minimum t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = Edge s a -> a
forall a. Ord a => Edge s a -> a
forall (t :: * -> *) a. (Foldable1 t, Ord a) => t a -> a
Foldable1.minimum (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE minimum #-}
    sum :: forall a. Num a => RadixTreeMap s a -> a
sum RadixTreeMap s a
Empty = a
0
    sum (Leaf a
v) = a
v
    sum t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = Edge s a -> a
forall a. Num a => Edge s a -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
Foldable.sum (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE sum #-}
    product :: forall a. Num a => RadixTreeMap s a -> a
product RadixTreeMap s a
Empty = a
1
    product (Leaf a
v) = a
v
    product t :: RadixTreeMap s a
t@(WithSomeKey String s
k) = Edge s a -> a
forall a. Num a => Edge s a -> a
forall (t :: * -> *) a. (Foldable t, Num a) => t a -> a
Foldable.product (String s
k String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> RadixTreeMap s a
t)
    {-# INLINEABLE product #-}

-- | Implementation based on @`Foldable1` (`Edge` s)@
instance Foldable.Foldable (Edge s) where
    {-# SPECIALIZE instance Foldable.Foldable (Edge Char) #-}
    {-# SPECIALIZE instance Foldable.Foldable (Edge Int) #-}
    {-# SPECIALIZE instance Foldable.Foldable (Edge Word8) #-}
    fold :: forall m. Monoid m => Edge s m -> m
fold = Edge s m -> m
forall m. Semigroup m => Edge s m -> m
forall (t :: * -> *) m. (Foldable1 t, Semigroup m) => t m -> m
Foldable1.fold1
    {-# INLINE fold #-}
    foldMap :: forall m a. Monoid m => (a -> m) -> Edge s a -> m
foldMap = (a -> m) -> Edge s a -> m
forall m a. Semigroup m => (a -> m) -> Edge s a -> m
forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
Foldable1.foldMap1
    {-# INLINE foldMap #-}
    foldMap' :: forall m a. Monoid m => (a -> m) -> Edge s a -> m
foldMap' = (a -> m) -> Edge s a -> m
forall m a. Semigroup m => (a -> m) -> Edge s a -> m
forall (t :: * -> *) m a.
(Foldable1 t, Semigroup m) =>
(a -> m) -> t a -> m
Foldable1.foldMap1'
    {-# INLINE foldMap' #-}
    foldr :: forall a b. (a -> b -> b) -> b -> Edge s a -> b
foldr a -> b -> b
f b
x (String s
_ :~> Tree Maybe a
val EdgeSet s a
es) = (a -> b -> b) -> b -> Maybe a -> b
forall a b. (a -> b -> b) -> b -> Maybe a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f ((Edge s a -> b -> b) -> b -> EdgeSet s a -> b
forall a b k. (a -> b -> b) -> b -> Map k a -> b
Map.foldr ((b -> Edge s a -> b) -> Edge s a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((b -> Edge s a -> b) -> Edge s a -> b -> b)
-> (b -> Edge s a -> b) -> Edge s a -> b -> b
forall a b. (a -> b) -> a -> b
$ (a -> b -> b) -> b -> Edge s a -> b
forall a b. (a -> b -> b) -> b -> Edge s a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr a -> b -> b
f) b
x EdgeSet s a
es) Maybe a
val
    {-# INLINEABLE foldr #-}
    foldr' :: forall a b. (a -> b -> b) -> b -> Edge s a -> b
foldr' a -> b -> b
f b
x (String s
_ :~> Tree !Maybe a
val !EdgeSet s a
es) = (a -> b -> b) -> b -> Maybe a -> b
forall a b. (a -> b -> b) -> b -> Maybe a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' a -> b -> b
f ((Edge s a -> b -> b) -> b -> EdgeSet s a -> b
forall a b k. (a -> b -> b) -> b -> Map k a -> b
Map.foldr' ((b -> Edge s a -> b) -> Edge s a -> b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((b -> Edge s a -> b) -> Edge s a -> b -> b)
-> (b -> Edge s a -> b) -> Edge s a -> b -> b
forall a b. (a -> b) -> a -> b
$! (a -> b -> b) -> b -> Edge s a -> b
forall a b. (a -> b -> b) -> b -> Edge s a -> b
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr' a -> b -> b
f) b
x EdgeSet s a
es) Maybe a
val
    {-# INLINEABLE foldr' #-}
    foldl :: forall b a. (b -> a -> b) -> b -> Edge s a -> b
foldl b -> a -> b
f b
x (String s
_ :~> Tree Maybe a
val EdgeSet s a
es) = (b -> Edge s a -> b) -> b -> EdgeSet s a -> b
forall a b k. (a -> b -> a) -> a -> Map k b -> a
Map.foldl ((b -> a -> b) -> b -> Edge s a -> b
forall b a. (b -> a -> b) -> b -> Edge s a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl b -> a -> b
f) ((b -> a -> b) -> b -> Maybe a -> b
forall b a. (b -> a -> b) -> b -> Maybe a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl b -> a -> b
f b
x Maybe a
val) EdgeSet s a
es
    {-# INLINEABLE foldl #-}
    foldl' :: forall b a. (b -> a -> b) -> b -> Edge s a -> b
foldl' b -> a -> b
f b
x (String s
_ :~> Tree !Maybe a
val !EdgeSet s a
es) = (b -> Edge s a -> b) -> b -> EdgeSet s a -> b
forall a b k. (a -> b -> a) -> a -> Map k b -> a
Map.foldl' ((b -> a -> b) -> b -> Edge s a -> b
forall b a. (b -> a -> b) -> b -> Edge s a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
f) ((b -> a -> b) -> b -> Maybe a -> b
forall b a. (b -> a -> b) -> b -> Maybe a -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' b -> a -> b
f b
x Maybe a
val) EdgeSet s a
es
    {-# INLINEABLE foldl' #-}
    foldr1 :: forall a. (a -> a -> a) -> Edge s a -> a
foldr1 = (a -> a -> a) -> Edge s a -> a
forall (t :: * -> *) a. Foldable1 t => (a -> a -> a) -> t a -> a
Foldable1.foldr1
    {-# INLINE foldr1 #-}
    foldl1 :: forall a. (a -> a -> a) -> Edge s a -> a
foldl1 = (a -> a -> a) -> Edge s a -> a
forall (t :: * -> *) a. Foldable1 t => (a -> a -> a) -> t a -> a
Foldable1.foldl1
    {-# INLINE foldl1 #-}
    toList :: forall a. Edge s a -> [a]
toList (String s
_ :~> Tree (Just a
x) EdgeSet s a
es) = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: (Edge s a -> [a]) -> EdgeSet s a -> [a]
forall m a. Monoid m => (a -> m) -> Map s a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap Edge s a -> [a]
forall a. Edge s a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList EdgeSet s a
es
    toList (String s
_ :~> Tree Maybe a
Nothing EdgeSet s a
es) = (Edge s a -> [a]) -> EdgeSet s a -> [a]
forall m a. Monoid m => (a -> m) -> Map s a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap Edge s a -> [a]
forall a. Edge s a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList EdgeSet s a
es
    {-# INLINEABLE toList #-}
    null :: forall a. Edge s a -> Bool
null Edge s a
_ = Bool
False
    {-# INLINE null #-}
    maximum :: forall a. Ord a => Edge s a -> a
maximum = Edge s a -> a
forall a. Ord a => Edge s a -> a
forall (t :: * -> *) a. (Foldable1 t, Ord a) => t a -> a
Foldable1.maximum
    {-# INLINE maximum #-}
    minimum :: forall a. Ord a => Edge s a -> a
minimum = Edge s a -> a
forall a. Ord a => Edge s a -> a
forall (t :: * -> *) a. (Foldable1 t, Ord a) => t a -> a
Foldable1.minimum
    {-# INLINE minimum #-}

instance Foldable1.Foldable1 (Edge s) where
    {-# SPECIALIZE instance Foldable1.Foldable1 (Edge Char) #-}
    {-# SPECIALIZE instance Foldable1.Foldable1 (Edge Int) #-}
    {-# SPECIALIZE instance Foldable1.Foldable1 (Edge Word8) #-}
    fold1 :: forall m. Semigroup m => Edge s m -> m
fold1 = String -> Maybe m -> m
forall a. String -> Maybe a -> a
unwrap String
"Edge.fold1: unexpected empty subtree" (Maybe m -> m) -> (Edge s m -> Maybe m) -> Edge s m -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge s m -> Maybe m
forall {v} {a}. Semigroup v => Edge a v -> Maybe v
go
      where
        go :: Edge a v -> Maybe v
go (String a
_ :~> Tree Maybe v
val EdgeSet a v
es) = Maybe v
val Maybe v -> Maybe v -> Maybe v
forall a. Semigroup a => a -> a -> a
<> (Edge a v -> Maybe v) -> EdgeSet a v -> Maybe v
forall m a. Monoid m => (a -> m) -> Map a a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap Edge a v -> Maybe v
go EdgeSet a v
es
    foldMap1 :: forall m a. Semigroup m => (a -> m) -> Edge s a -> m
foldMap1 a -> m
f = String -> Maybe m -> m
forall a. String -> Maybe a -> a
unwrap String
"Edge.foldMap1: unexpected empty subtree" (Maybe m -> m) -> (Edge s a -> Maybe m) -> Edge s a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> m) -> Edge s a -> Maybe m
forall {b} {a} {a}. Semigroup b => (a -> b) -> Edge a a -> Maybe b
go a -> m
f
      where
        go :: (a -> b) -> Edge a a -> Maybe b
go a -> b
fs (String a
_ :~> Tree Maybe a
val EdgeSet a a
es) = (a -> b) -> Maybe a -> Maybe b
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
fs Maybe a
val Maybe b -> Maybe b -> Maybe b
forall a. Semigroup a => a -> a -> a
<> (Edge a a -> Maybe b) -> EdgeSet a a -> Maybe b
forall m a. Monoid m => (a -> m) -> Map a a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ((a -> b) -> Edge a a -> Maybe b
go a -> b
fs) EdgeSet a a
es
    foldMap1' :: forall m a. Semigroup m => (a -> m) -> Edge s a -> m
foldMap1' a -> m
f = String -> Maybe m -> m
forall a. String -> Maybe a -> a
unwrap' String
"Edge.foldMap1': unexpected empty subtree" (Maybe m -> m) -> (Edge s a -> Maybe m) -> Edge s a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> m) -> Edge s a -> Maybe m
forall {b} {a} {a}. Semigroup b => (a -> b) -> Edge a a -> Maybe b
go a -> m
f
      where
        go :: (a -> b) -> Edge a a -> Maybe b
go a -> b
fs (String a
_ :~> Tree !Maybe a
val !EdgeSet a a
es) = (a -> b) -> Maybe a -> Maybe b
forall a b. (a -> b) -> Maybe a -> Maybe b
fmap' a -> b
fs Maybe a
val Maybe b -> Maybe b -> Maybe b
forall a. Semigroup a => a -> a -> a
<> (Edge a a -> Maybe b) -> EdgeSet a a -> Maybe b
forall m a. Monoid m => (a -> m) -> Map a a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap' ((a -> b) -> Edge a a -> Maybe b
go a -> b
fs) EdgeSet a a
es
    toNonEmpty :: forall a. Edge s a -> NonEmpty a
toNonEmpty = String -> Maybe (NonEmpty a) -> NonEmpty a
forall a. String -> Maybe a -> a
unwrap String
"Edge.toNonEmpty: unexpected empty subtree" (Maybe (NonEmpty a) -> NonEmpty a)
-> (Edge s a -> Maybe (NonEmpty a)) -> Edge s a -> NonEmpty a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [a] -> Maybe (NonEmpty a)
forall a. [a] -> Maybe (NonEmpty a)
nonEmpty ([a] -> Maybe (NonEmpty a))
-> (Edge s a -> [a]) -> Edge s a -> Maybe (NonEmpty a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Edge s a -> [a]
forall a. Edge s a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList
    {-# INLINE toNonEmpty #-}
    head :: forall a. Edge s a -> a
head (String s
_ :~> RadixTreeMap s a
t) = String -> Maybe a -> a
forall a. String -> Maybe a -> a
unwrap String
"Edge.head: unexpected empty subtree" (RadixTreeMap s a -> Maybe a
forall a v. RadixTreeMap a v -> Maybe v
lookupMin RadixTreeMap s a
t)
    {-# INLINE head #-}
    last :: forall a. Edge s a -> a
last (String s
_ :~> RadixTreeMap s a
t) = String -> Maybe a -> a
forall a. String -> Maybe a -> a
unwrap String
"Edge.last: unexpected empty subtree" (RadixTreeMap s a -> Maybe a
forall a v. RadixTreeMap a v -> Maybe v
lookupMax RadixTreeMap s a
t)
    {-# INLINE last #-}

-- --------------------- --
-- Traversable instances --
-- --------------------- --

instance Functor (RadixTreeMap s) where
    {-# SPECIALIZE instance Functor (RadixTreeMap Char) #-}
    {-# SPECIALIZE instance Functor (RadixTreeMap Int) #-}
    {-# SPECIALIZE instance Functor (RadixTreeMap Word8) #-}
    fmap :: forall a b. (a -> b) -> RadixTreeMap s a -> RadixTreeMap s b
fmap a -> b
f (Tree Maybe a
val EdgeSet s a
es) = Maybe b -> EdgeSet s b -> RadixTreeMap s b
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree (a -> b
f (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe a
val) ((a -> b) -> Edge s a -> Edge s b
forall a b. (a -> b) -> Edge s a -> Edge s b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f (Edge s a -> Edge s b) -> EdgeSet s a -> EdgeSet s b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> EdgeSet s a
es)
    {-# INLINEABLE fmap #-}
    a
x <$ :: forall a b. a -> RadixTreeMap s b -> RadixTreeMap s a
<$ (Tree Maybe b
val EdgeSet s b
es) = Maybe a -> EdgeSet s a -> RadixTreeMap s a
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree (a
x a -> Maybe b -> Maybe a
forall a b. a -> Maybe b -> Maybe a
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ Maybe b
val) ((a
x <$) (Edge s b -> Edge s a) -> EdgeSet s b -> EdgeSet s a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> EdgeSet s b
es)
    {-# INLINEABLE (<$) #-}

instance Functor (Edge s) where
    {-# SPECIALIZE instance Functor (Edge Char) #-}
    {-# SPECIALIZE instance Functor (Edge Int) #-}
    {-# SPECIALIZE instance Functor (Edge Word8) #-}
    fmap :: forall a b. (a -> b) -> Edge s a -> Edge s b
fmap a -> b
f (String s
label :~> RadixTreeMap s a
t) = String s
label String s -> RadixTreeMap s b -> Edge s b
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> (a -> b
f (a -> b) -> RadixTreeMap s a -> RadixTreeMap s b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> RadixTreeMap s a
t)
    {-# INLINE fmap #-}
    a
x <$ :: forall a b. a -> Edge s b -> Edge s a
<$ (String s
label :~> RadixTreeMap s b
t) = String s
label String s -> RadixTreeMap s a -> Edge s a
forall a v. String a -> RadixTreeMap a v -> Edge a v
:~> (a
x a -> RadixTreeMap s b -> RadixTreeMap s a
forall a b. a -> RadixTreeMap s b -> RadixTreeMap s a
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ RadixTreeMap s b
t)
    {-# INLINE (<$) #-}

instance Traversable (RadixTreeMap s) where
    {-# SPECIALIZE instance Traversable (RadixTreeMap Char) #-}
    {-# SPECIALIZE instance Traversable (RadixTreeMap Int) #-}
    {-# SPECIALIZE instance Traversable (RadixTreeMap Word8) #-}
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> RadixTreeMap s a -> f (RadixTreeMap s b)
traverse a -> f b
f (Tree Maybe a
val EdgeSet s a
es) = (Maybe b -> EdgeSet s b -> RadixTreeMap s b)
-> f (Maybe b) -> f (EdgeSet s b) -> f (RadixTreeMap s b)
forall a b c. (a -> b -> c) -> f a -> f b -> f c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Maybe b -> EdgeSet s b -> RadixTreeMap s b
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree ((a -> f b) -> Maybe a -> f (Maybe b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Maybe a -> f (Maybe b)
traverse a -> f b
f Maybe a
val) ((Edge s a -> f (Edge s b)) -> EdgeSet s a -> f (EdgeSet s b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map s a -> f (Map s b)
traverse ((a -> f b) -> Edge s a -> f (Edge s b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Edge s a -> f (Edge s b)
traverse a -> f b
f) EdgeSet s a
es)
    {-# INLINEABLE traverse #-}
    sequenceA :: forall (f :: * -> *) a.
Applicative f =>
RadixTreeMap s (f a) -> f (RadixTreeMap s a)
sequenceA (Tree Maybe (f a)
val EdgeSet s (f a)
es) = (Maybe a -> EdgeSet s a -> RadixTreeMap s a)
-> f (Maybe a) -> f (EdgeSet s a) -> f (RadixTreeMap s a)
forall a b c. (a -> b -> c) -> f a -> f b -> f c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Maybe a -> EdgeSet s a -> RadixTreeMap s a
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree (Maybe (f a) -> f (Maybe a)
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
forall (f :: * -> *) a. Applicative f => Maybe (f a) -> f (Maybe a)
sequenceA Maybe (f a)
val) ((Edge s (f a) -> f (Edge s a))
-> EdgeSet s (f a) -> f (EdgeSet s a)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Map s a -> f (Map s b)
traverse Edge s (f a) -> f (Edge s a)
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
forall (f :: * -> *) a.
Applicative f =>
Edge s (f a) -> f (Edge s a)
sequenceA EdgeSet s (f a)
es)
    {-# INLINEABLE sequenceA #-}
    mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> RadixTreeMap s a -> m (RadixTreeMap s b)
mapM a -> m b
f (Tree Maybe a
val EdgeSet s a
es) = (Maybe b -> EdgeSet s b -> RadixTreeMap s b)
-> m (Maybe b) -> m (EdgeSet s b) -> m (RadixTreeMap s b)
forall a b c. (a -> b -> c) -> m a -> m b -> m c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Maybe b -> EdgeSet s b -> RadixTreeMap s b
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree ((a -> m b) -> Maybe a -> m (Maybe b)
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Maybe a -> m (Maybe b)
mapM a -> m b
f Maybe a
val) ((Edge s a -> m (Edge s b)) -> EdgeSet s a -> m (EdgeSet s b)
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Map s a -> m (Map s b)
mapM ((a -> m b) -> Edge s a -> m (Edge s b)
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Edge s a -> m (Edge s b)
mapM a -> m b
f) EdgeSet s a
es)
    {-# INLINEABLE mapM #-}
    sequence :: forall (m :: * -> *) a.
Monad m =>
RadixTreeMap s (m a) -> m (RadixTreeMap s a)
sequence (Tree Maybe (m a)
val EdgeSet s (m a)
es) = (Maybe a -> EdgeSet s a -> RadixTreeMap s a)
-> m (Maybe a) -> m (EdgeSet s a) -> m (RadixTreeMap s a)
forall a b c. (a -> b -> c) -> m a -> m b -> m c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 Maybe a -> EdgeSet s a -> RadixTreeMap s a
forall a v. Maybe v -> EdgeSet a v -> RadixTreeMap a v
Tree (Maybe (m a) -> m (Maybe a)
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
forall (m :: * -> *) a. Monad m => Maybe (m a) -> m (Maybe a)
sequence Maybe (m a)
val) ((Edge s (m a) -> m (Edge s a))
-> EdgeSet s (m a) -> m (EdgeSet s a)
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Map s a -> m (Map s b)
mapM Edge s (m a) -> m (Edge s a)
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
forall (m :: * -> *) a. Monad m => Edge s (m a) -> m (Edge s a)
sequence EdgeSet s (m a)
es)
    {-# INLINEABLE sequence #-}

instance Traversable (Edge s) where
    {-# SPECIALIZE instance Traversable (Edge Char) #-}
    {-# SPECIALIZE instance Traversable (Edge Int) #-}
    {-# SPECIALIZE instance Traversable (Edge Word8) #-}
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Edge s a -> f (Edge s b)
traverse a -> f b
f (String s
label :~> RadixTreeMap s a
t) = (String s
label :~>) (RadixTreeMap s b -> Edge s b)
-> f (RadixTreeMap s b) -> f (Edge s b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> f b) -> RadixTreeMap s a -> f (RadixTreeMap s b)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> RadixTreeMap s a -> f (RadixTreeMap s b)
traverse a -> f b
f RadixTreeMap s a
t
    {-# INLINE traverse #-}
    sequenceA :: forall (f :: * -> *) a.
Applicative f =>
Edge s (f a) -> f (Edge s a)
sequenceA (String s
label :~> RadixTreeMap s (f a)
t) = (String s
label :~>) (RadixTreeMap s a -> Edge s a)
-> f (RadixTreeMap s a) -> f (Edge s a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> RadixTreeMap s (f a) -> f (RadixTreeMap s a)
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
forall (f :: * -> *) a.
Applicative f =>
RadixTreeMap s (f a) -> f (RadixTreeMap s a)
sequenceA RadixTreeMap s (f a)
t
    {-# INLINE sequenceA #-}
    mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Edge s a -> m (Edge s b)
mapM a -> m b
f (String s
label :~> RadixTreeMap s a
t) = (String s
label :~>) (RadixTreeMap s b -> Edge s b)
-> m (RadixTreeMap s b) -> m (Edge s b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (a -> m b) -> RadixTreeMap s a -> m (RadixTreeMap s b)
forall (t :: * -> *) (m :: * -> *) a b.
(Traversable t, Monad m) =>
(a -> m b) -> t a -> m (t b)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> RadixTreeMap s a -> m (RadixTreeMap s b)
mapM a -> m b
f RadixTreeMap s a
t
    {-# INLINE mapM #-}
    sequence :: forall (m :: * -> *) a. Monad m => Edge s (m a) -> m (Edge s a)
sequence (String s
label :~> RadixTreeMap s (m a)
t) = (String s
label :~>) (RadixTreeMap s a -> Edge s a)
-> m (RadixTreeMap s a) -> m (Edge s a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> RadixTreeMap s (m a) -> m (RadixTreeMap s a)
forall (t :: * -> *) (m :: * -> *) a.
(Traversable t, Monad m) =>
t (m a) -> m (t a)
forall (m :: * -> *) a.
Monad m =>
RadixTreeMap s (m a) -> m (RadixTreeMap s a)
sequence RadixTreeMap s (m a)
t
    {-# INLINE sequence #-}