module Data.LinkedHashMap.IntMap
(
LinkedHashMap(..)
, empty
, singleton
, null
, size
, member
, lookup
, lookupDefault
, (!)
, insert
, insertWith
, delete
, adjust
, union
, unionWith
, unions
, map
, mapWithKey
, traverseWithKey
, difference
, intersection
, intersectionWith
, foldl'
, foldlWithKey'
, foldr
, foldrWithKey
, filter
, filterWithKey
, keys
, elems
, toList
, fromList
, fromListWith
)
where
import Prelude hiding (foldr, map, null, lookup, filter)
import Data.Maybe
import Data.Hashable (Hashable)
import Control.DeepSeq (NFData(rnf))
import Control.Applicative ((<$>), Applicative)
import qualified Data.List as L
import qualified Data.Foldable as F
import qualified Data.Traversable as T
import qualified Data.HashMap.Strict as M
import qualified Data.IntMap.Strict as IM
data Entry a = Entry !Int a deriving (Show)
data LinkedHashMap k v = LinkedHashMap (M.HashMap k (Entry v)) (IM.IntMap (k, v)) !Int
instance (Show k, Show v) => Show (LinkedHashMap k v) where
showsPrec d m@(LinkedHashMap _ _ _) = showParen (d > 10) $
showString "fromList " . shows (toList m)
lookup :: (Eq k, Hashable k) => k -> LinkedHashMap k v -> Maybe v
lookup k0 (LinkedHashMap m0 _ _) = case M.lookup k0 m0 of
Just (Entry _ v) -> Just v
Nothing -> Nothing
lookupDefault :: (Eq k, Hashable k)
=> v
-> k -> LinkedHashMap k v -> v
lookupDefault def k t = case lookup k t of
Just v -> v
_ -> def
(!) :: (Eq k, Hashable k) => LinkedHashMap k v -> k -> v
(!) m k = case lookup k m of
Just v -> v
Nothing -> error "Data.LinkedHashMap.IntMap.(!): key not found"
delete :: (Eq k, Hashable k) => k -> LinkedHashMap k v -> LinkedHashMap k v
delete k0 (LinkedHashMap m s maxn) = LinkedHashMap (M.delete k0 m) (case M.lookup k0 m of
Nothing -> s
Just (Entry i _) -> IM.delete i s) maxn
empty :: LinkedHashMap k v
empty = LinkedHashMap M.empty IM.empty minBound
singleton :: (Eq k, Hashable k) => k -> v -> LinkedHashMap k v
singleton k v = fromList [(k, v)]
null :: LinkedHashMap k v -> Bool
null (LinkedHashMap m _ _) = M.null m
member :: (Eq k, Hashable k) => k -> LinkedHashMap k a -> Bool
member k m = case lookup k m of
Nothing -> False
Just _ -> True
size :: LinkedHashMap k v -> Int
size (LinkedHashMap _ s _) = IM.size s
keys :: (Eq k, Hashable k) => LinkedHashMap k v -> [k]
keys m = fmap (\(k, _) -> k) $ toList m
elems :: (Eq k, Hashable k) => LinkedHashMap k v -> [v]
elems m = fmap (\(_, v) -> v) $ toList m
fromList :: (Eq k, Hashable k) => [(k, v)] -> LinkedHashMap k v
fromList = F.foldl' (\m (k, v) -> insert k v m) empty
toList :: LinkedHashMap k v -> [(k, v)]
toList (LinkedHashMap _ s _) = IM.elems s
insert :: (Eq k, Hashable k) => k -> v -> LinkedHashMap k v -> LinkedHashMap k v
insert k v (LinkedHashMap m s maxn) = s' `seq` LinkedHashMap m' s' maxn'
where
m' = M.insert k (Entry n' v) m
s' = IM.insert n' (k, v) s
(n', maxn') = case M.lookup k m of
Just (Entry n _) -> (n, maxn)
Nothing -> let newn = maxn + 1 in (newn, newn)
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> LinkedHashMap k v -> LinkedHashMap k v
insertWith f k v0 (LinkedHashMap m s maxn) = s' `seq` LinkedHashMap m' s' maxn'
where
m' = M.insert k (Entry n' v') m
s' = IM.insert n' (k, v') s
(n', v', maxn') = case M.lookup k m of
Just (Entry n v) -> (n, f v0 v, maxn)
Nothing -> let newn = maxn + 1 in (newn, v0, newn)
adjust :: (Eq k, Hashable k) => (v -> v) -> k -> LinkedHashMap k v -> LinkedHashMap k v
adjust f k (LinkedHashMap m s maxn) = LinkedHashMap m' s' maxn
where
m' = M.adjust f' k m
f' (Entry ix v) = Entry ix $ f v
s' = case M.lookup k m' of
Just (Entry ix v) -> IM.insert ix (k, v) s
Nothing -> s
union :: (Eq k, Hashable k) => LinkedHashMap k v -> LinkedHashMap k v -> LinkedHashMap k v
union = unionWith const
unionWith :: (Eq k, Hashable k) => (v -> v -> v) -> LinkedHashMap k v -> LinkedHashMap k v
-> LinkedHashMap k v
unionWith f m1 m2 = m'
where
m' = F.foldl' (\m (k, v) -> insertWith (flip f) k v m) m1 $ toList m2
unions :: (Eq k, Hashable k) => [LinkedHashMap k v] -> LinkedHashMap k v
unions = F.foldl' union empty
map :: (v1 -> v2) -> LinkedHashMap k v1 -> LinkedHashMap k v2
map f = mapWithKey (const f)
mapWithKey :: (k -> v1 -> v2) -> LinkedHashMap k v1 -> LinkedHashMap k v2
mapWithKey f (LinkedHashMap m s maxn) = (LinkedHashMap m' s' maxn)
where
m' = M.mapWithKey f' m
s' = fmap f'' s
f' k (Entry ix v1) = Entry ix $ f k v1
f'' (k, v1) = (k, f k v1)
traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> LinkedHashMap k v1
-> f (LinkedHashMap k v2)
traverseWithKey f (LinkedHashMap m0 s0 maxn) = (\s -> LinkedHashMap (M.map (getV2 s) m0) s maxn) <$> s'
where
s' = T.traverse f' s0
f' (k, v1) = (\v -> (k, v)) <$> f k v1
getV2 s (Entry ix _) = let (_, v2) = fromJust $ IM.lookup ix s in Entry ix v2
difference :: (Eq k, Hashable k) => LinkedHashMap k v -> LinkedHashMap k w -> LinkedHashMap k v
difference a b = foldlWithKey' go empty a
where
go m k v = case lookup k b of
Nothing -> insert k v m
_ -> m
intersection :: (Eq k, Hashable k) => LinkedHashMap k v -> LinkedHashMap k w -> LinkedHashMap k v
intersection a b = foldlWithKey' go empty a
where
go m k v = case lookup k b of
Just _ -> insert k v m
_ -> m
intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> LinkedHashMap k v1
-> LinkedHashMap k v2 -> LinkedHashMap k v3
intersectionWith f a b = foldlWithKey' go empty a
where
go m k v = case lookup k b of
Just w -> insert k (f v w) m
_ -> m
foldl' :: (a -> v -> a) -> a -> LinkedHashMap k v -> a
foldl' f b0 (LinkedHashMap _ s _) = F.foldl' f' b0 s
where
f' b (_, v) = f b v
foldr :: (v -> a -> a) -> a -> LinkedHashMap k v -> a
foldr = F.foldr
foldlWithKey' :: (a -> k -> v -> a) -> a -> LinkedHashMap k v -> a
foldlWithKey' f b0 (LinkedHashMap _ s _) = F.foldl' f' b0 s
where
f' b (k, v) = f b k v
foldrWithKey :: (k -> v -> a -> a) -> a -> LinkedHashMap k v -> a
foldrWithKey f b0 (LinkedHashMap _ s _) = F.foldr f' b0 s
where
f' (k, v) b = f k v b
filterWithKey :: (Eq k, Hashable k) => (k -> v -> Bool) -> LinkedHashMap k v -> LinkedHashMap k v
filterWithKey p m = fromList $ L.filter (uncurry p) $ toList m
filter :: (Eq k, Hashable k) => (v -> Bool) -> LinkedHashMap k v -> LinkedHashMap k v
filter p = filterWithKey (\_ v -> p v)
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> LinkedHashMap k v
fromListWith f = L.foldl' (\ m (k, v) -> insertWith f k v m) empty
instance (NFData a) => NFData (Entry a) where
rnf (Entry _ a) = rnf a
instance (NFData k, NFData v) => NFData (LinkedHashMap k v) where
rnf (LinkedHashMap m s _) = rnf m `seq` rnf s
instance Functor (LinkedHashMap k) where
fmap = map
instance F.Foldable (LinkedHashMap k) where
foldr f b0 (LinkedHashMap _ s _) = F.foldr f' b0 s
where
f' (_, v) b = f v b
instance T.Traversable (LinkedHashMap k) where
traverse f = traverseWithKey (const f)