content: 
  module General.MRU(
      MRU, empty, insert, lookup, delete, toList
      ) where
  
  import Prelude hiding (lookup)
  import qualified Data.Map as Map
  import qualified Data.IntMap as IntMap
  import Data.Tuple.Extra
  
  
  -- Basically a bimap where we can do minview on the second element
  data MRU k v = MRU
      Int -- usage index
      (Map.Map k (Int, v)) -- when did I last use this thing
      (IntMap.IntMap k) -- what was used at which point
  
  
  empty :: MRU k v
  empty = MRU 0 Map.empty IntMap.empty
  
  toList :: MRU k v -> [(k, v)]
  toList (MRU _ mp1 _) = map (second snd) $ Map.toList mp1
  
  insert :: Ord k => k -> v -> MRU k v -> MRU k v
  insert k v (MRU n mp1 mp2) = MRU (n+1) (Map.insert k (n, v) mp1) (IntMap.insert n k mp22)
      where mp22 = case Map.lookup k mp1 of Nothing -> mp2; Just (i,_) -> IntMap.delete i mp2
  
  lookup :: Ord k => k -> MRU k v -> Maybe v
  lookup k (MRU _ mp1 _) = fmap snd $ Map.lookup k mp1
  
  delete :: Ord k => MRU k v -> Maybe (k, MRU k v)
  delete (MRU n mp1 mp2) = case IntMap.minViewWithKey mp2 of
      Nothing -> Nothing
      Just ((i,k), mp2) -> Just (k, MRU n (Map.delete k mp1) mp2)
  