{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE DerivingStrategies #-}

module Data.BCP47.Trie.Internal
  ( Trie(..)
  , fromList
  , fromNonEmpty
  , singleton
  , union
  , unionWith
  , unionUsing
  , mapMaybe
  , Trie2(..)
  , Subtags(..)
  , singleton2
  , lookup2
  , match2
  , union2
  , union2Using
  , fromSubtags
  , mapMaybe2
  )
  where

import Control.Applicative (liftA2, (<|>))
import Data.BCP47
import Data.BCP47.Internal.Subtags
import Data.List.NonEmpty (NonEmpty)
import qualified Data.List.NonEmpty as NE
import Data.Map (Map)
import qualified Data.Map as Map
import Data.Monoid (Last(Last, getLast))
import Test.QuickCheck.Arbitrary
import Test.QuickCheck.Modifiers (NonEmptyList(getNonEmpty))

-- | A trie mapping 'BCP47' tags to values
newtype Trie a
  = Trie { Trie a -> Map ISO639_1 (Trie2 a)
unLanguage :: Map ISO639_1 (Trie2 a)}
  deriving stock (Int -> Trie a -> ShowS
[Trie a] -> ShowS
Trie a -> String
(Int -> Trie a -> ShowS)
-> (Trie a -> String) -> ([Trie a] -> ShowS) -> Show (Trie a)
forall a. Show a => Int -> Trie a -> ShowS
forall a. Show a => [Trie a] -> ShowS
forall a. Show a => Trie a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Trie a] -> ShowS
$cshowList :: forall a. Show a => [Trie a] -> ShowS
show :: Trie a -> String
$cshow :: forall a. Show a => Trie a -> String
showsPrec :: Int -> Trie a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Trie a -> ShowS
Show, Trie a -> Trie a -> Bool
(Trie a -> Trie a -> Bool)
-> (Trie a -> Trie a -> Bool) -> Eq (Trie a)
forall a. Eq a => Trie a -> Trie a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Trie a -> Trie a -> Bool
$c/= :: forall a. Eq a => Trie a -> Trie a -> Bool
== :: Trie a -> Trie a -> Bool
$c== :: forall a. Eq a => Trie a -> Trie a -> Bool
Eq, Eq (Trie a)
Eq (Trie a)
-> (Trie a -> Trie a -> Ordering)
-> (Trie a -> Trie a -> Bool)
-> (Trie a -> Trie a -> Bool)
-> (Trie a -> Trie a -> Bool)
-> (Trie a -> Trie a -> Bool)
-> (Trie a -> Trie a -> Trie a)
-> (Trie a -> Trie a -> Trie a)
-> Ord (Trie a)
Trie a -> Trie a -> Bool
Trie a -> Trie a -> Ordering
Trie a -> Trie a -> Trie 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 (Trie a)
forall a. Ord a => Trie a -> Trie a -> Bool
forall a. Ord a => Trie a -> Trie a -> Ordering
forall a. Ord a => Trie a -> Trie a -> Trie a
min :: Trie a -> Trie a -> Trie a
$cmin :: forall a. Ord a => Trie a -> Trie a -> Trie a
max :: Trie a -> Trie a -> Trie a
$cmax :: forall a. Ord a => Trie a -> Trie a -> Trie a
>= :: Trie a -> Trie a -> Bool
$c>= :: forall a. Ord a => Trie a -> Trie a -> Bool
> :: Trie a -> Trie a -> Bool
$c> :: forall a. Ord a => Trie a -> Trie a -> Bool
<= :: Trie a -> Trie a -> Bool
$c<= :: forall a. Ord a => Trie a -> Trie a -> Bool
< :: Trie a -> Trie a -> Bool
$c< :: forall a. Ord a => Trie a -> Trie a -> Bool
compare :: Trie a -> Trie a -> Ordering
$ccompare :: forall a. Ord a => Trie a -> Trie a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (Trie a)
Ord, a -> Trie b -> Trie a
(a -> b) -> Trie a -> Trie b
(forall a b. (a -> b) -> Trie a -> Trie b)
-> (forall a b. a -> Trie b -> Trie a) -> Functor Trie
forall a b. a -> Trie b -> Trie a
forall a b. (a -> b) -> Trie a -> Trie b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Trie b -> Trie a
$c<$ :: forall a b. a -> Trie b -> Trie a
fmap :: (a -> b) -> Trie a -> Trie b
$cfmap :: forall a b. (a -> b) -> Trie a -> Trie b
Functor, Trie a -> Bool
(a -> m) -> Trie a -> m
(a -> b -> b) -> b -> Trie a -> b
(forall m. Monoid m => Trie m -> m)
-> (forall m a. Monoid m => (a -> m) -> Trie a -> m)
-> (forall m a. Monoid m => (a -> m) -> Trie a -> m)
-> (forall a b. (a -> b -> b) -> b -> Trie a -> b)
-> (forall a b. (a -> b -> b) -> b -> Trie a -> b)
-> (forall b a. (b -> a -> b) -> b -> Trie a -> b)
-> (forall b a. (b -> a -> b) -> b -> Trie a -> b)
-> (forall a. (a -> a -> a) -> Trie a -> a)
-> (forall a. (a -> a -> a) -> Trie a -> a)
-> (forall a. Trie a -> [a])
-> (forall a. Trie a -> Bool)
-> (forall a. Trie a -> Int)
-> (forall a. Eq a => a -> Trie a -> Bool)
-> (forall a. Ord a => Trie a -> a)
-> (forall a. Ord a => Trie a -> a)
-> (forall a. Num a => Trie a -> a)
-> (forall a. Num a => Trie a -> a)
-> Foldable Trie
forall a. Eq a => a -> Trie a -> Bool
forall a. Num a => Trie a -> a
forall a. Ord a => Trie a -> a
forall m. Monoid m => Trie m -> m
forall a. Trie a -> Bool
forall a. Trie a -> Int
forall a. Trie a -> [a]
forall a. (a -> a -> a) -> Trie a -> a
forall m a. Monoid m => (a -> m) -> Trie a -> m
forall b a. (b -> a -> b) -> b -> Trie a -> b
forall a b. (a -> b -> b) -> b -> Trie a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: Trie a -> a
$cproduct :: forall a. Num a => Trie a -> a
sum :: Trie a -> a
$csum :: forall a. Num a => Trie a -> a
minimum :: Trie a -> a
$cminimum :: forall a. Ord a => Trie a -> a
maximum :: Trie a -> a
$cmaximum :: forall a. Ord a => Trie a -> a
elem :: a -> Trie a -> Bool
$celem :: forall a. Eq a => a -> Trie a -> Bool
length :: Trie a -> Int
$clength :: forall a. Trie a -> Int
null :: Trie a -> Bool
$cnull :: forall a. Trie a -> Bool
toList :: Trie a -> [a]
$ctoList :: forall a. Trie a -> [a]
foldl1 :: (a -> a -> a) -> Trie a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Trie a -> a
foldr1 :: (a -> a -> a) -> Trie a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Trie a -> a
foldl' :: (b -> a -> b) -> b -> Trie a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Trie a -> b
foldl :: (b -> a -> b) -> b -> Trie a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Trie a -> b
foldr' :: (a -> b -> b) -> b -> Trie a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Trie a -> b
foldr :: (a -> b -> b) -> b -> Trie a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Trie a -> b
foldMap' :: (a -> m) -> Trie a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Trie a -> m
foldMap :: (a -> m) -> Trie a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Trie a -> m
fold :: Trie m -> m
$cfold :: forall m. Monoid m => Trie m -> m
Foldable, Functor Trie
Foldable Trie
Functor Trie
-> Foldable Trie
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Trie a -> f (Trie b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Trie (f a) -> f (Trie a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Trie a -> m (Trie b))
-> (forall (m :: * -> *) a. Monad m => Trie (m a) -> m (Trie a))
-> Traversable Trie
(a -> f b) -> Trie a -> f (Trie b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => Trie (m a) -> m (Trie a)
forall (f :: * -> *) a. Applicative f => Trie (f a) -> f (Trie a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Trie a -> m (Trie b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Trie a -> f (Trie b)
sequence :: Trie (m a) -> m (Trie a)
$csequence :: forall (m :: * -> *) a. Monad m => Trie (m a) -> m (Trie a)
mapM :: (a -> m b) -> Trie a -> m (Trie b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Trie a -> m (Trie b)
sequenceA :: Trie (f a) -> f (Trie a)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Trie (f a) -> f (Trie a)
traverse :: (a -> f b) -> Trie a -> f (Trie b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Trie a -> f (Trie b)
$cp2Traversable :: Foldable Trie
$cp1Traversable :: Functor Trie
Traversable)

instance Semigroup a => Semigroup (Trie a) where
  Trie a
x <> :: Trie a -> Trie a -> Trie a
<> Trie a
y = (Maybe a -> Maybe a -> Maybe a) -> Trie a -> Trie a -> Trie a
forall a.
(Maybe a -> Maybe a -> Maybe a) -> Trie a -> Trie a -> Trie a
unionUsing ((a -> a -> a) -> Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 a -> a -> a
forall a. Semigroup a => a -> a -> a
(<>)) Trie a
x Trie a
y

instance Arbitrary a => Arbitrary (Trie a) where
  arbitrary :: Gen (Trie a)
arbitrary = NonEmpty (BCP47, a) -> Trie a
forall a. NonEmpty (BCP47, a) -> Trie a
fromNonEmpty (NonEmpty (BCP47, a) -> Trie a)
-> (NonEmptyList (BCP47, a) -> NonEmpty (BCP47, a))
-> NonEmptyList (BCP47, a)
-> Trie a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(BCP47, a)] -> NonEmpty (BCP47, a)
forall a. [a] -> NonEmpty a
NE.fromList ([(BCP47, a)] -> NonEmpty (BCP47, a))
-> (NonEmptyList (BCP47, a) -> [(BCP47, a)])
-> NonEmptyList (BCP47, a)
-> NonEmpty (BCP47, a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmptyList (BCP47, a) -> [(BCP47, a)]
forall a. NonEmptyList a -> [a]
getNonEmpty (NonEmptyList (BCP47, a) -> Trie a)
-> Gen (NonEmptyList (BCP47, a)) -> Gen (Trie a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Gen (NonEmptyList (BCP47, a))
forall a. Arbitrary a => Gen a
arbitrary

-- | Construct a 'Trie' from a list of tag/value pairs.
fromList :: [(BCP47, a)] -> Maybe (Trie a)
fromList :: [(BCP47, a)] -> Maybe (Trie a)
fromList = (NonEmpty (BCP47, a) -> Trie a)
-> Maybe (NonEmpty (BCP47, a)) -> Maybe (Trie a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap NonEmpty (BCP47, a) -> Trie a
forall a. NonEmpty (BCP47, a) -> Trie a
fromNonEmpty (Maybe (NonEmpty (BCP47, a)) -> Maybe (Trie a))
-> ([(BCP47, a)] -> Maybe (NonEmpty (BCP47, a)))
-> [(BCP47, a)]
-> Maybe (Trie a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(BCP47, a)] -> Maybe (NonEmpty (BCP47, a))
forall a. [a] -> Maybe (NonEmpty a)
NE.nonEmpty

-- | Construct a 'Trie' from a non empty list of tag/value pairs.
fromNonEmpty :: NonEmpty (BCP47, a) -> Trie a
fromNonEmpty :: NonEmpty (BCP47, a) -> Trie a
fromNonEmpty = ((BCP47, a) -> Trie a -> Trie a)
-> Trie a -> NonEmpty (BCP47, a) -> Trie a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Trie a -> Trie a -> Trie a
forall a. Trie a -> Trie a -> Trie a
union (Trie a -> Trie a -> Trie a)
-> ((BCP47, a) -> Trie a) -> (BCP47, a) -> Trie a -> Trie a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (BCP47 -> a -> Trie a) -> (BCP47, a) -> Trie a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry BCP47 -> a -> Trie a
forall a. BCP47 -> a -> Trie a
singleton) (Map ISO639_1 (Trie2 a) -> Trie a
forall a. Map ISO639_1 (Trie2 a) -> Trie a
Trie Map ISO639_1 (Trie2 a)
forall a. Monoid a => a
mempty)

-- | Construct a 'Trie' from a single tag/value pair.
singleton :: BCP47 -> a -> Trie a
singleton :: BCP47 -> a -> Trie a
singleton BCP47
tag = Map ISO639_1 (Trie2 a) -> Trie a
forall a. Map ISO639_1 (Trie2 a) -> Trie a
Trie (Map ISO639_1 (Trie2 a) -> Trie a)
-> (a -> Map ISO639_1 (Trie2 a)) -> a -> Trie a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ISO639_1 -> Trie2 a -> Map ISO639_1 (Trie2 a)
forall k a. k -> a -> Map k a
Map.singleton (BCP47 -> ISO639_1
language BCP47
tag) (Trie2 a -> Map ISO639_1 (Trie2 a))
-> (a -> Trie2 a) -> a -> Map ISO639_1 (Trie2 a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. BCP47 -> a -> Trie2 a
forall a. BCP47 -> a -> Trie2 a
singleton2 BCP47
tag

-- | A left-biased union of two 'Trie' structures. The left value is prefered
-- when duplicate tags are found.
union :: Trie a -> Trie a -> Trie a
union :: Trie a -> Trie a -> Trie a
union = (Maybe a -> Maybe a -> Maybe a) -> Trie a -> Trie a -> Trie a
forall a.
(Maybe a -> Maybe a -> Maybe a) -> Trie a -> Trie a -> Trie a
unionUsing Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>)

-- | 'union' with a combining function.
unionWith :: (a -> a -> a) -> Trie a -> Trie a -> Trie a
unionWith :: (a -> a -> a) -> Trie a -> Trie a -> Trie a
unionWith a -> a -> a
f = (Maybe a -> Maybe a -> Maybe a) -> Trie a -> Trie a -> Trie a
forall a.
(Maybe a -> Maybe a -> Maybe a) -> Trie a -> Trie a -> Trie a
unionUsing ((a -> a -> a) -> Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 a -> a -> a
f)

unionUsing :: (Maybe a -> Maybe a -> Maybe a) -> Trie a -> Trie a -> Trie a
unionUsing :: (Maybe a -> Maybe a -> Maybe a) -> Trie a -> Trie a -> Trie a
unionUsing Maybe a -> Maybe a -> Maybe a
f (Trie Map ISO639_1 (Trie2 a)
x) (Trie Map ISO639_1 (Trie2 a)
y) = Map ISO639_1 (Trie2 a) -> Trie a
forall a. Map ISO639_1 (Trie2 a) -> Trie a
Trie (Map ISO639_1 (Trie2 a) -> Trie a)
-> Map ISO639_1 (Trie2 a) -> Trie a
forall a b. (a -> b) -> a -> b
$ (Trie2 a -> Trie2 a -> Trie2 a)
-> Map ISO639_1 (Trie2 a)
-> Map ISO639_1 (Trie2 a)
-> Map ISO639_1 (Trie2 a)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith ((Maybe a -> Maybe a -> Maybe a) -> Trie2 a -> Trie2 a -> Trie2 a
forall a.
(Maybe a -> Maybe a -> Maybe a) -> Trie2 a -> Trie2 a -> Trie2 a
union2Using Maybe a -> Maybe a -> Maybe a
f) Map ISO639_1 (Trie2 a)
x Map ISO639_1 (Trie2 a)
y

nullToMaybe :: Map k a -> Maybe (Map k a)
nullToMaybe :: Map k a -> Maybe (Map k a)
nullToMaybe Map k a
m = if Map k a -> Bool
forall k a. Map k a -> Bool
Map.null Map k a
m then Maybe (Map k a)
forall a. Maybe a
Nothing else Map k a -> Maybe (Map k a)
forall a. a -> Maybe a
Just Map k a
m

-- Like `Map.mapMaybe` but returns a `Maybe` because `Trie` should be non-empty
mapMaybe :: (a -> Maybe b) -> Trie a -> Maybe (Trie b)
mapMaybe :: (a -> Maybe b) -> Trie a -> Maybe (Trie b)
mapMaybe a -> Maybe b
f (Trie Map ISO639_1 (Trie2 a)
x) = Map ISO639_1 (Trie2 b) -> Trie b
forall a. Map ISO639_1 (Trie2 a) -> Trie a
Trie (Map ISO639_1 (Trie2 b) -> Trie b)
-> Maybe (Map ISO639_1 (Trie2 b)) -> Maybe (Trie b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Map ISO639_1 (Trie2 b) -> Maybe (Map ISO639_1 (Trie2 b))
forall k a. Map k a -> Maybe (Map k a)
nullToMaybe ((Trie2 a -> Maybe (Trie2 b))
-> Map ISO639_1 (Trie2 a) -> Map ISO639_1 (Trie2 b)
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe ((a -> Maybe b) -> Trie2 a -> Maybe (Trie2 b)
forall a b. (a -> Maybe b) -> Trie2 a -> Maybe (Trie2 b)
mapMaybe2 a -> Maybe b
f) Map ISO639_1 (Trie2 a)
x)

data Trie2 a = Trie2 (Maybe a) (Map Subtags (Trie2 a))
  deriving stock (Int -> Trie2 a -> ShowS
[Trie2 a] -> ShowS
Trie2 a -> String
(Int -> Trie2 a -> ShowS)
-> (Trie2 a -> String) -> ([Trie2 a] -> ShowS) -> Show (Trie2 a)
forall a. Show a => Int -> Trie2 a -> ShowS
forall a. Show a => [Trie2 a] -> ShowS
forall a. Show a => Trie2 a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Trie2 a] -> ShowS
$cshowList :: forall a. Show a => [Trie2 a] -> ShowS
show :: Trie2 a -> String
$cshow :: forall a. Show a => Trie2 a -> String
showsPrec :: Int -> Trie2 a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> Trie2 a -> ShowS
Show, Trie2 a -> Trie2 a -> Bool
(Trie2 a -> Trie2 a -> Bool)
-> (Trie2 a -> Trie2 a -> Bool) -> Eq (Trie2 a)
forall a. Eq a => Trie2 a -> Trie2 a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Trie2 a -> Trie2 a -> Bool
$c/= :: forall a. Eq a => Trie2 a -> Trie2 a -> Bool
== :: Trie2 a -> Trie2 a -> Bool
$c== :: forall a. Eq a => Trie2 a -> Trie2 a -> Bool
Eq, Eq (Trie2 a)
Eq (Trie2 a)
-> (Trie2 a -> Trie2 a -> Ordering)
-> (Trie2 a -> Trie2 a -> Bool)
-> (Trie2 a -> Trie2 a -> Bool)
-> (Trie2 a -> Trie2 a -> Bool)
-> (Trie2 a -> Trie2 a -> Bool)
-> (Trie2 a -> Trie2 a -> Trie2 a)
-> (Trie2 a -> Trie2 a -> Trie2 a)
-> Ord (Trie2 a)
Trie2 a -> Trie2 a -> Bool
Trie2 a -> Trie2 a -> Ordering
Trie2 a -> Trie2 a -> Trie2 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 (Trie2 a)
forall a. Ord a => Trie2 a -> Trie2 a -> Bool
forall a. Ord a => Trie2 a -> Trie2 a -> Ordering
forall a. Ord a => Trie2 a -> Trie2 a -> Trie2 a
min :: Trie2 a -> Trie2 a -> Trie2 a
$cmin :: forall a. Ord a => Trie2 a -> Trie2 a -> Trie2 a
max :: Trie2 a -> Trie2 a -> Trie2 a
$cmax :: forall a. Ord a => Trie2 a -> Trie2 a -> Trie2 a
>= :: Trie2 a -> Trie2 a -> Bool
$c>= :: forall a. Ord a => Trie2 a -> Trie2 a -> Bool
> :: Trie2 a -> Trie2 a -> Bool
$c> :: forall a. Ord a => Trie2 a -> Trie2 a -> Bool
<= :: Trie2 a -> Trie2 a -> Bool
$c<= :: forall a. Ord a => Trie2 a -> Trie2 a -> Bool
< :: Trie2 a -> Trie2 a -> Bool
$c< :: forall a. Ord a => Trie2 a -> Trie2 a -> Bool
compare :: Trie2 a -> Trie2 a -> Ordering
$ccompare :: forall a. Ord a => Trie2 a -> Trie2 a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (Trie2 a)
Ord, a -> Trie2 b -> Trie2 a
(a -> b) -> Trie2 a -> Trie2 b
(forall a b. (a -> b) -> Trie2 a -> Trie2 b)
-> (forall a b. a -> Trie2 b -> Trie2 a) -> Functor Trie2
forall a b. a -> Trie2 b -> Trie2 a
forall a b. (a -> b) -> Trie2 a -> Trie2 b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Trie2 b -> Trie2 a
$c<$ :: forall a b. a -> Trie2 b -> Trie2 a
fmap :: (a -> b) -> Trie2 a -> Trie2 b
$cfmap :: forall a b. (a -> b) -> Trie2 a -> Trie2 b
Functor, Trie2 a -> Bool
(a -> m) -> Trie2 a -> m
(a -> b -> b) -> b -> Trie2 a -> b
(forall m. Monoid m => Trie2 m -> m)
-> (forall m a. Monoid m => (a -> m) -> Trie2 a -> m)
-> (forall m a. Monoid m => (a -> m) -> Trie2 a -> m)
-> (forall a b. (a -> b -> b) -> b -> Trie2 a -> b)
-> (forall a b. (a -> b -> b) -> b -> Trie2 a -> b)
-> (forall b a. (b -> a -> b) -> b -> Trie2 a -> b)
-> (forall b a. (b -> a -> b) -> b -> Trie2 a -> b)
-> (forall a. (a -> a -> a) -> Trie2 a -> a)
-> (forall a. (a -> a -> a) -> Trie2 a -> a)
-> (forall a. Trie2 a -> [a])
-> (forall a. Trie2 a -> Bool)
-> (forall a. Trie2 a -> Int)
-> (forall a. Eq a => a -> Trie2 a -> Bool)
-> (forall a. Ord a => Trie2 a -> a)
-> (forall a. Ord a => Trie2 a -> a)
-> (forall a. Num a => Trie2 a -> a)
-> (forall a. Num a => Trie2 a -> a)
-> Foldable Trie2
forall a. Eq a => a -> Trie2 a -> Bool
forall a. Num a => Trie2 a -> a
forall a. Ord a => Trie2 a -> a
forall m. Monoid m => Trie2 m -> m
forall a. Trie2 a -> Bool
forall a. Trie2 a -> Int
forall a. Trie2 a -> [a]
forall a. (a -> a -> a) -> Trie2 a -> a
forall m a. Monoid m => (a -> m) -> Trie2 a -> m
forall b a. (b -> a -> b) -> b -> Trie2 a -> b
forall a b. (a -> b -> b) -> b -> Trie2 a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: Trie2 a -> a
$cproduct :: forall a. Num a => Trie2 a -> a
sum :: Trie2 a -> a
$csum :: forall a. Num a => Trie2 a -> a
minimum :: Trie2 a -> a
$cminimum :: forall a. Ord a => Trie2 a -> a
maximum :: Trie2 a -> a
$cmaximum :: forall a. Ord a => Trie2 a -> a
elem :: a -> Trie2 a -> Bool
$celem :: forall a. Eq a => a -> Trie2 a -> Bool
length :: Trie2 a -> Int
$clength :: forall a. Trie2 a -> Int
null :: Trie2 a -> Bool
$cnull :: forall a. Trie2 a -> Bool
toList :: Trie2 a -> [a]
$ctoList :: forall a. Trie2 a -> [a]
foldl1 :: (a -> a -> a) -> Trie2 a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> Trie2 a -> a
foldr1 :: (a -> a -> a) -> Trie2 a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> Trie2 a -> a
foldl' :: (b -> a -> b) -> b -> Trie2 a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> Trie2 a -> b
foldl :: (b -> a -> b) -> b -> Trie2 a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> Trie2 a -> b
foldr' :: (a -> b -> b) -> b -> Trie2 a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> Trie2 a -> b
foldr :: (a -> b -> b) -> b -> Trie2 a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> Trie2 a -> b
foldMap' :: (a -> m) -> Trie2 a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> Trie2 a -> m
foldMap :: (a -> m) -> Trie2 a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> Trie2 a -> m
fold :: Trie2 m -> m
$cfold :: forall m. Monoid m => Trie2 m -> m
Foldable, Functor Trie2
Foldable Trie2
Functor Trie2
-> Foldable Trie2
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Trie2 a -> f (Trie2 b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Trie2 (f a) -> f (Trie2 a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Trie2 a -> m (Trie2 b))
-> (forall (m :: * -> *) a. Monad m => Trie2 (m a) -> m (Trie2 a))
-> Traversable Trie2
(a -> f b) -> Trie2 a -> f (Trie2 b)
forall (t :: * -> *).
Functor t
-> Foldable t
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a. Monad m => Trie2 (m a) -> m (Trie2 a)
forall (f :: * -> *) a. Applicative f => Trie2 (f a) -> f (Trie2 a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Trie2 a -> m (Trie2 b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Trie2 a -> f (Trie2 b)
sequence :: Trie2 (m a) -> m (Trie2 a)
$csequence :: forall (m :: * -> *) a. Monad m => Trie2 (m a) -> m (Trie2 a)
mapM :: (a -> m b) -> Trie2 a -> m (Trie2 b)
$cmapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Trie2 a -> m (Trie2 b)
sequenceA :: Trie2 (f a) -> f (Trie2 a)
$csequenceA :: forall (f :: * -> *) a. Applicative f => Trie2 (f a) -> f (Trie2 a)
traverse :: (a -> f b) -> Trie2 a -> f (Trie2 b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Trie2 a -> f (Trie2 b)
$cp2Traversable :: Foldable Trie2
$cp1Traversable :: Functor Trie2
Traversable)

instance Semigroup a => Semigroup (Trie2 a) where
  Trie2 a
x <> :: Trie2 a -> Trie2 a -> Trie2 a
<> Trie2 a
y = (Maybe a -> Maybe a -> Maybe a) -> Trie2 a -> Trie2 a -> Trie2 a
forall a.
(Maybe a -> Maybe a -> Maybe a) -> Trie2 a -> Trie2 a -> Trie2 a
union2Using ((a -> a -> a) -> Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 a -> a -> a
forall a. Semigroup a => a -> a -> a
(<>)) Trie2 a
x Trie2 a
y

instance Monoid a => Monoid (Trie2 a) where
  mempty :: Trie2 a
mempty = Maybe a -> Map Subtags (Trie2 a) -> Trie2 a
forall a. Maybe a -> Map Subtags (Trie2 a) -> Trie2 a
Trie2 Maybe a
forall a. Monoid a => a
mempty Map Subtags (Trie2 a)
forall a. Monoid a => a
mempty

mapMaybe2 :: (a -> Maybe b) -> Trie2 a -> Maybe (Trie2 b)
mapMaybe2 :: (a -> Maybe b) -> Trie2 a -> Maybe (Trie2 b)
mapMaybe2 a -> Maybe b
f = Trie2 a -> Maybe (Trie2 b)
go
 where
  go :: Trie2 a -> Maybe (Trie2 b)
go (Trie2 Maybe a
x Map Subtags (Trie2 a)
xs) = case (a -> Maybe b
f (a -> Maybe b) -> Maybe a -> Maybe b
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Maybe a
x, Map Subtags (Trie2 b) -> Maybe (Map Subtags (Trie2 b))
forall k a. Map k a -> Maybe (Map k a)
nullToMaybe (Map Subtags (Trie2 b) -> Maybe (Map Subtags (Trie2 b)))
-> Map Subtags (Trie2 b) -> Maybe (Map Subtags (Trie2 b))
forall a b. (a -> b) -> a -> b
$ (Trie2 a -> Maybe (Trie2 b))
-> Map Subtags (Trie2 a) -> Map Subtags (Trie2 b)
forall a b k. (a -> Maybe b) -> Map k a -> Map k b
Map.mapMaybe Trie2 a -> Maybe (Trie2 b)
go Map Subtags (Trie2 a)
xs) of
    (Maybe b
Nothing, Maybe (Map Subtags (Trie2 b))
Nothing) -> Maybe (Trie2 b)
forall a. Maybe a
Nothing
    (Just b
x', Maybe (Map Subtags (Trie2 b))
Nothing) -> Trie2 b -> Maybe (Trie2 b)
forall a. a -> Maybe a
Just (Trie2 b -> Maybe (Trie2 b)) -> Trie2 b -> Maybe (Trie2 b)
forall a b. (a -> b) -> a -> b
$ Maybe b -> Map Subtags (Trie2 b) -> Trie2 b
forall a. Maybe a -> Map Subtags (Trie2 a) -> Trie2 a
Trie2 (b -> Maybe b
forall a. a -> Maybe a
Just b
x') Map Subtags (Trie2 b)
forall a. Monoid a => a
mempty
    (Maybe b
x', Just Map Subtags (Trie2 b)
xs') -> Trie2 b -> Maybe (Trie2 b)
forall a. a -> Maybe a
Just (Trie2 b -> Maybe (Trie2 b)) -> Trie2 b -> Maybe (Trie2 b)
forall a b. (a -> b) -> a -> b
$ Maybe b -> Map Subtags (Trie2 b) -> Trie2 b
forall a. Maybe a -> Map Subtags (Trie2 a) -> Trie2 a
Trie2 Maybe b
x' Map Subtags (Trie2 b)
xs'

singleton2 :: BCP47 -> a -> Trie2 a
singleton2 :: BCP47 -> a -> Trie2 a
singleton2 BCP47
tag = [Subtags] -> a -> Trie2 a
forall a. [Subtags] -> a -> Trie2 a
fromSubtags (BCP47 -> [Subtags]
toSubtags BCP47
tag)

fromSubtags :: [Subtags] -> a -> Trie2 a
fromSubtags :: [Subtags] -> a -> Trie2 a
fromSubtags =
  (Subtags -> (a -> Trie2 a) -> a -> Trie2 a)
-> (a -> Trie2 a) -> [Subtags] -> a -> Trie2 a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\Subtags
path a -> Trie2 a
leaf -> Maybe a -> Map Subtags (Trie2 a) -> Trie2 a
forall a. Maybe a -> Map Subtags (Trie2 a) -> Trie2 a
Trie2 Maybe a
forall a. Maybe a
Nothing (Map Subtags (Trie2 a) -> Trie2 a)
-> (a -> Map Subtags (Trie2 a)) -> a -> Trie2 a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Subtags -> Trie2 a -> Map Subtags (Trie2 a)
forall k a. k -> a -> Map k a
Map.singleton Subtags
path (Trie2 a -> Map Subtags (Trie2 a))
-> (a -> Trie2 a) -> a -> Map Subtags (Trie2 a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Trie2 a
leaf) a -> Trie2 a
forall a. a -> Trie2 a
toVal

toVal :: a -> Trie2 a
toVal :: a -> Trie2 a
toVal a
x = Maybe a -> Map Subtags (Trie2 a) -> Trie2 a
forall a. Maybe a -> Map Subtags (Trie2 a) -> Trie2 a
Trie2 (a -> Maybe a
forall a. a -> Maybe a
Just a
x) Map Subtags (Trie2 a)
forall a. Monoid a => a
mempty

lookup2 :: BCP47 -> Trie2 a -> Maybe a
lookup2 :: BCP47 -> Trie2 a -> Maybe a
lookup2 BCP47
tag = Last a -> Maybe a
forall a. Last a -> Maybe a
getLast (Last a -> Maybe a) -> (Trie2 a -> Last a) -> Trie2 a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Subtags] -> Trie2 a -> Last a
forall a. [Subtags] -> Trie2 a -> Last a
go (BCP47 -> [Subtags]
toSubtags BCP47
tag)
 where
  go :: [Subtags] -> Trie2 a -> Last a
  go :: [Subtags] -> Trie2 a -> Last a
go [] (Trie2 Maybe a
mVal Map Subtags (Trie2 a)
_) = Maybe a -> Last a
forall a. Maybe a -> Last a
Last Maybe a
mVal
  go (Subtags
p : [Subtags]
ps) (Trie2 Maybe a
mVal Map Subtags (Trie2 a)
children) =
    Maybe a -> Last a
forall a. Maybe a -> Last a
Last Maybe a
mVal Last a -> Last a -> Last a
forall a. Semigroup a => a -> a -> a
<> ([Subtags] -> Trie2 a -> Last a
forall a. [Subtags] -> Trie2 a -> Last a
go [Subtags]
ps (Trie2 a -> Last a) -> Last (Trie2 a) -> Last a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Maybe (Trie2 a) -> Last (Trie2 a)
forall a. Maybe a -> Last a
Last (Subtags -> Map Subtags (Trie2 a) -> Maybe (Trie2 a)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup Subtags
p Map Subtags (Trie2 a)
children))

match2 :: BCP47 -> Trie2 a -> Maybe a
match2 :: BCP47 -> Trie2 a -> Maybe a
match2 BCP47
tag = [Subtags] -> Trie2 a -> Maybe a
forall a. [Subtags] -> Trie2 a -> Maybe a
go (BCP47 -> [Subtags]
toSubtags BCP47
tag)
 where
  go :: [Subtags] -> Trie2 a -> Maybe a
  go :: [Subtags] -> Trie2 a -> Maybe a
go [] (Trie2 Maybe a
mVal Map Subtags (Trie2 a)
_) = Maybe a
mVal
  go (Subtags
p : [Subtags]
ps) (Trie2 Maybe a
_ Map Subtags (Trie2 a)
children) = [Subtags] -> Trie2 a -> Maybe a
forall a. [Subtags] -> Trie2 a -> Maybe a
go [Subtags]
ps (Trie2 a -> Maybe a) -> Maybe (Trie2 a) -> Maybe a
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Subtags -> Map Subtags (Trie2 a) -> Maybe (Trie2 a)
forall k a. Ord k => k -> Map k a -> Maybe a
Map.lookup Subtags
p Map Subtags (Trie2 a)
children

union2 :: Trie2 a -> Trie2 a -> Trie2 a
union2 :: Trie2 a -> Trie2 a -> Trie2 a
union2 = (Maybe a -> Maybe a -> Maybe a) -> Trie2 a -> Trie2 a -> Trie2 a
forall a.
(Maybe a -> Maybe a -> Maybe a) -> Trie2 a -> Trie2 a -> Trie2 a
union2Using Maybe a -> Maybe a -> Maybe a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>)

union2Using :: (Maybe a -> Maybe a -> Maybe a) -> Trie2 a -> Trie2 a -> Trie2 a
union2Using :: (Maybe a -> Maybe a -> Maybe a) -> Trie2 a -> Trie2 a -> Trie2 a
union2Using Maybe a -> Maybe a -> Maybe a
f (Trie2 Maybe a
x Map Subtags (Trie2 a)
xs) (Trie2 Maybe a
y Map Subtags (Trie2 a)
ys) =
  Maybe a -> Map Subtags (Trie2 a) -> Trie2 a
forall a. Maybe a -> Map Subtags (Trie2 a) -> Trie2 a
Trie2 (Maybe a -> Maybe a -> Maybe a
f Maybe a
x Maybe a
y) ((Trie2 a -> Trie2 a -> Trie2 a)
-> Map Subtags (Trie2 a)
-> Map Subtags (Trie2 a)
-> Map Subtags (Trie2 a)
forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
Map.unionWith ((Maybe a -> Maybe a -> Maybe a) -> Trie2 a -> Trie2 a -> Trie2 a
forall a.
(Maybe a -> Maybe a -> Maybe a) -> Trie2 a -> Trie2 a -> Trie2 a
union2Using Maybe a -> Maybe a -> Maybe a
f) Map Subtags (Trie2 a)
xs Map Subtags (Trie2 a)
ys)