{-# LANGUAGE CPP                   #-}
{-# LANGUAGE DeriveDataTypeable    #-}
{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE GADTs                 #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables   #-}
{-# LANGUAGE Trustworthy           #-}
{-# LANGUAGE TypeFamilies          #-}
-- | 'InsOrdHashSet' is like 'HashMap', 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 hiding (filter, foldr, lookup, map, null)

import Control.Arrow                   (first)
import Control.DeepSeq                 (NFData (..))
import Data.Aeson
import Data.Data                       (Data, Typeable)
import Data.Hashable                   (Hashable (..))
import Data.List                       (nub, sortBy)
import Data.Ord                        (comparing)
import Data.Semigroup                  (Semigroup (..))
import Text.ParserCombinators.ReadPrec (prec)
import Text.Read
       (Lexeme (..), Read (..), lexP, parens, readListPrecDefault)

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

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
    { InsOrdHashSet k -> Int
_getIndex        :: !Int
    , InsOrdHashSet k -> HashMap k Int
getInsOrdHashSet :: !(HashMap k Int)
    }
    deriving (Typeable, Typeable (InsOrdHashSet k)
DataType
Constr
Typeable (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 (c :: * -> *).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (InsOrdHashSet k))
-> (InsOrdHashSet k -> Constr)
-> (InsOrdHashSet k -> DataType)
-> (forall (t :: * -> *) (c :: * -> *).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (InsOrdHashSet k)))
-> (forall (t :: * -> * -> *) (c :: * -> *).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (InsOrdHashSet k)))
-> ((forall b. Data b => b -> b)
    -> InsOrdHashSet k -> InsOrdHashSet k)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> InsOrdHashSet k -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> InsOrdHashSet k -> r)
-> (forall u.
    (forall d. Data d => d -> u) -> InsOrdHashSet k -> [u])
-> (forall u.
    Int -> (forall d. Data d => d -> u) -> InsOrdHashSet k -> u)
-> (forall (m :: * -> *).
    Monad m =>
    (forall d. Data d => d -> m d)
    -> InsOrdHashSet k -> m (InsOrdHashSet k))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> InsOrdHashSet k -> m (InsOrdHashSet k))
-> (forall (m :: * -> *).
    MonadPlus m =>
    (forall d. Data d => d -> m d)
    -> InsOrdHashSet k -> m (InsOrdHashSet k))
-> Data (InsOrdHashSet k)
InsOrdHashSet k -> DataType
InsOrdHashSet k -> Constr
(forall d. Data d => c (t d)) -> Maybe (c (InsOrdHashSet k))
(forall b. Data b => b -> b) -> InsOrdHashSet k -> InsOrdHashSet k
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> InsOrdHashSet k -> c (InsOrdHashSet k)
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (InsOrdHashSet k)
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 u.
Int -> (forall d. Data d => d -> u) -> InsOrdHashSet k -> u
forall u. (forall d. Data d => d -> u) -> InsOrdHashSet k -> [u]
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> InsOrdHashSet k -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> InsOrdHashSet k -> r
forall (m :: * -> *).
Monad m =>
(forall d. Data d => d -> m d)
-> InsOrdHashSet k -> m (InsOrdHashSet k)
forall (m :: * -> *).
MonadPlus m =>
(forall d. Data d => d -> m d)
-> InsOrdHashSet k -> m (InsOrdHashSet k)
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))
forall (t :: * -> * -> *) (c :: * -> *).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e))
-> Maybe (c (InsOrdHashSet k))
$cInsOrdHashSet :: Constr
$tInsOrdHashSet :: DataType
gmapMo :: (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 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 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 :: 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 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 :: (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 :: (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 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 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 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 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)
$cp1Data :: forall k. (Data k, Hashable k) => Typeable (InsOrdHashSet k)
Data)

-- | @since 0.2.5
instance NFData k => NFData (InsOrdHashSet k) where
    rnf :: InsOrdHashSet k -> ()
rnf (InsOrdHashSet Int
_ HashMap k Int
hs) = HashMap k Int -> ()
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 :: (a -> ()) -> InsOrdHashSet a -> ()
liftRnf a -> ()
rnf1 (InsOrdHashSet Int
_ HashMap a Int
m) = (a -> ()) -> (Int -> ()) -> HashMap a Int -> ()
forall (p :: * -> * -> *) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
NF.liftRnf2 a -> ()
rnf1 Int -> ()
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 HashMap k Int -> HashMap k Int -> Bool
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$
        String -> ShowS
showString String
"fromList " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [k] -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec Int
11 (InsOrdHashSet k -> [k]
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 = ReadPrec (InsOrdHashSet k) -> ReadPrec (InsOrdHashSet k)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (InsOrdHashSet k) -> ReadPrec (InsOrdHashSet k))
-> ReadPrec (InsOrdHashSet k) -> ReadPrec (InsOrdHashSet k)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (InsOrdHashSet k) -> ReadPrec (InsOrdHashSet k)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (InsOrdHashSet k) -> ReadPrec (InsOrdHashSet k))
-> ReadPrec (InsOrdHashSet k) -> ReadPrec (InsOrdHashSet k)
forall a b. (a -> b) -> a -> b
$ do
      Ident String
