{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE GeneralisedNewtypeDeriving #-}
{-# LANGUAGE TypeFamilies #-}
{-# OPTIONS_GHC -fno-warn-orphans -Wno-redundant-constraints #-}
module Core.Data.Structures (
Map,
emptyMap,
singletonMap,
insertKeyValue,
containsKey,
lookupKeyValue,
Dictionary (K, V, fromMap, intoMap),
Set,
emptySet,
singletonSet,
insertElement,
containsElement,
Collection (E, fromSet, intoSet),
Key,
unMap,
unSet,
) where
import Core.Text.Bytes (Bytes)
import Core.Text.Rope (Rope)
import Data.Bifoldable (Bifoldable)
import qualified Data.ByteString as B (ByteString)
import qualified Data.HashMap.Strict as HashMap
import qualified Data.HashSet as HashSet
import Data.Hashable (Hashable)
import Data.Kind (Type)
import qualified Data.Map.Strict as OrdMap
import qualified Data.Set as OrdSet
import qualified Data.Text as T (Text)
import qualified Data.Text.Lazy as U (Text)
import qualified GHC.Exts as Exts (IsList (..))
newtype Map κ ν = Map (HashMap.HashMap κ ν)
deriving (Int -> Map κ ν -> ShowS
[Map κ ν] -> ShowS
Map κ ν -> String
(Int -> Map κ ν -> ShowS)
-> (Map κ ν -> String) -> ([Map κ ν] -> ShowS) -> Show (Map κ ν)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall κ ν. (Show κ, Show ν) => Int -> Map κ ν -> ShowS
forall κ ν. (Show κ, Show ν) => [Map κ ν] -> ShowS
forall κ ν. (Show κ, Show ν) => Map κ ν -> String
showList :: [Map κ ν] -> ShowS
$cshowList :: forall κ ν. (Show κ, Show ν) => [Map κ ν] -> ShowS
show :: Map κ ν -> String
$cshow :: forall κ ν. (Show κ, Show ν) => Map κ ν -> String
showsPrec :: Int -> Map κ ν -> ShowS
$cshowsPrec :: forall κ ν. (Show κ, Show ν) => Int -> Map κ ν -> ShowS
Show, Map κ ν -> Map κ ν -> Bool
(Map κ ν -> Map κ ν -> Bool)
-> (Map κ ν -> Map κ ν -> Bool) -> Eq (Map κ ν)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall κ ν. (Eq κ, Eq ν) => Map κ ν -> Map κ ν -> Bool
/= :: Map κ ν -> Map κ ν -> Bool
$c/= :: forall κ ν. (Eq κ, Eq ν) => Map κ ν -> Map κ ν -> Bool
== :: Map κ ν -> Map κ ν -> Bool
$c== :: forall κ ν. (Eq κ, Eq ν) => Map κ ν -> Map κ ν -> Bool
Eq, Map m m -> m
(a -> m) -> (b -> m) -> Map a b -> m
(a -> c -> c) -> (b -> c -> c) -> c -> Map a b -> c
(c -> a -> c) -> (c -> b -> c) -> c -> Map a b -> c
(forall m. Monoid m => Map m m -> m)
-> (forall m a b. Monoid m => (a -> m) -> (b -> m) -> Map a b -> m)
-> (forall a c b.
(a -> c -> c) -> (b -> c -> c) -> c -> Map a b -> c)
-> (forall c a b.
(c -> a -> c) -> (c -> b -> c) -> c -> Map a b -> c)
-> Bifoldable Map
forall m. Monoid m => Map m m -> m
forall m a b. Monoid m => (a -> m) -> (b -> m) -> Map a b -> m
forall c a b. (c -> a -> c) -> (c -> b -> c) -> c -> Map a b -> c
forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> Map a b -> c
forall (p :: * -> * -> *).
(forall m. Monoid m => p m m -> m)
-> (forall m a b. Monoid m => (a -> m) -> (b -> m) -> p a b -> m)
-> (forall a c b.
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c)
-> (forall c a b.
(c -> a -> c) -> (c -> b -> c) -> c -> p a b -> c)
-> Bifoldable p
bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> Map a b -> c
$cbifoldl :: forall c a b. (c -> a -> c) -> (c -> b -> c) -> c -> Map a b -> c
bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> Map a b -> c
$cbifoldr :: forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> Map a b -> c
bifoldMap :: (a -> m) -> (b -> m) -> Map a b -> m
$cbifoldMap :: forall m a b. Monoid m => (a -> m) -> (b -> m) -> Map a b -> m
bifold :: Map m m -> m
$cbifold :: forall m. Monoid m => Map m m -> m
Bifoldable)
unMap :: Map κ ν -> HashMap.HashMap κ ν
unMap :: Map κ ν -> HashMap κ ν
unMap (Map HashMap κ ν
u) = HashMap κ ν
u
{-# INLINE unMap #-}
class (Hashable κ, Ord κ) => Key κ
instance Key String
instance Key Rope
instance Key Bytes
instance Key T.Text
instance Key U.Text
instance Key Char
instance Key Int
instance Key B.ByteString
instance Foldable (Map κ) where
foldr :: (a -> b -> b) -> b -> Map κ a -> b
foldr a -> b -> b
f b
start (Map HashMap κ a
u) = (a -> b -> b) -> b -> HashMap κ a -> b
forall v a k. (v -> a -> a) -> a -> HashMap k v -> a
HashMap.foldr a -> b -> b
f b
start HashMap κ a
u
null :: Map κ a -> Bool
null (Map HashMap κ a
u) = HashMap κ a -> Bool
forall k v. HashMap k v -> Bool
HashMap.null HashMap κ a
u
length :: Map κ a -> Int
length (Map HashMap κ a
u) = HashMap κ a -> Int
forall k v. HashMap k v -> Int
HashMap.size HashMap κ a
u
emptyMap :: Map κ ν
emptyMap :: Map κ ν
emptyMap = HashMap κ ν -> Map κ ν
forall κ ν. HashMap κ ν -> Map κ ν
Map (HashMap κ ν
forall k v. HashMap k v
HashMap.empty)
singletonMap :: Key κ => κ -> ν -> Map κ ν
singletonMap :: κ -> ν -> Map κ ν
singletonMap κ
k ν
v = HashMap κ ν -> Map κ ν
forall κ ν. HashMap κ ν -> Map κ ν
Map (κ -> ν -> HashMap κ ν
forall k v. Hashable k => k -> v -> HashMap k v
HashMap.singleton κ
k ν
v)
insertKeyValue :: Key κ => κ -> ν -> Map κ ν -> Map κ ν
insertKeyValue :: κ -> ν -> Map κ ν -> Map κ ν
insertKeyValue κ
k ν
v (Map HashMap κ ν
u) = HashMap κ ν -> Map κ ν
forall κ ν. HashMap κ ν -> Map κ ν
Map (κ -> ν -> HashMap κ ν -> HashMap κ ν
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HashMap.insert κ
k ν
v HashMap κ ν
u)
lookupKeyValue :: Key κ => κ -> Map κ ν -> Maybe ν
lookupKeyValue :: κ -> Map κ ν -> Maybe ν
lookupKeyValue κ
k (Map HashMap κ ν
u) = κ -> HashMap κ ν -> Maybe ν
forall k v. (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
HashMap.lookup κ
k HashMap κ ν
u
containsKey :: Key κ => κ -> Map κ ν -> Bool
containsKey :: κ -> Map κ ν -> Bool
containsKey κ
k (Map HashMap κ ν
u) = κ -> HashMap κ ν -> Bool
forall k a. (Eq k, Hashable k) => k -> HashMap k a -> Bool
HashMap.member κ
k HashMap κ ν
u
instance Key κ => Semigroup (Map κ ν) where
<> :: Map κ ν -> Map κ ν -> Map κ ν
(<>) (Map HashMap κ ν
u1) (Map HashMap κ ν
u2) = HashMap κ ν -> Map κ ν
forall κ ν. HashMap κ ν -> Map κ ν
Map (HashMap κ ν -> HashMap κ ν -> HashMap κ ν
forall k v.
(Eq k, Hashable k) =>
HashMap k v -> HashMap k v -> HashMap k v
HashMap.union HashMap κ ν
u1 HashMap κ ν
u2)
instance Key κ => Monoid (Map κ ν) where
mempty :: Map κ ν
mempty = Map κ ν
forall κ ν. Map κ ν
emptyMap
mappend :: Map κ ν -> Map κ ν -> Map κ ν
mappend = Map κ ν -> Map κ ν -> Map κ ν
forall a. Semigroup a => a -> a -> a
(<>)
instance Key κ => Exts.IsList (Map κ ν) where
type Item (Map κ ν) = (κ, ν)
fromList :: [Item (Map κ ν)] -> Map κ ν
fromList [Item (Map κ ν)]
pairs = HashMap κ ν -> Map κ ν
forall κ ν. HashMap κ ν -> Map κ ν
Map ([(κ, ν)] -> HashMap κ ν
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HashMap.fromList [(κ, ν)]
[Item (Map κ ν)]
pairs)
toList :: Map κ ν -> [Item (Map κ ν)]
toList (Map HashMap κ ν
u) = HashMap κ ν -> [(κ, ν)]
forall k v. HashMap k v -> [(k, v)]
HashMap.toList HashMap κ ν
u
class Dictionary α where
type K α :: Type
type V α :: Type
fromMap :: Map (K α) (V α) -> α
intoMap :: α -> Map (K α) (V α)
instance Key κ => Dictionary (Map κ ν) where
type K (Map κ ν) = κ
type V (Map κ ν) = ν
fromMap :: Map (K (Map κ ν)) (V (Map κ ν)) -> Map κ ν
fromMap = Map (K (Map κ ν)) (V (Map κ ν)) -> Map κ ν
forall a. a -> a
id
intoMap :: Map κ ν -> Map (K (Map κ ν)) (V (Map κ ν))
intoMap = Map κ ν -> Map (K (Map κ ν)) (V (Map κ ν))
forall a. a -> a
id
instance Key κ => Dictionary (HashMap.HashMap κ ν) where
type K (HashMap.HashMap κ ν) = κ
type V (HashMap.HashMap κ ν) = ν
fromMap :: Map (K (HashMap κ ν)) (V (HashMap κ ν)) -> HashMap κ ν
fromMap (Map HashMap (K (HashMap κ ν)) (V (HashMap κ ν))
u) = HashMap κ ν
HashMap (K (HashMap κ ν)) (V (HashMap κ ν))
u
intoMap :: HashMap κ ν -> Map (K (HashMap κ ν)) (V (HashMap κ ν))
intoMap HashMap κ ν
u = HashMap κ ν -> Map κ ν
forall κ ν. HashMap κ ν -> Map κ ν
Map HashMap κ ν
u
instance Key κ => Dictionary (OrdMap.Map κ ν) where
type K (OrdMap.Map κ ν) = κ
type V (OrdMap.Map κ ν) = ν
fromMap :: Map (K (Map κ ν)) (V (Map κ ν)) -> Map κ ν
fromMap (Map HashMap (K (Map κ ν)) (V (Map κ ν))
u) = (κ -> ν -> Map κ ν -> Map κ ν) -> Map κ ν -> HashMap κ ν -> Map κ ν
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
HashMap.foldrWithKey κ -> ν -> Map κ ν -> Map κ ν
forall k a. Ord k => k -> a -> Map k a -> Map k a
OrdMap.insert Map κ ν
forall k a. Map k a
OrdMap.empty HashMap κ ν
HashMap (K (Map κ ν)) (V (Map κ ν))
u
intoMap :: Map κ ν -> Map (K (Map κ ν)) (V (Map κ ν))
intoMap Map κ ν
o = HashMap κ ν -> Map κ ν
forall κ ν. HashMap κ ν -> Map κ ν
Map ((κ -> ν -> HashMap κ ν -> HashMap κ ν)
-> HashMap κ ν -> Map κ ν -> HashMap κ ν
forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
OrdMap.foldrWithKey κ -> ν -> HashMap κ ν -> HashMap κ ν
forall k v.
(Eq k, Hashable k) =>
k -> v -> HashMap k v -> HashMap k v
HashMap.insert HashMap κ ν
forall k v. HashMap k v
HashMap.empty Map κ ν
o)
instance Key κ => Dictionary [(κ, ν)] where
type K [(κ, ν)] = κ
type V [(κ, ν)] = ν
fromMap :: Map (K [(κ, ν)]) (V [(κ, ν)]) -> [(κ, ν)]
fromMap (Map HashMap (K [(κ, ν)]) (V [(κ, ν)])
u) = Map κ ν -> [(κ, ν)]
forall k a. Map k a -> [(k, a)]
OrdMap.toList ((κ -> ν -> Map κ ν -> Map κ ν) -> Map κ ν -> HashMap κ ν -> Map κ ν
forall k v a. (k -> v -> a -> a) -> a -> HashMap k v -> a
HashMap.foldrWithKey κ -> ν -> Map κ ν -> Map κ ν
forall k a. Ord k => k -> a -> Map k a -> Map k a
OrdMap.insert Map κ ν
forall k a. Map k a
OrdMap.empty HashMap κ ν
HashMap (K [(κ, ν)]) (V [(κ, ν)])
u)
intoMap :: [(κ, ν)] -> Map (K [(κ, ν)]) (V [(κ, ν)])
intoMap [(κ, ν)]
kvs = HashMap κ ν -> Map κ ν
forall κ ν. HashMap κ ν -> Map κ ν
Map ([(κ, ν)] -> HashMap κ ν
forall k v. (Eq k, Hashable k) => [(k, v)] -> HashMap k v
HashMap.fromList [(κ, ν)]
kvs)
newtype Set ε = Set (HashSet.HashSet ε)
deriving (Int -> Set ε -> ShowS
[Set ε] -> ShowS
Set ε -> String
(Int -> Set ε -> ShowS)
-> (Set ε -> String) -> ([Set ε] -> ShowS) -> Show (Set ε)
forall ε. Show ε => Int -> Set ε -> ShowS
forall ε. Show ε => [Set ε] -> ShowS
forall ε. Show ε => Set ε -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Set ε] -> ShowS
$cshowList :: forall ε. Show ε => [Set ε] -> ShowS
show :: Set ε -> String
$cshow :: forall ε. Show ε => Set ε -> String
showsPrec :: Int -> Set ε -> ShowS
$cshowsPrec :: forall ε. Show ε => Int -> Set ε -> ShowS
Show, Set ε -> Set ε -> Bool
(Set ε -> Set ε -> Bool) -> (Set ε -> Set ε -> Bool) -> Eq (Set ε)
forall ε. Eq ε => Set ε -> Set ε -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Set ε -> Set ε -> Bool
$c/= :: forall ε. Eq ε => Set ε -> Set ε -> Bool
== :: Set ε -> Set ε -> Bool
$c== :: forall ε. Eq ε => Set ε -> Set ε -> Bool
Eq)
unSet :: Set ε -> HashSet.HashSet ε
unSet :: Set ε -> HashSet ε
unSet (Set HashSet ε
u) = HashSet ε
u
{-# INLINE unSet #-}
instance Foldable Set where
foldr :: (a -> b -> b) -> b -> Set a -> b
foldr a -> b -> b
f b
start (Set HashSet a
u) = (a -> b -> b) -> b -> HashSet a -> b
forall b a. (b -> a -> a) -> a -> HashSet b -> a
HashSet.foldr a -> b -> b
f b
start HashSet a
u
null :: Set a -> Bool
null (Set HashSet a
u) = HashSet a -> Bool
forall a. HashSet a -> Bool
HashSet.null HashSet a
u
length :: Set a -> Int
length (Set HashSet a
u) = HashSet a -> Int
forall a. HashSet a -> Int
HashSet.size HashSet a
u
instance Key ε => Semigroup (Set ε) where
<> :: Set ε -> Set ε -> Set ε
(<>) (Set HashSet ε
u1) (Set HashSet ε
u2) = HashSet ε -> Set ε
forall ε. HashSet ε -> Set ε
Set (HashSet ε -> HashSet ε -> HashSet ε
forall a. (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a
HashSet.union HashSet ε
u1 HashSet ε
u2)
instance Key ε => Monoid (Set ε) where
mempty :: Set ε
mempty = Set ε
forall ε. Key ε => Set ε
emptySet
mappend :: Set ε -> Set ε -> Set ε
mappend = Set ε -> Set ε -> Set ε
forall a. Semigroup a => a -> a -> a
(<>)
emptySet :: Key ε => Set ε
emptySet :: Set ε
emptySet = HashSet ε -> Set ε
forall ε. HashSet ε -> Set ε
Set (HashSet ε
forall a. HashSet a
HashSet.empty)
singletonSet :: Key ε => ε -> Set ε
singletonSet :: ε -> Set ε
singletonSet ε
e = HashSet ε -> Set ε
forall ε. HashSet ε -> Set ε
Set (ε -> HashSet ε
forall a. Hashable a => a -> HashSet a
HashSet.singleton ε
e)
insertElement :: Key ε => ε -> Set ε -> Set ε
insertElement :: ε -> Set ε -> Set ε
insertElement ε
e (Set HashSet ε
u) = HashSet ε -> Set ε
forall ε. HashSet ε -> Set ε
Set (ε -> HashSet ε -> HashSet ε
forall a. (Eq a, Hashable a) => a -> HashSet a -> HashSet a
HashSet.insert ε
e HashSet ε
u)
containsElement :: Key ε => ε -> Set ε -> Bool
containsElement :: ε -> Set ε -> Bool
containsElement ε
e (Set HashSet ε
u) = ε -> HashSet ε -> Bool
forall a. (Eq a, Hashable a) => a -> HashSet a -> Bool
HashSet.member ε
e HashSet ε
u
class Collection α where
type E α :: Type
fromSet :: Set (E α) -> α
intoSet :: α -> Set (E α)
instance Key ε => Collection (Set ε) where
type E (Set ε) = ε
fromSet :: Set (E (Set ε)) -> Set ε
fromSet = Set (E (Set ε)) -> Set ε
forall a. a -> a
id
intoSet :: Set ε -> Set (E (Set ε))
intoSet = Set ε -> Set (E (Set ε))
forall a. a -> a
id
instance Key ε => Collection (HashSet.HashSet ε) where
type E (HashSet.HashSet ε) = ε
fromSet :: Set (E (HashSet ε)) -> HashSet ε
fromSet (Set HashSet (E (HashSet ε))
u) = HashSet ε
HashSet (E (HashSet ε))
u
intoSet :: HashSet ε -> Set (E (HashSet ε))
intoSet HashSet ε
u = HashSet ε -> Set ε
forall ε. HashSet ε -> Set ε
Set HashSet ε
u
instance Key ε => Collection (OrdSet.Set ε) where
type E (OrdSet.Set ε) = ε
fromSet :: Set (E (Set ε)) -> Set ε
fromSet (Set HashSet (E (Set ε))
u) = (ε -> Set ε -> Set ε) -> Set ε -> HashSet ε -> Set ε
forall b a. (b -> a -> a) -> a -> HashSet b -> a
HashSet.foldr ε -> Set ε -> Set ε
forall a. Ord a => a -> Set a -> Set a
OrdSet.insert Set ε
forall a. Set a
OrdSet.empty HashSet ε
HashSet (E (Set ε))
u
intoSet :: Set ε -> Set (E (Set ε))
intoSet Set ε
u = HashSet ε -> Set ε
forall ε. HashSet ε -> Set ε
Set ((ε -> HashSet ε -> HashSet ε) -> HashSet ε -> Set ε -> HashSet ε
forall a b. (a -> b -> b) -> b -> Set a -> b
OrdSet.foldr ε -> HashSet ε -> HashSet ε
forall a. (Eq a, Hashable a) => a -> HashSet a -> HashSet a
HashSet.insert HashSet ε
forall a. HashSet a
HashSet.empty Set ε
u)
instance Key ε => Collection [ε] where
type E [ε] = ε
fromSet :: Set (E [ε]) -> [ε]
fromSet (Set HashSet (E [ε])
u) = Set ε -> [ε]
forall a. Set a -> [a]
OrdSet.toList ((ε -> Set ε -> Set ε) -> Set ε -> HashSet ε -> Set ε
forall b a. (b -> a -> a) -> a -> HashSet b -> a
HashSet.foldr ε -> Set ε -> Set ε
forall a. Ord a => a -> Set a -> Set a
OrdSet.insert Set ε
forall a. Set a
OrdSet.empty HashSet ε
HashSet (E [ε])
u)
intoSet :: [ε] -> Set (E [ε])
intoSet [ε]
es = HashSet ε -> Set ε
forall ε. HashSet ε -> Set ε
Set ([ε] -> HashSet ε
forall a. (Eq a, Hashable a) => [a] -> HashSet a
HashSet.fromList [ε]
es)