{-# LANGUAGE CPP                   #-}
{-# LANGUAGE DeriveDataTypeable    #-}
{-# LANGUAGE DeriveFoldable        #-}
{-# LANGUAGE DeriveFunctor         #-}
{-# LANGUAGE DeriveTraversable     #-}
{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE GADTs                 #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables   #-}
{-# LANGUAGE Trustworthy           #-}
{-# LANGUAGE TypeFamilies          #-}
-- | 'InsOrdHashMap' is like 'HashMap', but it folds and traverses in insertion order.
--
-- This module interface mimics "Data.HashMap.Strict", with some additions.
module Data.HashMap.Strict.InsOrd (
    InsOrdHashMap,
    -- * Construction
    empty,
    singleton,
    -- * Basic interface
    null,
    size,
    member,
    lookup,
    lookupDefault,
    insert,
    insertWith,
    delete,
    adjust,
    update,
    alter,
    -- * Combine
    union,
    unionWith,
    unionWithKey,
    unions,
    -- * Transformations
    map,
    mapKeys,
    traverseKeys,
    mapWithKey,
    traverseWithKey,
    -- ** Unordered
    unorderedTraverse,
    unorderedTraverseWithKey,
    -- * Difference and intersection
    difference,
    intersection,
    intersectionWith,
    intersectionWithKey,
    -- * Folds
    foldl',
    foldlWithKey',
    foldr,
    foldrWithKey,
    foldMapWithKey,
    -- ** Unordered
    unorderedFoldMap,
    unorderedFoldMapWithKey,
    -- * Filter
    filter,
    filterWithKey,
    mapMaybe,
    mapMaybeWithKey,
    -- * Conversions
    keys,
    elems,
    toList,
    toRevList,
    fromList,
    toHashMap,
    fromHashMap,
    -- * Lenses
    hashMap,
    unorderedTraversal,
    -- * Debugging
    valid,
    ) where

import Prelude
       (Bool (..), Eq, Functor, Int, Maybe (..), all, const, flip, fmap, fst,
       id, maybe, otherwise, pure, return, snd, uncurry, ($), (&&), (+), (.),
       (<$>), (<), (==), (>), (>=), (>>=), (||))

import Control.Applicative             (Applicative, Const (..))
import Control.Arrow                   (first, second)
import Control.DeepSeq                 (NFData (..))
import Data.Data                       (Data, Typeable)
import Data.Foldable                   (Foldable (foldMap))
import Data.Foldable.WithIndex         (FoldableWithIndex (..))
import Data.Functor.Apply              (Apply (..))
import Data.Functor.Bind               (Bind (..))
import Data.Functor.WithIndex          (FunctorWithIndex (..))
import Data.Hashable                   (Hashable (..))
import Data.List                       (nub, sortBy)
import Data.Maybe                      (fromMaybe)
import Data.Monoid                     (Monoid, mappend, mempty)
import Data.Ord                        (comparing)
import Data.Semigroup                  (Semigroup (..))
import Data.Traversable                (Traversable (traverse))
import Data.Traversable.WithIndex      (TraversableWithIndex (..))
import Text.ParserCombinators.ReadPrec (prec)
import Text.Read
       (Lexeme (..), Read (..), lexP, parens, readListPrecDefault)
import Text.Show                       (Show (..), showParen, showString)

import Control.Lens
       (At (..), Index, Iso, IxValue, Ixed (..), Traversal, _1, _2, iso, (<&>))
import Control.Monad.Trans.State.Strict (State, runState, state)

import qualified Control.Lens        as Lens
import qualified Data.Aeson          as A
import qualified Data.Aeson.Encoding as E
import qualified Data.Foldable       as F
import qualified Optics.At           as Optics
import qualified Optics.Core         as Optics

import           Data.HashMap.Strict (HashMap)
import qualified Data.HashMap.Strict as HashMap

import qualified GHC.Exts as Exts

#if MIN_VERSION_deepseq(1,4,3)
import qualified Control.DeepSeq as NF
#endif

import Data.HashMap.InsOrd.Internal

-------------------------------------------------------------------------------
-- Strict Pair Int a
-------------------------------------------------------------------------------

data P a = P !Int !a
    deriving (forall a b. a -> P b -> P a
forall a b. (a -> b) -> P a -> P b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> P b -> P a
$c<$ :: forall a b. a -> P b -> P a
fmap :: forall a b. (a -> b) -> P a -> P b
$cfmap :: forall a b. (a -> b) -> P a -> P b
Functor, forall a. Eq a => a -> P a -> Bool
forall a. Num a => P a -> a
forall a. Ord a => P a -> a
forall m. Monoid m => P m -> m
forall a. P a -> Bool
forall a. P a -> Int
forall a. P a -> [a]
forall a. (a -> a -> a) -> P a -> a
forall m a. Monoid m => (a -> m) -> P a -> m
forall b a. (b -> a -> b) -> b -> P a -> b
forall a b. (a -> b -> b) -> b -> P 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 :: forall a. Num a => P a -> a
$cproduct :: forall a. Num a => P a -> a
sum :: forall a. Num a => P a -> a
$csum :: forall a. Num a => P a -> a
minimum :: forall a. Ord a => P a -> a
$cminimum :: forall a. Ord a => P a -> a
maximum :: forall a. Ord a => P a -> a
$cmaximum :: forall a. Ord a => P a -> a
elem :: forall a. Eq a => a -> P a -> Bool
$celem :: forall a. Eq a => a -> P a -> Bool
length :: forall a. P a -> Int
$clength :: forall a. P a -> Int
null :: forall a. P a -> Bool
$cnull :: forall a. P a -> Bool
toList :: forall a. P a -> [a]
$ctoList :: forall a. P a -> [a]
foldl1 :: forall a. (a -> a -> a) -> P a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> P a -> a
foldr1 :: forall a. (a -> a -> a) -> P a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> P a -> a
foldl' :: forall b a. (b -> a -> b) -> b -> P a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> P a -> b
foldl :: forall b a. (b -> a -> b) -> b -> P a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> P a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> P a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> P a -> b
foldr :: forall a b. (a -> b -> b) -> b -> P a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> P a -> b
foldMap' :: forall m a. Monoid m => (a -> m) -> P a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> P a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> P a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> P a -> m
fold :: forall m. Monoid m => P m -> m
$cfold :: forall m. Monoid m => P m -> m
Foldable, Functor P
Foldable P
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 => P (m a) -> m (P a)
forall (f :: * -> *) a. Applicative f => P (f a) -> f (P a)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> P a -> m (P b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> P a -> f (P b)
sequence :: forall (m :: * -> *) a. Monad m => P (m a) -> m (P a)
$csequence :: forall (m :: * -> *) a. Monad m => P (m a) -> m (P a)
mapM :: forall (m :: * -> *) a b. Monad m => (a -> m b) -> P a -> m (P b)
$cmapM :: forall (m :: * -> *) a b. Monad m => (a -> m b) -> P a -> m (P b)
sequenceA :: forall (f :: * -> *) a. Applicative f => P (f a) -> f (P a)
$csequenceA :: forall (f :: * -> *) a. Applicative f => P (f a) -> f (P a)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> P a -> f (P b)
$ctraverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> P a -> f (P b)
Traversable, Typeable, P a -> DataType
P a -> Constr
forall {a}. Data a => Typeable (P a)
forall a. Data a => P a -> DataType
forall a. Data a => P a -> Constr
forall a. Data a => (forall b. Data b => b -> b) -> P a -> P a
forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> P a -> u
forall a u. Data a => (forall d. Data d => d -> u) -> P a -> [u]
forall a r r'.
Data a =>
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> P a -> r
forall a r r'.
Data a =>
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> P a -> r
forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> P a -> m (P a)
forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> P a -> m (P a)
forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (P a)
forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> P a -> c (P a)
forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (P a))
forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (P a))
forall a.
Typeable a
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (P a)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> P a -> c (P a)
forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (P a))
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> P a -> m (P a)
$cgmapMo :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> P a -> m (P a)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d) -> P a -> m (P a)
$cgmapMp :: forall a (m :: * -> *).
(Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> P a -> m (P a)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d) -> P a -> m (P a)
$cgmapM :: forall a (m :: * -> *).
(Data a, Monad m) =>
(forall d. Data d => d -> m d) -> P a -> m (P a)
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> P a -> u
$cgmapQi :: forall a u.
Data a =>
Int -> (forall d. Data d => d -> u) -> P a -> u
gmapQ :: forall u. (forall d. Data d => d -> u) -> P a -> [u]
$cgmapQ :: forall a u. Data a => (forall d. Data d => d -> u) -> P a -> [u]
gmapQr :: forall r r'.
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> P a -> r
$cgmapQr :: forall a r r'.
Data a =>
(r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> P a -> r
gmapQl :: forall r r'.
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> P a -> r
$cgmapQl :: forall a r r'.
Data a =>
(r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> P a -> r
gmapT :: (forall b. Data b => b -> b) -> P a -> P a
$cgmapT :: forall a. Data a => (forall b. Data b => b -> b) -> P a -> P a
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (P a))
$cdataCast2 :: forall a (t :: * -> * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (P a))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (P a))
$cdataCast1 :: forall a (t :: * -> *) (c :: * -> *).
(Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (P a))
dataTypeOf :: P a -> DataType
$cdataTypeOf :: forall a. Data a => P a -> DataType
toConstr :: P a -> Constr
$ctoConstr :: forall a. Data a => P a -> Constr
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (P a)
$cgunfold :: forall a (c :: * -> *).
Data a =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (P a)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> P a -> c (P a)
$cgfoldl :: forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> P a -> c (P a)
Data)

instance NFData a => NFData (P a) where
    rnf :: P a -> ()
rnf (P Int
_ a
a) = forall a. NFData a => a -> ()
rnf a
a

#if MIN_VERSION_deepseq(1,4,3)
-- | @since 0.2.5
instance NF.NFData1 P where
    liftRnf :: forall a. (a -> ()) -> P a -> ()
liftRnf a -> ()
rnf1 (P Int
_ a
a) = a -> ()
rnf1 a
a
#endif

getPK :: P a -> Int
getPK :: forall a. P a -> Int
getPK (P Int
i a
_) = Int
i
{-# INLINABLE getPK #-}

getPV :: P a -> a
getPV :: forall a. P a -> a
getPV (P Int
_ a
a) = a
a
{-# INLINABLE getPV #-}

incPK :: Int -> P a -> P a
incPK :: forall a. Int -> P a -> P a
incPK Int
i (P Int
j a
x) = forall a. Int -> a -> P a
P (Int
i forall a. Num a => a -> a -> a
+ Int
j) a
x
{-# INLINABLE incPK #-}

instance Eq a => Eq (P a) where
    P Int
_ a
a == :: P a -> P a -> Bool
== P Int
_ a
b = a
a forall a. Eq a => a -> a -> Bool
== a
b

instance Show a => Show (P a) where
    showsPrec :: Int -> P a -> ShowS
showsPrec Int
d (P Int
_ a
x) = forall a. Show a => Int -> a -> ShowS
showsPrec Int
d a
x

instance Hashable a => Hashable (P a) where
    hashWithSalt :: Int -> P a -> Int
hashWithSalt Int
salt (P Int
_ a
x) = forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt a
x

-------------------------------------------------------------------------------
-- InsOrdHashMap
-------------------------------------------------------------------------------

-- | 'HashMap' which tries its best to remember insertion order of elements.

data InsOrdHashMap k v = InsOrdHashMap
    { forall k v. InsOrdHashMap k v -> Int
_getIndex        :: !Int
    , forall k v. InsOrdHashMap k v -> HashMap k (P v)
getInsOrdHashMap :: !(HashMap k (P v))
    }
    deriving (forall a b. a -> InsOrdHashMap k b -> InsOrdHashMap k a
forall a b. (a -> b) -> InsOrdHashMap k a -> InsOrdHashMap k b
forall k a b. a -> InsOrdHashMap k b -> InsOrdHashMap k a
forall k a b. (a -> b) -> InsOrdHashMap k a -> InsOrdHashMap k b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> InsOrdHashMap k b -> InsOrdHashMap k a
$c<$ :: forall k a b. a -> InsOrdHashMap k b -> InsOrdHashMap k a
fmap :: forall a b. (a -> b) -> InsOrdHashMap k a -> InsOrdHashMap k b
$cfmap :: forall k a b. (a -> b) -> InsOrdHashMap k a -> InsOrdHashMap k b
Functor, Typeable, InsOrdHashMap k v -> DataType
InsOrdHashMap k v -> Constr
forall a.
Typeable a
-> (forall (c :: * -> *).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall {k} {v}.
(Data k, Data v, Hashable k) =>
Typeable (InsOrdHashMap k v)
forall k v.
(Data k, Data v, Hashable k) =>
InsOrdHashMap k v -> DataType
forall k v.
(Data k, Data v, Hashable k) =>
InsOrdHashMap k v -> Constr
forall k v.
(Data k, Data v, Hashable k) =>
(forall b. Data b => b -> b)
-> InsOrdHashMap k v -> InsOrdHashMap k v
forall k v u.
(Data k, Data v, Hashable k) =>
Int -> (forall d. Data d => d -> u) -> InsOrdHashMap k v -> u
forall k v u.
(Data k, Data v, Hashable k) =>
(forall d. Data d => d -> u) -> InsOrdHashMap k v -> [u]
forall k v r r'.
(Data k, Data v, Hashable k) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> InsOrdHashMap k v -> r
forall k v r r'.
(Data k, Data v, Hashable k) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> InsOrdHashMap k v -> r
forall k v (m :: * -> *).
(Data k, Data v, Hashable k, Monad m) =>
(forall d. Data d => d -> m d)
-> InsOrdHashMap k v -> m (InsOrdHashMap k v)
forall k v (m :: * -> *).
(Data k, Data v, Hashable k, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> InsOrdHashMap k v -> m (InsOrdHashMap k v)
forall k v (c :: * -> *).
(Data k, Data v, Hashable k) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (InsOrdHashMap k v)
forall k v (c :: * -> *).
(Data k, Data v, Hashable k) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g)
-> InsOrdHashMap k v
-> c (InsOrdHashMap k v)
forall k v (t :: * -> *) (c :: * -> *).
(Data k, Data v, Hashable k, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (InsOrdHashMap k v))
forall k v (t :: * -> * -> *) (c :: * -> *).
(Data k, Data v, Hashable k, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (InsOrdHashMap k v))
forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (InsOrdHashMap k v)
forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g)
-> InsOrdHashMap k v
-> c (InsOrdHashMap k v)
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (InsOrdHashMap k v))
gmapMo :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> InsOrdHashMap k v -> m (InsOrdHashMap k v)
$cgmapMo :: forall k v (m :: * -> *).
(Data k, Data v, Hashable k, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> InsOrdHashMap k v -> m (InsOrdHashMap k v)
gmapMp :: forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> InsOrdHashMap k v -> m (InsOrdHashMap k v)
$cgmapMp :: forall k v (m :: * -> *).
(Data k, Data v, Hashable k, MonadPlus m) =>
(forall d. Data d => d -> m d)
-> InsOrdHashMap k v -> m (InsOrdHashMap k v)
gmapM :: forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> InsOrdHashMap k v -> m (InsOrdHashMap k v)
$cgmapM :: forall k v (m :: * -> *).
(Data k, Data v, Hashable k, Monad m) =>
(forall d. Data d => d -> m d)
-> InsOrdHashMap k v -> m (InsOrdHashMap k v)
gmapQi :: forall u.
Int -> (forall d. Data d => d -> u) -> InsOrdHashMap k v -> u
$cgmapQi :: forall k v u.
(Data k, Data v, Hashable k) =>
Int -> (forall d. Data d => d -> u) -> InsOrdHashMap k v -> u
gmapQ :: forall u. (forall d. Data d => d -> u) -> InsOrdHashMap k v -> [u]
$cgmapQ :: forall k v u.
(Data k, Data v, Hashable k) =>
(forall d. Data d => d -> u) -> InsOrdHashMap k v -> [u]
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> InsOrdHashMap k v -> r
$cgmapQr :: forall k v r r'.
(Data k, Data v, Hashable k) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> InsOrdHashMap k v -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> InsOrdHashMap k v -> r
$cgmapQl :: forall k v r r'.
(Data k, Data v, Hashable k) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> InsOrdHashMap k v -> r
gmapT :: (forall b. Data b => b -> b)
-> InsOrdHashMap k v -> InsOrdHashMap k v
$cgmapT :: forall k v.
(Data k, Data v, Hashable k) =>
(forall b. Data b => b -> b)
-> InsOrdHashMap k v -> InsOrdHashMap k v
dataCast2 :: forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (InsOrdHashMap k v))
$cdataCast2 :: forall k v (t :: * -> * -> *) (c :: * -> *).
(Data k, Data v, Hashable k, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (InsOrdHashMap k v))
dataCast1 :: forall (t :: * -> *) (c :: * -> *).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (InsOrdHashMap k v))
$cdataCast1 :: forall k v (t :: * -> *) (c :: * -> *).
(Data k, Data v, Hashable k, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (InsOrdHashMap k v))
dataTypeOf :: InsOrdHashMap k v -> DataType
$cdataTypeOf :: forall k v.
(Data k, Data v, Hashable k) =>
InsOrdHashMap k v -> DataType
toConstr :: InsOrdHashMap k v -> Constr
$ctoConstr :: forall k v.
(Data k, Data v, Hashable k) =>
InsOrdHashMap k v -> Constr
gunfold :: forall (c :: * -> *).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (InsOrdHashMap k v)
$cgunfold :: forall k v (c :: * -> *).
(Data k, Data v, Hashable k) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (InsOrdHashMap k v)
gfoldl :: forall (c :: * -> *).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g)
-> InsOrdHashMap k v
-> c (InsOrdHashMap k v)
$cgfoldl :: forall k v (c :: * -> *).
(Data k, Data v, Hashable k) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g)
-> InsOrdHashMap k v
-> c (InsOrdHashMap k v)
Data)

-- | @since 0.2.5
instance (NFData k, NFData v) => NFData (InsOrdHashMap k v) where
    rnf :: InsOrdHashMap k v -> ()
rnf (InsOrdHashMap Int
_ HashMap k (P v)
hm) = forall a. NFData a => a -> ()
rnf HashMap k (P v)
hm

#if MIN_VERSION_deepseq(1,4,3)
-- | @since 0.2.5
instance NFData k => NF.NFData1 (InsOrdHashMap k) where
    liftRnf :: forall a. (a -> ()) -> InsOrdHashMap k a -> ()
liftRnf a -> ()
rnf2 = forall (p :: * -> * -> *) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
NF.liftRnf2 forall a. NFData a => a -> ()
rnf a -> ()
rnf2

-- | @since 0.2.5
instance NF.NFData2 InsOrdHashMap  where
    liftRnf2 :: forall a b. (a -> ()) -> (b -> ()) -> InsOrdHashMap a b -> ()
liftRnf2 a -> ()
rnf1 b -> ()
rnf2 (InsOrdHashMap Int
_ HashMap a (P b)
m) = forall (p :: * -> * -> *) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
NF.liftRnf2 a -> ()
rnf1 (forall (f :: * -> *) a. NFData1 f => (a -> ()) -> f a -> ()
NF.liftRnf b -> ()
rnf2) HashMap a (P b)
m
#endif

instance (Eq k, Eq v) => Eq (InsOrdHashMap k v) where
    InsOrdHashMap Int
_ HashMap k (P v)
a == :: InsOrdHashMap k v -> InsOrdHashMap k v -> Bool
== InsOrdHashMap Int
_ HashMap k (P v)
b = HashMap k (P v)
a forall a. Eq a => a -> a -> Bool
== HashMap k (P v)
b

instance (Show k, Show v) => Show (InsOrdHashMap k v) where
    showsPrec :: Int -> InsOrdHashMap k v -> ShowS
showsPrec Int
d InsOrdHashMap k v
m = Bool -> ShowS -> ShowS
showParen (Int
d forall a. Ord a => a -> a -> Bool
> Int
10) forall a b. (a -> b) -> a -> b
$
        String -> ShowS
showString String
"fromList " forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (forall k v. InsOrdHashMap k v -> [(k, v)]
toList InsOrdHashMap k v
m)

instance (Eq k, Hashable k, Read k, Read v) => Read (InsOrdHashMap k v) where
    readPrec :: ReadPrec (InsOrdHashMap k v)
readPrec = forall a. ReadPrec a -> ReadPrec a
parens forall a b. (a -> b) -> a -> b
$ forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 forall a b. (a -> b) -> a -> b
$ do
      Ident String
"fromList" <- ReadPrec Lexeme
lexP
      [(k, v)]
xs <- forall a. Read a => ReadPrec a
readPrec
      forall (m :: * -> *) a. Monad m => a -> m a
return (forall k v. (Eq k, Hashable k) => [(k, v)] -> InsOrdHashMap k v
fromList [(k, v)]
xs)

    readListPrec :: ReadPrec [InsOrdHashMap k v]
readListPrec = forall a. Read a => ReadPrec [a]
readListPrecDefault

instance (Eq k, Hashable k) => Semigroup (InsOrdHashMap k v) where
    <> :: InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
(<>) = forall k v.
(Eq k, Hashable k) =>
InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
union

instance (Eq k, Hashable k) => Monoid (InsOrdHashMap k v) where
    mempty :: InsOrdHashMap k v
mempty = forall k v. InsOrdHashMap k v
empty
    mappend :: InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
mappend = forall k v.
(Eq k, Hashable k) =>
InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
union

-- We cannot derive this, as we want to ordered folding and traversing
instance Foldable (InsOrdHashMap k) where
    -- in newer base only
    -- length = length . getInsOrdHashMap
    foldMap :: forall m a. Monoid m => (a -> m) -> InsOrdHashMap k a -> m
foldMap a -> m
f = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (a -> m
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> b
snd) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> [(k, v)]
toList

    null :: forall a. InsOrdHashMap k a -> Bool
null = forall k a. InsOrdHashMap k a -> Bool
null
    toList :: forall a. InsOrdHashMap k a -> [a]
toList = forall k a. InsOrdHashMap k a -> [a]
elems
    length :: forall a. InsOrdHashMap k a -> Int
length = forall k v. InsOrdHashMap k v -> Int
size

instance Traversable (InsOrdHashMap k) where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> InsOrdHashMap k a -> f (InsOrdHashMap k b)
traverse a -> f b
f InsOrdHashMap k a
m = forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> InsOrdHashMap k a -> f (InsOrdHashMap k b)
traverseWithKey (\k
_ -> a -> f b
f) InsOrdHashMap k a
m

instance (Eq k, Hashable k) => Apply (InsOrdHashMap k) where
    <.> :: forall a b.
InsOrdHashMap k (a -> b) -> InsOrdHashMap k a -> InsOrdHashMap k b
(<.>) = forall k v1 v2 v3.
(Eq k, Hashable k) =>
(v1 -> v2 -> v3)
-> InsOrdHashMap k v1 -> InsOrdHashMap k v2 -> InsOrdHashMap k v3
intersectionWith forall a. a -> a
id
    (<. ) = forall k v1 v2 v3.
(Eq k, Hashable k) =>
(v1 -> v2 -> v3)
-> InsOrdHashMap k v1 -> InsOrdHashMap k v2 -> InsOrdHashMap k v3
intersectionWith forall a b. a -> b -> a
const
    ( .>) = forall k v1 v2 v3.
(Eq k, Hashable k) =>
(v1 -> v2 -> v3)
-> InsOrdHashMap k v1 -> InsOrdHashMap k v2 -> InsOrdHashMap k v3
intersectionWith (forall a b. a -> b -> a
const forall a. a -> a
id)

instance (Eq k, Hashable k) => Bind (InsOrdHashMap k) where
    InsOrdHashMap k a
m >>- :: forall a b.
InsOrdHashMap k a -> (a -> InsOrdHashMap k b) -> InsOrdHashMap k b
>>- a -> InsOrdHashMap k b
f = forall k v1 v2.
(k -> v1 -> Maybe v2) -> InsOrdHashMap k v1 -> InsOrdHashMap k v2
mapMaybeWithKey (\k
k -> forall k v. (Eq k, Hashable k) => k -> InsOrdHashMap k v -> Maybe v
lookup k
k forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> InsOrdHashMap k b
f) InsOrdHashMap k a
m

-- | @hashWithSalt salt . toHashMap = hashWithSalt salt@.
instance (Hashable k, Hashable v) => Hashable (InsOrdHashMap k v) where
    hashWithSalt :: Int -> InsOrdHashMap k v -> Int
hashWithSalt Int
salt (InsOrdHashMap Int
_ HashMap k (P v)
m) =
        forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt HashMap k (P v)
m

instance (Eq k, Hashable k) => Exts.IsList (InsOrdHashMap k v) where
    type Item (InsOrdHashMap k v) = (k, v)
    fromList :: [Item (InsOrdHashMap k v)] -> InsOrdHashMap k v
fromList = forall k v. (Eq k, Hashable k) => [(k, v)] -> InsOrdHashMap k v
fromList
    toList :: InsOrdHashMap k v -> [Item (InsOrdHashMap k v)]
toList   = forall k v. InsOrdHashMap k v -> [(k, v)]
toList

-------------------------------------------------------------------------------
-- Aeson
-------------------------------------------------------------------------------

instance (A.ToJSONKey k) => A.ToJSON1 (InsOrdHashMap k) where
#if MIN_VERSION_aeson(2,2,0)
    liftToJSON _ t _ = case A.toJSONKey :: A.ToJSONKeyFunction k of
      A.ToJSONKeyText f _ -> A.object . fmap (\(k, v) -> (f k, t v)) . toList
      A.ToJSONKeyValue f _ -> A.toJSON . fmap (\(k,v) -> A.toJSON (f k, t v)) . toList
#else
    liftToJSON :: forall a.
(a -> Value) -> ([a] -> Value) -> InsOrdHashMap k a -> Value
liftToJSON a -> Value
t [a] -> Value
_ = case forall a. ToJSONKey a => ToJSONKeyFunction a
A.toJSONKey :: A.ToJSONKeyFunction k of
      A.ToJSONKeyText k -> Key
f k -> Encoding' Key
_ -> [Pair] -> Value
A.object forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(k
k, a
v) -> (k -> Key
f k
k, a -> Value
t a
v)) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> [(k, v)]
toList
      A.ToJSONKeyValue k -> Value
f k -> Encoding
_ -> forall a. ToJSON a => a -> Value
A.toJSON forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\(k
k,a
v) -> forall a. ToJSON a => a -> Value
A.toJSON (k -> Value
f k
k, a -> Value
t a
v)) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> [(k, v)]
toList
#endif

#if MIN_VERSION_aeson(2,2,0)
    liftToEncoding o t _ = case A.toJSONKey :: A.ToJSONKeyFunction k of
      A.ToJSONKeyText _ f ->  E.dict f t foldrWithKey
      A.ToJSONKeyValue _ f -> E.list (A.liftToEncoding2 (const False) f (E.list f) o t (E.list t)) . toList
#else
    liftToEncoding :: forall a.
(a -> Encoding)
-> ([a] -> Encoding) -> InsOrdHashMap k a -> Encoding
liftToEncoding a -> Encoding
t [a] -> Encoding
_ = case forall a. ToJSONKey a => ToJSONKeyFunction a
A.toJSONKey :: A.ToJSONKeyFunction k of
      A.ToJSONKeyText k -> Key
_ k -> Encoding' Key
f ->  forall k v m.
(k -> Encoding' Key)
-> (v -> Encoding)
-> (forall a. (k -> v -> a -> a) -> a -> m -> a)
-> m
-> Encoding
E.dict k -> Encoding' Key
f a -> Encoding
t forall k v a. (k -> v -> a -> a) -> a -> InsOrdHashMap k v -> a
foldrWithKey
      A.ToJSONKeyValue k -> Value
_ k -> Encoding
f -> forall a. (a -> Encoding) -> [a] -> Encoding
E.list (forall (f :: * -> * -> *) a b.
ToJSON2 f =>
(a -> Encoding)
-> ([a] -> Encoding)
-> (b -> Encoding)
-> ([b] -> Encoding)
-> f a b
-> Encoding
A.liftToEncoding2 k -> Encoding
f (forall a. (a -> Encoding) -> [a] -> Encoding
E.list k -> Encoding
f) a -> Encoding
t (forall a. (a -> Encoding) -> [a] -> Encoding
E.list a -> Encoding
t)) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> [(k, v)]
toList
#endif

instance (A.ToJSONKey k, A.ToJSON v) => A.ToJSON (InsOrdHashMap k v) where
    toJSON :: InsOrdHashMap k v -> Value
toJSON = forall (f :: * -> *) a. (ToJSON1 f, ToJSON a) => f a -> Value
A.toJSON1
    toEncoding :: InsOrdHashMap k v -> Encoding
toEncoding = forall (f :: * -> *) a. (ToJSON1 f, ToJSON a) => f a -> Encoding
A.toEncoding1

-------------------------------------------------------------------------------

instance (Eq k, Hashable k, A.FromJSONKey k) => A.FromJSON1 (InsOrdHashMap k) where
#if MIN_VERSION_aeson(2,2,0)
    liftParseJSON o p pl v = fromList . HashMap.toList <$> A.liftParseJSON o p pl v
#else
    liftParseJSON :: forall a.
(Value -> Parser a)
-> (Value -> Parser [a]) -> Value -> Parser (InsOrdHashMap k a)
liftParseJSON Value -> Parser a
p Value -> Parser [a]
pl Value
v = forall k v. (Eq k, Hashable k) => [(k, v)] -> InsOrdHashMap k v
fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. HashMap k v -> [(k, v)]
HashMap.toList forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) a.
FromJSON1 f =>
(Value -> Parser a)
-> (Value -> Parser [a]) -> Value -> Parser (f a)
A.liftParseJSON Value -> Parser a
p Value -> Parser [a]
pl Value
v
#endif

instance (Eq k, Hashable k, A.FromJSONKey k, A.FromJSON v) => A.FromJSON (InsOrdHashMap k v) where
    parseJSON :: Value -> Parser (InsOrdHashMap k v)
parseJSON = forall (f :: * -> *) a.
(FromJSON1 f, FromJSON a) =>
Value -> Parser (f a)
A.parseJSON1

-------------------------------------------------------------------------------
-- indexed-traversals
-------------------------------------------------------------------------------

instance (Eq k, Hashable k) => FunctorWithIndex k (InsOrdHashMap k) where
    imap :: forall a b. (k -> a -> b) -> InsOrdHashMap k a -> InsOrdHashMap k b
imap = forall k v1 v2.
(k -> v1 -> v2) -> InsOrdHashMap k v1 -> InsOrdHashMap k v2
mapWithKey
instance (Eq k, Hashable k) => FoldableWithIndex k (InsOrdHashMap k) where
    ifoldMap :: forall m a. Monoid m => (k -> a -> m) -> InsOrdHashMap k a -> m
ifoldMap = forall m k a. Monoid m => (k -> a -> m) -> InsOrdHashMap k a -> m
foldMapWithKey
    ifoldr :: forall a b. (k -> a -> b -> b) -> b -> InsOrdHashMap k a -> b
ifoldr   = forall k v a. (k -> v -> a -> a) -> a -> InsOrdHashMap k v -> a
foldrWithKey
instance (Eq k, Hashable k) => TraversableWithIndex k (InsOrdHashMap k) where
    itraverse :: forall (f :: * -> *) a b.
Applicative f =>
(k -> a -> f b) -> InsOrdHashMap k a -> f (InsOrdHashMap k b)
itraverse = forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> InsOrdHashMap k a -> f (InsOrdHashMap k b)
traverseWithKey

-------------------------------------------------------------------------------
-- Lens
-------------------------------------------------------------------------------

type instance Index (InsOrdHashMap k v) = k
type instance IxValue (InsOrdHashMap k v) = v

instance (Eq k, Hashable k) => Ixed (InsOrdHashMap k v) where
    ix :: Index (InsOrdHashMap k v)
-> Traversal' (InsOrdHashMap k v) (IxValue (InsOrdHashMap k v))
ix Index (InsOrdHashMap k v)
k IxValue (InsOrdHashMap k v) -> f (IxValue (InsOrdHashMap k v))
f InsOrdHashMap k v
m = forall k (f :: * -> *) v.
(Eq k, Hashable k, Functor f) =>
k
-> (InsOrdHashMap k v -> f (InsOrdHashMap k v))
-> (v -> f v)
-> InsOrdHashMap k v
-> f (InsOrdHashMap k v)
ixImpl Index (InsOrdHashMap k v)
k forall (f :: * -> *) a. Applicative f => a -> f a
pure IxValue (InsOrdHashMap k v) -> f (IxValue (InsOrdHashMap k v))
f InsOrdHashMap k v
m
    {-# INLINABLE ix #-}

ixImpl
  :: (Eq k, Hashable k, Functor f)
  => k
  -> (InsOrdHashMap k v -> f (InsOrdHashMap k v))
  -> (v -> f v)
  -> InsOrdHashMap k v
  -> f (InsOrdHashMap k v)
ixImpl :: forall k (f :: * -> *) v.
(Eq k, Hashable k, Functor f) =>
k
-> (InsOrdHashMap k v -> f (InsOrdHashMap k v))
-> (v -> f v)
-> InsOrdHashMap k v
-> f (InsOrdHashMap k v)
ixImpl k
k InsOrdHashMap k v -> f (InsOrdHashMap k v)
point v -> f v
f InsOrdHashMap k v
m = case forall k v. (Eq k, Hashable k) => k -> InsOrdHashMap k v -> Maybe v
lookup k
k InsOrdHashMap k v
m of
    Just v
v  -> v -> f v
f v
v forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \v
v' -> forall k v.
(Eq k, Hashable k) =>
k -> v -> InsOrdHashMap k v -> InsOrdHashMap k v
insert k
k v
v' InsOrdHashMap k v
m
    Maybe v
Nothing -> InsOrdHashMap k v -> f (InsOrdHashMap k v)
point InsOrdHashMap k v
m
{-# INLINE ixImpl #-}

instance (Eq k, Hashable k) => At (InsOrdHashMap k a) where
    at :: Index (InsOrdHashMap k a)
-> Lens' (InsOrdHashMap k a) (Maybe (IxValue (InsOrdHashMap k a)))
at Index (InsOrdHashMap k a)
k Maybe (IxValue (InsOrdHashMap k a))
-> f (Maybe (IxValue (InsOrdHashMap k a)))
f InsOrdHashMap k a
m = Maybe (IxValue (InsOrdHashMap k a))
-> f (Maybe (IxValue (InsOrdHashMap k a)))
f Maybe a
mv forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \Maybe a
r -> case Maybe a
r of
        Maybe a
Nothing -> forall b a. b -> (a -> b) -> Maybe a -> b
maybe InsOrdHashMap k a
m (forall a b. a -> b -> a
const (forall k v.
(Eq k, Hashable k) =>
k -> InsOrdHashMap k v -> InsOrdHashMap k v
delete Index (InsOrdHashMap k a)
k InsOrdHashMap k a
m)) Maybe a
mv
        Just a
v' -> forall k v.
(Eq k, Hashable k) =>
k -> v -> InsOrdHashMap k v -> InsOrdHashMap k v
insert Index (InsOrdHashMap k a)
k a
v' InsOrdHashMap k a
m
      where mv :: Maybe a
mv = forall k v. (Eq k, Hashable k) => k -> InsOrdHashMap k v -> Maybe v
lookup Index (InsOrdHashMap k a)
k InsOrdHashMap k a
m
    {-# INLINABLE at #-}

-- | This is a slight lie, as roundtrip doesn't preserve ordering.
hashMap :: Iso (InsOrdHashMap k a) (InsOrdHashMap k b) (HashMap k a) (HashMap k b)
hashMap :: forall k a b.
Iso
  (InsOrdHashMap k a) (InsOrdHashMap k b) (HashMap k a) (HashMap k b)
hashMap = forall s a b t. (s -> a) -> (b -> t) -> Iso s t a b
iso forall k v. InsOrdHashMap k v -> HashMap k v
toHashMap forall k v. HashMap k v -> InsOrdHashMap k v
fromHashMap

unorderedTraversal :: Traversal (InsOrdHashMap k a) (InsOrdHashMap k b) a b
unorderedTraversal :: forall k a b. Traversal (InsOrdHashMap k a) (InsOrdHashMap k b) a b
unorderedTraversal = forall k a b.
Iso
  (InsOrdHashMap k a) (InsOrdHashMap k b) (HashMap k a) (HashMap k b)
hashMap forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse

#if !MIN_VERSION_lens(5,0,0)
instance (Eq k, Hashable k) => Lens.FunctorWithIndex k (InsOrdHashMap k) where
    imap = mapWithKey
instance (Eq k, Hashable k) => Lens.FoldableWithIndex k (InsOrdHashMap k) where
    ifoldMap = foldMapWithKey
    ifoldr   = foldrWithKey
instance (Eq k, Hashable k) => Lens.TraversableWithIndex k (InsOrdHashMap k) where
    itraverse = traverseWithKey
#endif

-------------------------------------------------------------------------------
-- Optics
-------------------------------------------------------------------------------

type instance Optics.Index (InsOrdHashMap k v) = k
type instance Optics.IxValue (InsOrdHashMap k v) = v

instance (Eq k, Hashable k) => Optics.Ixed (InsOrdHashMap k v) where
    ix :: Index (InsOrdHashMap k v)
-> Optic'
     (IxKind (InsOrdHashMap k v))
     NoIx
     (InsOrdHashMap k v)
     (IxValue (InsOrdHashMap k v))
ix Index (InsOrdHashMap k v)
k = forall s t a b.
AffineTraversalVL s t a b -> AffineTraversal s t a b
Optics.atraversalVL forall a b. (a -> b) -> a -> b
$ \forall r. r -> f r
point IxValue (InsOrdHashMap k v) -> f (IxValue (InsOrdHashMap k v))
f InsOrdHashMap k v
m -> forall k (f :: * -> *) v.
(Eq k, Hashable k, Functor f) =>
k
-> (InsOrdHashMap k v -> f (InsOrdHashMap k v))
-> (v -> f v)
-> InsOrdHashMap k v
-> f (InsOrdHashMap k v)
ixImpl Index (InsOrdHashMap k v)
k forall r. r -> f r
point IxValue (InsOrdHashMap k v) -> f (IxValue (InsOrdHashMap k v))
f InsOrdHashMap k v
m
    {-# INLINE ix #-}

instance (Eq k, Hashable k) => Optics.At (InsOrdHashMap k a) where
    at :: Index (InsOrdHashMap k a)
-> Lens' (InsOrdHashMap k a) (Maybe (IxValue (InsOrdHashMap k a)))
at Index (InsOrdHashMap k a)
k = forall s t a b. LensVL s t a b -> Lens s t a b
Optics.lensVL forall a b. (a -> b) -> a -> b
$ \Maybe (IxValue (InsOrdHashMap k a))
-> f (Maybe (IxValue (InsOrdHashMap k a)))
f InsOrdHashMap k a
m -> forall m. At m => Index m -> Lens' m (Maybe (IxValue m))
Lens.at Index (InsOrdHashMap k a)
k Maybe (IxValue (InsOrdHashMap k a))
-> f (Maybe (IxValue (InsOrdHashMap k a)))
f InsOrdHashMap k a
m
    {-# INLINE at #-}

#if !MIN_VERSION_optics_core(0,4,0)
instance (Eq k, Hashable k) => Optics.FunctorWithIndex k (InsOrdHashMap k) where
    imap = mapWithKey
instance (Eq k, Hashable k) => Optics.FoldableWithIndex k (InsOrdHashMap k) where
    ifoldMap = foldMapWithKey
    ifoldr   = foldrWithKey
instance (Eq k, Hashable k) => Optics.TraversableWithIndex k (InsOrdHashMap k) where
    itraverse = traverseWithKey
#endif

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

empty :: InsOrdHashMap k v
empty :: forall k v. InsOrdHashMap k v
empty = forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
0 forall k v. HashMap k v
HashMap.empty
{-# INLINABLE empty #-}

singleton :: Hashable k => k -> v -> InsOrdHashMap k v
singleton :: forall k v. Hashable k => k -> v -> InsOrdHashMap k v
singleton k
k v
v = forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
1 (forall k v. Hashable k => k -> v -> HashMap k v
HashMap.singleton k
k (forall a. Int -> a -> P a
P Int
0 v
v))
{-# INLINABLE singleton #-}

-------------------------------------------------------------------------------
-- Basic interface
-------------------------------------------------------------------------------

null :: InsOrdHashMap k v -> Bool
null :: forall k a. InsOrdHashMap k a -> Bool
null = forall k v. HashMap k v -> Bool
HashMap.null forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> HashMap k (P v)
getInsOrdHashMap
{-# INLINABLE null #-}

size :: InsOrdHashMap k v -> Int
size :: forall k v. InsOrdHashMap k v -> Int
size = forall k v. HashMap k v -> Int
HashMap.size forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> HashMap k (P v)
getInsOrdHashMap
{-# INLINABLE size #-}

member :: (Eq k, Hashable k) => k -> InsOrdHashMap k a -> Bool
member :: forall k a. (Eq k, Hashable k) => k -> InsOrdHashMap k a -> Bool
member k
k = forall k a. (Eq k, Hashable k) => k -> HashMap k a -> Bool
HashMap.member k
k forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> HashMap k (P v)
getInsOrdHashMap
{-# INLINABLE member #-}

lookup :: (Eq k, Hashable k) => k -> InsOrdHashMap k v -> Maybe v
lookup :: forall k v. (Eq k, Hashable k) => k -> InsOrdHashMap k v -> Maybe v
lookup k
k = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. P a -> a
getPV forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
HashMap.lookup k
k forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> HashMap k (P v)
getInsOrdHashMap
{-# INLINABLE lookup #-}

lookupDefault
    :: (Eq k, Hashable k)
    => v  -- ^ Default value to return.
    -> k -> InsOrdHashMap k v -> v
lookupDefault :: forall k v. (Eq k, Hashable k) => v -> k -> InsOrdHashMap k v -> v
lookupDefault v
def k
k InsOrdHashMap k v
m = forall a. a -> Maybe a -> a
fromMaybe v
def forall a b. (a -> b) -> a -> b
$ forall k v. (Eq k, Hashable k) => k -> InsOrdHashMap k v -> Maybe v
lookup k
k InsOrdHashMap k v
m
{-# INLINABLE lookupDefault #-}

delete :: (Eq k, Hashable k) => k -> InsOrdHashMap k v -> InsOrdHashMap k v
delete :: forall k v.
(Eq k, Hashable k) =>
k -> InsOrdHashMap k v -> InsOrdHashMap k v
delete k
k (InsOrdHashMap Int
i HashMap k (P v)
m) = forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall a b. (a -> b) -> a -> b
$ forall k v. (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
HashMap.delete k
k HashMap k (P v)
m
{-# INLINABLE delete #-}

insert :: (Eq k, Hashable k) => k -> v -> InsOrdHashMap k v -> InsOrdHashMap k v
insert :: forall k v.
(Eq k, Hashable k) =>
k -> v -> InsOrdHashMap k v -> InsOrdHashMap k v
insert = forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> InsOrdHashMap k v -> InsOrdHashMap k v
insertWith forall a b. a -> b -> a
const
{-# INLINABLE insert #-}

insertWith
    :: (Eq k, Hashable k)
    => (v -> v -> v) -> k -> v -> InsOrdHashMap k v -> InsOrdHashMap k v
insertWith :: forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> k -> v -> InsOrdHashMap k v -> InsOrdHashMap k v
insertWith v -> v -> v
f k
k v
v = forall k v.
(Eq k, Hashable k) =>
(Maybe v -> Maybe v) -> k -> InsOrdHashMap k v -> InsOrdHashMap k v
alter (forall a. a -> Maybe a
Just forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall b a. b -> (a -> b) -> Maybe a -> b
maybe v
v (v -> v -> v
f v
v)) k
k
{-# INLINABLE insertWith #-}

adjust
    :: (Eq k, Hashable k)
    => (v -> v) -> k -> InsOrdHashMap k v -> InsOrdHashMap k v
adjust :: forall k v.
(Eq k, Hashable k) =>
(v -> v) -> k -> InsOrdHashMap k v -> InsOrdHashMap k v
adjust v -> v
f = forall k v.
(Eq k, Hashable k) =>
(Maybe v -> Maybe v) -> k -> InsOrdHashMap k v -> InsOrdHashMap k v
alter (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap v -> v
f)
{-# INLINABLE adjust #-}

update
    :: (Eq k, Hashable k)
    => (a -> Maybe a) -> k -> InsOrdHashMap k a -> InsOrdHashMap k a
update :: forall k a.
(Eq k, Hashable k) =>
(a -> Maybe a) -> k -> InsOrdHashMap k a -> InsOrdHashMap k a
update a -> Maybe a
f = forall k v.
(Eq k, Hashable k) =>
(Maybe v -> Maybe v) -> k -> InsOrdHashMap k v -> InsOrdHashMap k v
alter (forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Maybe a
f)
{-# INLINABLE update #-}

alter
    :: (Eq k, Hashable k)
    => (Maybe v -> Maybe v) -> k -> InsOrdHashMap k v -> InsOrdHashMap k v
alter :: forall k v.
(Eq k, Hashable k) =>
(Maybe v -> Maybe v) -> k -> InsOrdHashMap k v -> InsOrdHashMap k v
alter Maybe v -> Maybe v
f k
k insm :: InsOrdHashMap k v
insm@(InsOrdHashMap Int
j HashMap k (P v)
m) =
    case forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
HashMap.lookup k
k HashMap k (P v)
m of
        Maybe (P v)
Nothing       -> case Maybe v -> Maybe v
f forall a. Maybe a
Nothing of
            Maybe v
Nothing   -> InsOrdHashMap k v
insm
            Just v
v    -> forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap (Int
j forall a. Num a => a -> a -> a
+ Int
1) (forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HashMap.insert k
k (forall a. Int -> a -> P a
P Int
j v
v) HashMap k (P v)
m)
        Just (P Int
i v
v)  -> case Maybe v -> Maybe v
f (forall a. a -> Maybe a
Just v
v) of
            Maybe v
Nothing   -> forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
j (forall k v. (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
HashMap.delete k
k HashMap k (P v)
m)
            Just v
u    -> forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
j (forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HashMap.insert k
k (forall a. Int -> a -> P a
P Int
i v
u) HashMap k (P v)
m)
{-# INLINABLE alter #-}

-------------------------------------------------------------------------------
-- Combine
-------------------------------------------------------------------------------

-- | The union of two maps.  If a key occurs in both maps,
-- the provided function (first argument) will be used to compute the result.
--
-- Ordered traversal will go thru keys in the first map first.
unionWith
    :: (Eq k, Hashable k)
    => (v -> v -> v)
    -> InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
unionWith :: forall k v.
(Eq k, Hashable k) =>
(v -> v -> v)
-> InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
unionWith v -> v -> v
f (InsOrdHashMap Int
i HashMap k (P v)
a) (InsOrdHashMap Int
j HashMap k (P v)
b) =
    HashMap k (P v) -> InsOrdHashMap k v
mk forall a b. (a -> b) -> a -> b
$ forall k v.
(Eq k, Hashable k) =>
(v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
HashMap.unionWith P v -> P v -> P v
f' HashMap k (P v)
a HashMap k (P v)
b'
  where
    -- the threshold is arbitrary, it meant to amortise need for packing of indices
    mk :: HashMap k (P v) -> InsOrdHashMap k v
mk | Int
i forall a. Ord a => a -> a -> Bool
> Int
0xfffff Bool -> Bool -> Bool
|| Int
j forall a. Ord a => a -> a -> Bool
>= Int
0xfffff = forall k v. HashMap k (P v) -> InsOrdHashMap k v
fromHashMapP
       | Bool
otherwise                   = forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap (Int
i forall a. Num a => a -> a -> a
+ Int
j)
    b' :: HashMap k (P v)
b' = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a. Int -> P a -> P a
incPK Int
i) HashMap k (P v)
b
    f' :: P v -> P v -> P v
f' (P Int
ii v
x) (P Int
_ v
y) = forall a. Int -> a -> P a
P Int
ii (v -> v -> v
f v
x v
y)

unionWithKey
    :: (Eq k, Hashable k)
    => (k -> v -> v -> v)
    -> InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
unionWithKey :: forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v)
-> InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
unionWithKey k -> v -> v -> v
f (InsOrdHashMap Int
i HashMap k (P v)
a) (InsOrdHashMap Int
j HashMap k (P v)
b) =
    forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap (Int
i forall a. Num a => a -> a -> a
+ Int
j) forall a b. (a -> b) -> a -> b
$ forall k v.
(Eq k, Hashable k) =>
(k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
HashMap.unionWithKey k -> P v -> P v -> P v
f' HashMap k (P v)
a HashMap k (P v)
b'
  where
    b' :: HashMap k (P v)
b' = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a. Int -> P a -> P a
incPK Int
i) HashMap k (P v)
b
    f' :: k -> P v -> P v -> P v
f' k
k (P Int
ii v
x) (P Int
_ v
y) = forall a. Int -> a -> P a
P Int
ii (k -> v -> v -> v
f k
k v
x v
y)

union
    :: (Eq k, Hashable k)
    => InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
union :: forall k v.
(Eq k, Hashable k) =>
InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
union = forall k v.
(Eq k, Hashable k) =>
(v -> v -> v)
-> InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
unionWith forall a b. a -> b -> a
const

unions
    :: (Eq k, Hashable k, Foldable f)
    => f (InsOrdHashMap k v) -> InsOrdHashMap k v
unions :: forall k (f :: * -> *) v.
(Eq k, Hashable k, Foldable f) =>
f (InsOrdHashMap k v) -> InsOrdHashMap k v
unions = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' forall k v.
(Eq k, Hashable k) =>
InsOrdHashMap k v -> InsOrdHashMap k v -> InsOrdHashMap k v
union forall k v. InsOrdHashMap k v
empty

-------------------------------------------------------------------------------
-- Transformations
-------------------------------------------------------------------------------

-- | Order preserving mapping of keys.
mapKeys :: (Eq k', Hashable k') => (k -> k') -> InsOrdHashMap k v -> InsOrdHashMap k' v
mapKeys :: forall k' k v.
(Eq k', Hashable k') =>
(k -> k') -> InsOrdHashMap k v -> InsOrdHashMap k' v
mapKeys k -> k'
f (InsOrdHashMap Int
i HashMap k (P v)
m) = forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall a b. (a -> b) -> a -> b
$
    forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HashMap.fromList forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first k -> k'
f) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. HashMap k v -> [(k, v)]
HashMap.toList forall a b. (a -> b) -> a -> b
$ HashMap k (P v)
m

traverseKeys
    :: (Eq k', Hashable k', Applicative f)
    => (k -> f k') -> InsOrdHashMap k v -> f (InsOrdHashMap k' v)
traverseKeys :: forall k' (f :: * -> *) k v.
(Eq k', Hashable k', Applicative f) =>
(k -> f k') -> InsOrdHashMap k v -> f (InsOrdHashMap k' v)
traverseKeys k -> f k'
f (InsOrdHashMap Int
i HashMap k (P v)
m) = forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HashMap.fromList forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
    (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall s t a b. Field1 s t a b => Lens s t a b
_1) k -> f k'
f (forall k v. HashMap k v -> [(k, v)]
HashMap.toList HashMap k (P v)
m)

map :: (v1 -> v2) -> InsOrdHashMap k v1 -> InsOrdHashMap k v2
map :: forall v1 v2 k.
(v1 -> v2) -> InsOrdHashMap k v1 -> InsOrdHashMap k v2
map = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap

mapWithKey :: (k -> v1 -> v2) -> InsOrdHashMap k v1 -> InsOrdHashMap k v2
mapWithKey :: forall k v1 v2.
(k -> v1 -> v2) -> InsOrdHashMap k v1 -> InsOrdHashMap k v2
mapWithKey k -> v1 -> v2
f (InsOrdHashMap Int
i HashMap k (P v1)
m) =
    forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall a b. (a -> b) -> a -> b
$ forall k v1 v2. (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
HashMap.mapWithKey k -> P v1 -> P v2
f' HashMap k (P v1)
m
  where
    f' :: k -> P v1 -> P v2
f' k
k (P Int
j v1
x) = forall a. Int -> a -> P a
P Int
j (k -> v1 -> v2
f k
k v1
x)

foldMapWithKey :: Monoid m => (k -> a -> m) -> InsOrdHashMap k a -> m
foldMapWithKey :: forall m k a. Monoid m => (k -> a -> m) -> InsOrdHashMap k a -> m
foldMapWithKey k -> a -> m
f = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry k -> a -> m
f) forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> [(k, v)]
toList

traverseWithKey :: Applicative f => (k -> a -> f b) -> InsOrdHashMap k a -> f (InsOrdHashMap k b)
traverseWithKey :: forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> InsOrdHashMap k a -> f (InsOrdHashMap k b)
traverseWithKey k -> a -> f b
f (InsOrdHashMap Int
n HashMap k (P a)
m) = forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
n forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) a. Applicative f => SortedAp f a -> f a
retractSortedAp
    (forall (f :: * -> *) k v1 v2.
Applicative f =>
(k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)
HashMap.traverseWithKey (\k
k (P Int
i a
v) -> forall (f :: * -> *) a. Int -> f a -> SortedAp f a
liftSortedAp Int
i (forall a. Int -> a -> P a
P Int
i forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> a -> f b
f k
k a
v)) HashMap k (P a)
m)

-------------------------------------------------------------------------------
-- Unordered
-------------------------------------------------------------------------------

-- | More efficient than 'foldMap', when folding in insertion order is not important.
unorderedFoldMap :: Monoid m => (a -> m) -> InsOrdHashMap k a -> m
unorderedFoldMap :: forall m a k. Monoid m => (a -> m) -> InsOrdHashMap k a -> m
unorderedFoldMap a -> m
f (InsOrdHashMap Int
_ HashMap k (P a)
m) = forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (a -> m
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. P a -> a
getPV) HashMap k (P a)
m

-- | More efficient than 'foldMapWithKey', when folding in insertion order is not important.
unorderedFoldMapWithKey :: Monoid m => (k -> a -> m) -> InsOrdHashMap k a -> m
unorderedFoldMapWithKey :: forall m k a. Monoid m => (k -> a -> m) -> InsOrdHashMap k a -> m
unorderedFoldMapWithKey k -> a -> m
f InsOrdHashMap k a
m =
    forall {k} a (b :: k). Const a b -> a
getConst (forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> InsOrdHashMap k a -> f (InsOrdHashMap k b)
unorderedTraverseWithKey (\k
k a
a -> forall {k} a (b :: k). a -> Const a b
Const (k -> a -> m
f k
k a
a)) InsOrdHashMap k a
m)

-- | More efficient than 'traverse', when traversing in insertion order is not important.
unorderedTraverse :: Applicative f => (a -> f b) -> InsOrdHashMap k a -> f (InsOrdHashMap k b)
unorderedTraverse :: forall (f :: * -> *) a b k.
Applicative f =>
(a -> f b) -> InsOrdHashMap k a -> f (InsOrdHashMap k b)
unorderedTraverse a -> f b
f (InsOrdHashMap Int
i HashMap k (P a)
m) =
    forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse) a -> f b
f HashMap k (P a)
m

-- | More efficient than `traverseWithKey`, when traversing in insertion order is not important.
unorderedTraverseWithKey :: Applicative f => (k -> a -> f b) -> InsOrdHashMap k a -> f (InsOrdHashMap k b)
unorderedTraverseWithKey :: forall (f :: * -> *) k a b.
Applicative f =>
(k -> a -> f b) -> InsOrdHashMap k a -> f (InsOrdHashMap k b)
unorderedTraverseWithKey k -> a -> f b
f (InsOrdHashMap Int
i HashMap k (P a)
m) =
    forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) k v1 v2.
Applicative f =>
(k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)
HashMap.traverseWithKey k -> P a -> f (P b)
f' HashMap k (P a)
m
  where
    f' :: k -> P a -> f (P b)
f' k
k (P Int
j a
x) = forall a. Int -> a -> P a
P Int
j forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> a -> f b
f k
k a
x

-------------------------------------------------------------------------------
-- Difference and intersection
-------------------------------------------------------------------------------

difference
    :: (Eq k, Hashable k)
    => InsOrdHashMap k v -> InsOrdHashMap k w -> InsOrdHashMap k v
difference :: forall k v w.
(Eq k, Hashable k) =>
InsOrdHashMap k v -> InsOrdHashMap k w -> InsOrdHashMap k v
difference (InsOrdHashMap Int
i HashMap k (P v)
a) (InsOrdHashMap Int
_ HashMap k (P w)
b) =
    forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall a b. (a -> b) -> a -> b
$ forall k v w.
(Eq k, Hashable k) =>
HashMap k v -> HashMap k w -> HashMap k v
HashMap.difference HashMap k (P v)
a HashMap k (P w)
b

intersection
    :: (Eq k, Hashable k)
    => InsOrdHashMap k v -> InsOrdHashMap k w -> InsOrdHashMap k v
intersection :: forall k v w.
(Eq k, Hashable k) =>
InsOrdHashMap k v -> InsOrdHashMap k w -> InsOrdHashMap k v
intersection = forall k v1 v2 v3.
(Eq k, Hashable k) =>
(v1 -> v2 -> v3)
-> InsOrdHashMap k v1 -> InsOrdHashMap k v2 -> InsOrdHashMap k v3
intersectionWith forall a b. a -> b -> a
const

intersectionWith
    :: (Eq k, Hashable k)
    => (v1 -> v2 -> v3)
    -> InsOrdHashMap k v1 -> InsOrdHashMap k v2 -> InsOrdHashMap k v3
intersectionWith :: forall k v1 v2 v3.
(Eq k, Hashable k) =>
(v1 -> v2 -> v3)
-> InsOrdHashMap k v1 -> InsOrdHashMap k v2 -> InsOrdHashMap k v3
intersectionWith v1 -> v2 -> v3
f = forall k v1 v2 v3.
(Eq k, Hashable k) =>
(k -> v1 -> v2 -> v3)
-> InsOrdHashMap k v1 -> InsOrdHashMap k v2 -> InsOrdHashMap k v3
intersectionWithKey (\k
_ -> v1 -> v2 -> v3
f)

intersectionWithKey
    :: (Eq k, Hashable k)
    => (k -> v1 -> v2 -> v3)
    -> InsOrdHashMap k v1 -> InsOrdHashMap k v2 -> InsOrdHashMap k v3
intersectionWithKey :: forall k v1 v2 v3.
(Eq k, Hashable k) =>
(k -> v1 -> v2 -> v3)
-> InsOrdHashMap k v1 -> InsOrdHashMap k v2 -> InsOrdHashMap k v3
intersectionWithKey k -> v1 -> v2 -> v3
f (InsOrdHashMap Int
i HashMap k (P v1)
a) (InsOrdHashMap Int
_ HashMap k (P v2)
b) =
    forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall a b. (a -> b) -> a -> b
$ forall k v1 v2 v3.
(Eq k, Hashable k) =>
(k -> v1 -> v2 -> v3)
-> HashMap k v1 -> HashMap k v2 -> HashMap k v3
HashMap.intersectionWithKey k -> P v1 -> P v2 -> P v3
f' HashMap k (P v1)
a HashMap k (P v2)
b
  where
    f' :: k -> P v1 -> P v2 -> P v3
f' k
k (P Int
j v1
x) (P Int
_ v2
y) = forall a. Int -> a -> P a
P Int
j (k -> v1 -> v2 -> v3
f k
k v1
x v2
y)

-------------------------------------------------------------------------------
-- Folds
-------------------------------------------------------------------------------

foldl' :: (a -> v -> a) -> a -> InsOrdHashMap k v -> a
foldl' :: forall a v k. (a -> v -> a) -> a -> InsOrdHashMap k v -> a
foldl' a -> v -> a
f a
x = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' a -> (k, v) -> a
f' a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> [(k, v)]
toList
  where
    f' :: a -> (k, v) -> a
f' a
a (k
_, v
v) = a -> v -> a
f a
a v
v

foldlWithKey' :: (a -> k -> v -> a) -> a -> InsOrdHashMap k v -> a
foldlWithKey' :: forall a k v. (a -> k -> v -> a) -> a -> InsOrdHashMap k v -> a
foldlWithKey' a -> k -> v -> a
f a
x = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
F.foldl' a -> (k, v) -> a
f' a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> [(k, v)]
toList
  where
    f' :: a -> (k, v) -> a
f' a
a (k
k, v
v) = a -> k -> v -> a
f a
a k
k v
v

foldr :: (v -> a -> a) -> a -> InsOrdHashMap k v -> a
foldr :: forall v a k. (v -> a -> a) -> a -> InsOrdHashMap k v -> a
foldr v -> a -> a
f a
x = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
F.foldr (k, v) -> a -> a
f' a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> [(k, v)]
toList
  where
    f' :: (k, v) -> a -> a
f' (k
_, v
v) a
a = v -> a -> a
f v
v a
a

foldrWithKey :: (k -> v -> a -> a) -> a -> InsOrdHashMap k v -> a
foldrWithKey :: forall k v a. (k -> v -> a -> a) -> a -> InsOrdHashMap k v -> a
foldrWithKey k -> v -> a -> a
f a
x = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
F.foldr (k, v) -> a -> a
f' a
x forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> [(k, v)]
toList
  where
    f' :: (k, v) -> a -> a
f' (k
k, v
v) a
a = k -> v -> a -> a
f k
k v
v a
a

-------------------------------------------------------------------------------
-- Filter
-------------------------------------------------------------------------------

filter :: (v -> Bool) -> InsOrdHashMap k v -> InsOrdHashMap k v
filter :: forall v k. (v -> Bool) -> InsOrdHashMap k v -> InsOrdHashMap k v
filter v -> Bool
f (InsOrdHashMap Int
i HashMap k (P v)
m) =
    forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall a b. (a -> b) -> a -> b
$ forall v k. (v -> Bool) -> HashMap k v -> HashMap k v
HashMap.filter (v -> Bool
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. P a -> a
getPV) HashMap k (P v)
m

filterWithKey :: (k -> v -> Bool) -> InsOrdHashMap k v -> InsOrdHashMap k v
filterWithKey :: forall k v.
(k -> v -> Bool) -> InsOrdHashMap k v -> InsOrdHashMap k v
filterWithKey k -> v -> Bool
f (InsOrdHashMap Int
i HashMap k (P v)
m) =
    forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall a b. (a -> b) -> a -> b
$ forall k v. (k -> v -> Bool) -> HashMap k v -> HashMap k v
HashMap.filterWithKey k -> P v -> Bool
f' HashMap k (P v)
m
  where
    f' :: k -> P v -> Bool
f' k
k (P Int
_ v
x) = k -> v -> Bool
f k
k v
x

mapMaybe :: (v1 -> Maybe v2) -> InsOrdHashMap k v1 -> InsOrdHashMap k v2
mapMaybe :: forall v1 v2 k.
(v1 -> Maybe v2) -> InsOrdHashMap k v1 -> InsOrdHashMap k v2
mapMaybe v1 -> Maybe v2
f (InsOrdHashMap Int
i HashMap k (P v1)
m) = forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall a b. (a -> b) -> a -> b
$ forall v1 v2 k. (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
HashMap.mapMaybe P v1 -> Maybe (P v2)
f' HashMap k (P v1)
m
  where
    f' :: P v1 -> Maybe (P v2)
f' (P Int
j v1
x) = forall a. Int -> a -> P a
P Int
j forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> v1 -> Maybe v2
f v1
x

mapMaybeWithKey :: (k -> v1 -> Maybe v2) -> InsOrdHashMap k v1 -> InsOrdHashMap k v2
mapMaybeWithKey :: forall k v1 v2.
(k -> v1 -> Maybe v2) -> InsOrdHashMap k v1 -> InsOrdHashMap k v2
mapMaybeWithKey k -> v1 -> Maybe v2
f (InsOrdHashMap Int
i HashMap k (P v1)
m) =
    forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i forall a b. (a -> b) -> a -> b
$ forall k v1 v2.
(k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
HashMap.mapMaybeWithKey k -> P v1 -> Maybe (P v2)
f' HashMap k (P v1)
m
  where
    f' :: k -> P v1 -> Maybe (P v2)
f' k
k (P Int
j v1
x) = forall a. Int -> a -> P a
P Int
j forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> k -> v1 -> Maybe v2
f k
k v1
x

-------------------------------------------------------------------------------
-- Conversions
-------------------------------------------------------------------------------

keys :: InsOrdHashMap k v -> [k]
keys :: forall k v. InsOrdHashMap k v -> [k]
keys = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> a
fst forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> [(k, v)]
toList
{-# INLINABLE keys #-}

elems :: InsOrdHashMap k v -> [v]
elems :: forall k a. InsOrdHashMap k a -> [a]
elems = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> [(k, v)]
toList
{-# INLINABLE elems #-}

fromList :: forall k v. (Eq k, Hashable k) => [(k, v)] -> InsOrdHashMap k v
fromList :: forall k v. (Eq k, Hashable k) => [(k, v)] -> InsOrdHashMap k v
fromList
    = ([(k, P v)], Int) -> InsOrdHashMap k v
mk
    forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (a -> b -> c) -> b -> a -> c
flip forall s a. State s a -> s -> (a, s)
runState Int
0
    forall b c a. (b -> c) -> (a -> b) -> a -> c
. (forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall s t a b. Field2 s t a b => Lens s t a b
_2) forall a. a -> State Int (P a)
newP
  where
    mk :: ([(k, P v)], Int) -> InsOrdHashMap k v
    mk :: ([(k, P v)], Int) -> InsOrdHashMap k v
mk ([(k, P v)]
m, Int
i) = forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i (forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HashMap.fromList [(k, P v)]
m)

toList :: InsOrdHashMap k v -> [(k, v)]
toList :: forall k v. InsOrdHashMap k v -> [(k, v)]
toList
    = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second forall a. P a -> a
getPV)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (forall a. P a -> Int
getPK forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> b
snd))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. HashMap k v -> [(k, v)]
HashMap.toList
    forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> HashMap k (P v)
getInsOrdHashMap

toRevList :: InsOrdHashMap k v -> [(k, v)]
toRevList :: forall k v. InsOrdHashMap k v -> [(k, v)]
toRevList
    = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second forall a. P a -> a
getPV)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (forall a b c. (a -> b -> c) -> b -> a -> c
flip forall a b. (a -> b) -> a -> b
$ forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (forall a. P a -> Int
getPK forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. (a, b) -> b
snd))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. HashMap k v -> [(k, v)]
HashMap.toList
    forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k v. InsOrdHashMap k v -> HashMap k (P v)
getInsOrdHashMap

fromHashMap :: HashMap k v -> InsOrdHashMap k v
fromHashMap :: forall k v. HashMap k v -> InsOrdHashMap k v
fromHashMap = forall {k} {v}. (HashMap k (P v), Int) -> InsOrdHashMap k v
mk forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (a -> b -> c) -> b -> a -> c
flip forall s a. State s a -> s -> (a, s)
runState Int
0 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse forall a. a -> State Int (P a)
newP
  where
    mk :: (HashMap k (P v), Int) -> InsOrdHashMap k v
mk (HashMap k (P v)
m, Int
i) = forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i HashMap k (P v)
m

toHashMap :: InsOrdHashMap k v -> HashMap k v
toHashMap :: forall k v. InsOrdHashMap k v -> HashMap k v
toHashMap (InsOrdHashMap Int
_ HashMap k (P v)
m) = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a. P a -> a
getPV HashMap k (P v)
m

-------------------------------------------------------------------------------
-- Internal
-------------------------------------------------------------------------------

-- TODO: more efficient way is to do two traversals
-- - collect the indexes
-- - pack the indexes (Map old new)
-- - traverse second time, changing the indexes
fromHashMapP :: HashMap k (P v) -> InsOrdHashMap k v
fromHashMapP :: forall k v. HashMap k (P v) -> InsOrdHashMap k v
fromHashMapP = forall {k} {v}. (HashMap k (P v), Int) -> InsOrdHashMap k v
mk forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b c. (a -> b -> c) -> b -> a -> c
flip forall s a. State s a -> s -> (a, s)
runState Int
0 forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a. Applicative f => SortedAp f a -> f a
retractSortedAp forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse forall {a}. P a -> SortedAp (StateT Int Identity) (P a)
f
  where
    mk :: (HashMap k (P v), Int) -> InsOrdHashMap k v
mk (HashMap k (P v)
m, Int
i) = forall k v. Int -> HashMap k (P v) -> InsOrdHashMap k v
InsOrdHashMap Int
i HashMap k (P v)
m
    f :: P a -> SortedAp (StateT Int Identity) (P a)
f (P Int
i a
v) = forall (f :: * -> *) a. Int -> f a -> SortedAp f a
liftSortedAp Int
i (forall a. a -> State Int (P a)
newP a
v)

-- | Test if the internal map structure is valid.
valid :: InsOrdHashMap k v -> Bool
valid :: forall k a. InsOrdHashMap k a -> Bool
valid (InsOrdHashMap Int
i HashMap k (P v)
m) = Bool
indexesDistinct Bool -> Bool -> Bool
&& Bool
indexesSmaller
  where
    indexes :: [Int]
    indexes :: [Int]
indexes = forall a. P a -> Int
getPK forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall k v. HashMap k v -> [v]
HashMap.elems HashMap k (P v)
m

    indexesDistinct :: Bool
indexesDistinct = [Int]
indexes forall a. Eq a => a -> a -> Bool
== forall a. Eq a => [a] -> [a]
nub [Int]
indexes
    indexesSmaller :: Bool
indexesSmaller  = forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (forall a. Ord a => a -> a -> Bool
< Int
i) [Int]
indexes

newP :: a -> State Int (P a)
newP :: forall a. a -> State Int (P a)
newP a
x = forall (m :: * -> *) s a. Monad m => (s -> (a, s)) -> StateT s m a
state forall a b. (a -> b) -> a -> b
$ \Int
s -> (forall a. Int -> a -> P a
P Int
s a
x, Int
s forall a. Num a => a -> a -> a
+ Int
1)