{-# LANGUAGE CPP #-}
{-# LANGUAGE DeriveTraversable #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE NamedFieldPuns #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE TemplateHaskell #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE NoImplicitPrelude #-}

module Data.Mergeable.OrdMap
  ( OrdMap (..),
  )
where

import Control.Monad.Except (MonadError)
import qualified Data.HashMap.Lazy as HM
import Data.Mergeable.Internal.Merge (Merge (..))
import Data.Mergeable.Internal.NameCollision (NameCollision (..))
import Data.Mergeable.Internal.Resolution
  ( Indexed (..),
    indexed,
  )
import Data.Mergeable.IsMap
  ( FromList (..),
    IsMap (..),
  )
import Data.Morpheus.Ext.Empty (Empty (..))
import Language.Haskell.TH.Syntax (Lift (..))
import Relude hiding (fromList)

-- OrdMap
newtype OrdMap k a = OrdMap
  { OrdMap k a -> HashMap k (Indexed k a)
mapEntries :: HashMap k (Indexed k a)
  }
  deriving
    ( Int -> OrdMap k a -> ShowS
[OrdMap k a] -> ShowS
OrdMap k a -> String
(Int -> OrdMap k a -> ShowS)
-> (OrdMap k a -> String)
-> ([OrdMap k a] -> ShowS)
-> Show (OrdMap k a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall k a. (Show k, Show a) => Int -> OrdMap k a -> ShowS
forall k a. (Show k, Show a) => [OrdMap k a] -> ShowS
forall k a. (Show k, Show a) => OrdMap k a -> String
showList :: [OrdMap k a] -> ShowS
$cshowList :: forall k a. (Show k, Show a) => [OrdMap k a] -> ShowS
show :: OrdMap k a -> String
$cshow :: forall k a. (Show k, Show a) => OrdMap k a -> String
showsPrec :: Int -> OrdMap k a -> ShowS
$cshowsPrec :: forall k a. (Show k, Show a) => Int -> OrdMap k a -> ShowS
Show,
      OrdMap k a -> OrdMap k a -> Bool
(OrdMap k a -> OrdMap k a -> Bool)
-> (OrdMap k a -> OrdMap k a -> Bool) -> Eq (OrdMap k a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall k a. (Eq k, Eq a) => OrdMap k a -> OrdMap k a -> Bool
/= :: OrdMap k a -> OrdMap k a -> Bool
$c/= :: forall k a. (Eq k, Eq a) => OrdMap k a -> OrdMap k a -> Bool
== :: OrdMap k a -> OrdMap k a -> Bool
$c== :: forall k a. (Eq k, Eq a) => OrdMap k a -> OrdMap k a -> Bool
Eq,
      a -> OrdMap k b -> OrdMap k a
(a -> b) -> OrdMap k a -> OrdMap k b
(forall a b. (a -> b) -> OrdMap k a -> OrdMap k b)
-> (forall a b. a -> OrdMap k b -> OrdMap k a)
-> Functor (OrdMap k)
forall a b. a -> OrdMap k b -> OrdMap k a
forall a b. (a -> b) -> OrdMap k a -> OrdMap k b
forall k a b. a -> OrdMap k b -> OrdMap k a
forall k a b. (a -> b) -> OrdMap k a -> OrdMap k b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> OrdMap k b -> OrdMap k a
$c<$ :: forall k a b. a -> OrdMap k b -> OrdMap k a
fmap :: (a -> b) -> OrdMap k a -> OrdMap k b
$cfmap :: forall k a b. (a -> b) -> OrdMap k a -> OrdMap k b
Functor,
      Functor (OrdMap k)
Foldable (OrdMap k)
Functor (OrdMap k)
-> Foldable (OrdMap k)
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> OrdMap k a -> f (OrdMap k b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    OrdMap k (f a) -> f (OrdMap k a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> OrdMap k a -> m (OrdMap k b))
-> (forall (m :: * -> *) a.
    Monad m =>
    OrdMap k (m a) -> m (OrdMap k a))
-> Traversable (OrdMap k)
(a -> f b) -> OrdMap k a -> f (OrdMap k b)
forall k. (Eq k, Hashable k) => Functor (OrdMap k)
forall k. (Eq k, Hashable k) => Foldable (OrdMap k)
forall k (m :: * -> *) a.
(Eq k, Hashable k, Monad m) =>
OrdMap k (m a) -> m (OrdMap k a)
forall k (f :: * -> *) a.
(Eq k, Hashable k, Applicative f) =>
OrdMap k (f a) -> f (OrdMap k a)
forall k (m :: * -> *) a b.
(Eq k, Hashable k, Monad m) =>
(a -> m b) -> OrdMap k a -> m (OrdMap k b)
forall k (f :: * -> *) a b.
(Eq k, Hashable k, Applicative f) =>
(a -> f b) -> OrdMap k a -> f (OrdMap k 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 => OrdMap k (m a) -> m (OrdMap k a)
forall (f :: * -> *) a.
Applicative f =>
OrdMap k (f a) -> f (OrdMap k a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> OrdMap k a -> m (OrdMap k b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> OrdMap k a -> f (OrdMap k b)
sequence :: OrdMap k (m a) -> m (OrdMap k a)
$csequence :: forall k (m :: * -> *) a.
(Eq k, Hashable k, Monad m) =>
OrdMap k (m a) -> m (OrdMap k a)
mapM :: (a -> m b) -> OrdMap k a -> m (OrdMap k b)
$cmapM :: forall k (m :: * -> *) a b.
(Eq k, Hashable k, Monad m) =>
(a -> m b) -> OrdMap k a -> m (OrdMap k b)
sequenceA :: OrdMap k (f a) -> f (OrdMap k a)
$csequenceA :: forall k (f :: * -> *) a.
(Eq k, Hashable k, Applicative f) =>
OrdMap k (f a) -> f (OrdMap k a)
traverse :: (a -> f b) -> OrdMap k a -> f (OrdMap k b)
$ctraverse :: forall k (f :: * -> *) a b.
(Eq k, Hashable k, Applicative f) =>
(a -> f b) -> OrdMap k a -> f (OrdMap k b)
$cp2Traversable :: forall k. (Eq k, Hashable k) => Foldable (OrdMap k)
$cp1Traversable :: forall k. (Eq k, Hashable k) => Functor (OrdMap k)
Traversable,
      OrdMap k a
OrdMap k a -> Empty (OrdMap k a)
forall coll. coll -> Empty coll
forall k a. OrdMap k a
empty :: OrdMap k a
$cempty :: forall k a. OrdMap k a
Empty
    )

instance (Lift a, Lift k, Eq k, Hashable k) => Lift (OrdMap k a) where
  lift :: OrdMap k a -> Q Exp
lift (OrdMap HashMap k (Indexed k a)
x) = [|OrdMap (HM.fromList ls)|]
    where
      ls :: [(k, Indexed k a)]
ls = HashMap k (Indexed k a) -> [(k, Indexed k a)]
forall k v. HashMap k v -> [(k, v)]
HM.toList HashMap k (Indexed k a)
x

#if MIN_VERSION_template_haskell(2,16,0)
  liftTyped :: OrdMap k a -> Q (TExp (OrdMap k a))
liftTyped (OrdMap HashMap k (Indexed k a)
x) = [||OrdMap (HM.fromList ls)||]
    where
      ls :: [(k, Indexed k a)]
ls = HashMap k (Indexed k a) -> [(k, Indexed k a)]
forall k v. HashMap k v -> [(k, v)]
HM.toList HashMap k (Indexed k a)
x
#endif

instance (Eq k, Hashable k) => Foldable (OrdMap k) where
  foldMap :: (a -> m) -> OrdMap k a -> m
foldMap a -> m
f = (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f ([a] -> m) -> (OrdMap k a -> [a]) -> OrdMap k a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrdMap k a -> [a]
forall k b. (Eq k, Hashable k) => OrdMap k b -> [b]
getElements

getElements :: (Eq k, Hashable k) => OrdMap k b -> [b]
getElements :: OrdMap k b -> [b]
getElements = (Indexed k b -> b) -> [Indexed k b] -> [b]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Indexed k b -> b
forall k a. Indexed k a -> a
indexedValue ([Indexed k b] -> [b])
-> (OrdMap k b -> [Indexed k b]) -> OrdMap k b -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Indexed k b -> Int) -> [Indexed k b] -> [Indexed k b]
forall b a. Ord b => (a -> b) -> [a] -> [a]
sortOn Indexed k b -> Int
forall k a. Indexed k a -> Int
index ([Indexed k b] -> [Indexed k b])
-> (OrdMap k b -> [Indexed k b]) -> OrdMap k b -> [Indexed k b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap k (Indexed k b) -> [Indexed k b]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList (HashMap k (Indexed k b) -> [Indexed k b])
-> (OrdMap k b -> HashMap k (Indexed k b))
-> OrdMap k b
-> [Indexed k b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. OrdMap k b -> HashMap k (Indexed k b)
forall k a. OrdMap k a -> HashMap k (Indexed k a)
mapEntries

instance (Eq k, Hashable k) => IsMap k (OrdMap k) where
  unsafeFromList :: [(k, a)] -> OrdMap k a
unsafeFromList = HashMap k (Indexed k a) -> OrdMap k a
forall k a. HashMap k (Indexed k a) -> OrdMap k a
OrdMap (HashMap k (Indexed k a) -> OrdMap k a)
-> ([(k, a)] -> HashMap k (Indexed k a)) -> [(k, a)] -> OrdMap k a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, Indexed k a)] -> HashMap k (Indexed k a)
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HM.fromList ([(k, Indexed k a)] -> HashMap k (Indexed k a))
-> ([(k, a)] -> [(k, Indexed k a)])
-> [(k, a)]
-> HashMap k (Indexed k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Indexed k a -> (k, Indexed k a))
-> [Indexed k a] -> [(k, Indexed k a)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Indexed k a -> (k, Indexed k a)
forall a a. Indexed a a -> (a, Indexed a a)
withKey ([Indexed k a] -> [(k, Indexed k a)])
-> ([(k, a)] -> [Indexed k a]) -> [(k, a)] -> [(k, Indexed k a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, a)] -> [Indexed k a]
forall k a. [(k, a)] -> [Indexed k a]
indexed
    where
      withKey :: Indexed a a -> (a, Indexed a a)
withKey Indexed a a
idx = (Indexed a a -> a
forall k a. Indexed k a -> k
indexedKey Indexed a a
idx, Indexed a a
idx)
  singleton :: k -> a -> OrdMap k a
singleton k
k a
x = HashMap k (Indexed k a) -> OrdMap k a
forall k a. HashMap k (Indexed k a) -> OrdMap k a
OrdMap (HashMap k (Indexed k a) -> OrdMap k a)
-> HashMap k (Indexed k a) -> OrdMap k a
forall a b. (a -> b) -> a -> b
$ k -> Indexed k a -> HashMap k (Indexed k a)
forall k v. Hashable k => k -> v -> HashMap k v
HM.singleton k
k (Int -> k -> a -> Indexed k a
forall k a. Int -> k -> a -> Indexed k a
Indexed Int
0 k
k a
x)
  lookup :: k -> OrdMap k a -> Maybe a
lookup k
key OrdMap {HashMap k (Indexed k a)
mapEntries :: HashMap k (Indexed k a)
mapEntries :: forall k a. OrdMap k a -> HashMap k (Indexed k a)
mapEntries} = Indexed k a -> a
forall k a. Indexed k a -> a
indexedValue (Indexed k a -> a) -> Maybe (Indexed k a) -> Maybe a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> HashMap k (Indexed k a) -> Maybe (Indexed k a)
forall k (m :: * -> *) a. IsMap k m => k -> m a -> Maybe a
lookup k
key HashMap k (Indexed k a)
mapEntries

instance (NameCollision e a, Eq k, Hashable k, Monad m, MonadError e m) => Merge m (OrdMap k a) where
  merge :: OrdMap k a -> OrdMap k a -> m (OrdMap k a)
merge (OrdMap HashMap k (Indexed k a)
x) (OrdMap HashMap k (Indexed k a)
y) = HashMap k (Indexed k a) -> OrdMap k a
forall k a. HashMap k (Indexed k a) -> OrdMap k a
OrdMap (HashMap k (Indexed k a) -> OrdMap k a)
-> m (HashMap k (Indexed k a)) -> m (OrdMap k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> HashMap k (Indexed k a)
-> HashMap k (Indexed k a) -> m (HashMap k (Indexed k a))
forall (m :: * -> *) a. (Merge m a, Monad m) => a -> a -> m a
merge HashMap k (Indexed k a)
x ((Indexed k a -> Indexed k a)
-> HashMap k (Indexed k a) -> HashMap k (Indexed k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Int -> Indexed k a -> Indexed k a
forall k a. Int -> Indexed k a -> Indexed k a
shiftIndexes (HashMap k (Indexed k a) -> Int
forall k v. HashMap k v -> Int
HM.size HashMap k (Indexed k a)
x)) HashMap k (Indexed k a)
y)

shiftIndexes :: Int -> Indexed k a -> Indexed k a
shiftIndexes :: Int -> Indexed k a -> Indexed k a
shiftIndexes Int
n Indexed {k
a
Int
indexedValue :: a
indexedKey :: k
index :: Int
indexedKey :: forall k a. Indexed k a -> k
index :: forall k a. Indexed k a -> Int
indexedValue :: forall k a. Indexed k a -> a
..} = Indexed :: forall k a. Int -> k -> a -> Indexed k a
Indexed {index :: Int
index = Int
index Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
n, k
a
indexedValue :: a
indexedKey :: k
indexedKey :: k
indexedValue :: a
..}

instance
  ( Hashable k,
    Eq k,
    NameCollision e a,
    MonadError e m
  ) =>
  FromList m OrdMap k a
  where
  fromList :: [(k, a)] -> m (OrdMap k a)
fromList = (HashMap k (Indexed k a) -> OrdMap k a)
-> m (HashMap k (Indexed k a)) -> m (OrdMap k a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap HashMap k (Indexed k a) -> OrdMap k a
forall k a. HashMap k (Indexed k a) -> OrdMap k a
OrdMap (m (HashMap k (Indexed k a)) -> m (OrdMap k a))
-> ([(k, a)] -> m (HashMap k (Indexed k a)))
-> [(k, a)]
-> m (OrdMap k a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, Indexed k a)] -> m (HashMap k (Indexed k a))
forall (m :: * -> *) (map :: * -> * -> *) k a.
(FromList m map k a, Monad m) =>
[(k, a)] -> m (map k a)
fromList ([(k, Indexed k a)] -> m (HashMap k (Indexed k a)))
-> ([(k, a)] -> [(k, Indexed k a)])
-> [(k, a)]
-> m (HashMap k (Indexed k a))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Indexed k a -> (k, Indexed k a))
-> [Indexed k a] -> [(k, Indexed k a)]
forall a b. (a -> b) -> [a] -> [b]
map Indexed k a -> (k, Indexed k a)
forall a a. Indexed a a -> (a, Indexed a a)
xyz ([Indexed k a] -> [(k, Indexed k a)])
-> ([(k, a)] -> [Indexed k a]) -> [(k, a)] -> [(k, Indexed k a)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(k, a)] -> [Indexed k a]
forall k a. [(k, a)] -> [Indexed k a]
indexed
    where
      xyz :: Indexed a a -> (a, Indexed a a)
xyz Indexed a a
x = (Indexed a a -> a
forall k a. Indexed k a -> k
indexedKey Indexed a a
x, Indexed a a
x)