module Data.QuickSet
(
QuickSet,
fromList,
fromListN,
fromVector,
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 QuickSet a =
QuickSet (Vu.Vector a)
deriving (Data, Eq, Ord, Typeable)
instance (Ord a, Read a, Unbox a) => Read (QuickSet a) where
readsPrec pr =
map (\(vec, r) -> (fromVector vec, r)) . readsPrec pr
instance (Show a, Unbox a) => Show (QuickSet a) where
show (QuickSet vec) = show vec
fromList :: (Ord a, Unbox a) => [a] -> QuickSet a
fromList = fromVector . Vu.fromList
fromListN :: (Ord a, Unbox a) => Int -> [a] -> QuickSet a
fromListN n = fromVector . Vu.fromListN n
fromVector :: (Ord a, Unbox a) => Vu.Vector a -> QuickSet a
fromVector = QuickSet . Vu.modify Va.sort
member :: (Ord a, Unbox a) => a -> QuickSet a -> Bool
member k (QuickSet vec') =
runST $ do
vec <- Vu.unsafeThaw vec'
i <- Va.binarySearchL vec k
let k' = vec' Vu.! i
return (if i < Vu.length vec'
then compare k k' == EQ
else False)