{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE ScopedTypeVariables #-}
module Arbor.LruCache.Internal.PriorityQueue where
import Data.List (sortOn, splitAt)
newtype PQueue p v = PQueue [(p, v)]
deriving (Eq, Show)
insert :: Eq v => p -> v -> PQueue p v -> PQueue p v
insert !p !v (PQueue qas) =
let lst = (p, v):filter ((/= v) . snd) qas
in PQueue (forceSpine lst)
take :: Ord p => Int -> PQueue p v -> ([v], PQueue p v)
take n (PQueue qas) = case splitAt n (sortOn fst qas) of
(as, bs) -> (snd <$> as, PQueue bs)
empty :: PQueue p v
empty = PQueue []
toList :: Ord p => PQueue p v -> [(p, v)]
toList (PQueue qas) = sortOn fst qas
size :: PQueue p v -> Int
size (PQueue qas) = length qas
forceSpine :: [a] -> [a]
forceSpine as =
let fc = foldr (const id) () as
in fc `seq` as