module Test.Util.InvertedMap (
    -- * InvertedMap type
    InvertedMap
    -- * Query
  , Test.Util.InvertedMap.null
    -- * Construction
  , toMap
  , unsafeInvertedMap
    -- * Conversion
  , fromMap
  , unsafeCoercion
    -- * Filter
  , spanAntitone
    -- * Min/Max
  , minViewWithKey
  ) where

import           Data.List.NonEmpty (NonEmpty)
import qualified Data.List.NonEmpty as NE
import           Data.Map.Strict (Map)
import qualified Data.Map.Strict as Map
import           Data.Type.Coercion

-- | An inverted 'Map'
--
-- INVARIANT the @k@s are all unique
--
-- INVARIANT the 'NonEmpty's are all ascending
--
newtype InvertedMap v k = UnsafeInvertedMap {forall v k. InvertedMap v k -> Map v (NonEmpty k)
getInvertedMap :: Map v (NonEmpty k)}
  deriving (Int -> InvertedMap v k -> ShowS
[InvertedMap v k] -> ShowS
InvertedMap v k -> String
(Int -> InvertedMap v k -> ShowS)
-> (InvertedMap v k -> String)
-> ([InvertedMap v k] -> ShowS)
-> Show (InvertedMap v k)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall v k. (Show v, Show k) => Int -> InvertedMap v k -> ShowS
forall v k. (Show v, Show k) => [InvertedMap v k] -> ShowS
forall v k. (Show v, Show k) => InvertedMap v k -> String
$cshowsPrec :: forall v k. (Show v, Show k) => Int -> InvertedMap v k -> ShowS
showsPrec :: Int -> InvertedMap v k -> ShowS
$cshow :: forall v k. (Show v, Show k) => InvertedMap v k -> String
show :: InvertedMap v k -> String
$cshowList :: forall v k. (Show v, Show k) => [InvertedMap v k] -> ShowS
showList :: [InvertedMap v k] -> ShowS
Show)

unsafeCoercion :: Coercion (InvertedMap v k) (Map v (NonEmpty k))
unsafeCoercion :: forall v k. Coercion (InvertedMap v k) (Map v (NonEmpty k))
unsafeCoercion = Coercion (InvertedMap v k) (Map v (NonEmpty k))
forall {k} (a :: k) (b :: k). Coercible a b => Coercion a b
Coercion

unsafeInvertedMap :: Map v (NonEmpty k) -> InvertedMap v k
unsafeInvertedMap :: forall v k. Map v (NonEmpty k) -> InvertedMap v k
unsafeInvertedMap = Map v (NonEmpty k) -> InvertedMap v k
forall v k. Map v (NonEmpty k) -> InvertedMap v k
UnsafeInvertedMap

-- | This inverts the given 'Map'
--
fromMap :: Ord v => Map k v -> InvertedMap v k
fromMap :: forall v k. Ord v => Map k v -> InvertedMap v k
fromMap Map k v
m =
    Map v (NonEmpty k) -> InvertedMap v k
forall v k. Map v (NonEmpty k) -> InvertedMap v k
UnsafeInvertedMap (Map v (NonEmpty k) -> InvertedMap v k)
-> Map v (NonEmpty k) -> InvertedMap v k
forall a b. (a -> b) -> a -> b
$ (NonEmpty k -> NonEmpty k -> NonEmpty k)
-> [(v, NonEmpty k)] -> Map v (NonEmpty k)
forall k a. Ord k => (a -> a -> a) -> [(k, a)] -> Map k a
Map.fromListWith NonEmpty k -> NonEmpty k -> NonEmpty k
forall a. Semigroup a => a -> a -> a
(<>) ([(v, NonEmpty k)] -> Map v (NonEmpty k))
-> [(v, NonEmpty k)] -> Map v (NonEmpty k)
forall a b. (a -> b) -> a -> b
$
    [ (v
v, k
k k -> [k] -> NonEmpty k
forall a. a -> [a] -> NonEmpty a
NE.:| []) | (k
k, v
v) <- Map k v -> [(k, v)]
forall k a. Map k a -> [(k, a)]
Map.toList Map k v
m ]

minViewWithKey :: InvertedMap v k -> Maybe ((v, NonEmpty k), InvertedMap v k)
minViewWithKey :: forall v k.
InvertedMap v k -> Maybe ((v, NonEmpty k), InvertedMap v k)
minViewWithKey =
    (((v, NonEmpty k), Map v (NonEmpty k))
 -> ((v, NonEmpty k), InvertedMap v k))
