1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
module RefMap (
RefMap,
null,
size,
member,
notMember,
fromList,
toList,
empty,
lookup,
insert,
insertNew,
elems,
delete,
adjust,
assocs,
) where
import Storage.Internal (RefDigest, Ref)
import Data.IntMap (IntMap)
import qualified Data.IntMap as IM
data RefMap a = IntMap [(RefDigest, a)]
instance Functor RefMap where
fmap f (RefMap im) = RefMap (fmap f im)
instance Foldable RefMap where
foldMap f (RefMap im) = foldMap f im
instance Traversable RefMap where
traverse f (RefMap im) = RefMap <$> traverse f im
splitRef :: Ref -> (Int, Digest)
splitRef r =
null :: RefMap a -> Bool
null (RefMap im) = IM.null im
size :: RefMap a -> Int
size (RefMap im) = sum $ map length $ IM.elems im
member :: Ref -> RefMap a -> Bool
member r (RefMap im) | Just xs <- IM.lookup i im = any ((==d) . fst) xs
| otherwise = False
where (i, d) = splitRef r
notMember :: (Integral i) => i -> RefMap a -> Bool
notMember i (RefMap im) = IM.notMember (fromIntegral i) im
fromList :: (Integral i) => [(i, a)] -> RefMap a
fromList xs = IDMap (maximum (map fst xs) + 1) $ IM.fromList $ map (\(i,x) -> (fromIntegral i, x)) xs
toList :: (Integral i) => RefMap a -> [(i, a)]
toList (RefMap im) = map (\(i,x) -> (fromIntegral i, x)) $ IM.toList im
empty :: (Integral i) => RefMap a
empty = IDMap 1 IM.empty
lookup :: (Integral i, Monad m) => i -> RefMap a -> m a
lookup i (RefMap im) = maybe (fail "IDMap.lookup: item not found") return $ IM.lookup (fromIntegral i) im
insert :: (Integral i) => i -> a -> RefMap a -> RefMap a
insert i x (RefMap im) = IDMap (max n (i+1)) (IM.insert (fromIntegral i) x im)
insertNew :: (Integral i) => a -> RefMap a -> (RefMap a, i)
insertNew x (RefMap im) = (IDMap (n+1) $ IM.insert (fromIntegral n) x im, n)
elems :: RefMap a -> [a]
elems (RefMap im) = IM.elems im
delete :: (Integral i) => i -> RefMap a -> RefMap a
delete i (RefMap im) = RefMap $ IM.delete (fromIntegral i) im
adjust :: (Integral i) => (a -> a) -> i -> RefMap a -> RefMap a
adjust f i (RefMap im) = RefMap $ IM.adjust f (fromIntegral i) im
assocs :: (Integral i) => RefMap a -> [(i,a)]
assocs (RefMap im) = map (\(i,x) -> (fromIntegral i, x)) $ IM.assocs im
|