module Data.QuickMap
(
QuickMap,
fromList,
fromListN,
fromVector,
lookup,
member
)
where
import qualified Data.Vector.Unboxed as Vu
import qualified Data.Vector.Algorithms.Heap as Va
import qualified Data.Vector.Algorithms.Search as Va
import Control.Monad
import Control.Monad.ST
import Data.Data
import Data.Ord
import Data.Vector.Unboxed (Unbox)
import Prelude hiding (lookup)
newtype QuickMap k a =
QuickMap (Vu.Vector (k, a))
deriving (Data, Eq, Ord, Typeable)
instance (Ord k, Read a, Read k, Unbox a, Unbox k) => Read (QuickMap k a) where
readsPrec pr =
map (\(vec, r) -> (fromVector vec, r)) . readsPrec pr
instance (Show a, Show k, Unbox a, Unbox k) => Show (QuickMap k a) where
show (QuickMap vec) = show vec
fromList :: (Ord k, Unbox a, Unbox k) => [(k, a)] -> QuickMap k a
fromList xs =
(QuickMap . Vu.create)
(do vec <- Vu.unsafeThaw (Vu.fromList xs)
Va.sortBy (comparing fst) vec
return vec)
fromListN :: (Ord k, Unbox a, Unbox k) => Int -> [(k, a)] -> QuickMap k a
fromListN n xs =
(QuickMap . Vu.create)
(do vec <- Vu.unsafeThaw (Vu.fromListN n xs)
Va.sortBy (comparing fst) vec
return vec)
fromVector :: (Ord k, Unbox a, Unbox k) => Vu.Vector (k, a) -> QuickMap k a
fromVector =
QuickMap .
Vu.modify (Va.sortBy (comparing fst))
lookup :: (Ord k, Unbox a, Unbox k) => k -> QuickMap k a -> Maybe a
lookup k (QuickMap vec') =
runST $ do
vec <- Vu.unsafeThaw vec'
i <- Va.binarySearchLBy (comparing fst) vec (k, undefined)
let (k', x) = vec' Vu.! i
return $ do
guard (i < Vu.length vec')
case compare k k' of
EQ -> return x
_ -> Nothing
member :: (Ord k, Unbox a, Unbox k) => k -> QuickMap k a -> Bool
member k = maybe False (const True) . lookup k