-> Maybe ((v, NonEmpty k), Map v (NonEmpty k))
-> Maybe ((v, NonEmpty k), InvertedMap v k)
forall a b. (a -> b) -> Maybe a -> Maybe b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Map v (NonEmpty k) -> InvertedMap v k)
-> ((v, NonEmpty k), Map v (NonEmpty k))
-> ((v, NonEmpty k), InvertedMap v k)
forall a b.
(a -> b) -> ((v, NonEmpty k), a) -> ((v, NonEmpty k), b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Map v (NonEmpty k) -> InvertedMap v k
forall v k. Map v (NonEmpty k) -> InvertedMap v k
UnsafeInvertedMap) (Maybe ((v, NonEmpty k), Map v (NonEmpty k))
 -> Maybe ((v, NonEmpty k), InvertedMap v k))
-> (InvertedMap v k -> Maybe ((v, NonEmpty k), Map v (NonEmpty k)))
-> InvertedMap v k
-> Maybe ((v, NonEmpty k), InvertedMap v k)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Map v (NonEmpty k) -> Maybe ((v, NonEmpty k), Map v (NonEmpty k))
forall k a. Map k a -> Maybe ((k, a), Map k a)
Map.minViewWithKey (Map v (NonEmpty k) -> Maybe ((v, NonEmpty k), Map v (NonEmpty k)))
-> (InvertedMap v k -> Map v (NonEmpty k))
-> InvertedMap v k
-> Maybe ((v, NonEmpty k), Map v (NonEmpty k))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. InvertedMap v k -> Map v (NonEmpty k)
forall v k. InvertedMap v k -> Map v (NonEmpty k)
getInvertedMap

null :: InvertedMap v k -> Bool
null :: forall v k. InvertedMap v k -> Bool
null = Map v (NonEmpty k) -> Bool
forall k a. Map k a -> Bool
Map.null (Map v (NonEmpty k) -> Bool)
-> (InvertedMap v k -> Map v (NonEmpty k))
-> InvertedMap v k
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. InvertedMap v k -> Map v (NonEmpty k)
forall v k. InvertedMap v k -> Map v (NonEmpty k)
getInvertedMap

spanAntitone :: (v -> Bool) -> InvertedMap v k -> (InvertedMap v k, InvertedMap v k)
spanAntitone :: forall v k.
(v -> Bool)
-> InvertedMap v k -> (InvertedMap v k, InvertedMap v k)
spanAntitone v -> Bool
f (UnsafeInvertedMap Map v (NonEmpty k)
m) = (Map v (NonEmpty k) -> InvertedMap v k
forall v k. Map v (NonEmpty k) -> InvertedMap v k
UnsafeInvertedMap Map v (NonEmpty k)
l, Map v (NonEmpty k) -> InvertedMap v k
forall v k. Map v (NonEmpty k) -> InvertedMap v k
UnsafeInvertedMap Map v (NonEmpty k)
r)
  where
    (Map v (NonEmpty k)
l, Map v (NonEmpty k)
r) = (v -> Bool)
-> Map v (NonEmpty k) -> (Map v (NonEmpty k), Map v (NonEmpty k))
forall k a. (k -> Bool) -> Map k a -> (Map k a, Map k a)
Map.spanAntitone v -> Bool
f Map v (NonEmpty k)
m

-- | This inverts the given 'InvertedMap'
--
-- Inversion is an <https://en.wikipedia.org/wiki/Involution_(mathematics)>, so
-- this returns to 'Map'.
--
toMap :: Ord k => InvertedMap v k -> Map k v
toMap :: forall k v. Ord k => InvertedMap v k -> Map k v
toMap (UnsafeInvertedMap Map v (NonEmpty k)
m) =
    [(k, v)] -> Map k v
forall k a. Ord k => [(k, a)] -> Map k a
Map.fromList ([(k, v)] -> Map k v) -> [(k, v)] -> Map k v
forall a b. (a -> b) -> a -> b
$
    [ (k
k, v
v) | (v
v, NonEmpty k
ks) <- Map v (NonEmpty k) -> [(v, NonEmpty k)]
forall k a. Map k a -> [(k, a)]
Map.toList Map v (NonEmpty k)
m, k
k <- NonEmpty k -> [k]
forall a. NonEmpty a -> [a]
NE.toList NonEmpty k
ks ]