{-# LANGUAGE CPP                   #-}
{-# LANGUAGE DeriveDataTypeable    #-}
{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE GADTs                 #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables   #-}
{-# LANGUAGE Trustworthy           #-}
{-# LANGUAGE TypeFamilies          #-}
-- | 'InsOrdHashSet' is like 'HashSet', but it folds in insertion order.
--
-- This module interface mimics "Data.HashSet", with some additions.
module Data.HashSet.InsOrd (
    InsOrdHashSet,
    -- * Construction
    empty,
    singleton,
    -- * Basic interface
    null,
    size,
    member,
    insert,
    delete,
    -- * Combine
    union,
    -- * Transformations
    map,
    -- ** Unordered
    -- * Difference and intersection
    difference,
    intersection,
    -- * Folds
    -- ** Unordered
    -- * Filter
    filter,
    -- * Conversions
    toList,
    fromList,
    toHashSet,
    fromHashSet,
    -- * Lenses
    hashSet,
    -- * Debugging
    valid,
    )where

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

import Control.Arrow                   (first)
import Control.DeepSeq                 (NFData (..))
import Data.Data                       (Data, Typeable)
import Data.Foldable                   (Foldable (foldMap), all)
import Data.Hashable                   (Hashable (..))
import Data.List                       (nub, sortBy)
import Data.Monoid                     (Monoid (..))
import Data.Ord                        (comparing)
import Data.Semigroup                  (Semigroup (..))
import Data.Traversable                (Traversable (traverse))
import Text.ParserCombinators.ReadPrec (prec)
import Text.Read
       (Lexeme (..), Read (..), lexP, parens, readListPrecDefault)
import Text.Show                       (Show (..), showParen, showString)

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

import qualified Data.Aeson as A
import qualified Control.Lens as Lens
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           Data.HashSet        (HashSet)
import qualified Data.HashSet        as HashSet

import qualified Data.Foldable
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

-------------------------------------------------------------------------------
-- InsOrdHashSet
-------------------------------------------------------------------------------

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

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

-- | @since 0.2.5
instance NFData k => NFData (InsOrdHashSet k) where
    rnf :: InsOrdHashSet k -> ()
rnf (InsOrdHashSet Int
_ HashMap k Int
hs) = forall a. NFData a => a -> ()
rnf HashMap k Int
hs

#if MIN_VERSION_deepseq(1,4,3)
-- | @since 0.2.5
instance NF.NFData1 InsOrdHashSet where
    liftRnf :: forall a. (a -> ()) -> InsOrdHashSet a -> ()
liftRnf a -> ()
rnf1 (InsOrdHashSet Int
_ HashMap a Int
m) = forall (p :: * -> * -> *) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
NF.liftRnf2 a -> ()
rnf1 forall a. NFData a => a -> ()
rnf HashMap a Int
m
#endif

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

instance Show k => Show (InsOrdHashSet k) where
    showsPrec :: Int -> InsOrdHashSet k -> ShowS
showsPrec Int
d InsOrdHashSet k
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. InsOrdHashSet k -> [k]
toList InsOrdHashSet k
m)

instance (Eq k, Hashable k, Read k) => Read (InsOrdHashSet k) where
    readPrec :: ReadPrec (InsOrdHashSet k)
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]
xs <- forall a. Read a => ReadPrec a
readPrec
      forall (m :: * -> *) a. Monad m => a -> m a
return (forall k. (Eq k, Hashable k) => [k] -> InsOrdHashSet k
fromList [k]
xs)

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

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

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

instance Foldable InsOrdHashSet where
    -- in newer base only
    -- length = length . getInsOrdHashSet
    foldMap :: forall m a. Monoid m => (a -> m) -> InsOrdHashSet 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 k. InsOrdHashSet k -> [k]
toList

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

-- | @'hashWithSalt' salt . 'toHashSet' = 'hashWithSalt' salt@.
instance Hashable k => Hashable (InsOrdHashSet k) where
    hashWithSalt :: Int -> InsOrdHashSet k -> Int
hashWithSalt Int
salt (InsOrdHashSet Int
_ HashMap k Int
m) =
        forall a. Hashable a => Int -> a -> Int
hashWithSalt Int
salt HashMap k Int
m

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

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

instance A.ToJSON a => A.ToJSON (InsOrdHashSet a) where
    toJSON :: InsOrdHashSet a -> Value
toJSON     = forall a. ToJSON a => a -> Value
A.toJSON forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k. InsOrdHashSet k -> [k]
toList
    toEncoding :: InsOrdHashSet a -> Encoding
toEncoding = forall a. ToJSON a => a -> Encoding
A.toEncoding forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k. InsOrdHashSet k -> [k]
toList

instance (Eq a, Hashable a, A.FromJSON a) => A.FromJSON (InsOrdHashSet a) where
    parseJSON :: Value -> Parser (InsOrdHashSet a)
parseJSON Value
v = forall k. (Eq k, Hashable k) => [k] -> InsOrdHashSet k
fromList forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a. FromJSON a => Value -> Parser a
A.parseJSON Value
v

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

type instance Index (InsOrdHashSet a) = a
type instance IxValue (InsOrdHashSet a) = ()

instance (Eq k, Hashable k) => Ixed (InsOrdHashSet k) where
    ix :: Index (InsOrdHashSet k)
-> Traversal' (InsOrdHashSet k) (IxValue (InsOrdHashSet k))
ix Index (InsOrdHashSet k)
k IxValue (InsOrdHashSet k) -> f (IxValue (InsOrdHashSet k))
f (InsOrdHashSet Int
i HashMap k Int
m) = forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Index (InsOrdHashSet k)
k (\IxValue (HashMap k Int)
j -> IxValue (HashMap k Int)
j forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ IxValue (InsOrdHashSet k) -> f (IxValue (InsOrdHashSet k))
f ()) HashMap k Int
m
    {-# INLINE ix #-}

instance (Eq k, Hashable k) => At (InsOrdHashSet k) where
  at :: Index (InsOrdHashSet k)
-> Lens' (InsOrdHashSet k) (Maybe (IxValue (InsOrdHashSet k)))
at Index (InsOrdHashSet k)
k Maybe (IxValue (InsOrdHashSet k))
-> f (Maybe (IxValue (InsOrdHashSet k)))
f InsOrdHashSet k
m = Maybe (IxValue (InsOrdHashSet k))
-> f (Maybe (IxValue (InsOrdHashSet k)))
f Maybe ()
mv forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \Maybe ()
r -> case Maybe ()
r of
    Maybe ()
Nothing -> forall b a. b -> (a -> b) -> Maybe a -> b
maybe InsOrdHashSet k
m (forall a b. a -> b -> a
const (forall k.
(Eq k, Hashable k) =>
k -> InsOrdHashSet k -> InsOrdHashSet k
delete Index (InsOrdHashSet k)
k InsOrdHashSet k
m)) Maybe ()
mv
    Just () -> forall k.
(Eq k, Hashable k) =>
k -> InsOrdHashSet k -> InsOrdHashSet k
insert Index (InsOrdHashSet k)
k InsOrdHashSet k
m
    where mv :: Maybe ()
mv = if forall k. (Eq k, Hashable k) => k -> InsOrdHashSet k -> Bool
member Index (InsOrdHashSet k)
k InsOrdHashSet k
m then forall a. a -> Maybe a
Just () else forall a. Maybe a
Nothing
  {-# INLINE at #-}

instance (Eq a, Hashable a) => Contains (InsOrdHashSet a) where
  contains :: Index (InsOrdHashSet a) -> Lens' (InsOrdHashSet a) Bool
contains Index (InsOrdHashSet a)
k Bool -> f Bool
f InsOrdHashSet a
s = Bool -> f Bool
f (forall k. (Eq k, Hashable k) => k -> InsOrdHashSet k -> Bool
member Index (InsOrdHashSet a)
k InsOrdHashSet a
s) forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \Bool
b ->
    if Bool
b then forall k.
(Eq k, Hashable k) =>
k -> InsOrdHashSet k -> InsOrdHashSet k
insert Index (InsOrdHashSet a)
k InsOrdHashSet a
s else forall k.
(Eq k, Hashable k) =>
k -> InsOrdHashSet k -> InsOrdHashSet k
delete Index (InsOrdHashSet a)
k InsOrdHashSet a
s
  {-# INLINE contains #-}

-- | This is a slight lie, as roundtrip doesn't preserve ordering.
hashSet :: Iso' (InsOrdHashSet a) (HashSet a)
hashSet :: forall a. Iso' (InsOrdHashSet a) (HashSet a)
hashSet = forall s a b t. (s -> a) -> (b -> t) -> Iso s t a b
iso forall k. InsOrdHashSet k -> HashSet k
toHashSet forall k. HashSet k -> InsOrdHashSet k
fromHashSet

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

type instance Optics.Index (InsOrdHashSet a) = a
type instance Optics.IxValue (InsOrdHashSet a) = ()

instance (Eq k, Hashable k) => Optics.Ixed (InsOrdHashSet k) where
    ix :: Index (InsOrdHashSet k)
-> Optic'
     (IxKind (InsOrdHashSet k))
     NoIx
     (InsOrdHashSet k)
     (IxValue (InsOrdHashSet k))
ix Index (InsOrdHashSet k)
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 (InsOrdHashSet k) -> f (IxValue (InsOrdHashSet k))
f (InsOrdHashSet Int
i HashMap k Int
m) ->
      forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
#if MIN_VERSION_optics_core(0,3,0)
          forall k (f :: * -> *) (is :: IxList) s t a b.
(Is k An_AffineTraversal, Functor f) =>
Optic k is s t a b
-> (forall r. r -> f r) -> (a -> f b) -> s -> f t
Optics.atraverseOf
#else
          Optics.toAtraversalVL
#endif
          (forall m. Ixed m => Index m -> Optic' (IxKind m) NoIx m (IxValue m)
Optics.ix Index (InsOrdHashSet k)
k) forall r. r -> f r
point (\Int
j -> Int
j forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ IxValue (InsOrdHashSet k) -> f (IxValue (InsOrdHashSet k))
f ()) HashMap k Int
m
    {-# INLINE ix #-}

instance (Eq k, Hashable k) => Optics.At (InsOrdHashSet k) where
    at :: Index (InsOrdHashSet k)
-> Lens' (InsOrdHashSet k) (Maybe (IxValue (InsOrdHashSet k)))
at Index (InsOrdHashSet k)
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 (InsOrdHashSet k))
-> f (Maybe (IxValue (InsOrdHashSet k)))
f InsOrdHashSet k
m -> forall m. At m => Index m -> Lens' m (Maybe (IxValue m))
Lens.at Index (InsOrdHashSet k)
k Maybe (IxValue (InsOrdHashSet k))
-> f (Maybe (IxValue (InsOrdHashSet k)))
f InsOrdHashSet k
m
    {-# INLINE at #-}

instance (Eq a, Hashable a) => Optics.Contains (InsOrdHashSet a) where
    contains :: Index (InsOrdHashSet a) -> Lens' (InsOrdHashSet a) Bool
contains Index (InsOrdHashSet 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
$ \Bool -> f Bool
f InsOrdHashSet a
s -> forall m. Contains m => Index m -> Lens' m Bool
Lens.contains Index (InsOrdHashSet a)
k Bool -> f Bool
f InsOrdHashSet a
s
    {-# INLINE contains #-}

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

empty :: InsOrdHashSet k
empty :: forall k. InsOrdHashSet k
empty = forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
0 forall k v. HashMap k v
HashMap.empty
{-# INLINABLE empty #-}

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

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

null :: InsOrdHashSet k -> Bool
null :: forall a. InsOrdHashSet a -> Bool
null = forall k v. HashMap k v -> Bool
HashMap.null forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall k. InsOrdHashSet k -> HashMap k Int
getInsOrdHashSet
{-# INLINABLE null #-}

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

member :: (Eq k, Hashable k) => k -> InsOrdHashSet k -> Bool
member :: forall k. (Eq k, Hashable k) => k -> InsOrdHashSet k -> 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. InsOrdHashSet k -> HashMap k Int
getInsOrdHashSet
{-# INLINABLE member #-}

insert :: (Eq k, Hashable k) => k -> InsOrdHashSet k -> InsOrdHashSet k
insert :: forall k.
(Eq k, Hashable k) =>
k -> InsOrdHashSet k -> InsOrdHashSet k
insert k
k (InsOrdHashSet Int
i HashMap k Int
m) = forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet (Int
i 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 Int
i HashMap k Int
m)

delete :: (Eq k, Hashable k) => k -> InsOrdHashSet k -> InsOrdHashSet k
delete :: forall k.
(Eq k, Hashable k) =>
k -> InsOrdHashSet k -> InsOrdHashSet k
delete k
k (InsOrdHashSet Int
i HashMap k Int
m) = forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i (forall k v. (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
HashMap.delete k
k HashMap k Int
m)

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

union
    :: (Eq k, Hashable k)
    => InsOrdHashSet k -> InsOrdHashSet k -> InsOrdHashSet k
union :: forall k.
(Eq k, Hashable k) =>
InsOrdHashSet k -> InsOrdHashSet k -> InsOrdHashSet k
union (InsOrdHashSet Int
i HashMap k Int
a) (InsOrdHashSet Int
j HashMap k Int
b) =
    HashMap k Int -> InsOrdHashSet k
mk forall a b. (a -> b) -> a -> b
$ forall k v.
(Eq k, Hashable k) =>
HashMap k v -> HashMap k v -> HashMap k v
HashMap.union HashMap k Int
a HashMap k Int
b'
  where
    mk :: HashMap k Int -> InsOrdHashSet k
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. HashMap k Int -> InsOrdHashSet k
fromHashMapInt
       | Bool
otherwise                    = forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet (Int
i forall a. Num a => a -> a -> a
+ Int
j)

    b' :: HashMap k Int
b' = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Int
k -> Int
k forall a. Num a => a -> a -> a
+ Int
i forall a. Num a => a -> a -> a
+ Int
1) HashMap k Int
b

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

map :: (Hashable b, Eq b) => (a -> b) -> InsOrdHashSet a -> InsOrdHashSet b
map :: forall b a.
(Hashable b, Eq b) =>
(a -> b) -> InsOrdHashSet a -> InsOrdHashSet b
map a -> b
f (InsOrdHashSet Int
i HashMap a Int
m) = forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet 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 a -> b
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 a Int
m

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

difference :: (Eq a, Hashable a) => InsOrdHashSet a -> InsOrdHashSet a -> InsOrdHashSet a
difference :: forall k.
(Eq k, Hashable k) =>
InsOrdHashSet k -> InsOrdHashSet k -> InsOrdHashSet k
difference (InsOrdHashSet Int
i HashMap a Int
a) (InsOrdHashSet Int
_ HashMap a Int
b) =
    forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet 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 a Int
a HashMap a Int
b

intersection :: (Eq a, Hashable a) => InsOrdHashSet a -> InsOrdHashSet a -> InsOrdHashSet a
intersection :: forall k.
(Eq k, Hashable k) =>
InsOrdHashSet k -> InsOrdHashSet k -> InsOrdHashSet k
intersection (InsOrdHashSet Int
i HashMap a Int
a) (InsOrdHashSet Int
_ HashMap a Int
b) =
    forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet 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.intersection HashMap a Int
a HashMap a Int
b

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

filter :: (a -> Bool) -> InsOrdHashSet a -> InsOrdHashSet a
filter :: forall a. (a -> Bool) -> InsOrdHashSet a -> InsOrdHashSet a
filter a -> Bool
p (InsOrdHashSet Int
i HashMap a Int
m) = forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i forall a b. (a -> b) -> a -> b
$
    forall k v. (k -> v -> Bool) -> HashMap k v -> HashMap k v
HashMap.filterWithKey (\a
k Int
_ -> a -> Bool
p a
k) HashMap a Int
m

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

fromList :: (Eq k, Hashable k) => [k] -> InsOrdHashSet k
fromList :: forall k. (Eq k, Hashable k) => [k] -> InsOrdHashSet k
fromList = forall {k}. Hashable k => ([(k, Int)], Int) -> InsOrdHashSet k
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 (a, Int)
newInt where
    mk :: ([(k, Int)], Int) -> InsOrdHashSet k
mk ([(k, Int)]
m, Int
i) = forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i (forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HashMap.fromList [(k, Int)]
m)

toList :: InsOrdHashSet k -> [k]
toList :: forall k. InsOrdHashSet k -> [k]
toList
    = 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 a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing 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. InsOrdHashSet k -> HashMap k Int
getInsOrdHashSet

fromHashSet :: HashSet k -> InsOrdHashSet k
fromHashSet :: forall k. HashSet k -> InsOrdHashSet k
fromHashSet = forall {k}. (HashMap k Int, Int) -> InsOrdHashSet k
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 b. a -> b -> a
const State Int Int
newInt') forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. HashSet a -> HashMap a ()
HashSet.toMap where
    mk :: (HashMap k Int, Int) -> InsOrdHashSet k
mk (HashMap k Int
m, Int
i) = forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i HashMap k Int
m

toHashSet :: InsOrdHashSet k -> HashSet k
toHashSet :: forall k. InsOrdHashSet k -> HashSet k
toHashSet (InsOrdHashSet Int
_ HashMap k Int
m) =
#if MIN_VERSION_unordered_containers(0,2,10)
    forall k a. HashMap k a -> HashSet k
HashMap.keysSet HashMap k Int
m
#else
    HashSet.fromMap (fmap (const ()) m)
#endif

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

fromHashMapInt :: HashMap k Int -> InsOrdHashSet k
fromHashMapInt :: forall k. HashMap k Int -> InsOrdHashSet k
fromHashMapInt = forall {k}. (HashMap k Int, Int) -> InsOrdHashSet k
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 Int -> SortedAp (StateT Int Identity) Int
f
  where
    mk :: (HashMap k Int, Int) -> InsOrdHashSet k
mk (HashMap k Int
m, Int
i) = forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i HashMap k Int
m
    f :: Int -> SortedAp (StateT Int Identity) Int
f Int
i = forall (f :: * -> *) a. Int -> f a -> SortedAp f a
liftSortedAp Int
i State Int Int
newInt'

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

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

-------------------------------------------------------------------------------
-- Valid
-------------------------------------------------------------------------------

-- | Test if the internal map structure is valid.
valid :: InsOrdHashSet a -> Bool
valid :: forall a. InsOrdHashSet a -> Bool
valid (InsOrdHashSet Int
i HashMap a Int
m) = Bool
indexesDistinct Bool -> Bool -> Bool
&& Bool
indexesSmaller
  where
    indexes :: [Int]
    indexes :: [Int]
indexes = forall k v. HashMap k v -> [v]
HashMap.elems HashMap a Int
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