"fromList" <- ReadPrec Lexeme
lexP
      [k]
xs <- ReadPrec [k]
forall a. Read a => ReadPrec a
readPrec
      InsOrdHashSet k -> ReadPrec (InsOrdHashSet k)
forall (m :: * -> *) a. Monad m => a -> m a
return ([k] -> InsOrdHashSet k
forall k. (Eq k, Hashable k) => [k] -> InsOrdHashSet k
fromList [k]
xs)

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

instance (Eq k, Hashable k) => Semigroup (InsOrdHashSet k) where
    <> :: InsOrdHashSet k -> InsOrdHashSet k -> InsOrdHashSet k
(<>) = 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 = InsOrdHashSet k
forall k. InsOrdHashSet k
empty
    mappend :: InsOrdHashSet k -> InsOrdHashSet k -> InsOrdHashSet k
mappend = InsOrdHashSet k -> InsOrdHashSet k -> InsOrdHashSet k
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 :: (a -> m) -> InsOrdHashSet a -> m
foldMap a -> m
f = (a -> m) -> [a] -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap a -> m
f ([a] -> m) -> (InsOrdHashSet a -> [a]) -> InsOrdHashSet a -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. InsOrdHashSet a -> [a]
forall k. InsOrdHashSet k -> [k]
toList

    null :: InsOrdHashSet a -> Bool
null = InsOrdHashSet a -> Bool
forall a. InsOrdHashSet a -> Bool
null
    toList :: InsOrdHashSet a -> [a]
toList = InsOrdHashSet a -> [a]
forall k. InsOrdHashSet k -> [k]
toList
    length :: InsOrdHashSet a -> Int
length = InsOrdHashSet a -> Int
forall a. InsOrdHashSet a -> 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) =
        Int -> HashMap k Int -> Int
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 = [Item (InsOrdHashSet k)] -> InsOrdHashSet k
forall k. (Eq k, Hashable k) => [k] -> InsOrdHashSet k
fromList
    toList :: InsOrdHashSet k -> [Item (InsOrdHashSet k)]
toList   = InsOrdHashSet k -> [Item (InsOrdHashSet k)]
forall k. InsOrdHashSet k -> [k]
toList

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

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

instance (Eq a, Hashable a, FromJSON a) => FromJSON (InsOrdHashSet a) where
    parseJSON :: Value -> Parser (InsOrdHashSet a)
