2009/8/19 Job Vranish
My first hacked up attempt is as follows:
data IndexedCollection a = IndexedCollection { nextKey :: Int, availableKeys :: [Int], items :: (IntMap Int a) } deriving (Show)
emptyIndexedCollection :: IndexedCollection a emptyIndexedCollection = IndexedCollection 0 [] empty
addItem :: a -> IndexedCollection a -> (Int, IndexedCollection a) addItem a (IndexedCollection nextKey' [] t) = (nextKey', IndexedCollection (nextKey' + 1) [] (insert nextKey' a t)) addItem a (IndexedCollection nextKey' (k:ks) t) = (k, IndexedCollection nextKey' ks (insert k a t))
removeItem :: Int -> IndexedCollection a -> IndexedCollection a removeItem k (IndexedCollection nextKey' ks t) = IndexedCollection nextKey' (k:ks) (delete k t)
lookupItem :: Int -> IndexedCollection a -> Maybe a lookupItem k (IndexedCollection _ _ t) = lookup k t
It might be the case for IntMap (I haven't checked) that it is better to do a modify operation than to do a deletion followed by an insertion on the same key. One possible improvement is to delay deletions by putting them in a pending queue. A pending deletion followed by an addItem could be coalesced into a modify operation on the key to be deleted. You could even push lookupItems through pending deletions, assuming that they aren't on the same key (if they are on the same key then the lookup would fail). One question is how big should the pending deletion queue be allowed to become? A long queue might not be a good idea. One problem with delaying deletions is that it could introduce a space leak (same as unintended lazy evaluation). Maybe a queue of max length one is sufficient? I'm not sure it is worth the trouble, but it might be fun to try. Cheers, Bernie.