parseJSON Value
v = [a] -> InsOrdHashSet a
forall k. (Eq k, Hashable k) => [k] -> InsOrdHashSet k
fromList ([a] -> InsOrdHashSet a) -> Parser [a] -> Parser (InsOrdHashSet a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Value -> Parser [a]
forall a. FromJSON a => Value -> Parser 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) = Int -> HashMap k Int -> InsOrdHashSet k
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i (HashMap k Int -> InsOrdHashSet k)
-> f (HashMap k Int) -> f (InsOrdHashSet k)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Index (HashMap k Int)
-> (IxValue (HashMap k Int) -> f (IxValue (HashMap k Int)))
-> HashMap k Int
-> f (HashMap k Int)
forall m. Ixed m => Index m -> Traversal' m (IxValue m)
ix Index (HashMap k Int)
Index (InsOrdHashSet k)
k (\IxValue (HashMap k Int)
j -> Int
IxValue (HashMap k Int)
j Int -> f () -> f Int
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 ()
Maybe (IxValue (InsOrdHashSet k))
mv f (Maybe ())
-> (Maybe () -> InsOrdHashSet k) -> f (InsOrdHashSet k)
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \Maybe ()
r -> case Maybe ()
r of
    Maybe ()
Nothing -> InsOrdHashSet k
-> (() -> InsOrdHashSet k) -> Maybe () -> InsOrdHashSet k
forall b a. b -> (a -> b) -> Maybe a -> b
maybe InsOrdHashSet k
m (InsOrdHashSet k -> () -> InsOrdHashSet k
forall a b. a -> b -> a
const (k -> InsOrdHashSet k -> InsOrdHashSet k
forall k.
(Eq k, Hashable k) =>
k -> InsOrdHashSet k -> InsOrdHashSet k
delete k
Index (InsOrdHashSet k)
k InsOrdHashSet k
m)) Maybe ()
mv
    Just () -> k -> InsOrdHashSet k -> InsOrdHashSet k
forall k.
(Eq k, Hashable k) =>
k -> InsOrdHashSet k -> InsOrdHashSet k
insert k
Index (InsOrdHashSet k)
k InsOrdHashSet k
m
    where mv :: Maybe ()
mv = if k -> InsOrdHashSet k -> Bool
forall k. (Eq k, Hashable k) => k -> InsOrdHashSet k -> Bool
member k
Index (InsOrdHashSet k)
k InsOrdHashSet k
m then () -> Maybe ()
forall a. a -> Maybe a
Just () else Maybe ()
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 (a -> InsOrdHashSet a -> Bool
forall k. (Eq k, Hashable k) => k -> InsOrdHashSet k -> Bool
member a
Index (InsOrdHashSet a)
k InsOrdHashSet a
s) f Bool -> (Bool -> InsOrdHashSet a) -> f (InsOrdHashSet a)
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \Bool
b ->
    if Bool
b then a -> InsOrdHashSet a -> InsOrdHashSet a
forall k.
(Eq k, Hashable k) =>
k -> InsOrdHashSet k -> InsOrdHashSet k
insert a
Index (InsOrdHashSet a)
k InsOrdHashSet a
s else a -> InsOrdHashSet a -> InsOrdHashSet a
forall k.
(Eq k, Hashable k) =>
k -> InsOrdHashSet k -> InsOrdHashSet k
delete a
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 :: p (HashSet a) (f (HashSet a))
-> p (InsOrdHashSet a) (f (InsOrdHashSet a))
hashSet = (InsOrdHashSet a -> HashSet a)
-> (HashSet a -> InsOrdHashSet a)
-> Iso (InsOrdHashSet a) (InsOrdHashSet a) (HashSet a) (HashSet a)
forall s a b t. (s -> a) -> (b -> t) -> Iso s t a b
iso InsOrdHashSet a -> HashSet a
forall k. InsOrdHashSet k -> HashSet k
toHashSet HashSet a -> InsOrdHashSet a
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 = AffineTraversalVL (InsOrdHashSet k) (InsOrdHashSet k) () ()
-> AffineTraversal (InsOrdHashSet k) (InsOrdHashSet k) () ()
forall s t a b.
AffineTraversalVL s t a b -> AffineTraversal s t a b
Optics.atraversalVL (AffineTraversalVL (InsOrdHashSet k) (InsOrdHashSet k) () ()
 -> AffineTraversal (InsOrdHashSet k) (InsOrdHashSet k) () ())
-> AffineTraversalVL (InsOrdHashSet k) (InsOrdHashSet k) () ()
-> AffineTraversal (InsOrdHashSet k) (InsOrdHashSet k) () ()
forall a b. (a -> b) -> a -> b
$ \forall r. r -> f r
point () -> f ()
f (InsOrdHashSet i m) ->
      Int -> HashMap k Int -> InsOrdHashSet k
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i (HashMap k Int -> InsOrdHashSet k)
-> f (HashMap k Int) -> f (InsOrdHashSet k)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$>
#if MIN_VERSION_optics_core(0,3,0)
          Optic
  An_AffineTraversal NoIx (HashMap k Int) (HashMap k Int) Int Int
-> (forall r. r -> f r)
-> (Int -> f Int)
-> HashMap k Int
-> f (HashMap k Int)
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
          (Index (HashMap k Int)
-> Optic'
     (IxKind (HashMap k Int))
     NoIx
     (HashMap k Int)
     (IxValue (HashMap k Int))
forall m. Ixed m => Index m -> Optic' (IxKind m) NoIx m (IxValue m)
Optics.ix Index (HashMap k Int)
Index (InsOrdHashSet k)
k) forall r. r -> f r
point (\Int
j -> Int
j Int -> f () -> f Int
forall (f :: * -> *) a b. Functor f => a -> f b -> f a
<$ () -> f ()
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 = LensVL (InsOrdHashSet k) (InsOrdHashSet k) (Maybe ()) (Maybe ())
-> Lens (InsOrdHashSet k) (InsOrdHashSet k) (Maybe ()) (Maybe ())
forall s t a b. LensVL s t a b -> Lens s t a b
Optics.lensVL (LensVL (InsOrdHashSet k) (InsOrdHashSet k) (Maybe ()) (Maybe ())
 -> Lens (InsOrdHashSet k) (InsOrdHashSet k) (Maybe ()) (Maybe ()))
-> LensVL (InsOrdHashSet k) (InsOrdHashSet k) (Maybe ()) (Maybe ())
-> Lens (InsOrdHashSet k) (InsOrdHashSet k) (Maybe ()) (Maybe ())
forall a b. (a -> b) -> a -> b
$ \Maybe () -> f (Maybe ())
f InsOrdHashSet k
m -> Index (InsOrdHashSet k)
-> (Maybe (IxValue (InsOrdHashSet k))
    -> f (Maybe (IxValue (InsOrdHashSet k))))
-> InsOrdHashSet k
-> f (InsOrdHashSet k)
forall m. At m => Index m -> Lens' m (Maybe (IxValue m))
Lens.at Index (InsOrdHashSet k)
Index (InsOrdHashSet k)
k Maybe () -> f (Maybe ())
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 = LensVL (InsOrdHashSet a) (InsOrdHashSet a) Bool Bool
-> Lens' (InsOrdHashSet a) Bool
forall s t a b. LensVL s t a b -> Lens s t a b
Optics.lensVL (LensVL (InsOrdHashSet a) (InsOrdHashSet a) Bool Bool
 -> Lens' (InsOrdHashSet a) Bool)
-> LensVL (InsOrdHashSet a) (InsOrdHashSet a) Bool Bool
-> Lens' (InsOrdHashSet a) Bool
forall a b. (a -> b) -> a -> b
$ \Bool -> f Bool
f InsOrdHashSet a
s -> Index (InsOrdHashSet a)
-> (Bool -> f Bool) -> InsOrdHashSet a -> f (InsOrdHashSet a)
forall m. Contains m => Index m -> Lens' m Bool
Lens.contains Index (InsOrdHashSet a)
Index (InsOrdHashSet a)
k Bool -> f Bool
f InsOrdHashSet a
s
    {-# INLINE contains #-}

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

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

singleton :: Hashable k => k -> InsOrdHashSet k
singleton :: k -> InsOrdHashSet k
singleton k
k = Int -> HashMap k Int -> InsOrdHashSet k
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
1 (k -> Int -> HashMap k Int
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 :: InsOrdHashSet k -> Bool
null = HashMap k Int -> Bool
forall k v. HashMap k v -> Bool
HashMap.null (HashMap k Int -> Bool)
-> (InsOrdHashSet k -> HashMap k Int) -> InsOrdHashSet k -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. InsOrdHashSet k -> HashMap k Int
forall k. InsOrdHashSet k -> HashMap k Int
getInsOrdHashSet
{-# INLINABLE null #-}

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

member :: (Eq k, Hashable k) => k -> InsOrdHashSet k -> Bool
member :: k -> InsOrdHashSet k -> Bool
member k
k = k -> HashMap k Int -> Bool
forall k a. (Eq k, Hashable k) => k -> HashMap k a -> Bool
HashMap.member k
k (HashMap k Int -> Bool)
-> (InsOrdHashSet k -> HashMap k Int) -> InsOrdHashSet k -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. InsOrdHashSet k -> HashMap k Int
forall k. InsOrdHashSet k -> HashMap k Int
getInsOrdHashSet
{-# INLINABLE member #-}

insert :: (Eq k, Hashable k) => k -> InsOrdHashSet k -> InsOrdHashSet k
insert :: k -> InsOrdHashSet k -> InsOrdHashSet k
insert k
k (InsOrdHashSet Int
i HashMap k Int
m) = Int -> HashMap k Int -> InsOrdHashSet k
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) (k -> Int -> HashMap k Int -> HashMap k Int
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 :: k -> InsOrdHashSet k -> InsOrdHashSet k
delete k
k (InsOrdHashSet Int
i HashMap k Int
m) = Int -> HashMap k Int -> InsOrdHashSet k
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i (k -> HashMap k Int -> HashMap k Int
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 :: 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 (HashMap k Int -> InsOrdHashSet k)
-> HashMap k Int -> InsOrdHashSet k
forall a b. (a -> b) -> a -> b
$ HashMap k Int -> HashMap k Int -> HashMap k Int
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 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0xfffff Bool -> Bool -> Bool
|| Int
j Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
0xfffff = HashMap k Int -> InsOrdHashSet k
forall k. HashMap k Int -> InsOrdHashSet k
fromHashMapInt
       | Bool
otherwise                    = Int -> HashMap k Int -> InsOrdHashSet k
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
j)

    b' :: HashMap k Int
b' = (Int -> Int) -> HashMap k Int -> HashMap k Int
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Int
k -> Int
k Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
i Int -> Int -> Int
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 :: (a -> b) -> InsOrdHashSet a -> InsOrdHashSet b
map a -> b
f (InsOrdHashSet Int
i HashMap a Int
m) = Int -> HashMap b Int -> InsOrdHashSet b
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i
    (HashMap b Int -> InsOrdHashSet b)
-> HashMap b Int -> InsOrdHashSet b
forall a b. (a -> b) -> a -> b
$ [(b, Int)] -> HashMap b Int
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HashMap.fromList ([(b, Int)] -> HashMap b Int)
-> (HashMap a Int -> [(b, Int)]) -> HashMap a Int -> HashMap b Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((a, Int) -> (b, Int)) -> [(a, Int)] -> [(b, Int)]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((a -> b) -> (a, Int) -> (b, Int)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first a -> b
f) ([(a, Int)] -> [(b, Int)])
-> (HashMap a Int -> [(a, Int)]) -> HashMap a Int -> [(b, Int)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap a Int -> [(a, Int)]
forall k v. HashMap k v -> [(k, v)]
HashMap.toList
    (HashMap a Int -> HashMap b Int) -> HashMap a Int -> HashMap b Int
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 :: InsOrdHashSet a -> InsOrdHashSet a -> InsOrdHashSet a
difference (InsOrdHashSet Int
i HashMap a Int
a) (InsOrdHashSet Int
_ HashMap a Int
b) =
    Int -> HashMap a Int -> InsOrdHashSet a
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i (HashMap a Int -> InsOrdHashSet a)
-> HashMap a Int -> InsOrdHashSet a
forall a b. (a -> b) -> a -> b
$ HashMap a Int -> HashMap a Int -> HashMap a Int
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 :: InsOrdHashSet a -> InsOrdHashSet a -> InsOrdHashSet a
intersection (InsOrdHashSet Int
i HashMap a Int
a) (InsOrdHashSet Int
_ HashMap a Int
b) =
    Int -> HashMap a Int -> InsOrdHashSet a
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i (HashMap a Int -> InsOrdHashSet a)
-> HashMap a Int -> InsOrdHashSet a
forall a b. (a -> b) -> a -> b
$ HashMap a Int -> HashMap a Int -> HashMap a Int
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 :: (a -> Bool) -> InsOrdHashSet a -> InsOrdHashSet a
filter a -> Bool
p (InsOrdHashSet Int
i HashMap a Int
m) = Int -> HashMap a Int -> InsOrdHashSet a
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i (HashMap a Int -> InsOrdHashSet a)
-> HashMap a Int -> InsOrdHashSet a
forall a b. (a -> b) -> a -> b
$
    (a -> Int -> Bool) -> HashMap a Int -> HashMap a Int
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 :: [k] -> InsOrdHashSet k
fromList = ([(k, Int)], Int) -> InsOrdHashSet k
forall k. Hashable k => ([(k, Int)], Int) -> InsOrdHashSet k
mk (([(k, Int)], Int) -> InsOrdHashSet k)
-> ([k] -> ([(k, Int)], Int)) -> [k] -> InsOrdHashSet k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (State Int [(k, Int)] -> Int -> ([(k, Int)], Int))
-> Int -> State Int [(k, Int)] -> ([(k, Int)], Int)
forall a b c. (a -> b -> c) -> b -> a -> c
flip State Int [(k, Int)] -> Int -> ([(k, Int)], Int)
forall s a. State s a -> s -> (a, s)
runState Int
0 (State Int [(k, Int)] -> ([(k, Int)], Int))
-> ([k] -> State Int [(k, Int)]) -> [k] -> ([(k, Int)], Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (k -> StateT Int Identity (k, Int)) -> [k] -> State Int [(k, Int)]
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse k -> StateT Int Identity (k, Int)
forall a. a -> State Int (a, Int)
newInt where
    mk :: ([(k, Int)], Int) -> InsOrdHashSet k
mk ([(k, Int)]
m, Int
i) = Int -> HashMap k Int -> InsOrdHashSet k
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i ([(k, Int)] -> HashMap k Int
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HashMap.fromList [(k, Int)]
m)

toList :: InsOrdHashSet k -> [k]
toList :: InsOrdHashSet k -> [k]
toList
    = ((k, Int) -> k) -> [(k, Int)] -> [k]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (k, Int) -> k
forall a b. (a, b) -> a
fst
    ([(k, Int)] -> [k])
-> (InsOrdHashSet k -> [(k, Int)]) -> InsOrdHashSet k -> [k]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((k, Int) -> (k, Int) -> Ordering) -> [(k, Int)] -> [(k, Int)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (((k, Int) -> Int) -> (k, Int) -> (k, Int) -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (k, Int) -> Int
forall a b. (a, b) -> b
snd)
    ([(k, Int)] -> [(k, Int)])
-> (InsOrdHashSet k -> [(k, Int)]) -> InsOrdHashSet k -> [(k, Int)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashMap k Int -> [(k, Int)]
forall k v. HashMap k v -> [(k, v)]
HashMap.toList
    (HashMap k Int -> [(k, Int)])
-> (InsOrdHashSet k -> HashMap k Int)
-> InsOrdHashSet k
-> [(k, Int)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. InsOrdHashSet k -> HashMap k Int
forall k. InsOrdHashSet k -> HashMap k Int
getInsOrdHashSet

fromHashSet :: HashSet k -> InsOrdHashSet k
fromHashSet :: HashSet k -> InsOrdHashSet k
fromHashSet = (HashMap k Int, Int) -> InsOrdHashSet k
forall k. (HashMap k Int, Int) -> InsOrdHashSet k
mk ((HashMap k Int, Int) -> InsOrdHashSet k)
-> (HashSet k -> (HashMap k Int, Int))
-> HashSet k
-> InsOrdHashSet k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (State Int (HashMap k Int) -> Int -> (HashMap k Int, Int))
-> Int -> State Int (HashMap k Int) -> (HashMap k Int, Int)
forall a b c. (a -> b -> c) -> b -> a -> c
flip State Int (HashMap k Int) -> Int -> (HashMap k Int, Int)
forall s a. State s a -> s -> (a, s)
runState Int
0 (State Int (HashMap k Int) -> (HashMap k Int, Int))
-> (HashSet k -> State Int (HashMap k Int))
-> HashSet k
-> (HashMap k Int, Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (() -> StateT Int Identity Int)
-> HashMap k () -> State Int (HashMap k Int)
forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse (StateT Int Identity Int -> () -> StateT Int Identity Int
forall a b. a -> b -> a
const StateT Int Identity Int
newInt') (HashMap k () -> State Int (HashMap k Int))
-> (HashSet k -> HashMap k ())
-> HashSet k
-> State Int (HashMap k Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. HashSet k -> HashMap k ()
forall a. HashSet a -> HashMap a ()
HashSet.toMap where
    mk :: (HashMap k Int, Int) -> InsOrdHashSet k
mk (HashMap k Int
m, Int
i) = Int -> HashMap k Int -> InsOrdHashSet k
forall k. Int -> HashMap k Int -> InsOrdHashSet k
InsOrdHashSet Int
i HashMap k Int
m

toHashSet :: InsOrdHashSet k -> HashSet k
toHashSet :: InsOrdHashSet k -> HashSet k
toHashSet (InsOrdHashSet Int
_ HashMap k Int
m) =
#if MIN_VERSION_unordered_containers(0,2,10)
    HashMap k Int -> HashSet k
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 :: HashMap k Int -> InsOrdHashSet k
fromHashMapInt = (HashMap k Int, Int) -> InsOrdHashSet k
forall k. (HashMap k Int, Int) -> InsOrdHashSet k
mk ((HashMap k Int, Int) -> InsOrdHashSet k)
-> (HashMap k Int -> (HashMap k Int, Int))
-> HashMap k Int
-> InsOrdHashSet k
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (State Int (HashMap k Int) -> Int -> (HashMap k Int, Int))
-> Int -> State Int (HashMap k Int) -> (HashMap k Int, Int)
forall a b c. (a -> b -> c) -> b -> a -> c
flip State Int (HashMap k Int) -> Int -> (HashMap k Int, Int)
forall s a. State s a -> s -> (a, s)
runState Int
0 (State Int (HashMap k Int) -> (HashMap k Int, Int))
-> (HashMap k Int -> State Int (HashMap k Int))
-> HashMap k Int
-> (HashMap k Int, Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. SortedAp (StateT Int Identity) (HashMap k Int)
-> State Int (HashMap k Int)
forall (f :: * -> *) a. Applicative f => SortedAp f a -> f a
retractSortedAp (SortedAp (StateT Int Identity) (HashMap k Int)
 -> State Int (HashMap k Int))
-> (HashMap k Int
    -> SortedAp (StateT Int Identity) (HashMap k Int))
-> HashMap k Int
-> State Int (HashMap k Int)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> SortedAp (StateT Int Identity) Int)
-> HashMap k Int -> SortedAp (StateT Int Identity) (HashMap k Int)
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) = Int -> HashMap k Int -> InsOrdHashSet k
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 = Int
-> StateT Int Identity Int -> SortedAp (StateT Int Identity) Int
forall (f :: * -> *) a. Int -> f a -> SortedAp f a
liftSortedAp Int
i StateT Int Identity Int
newInt'

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

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

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

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

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