quickset (empty) → 0.1.0

raw patch · 5 files changed

+262/−0 lines, 5 filesdep +basedep +vectordep +vector-algorithmssetup-changed

Dependencies added: base, vector, vector-algorithms

Files

• Data/QuickMap.hs +98/−0
• Data/QuickSet.hs +79/−0
• LICENSE +32/−0
• Setup.lhs +12/−0
• quickset.cabal +41/−0

@@ -0,0 +1,98 @@+-- |+-- Module:     Data.QuickMap+-- Copyright:  (c) 2012 Ertugrul Soeylemez+-- License:    BSD3+-- Maintainer: Ertugrul Soeylemez <es@ertes.de>+--+-- This module implements very fast and compact query-only maps.++module Data.QuickMap+    ( -- * QuickMap+      QuickMap,++      -- * Construction+      fromList,+      fromListN,+      fromVector,++      -- * Query+      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)+++-- | QuickMaps are maps from keys to values that use a compact unboxed+-- vector as the internal representation.  As such QuickMaps are always+-- strict in both the keys and values.++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+++-- | Convert a list to a 'QuickMap'.++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)+++-- | Convert a prefix of the given length of the given list to a+-- 'QuickMap'.++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)+++-- | Convert an unboxed vector to a 'QuickMap'.++fromVector :: (Ord k, Unbox a, Unbox k) => Vu.Vector (k, a) -> QuickMap k a+fromVector =+    QuickMap .+    Vu.modify (Va.sortBy (comparing fst))+++-- | Try to look up a key.++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+++-- | Check whether the given key is in the map.++member :: (Ord k, Unbox a, Unbox k) => k -> QuickMap k a -> Bool+member k = maybe False (const True) . lookup k

@@ -0,0 +1,79 @@+-- |+-- Module:     Data.QuickSet+-- Copyright:  (c) 2012 Ertugrul Soeylemez+-- License:    BSD3+-- Maintainer: Ertugrul Soeylemez <es@ertes.de>+--+-- This module implements very fast and compact query-only sets.++module Data.QuickSet+    ( -- * QuickSet+      QuickSet,++      -- * Construction+      fromList,+      fromListN,+      fromVector,++      -- * Query+      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)+++-- | QuickSets are sets that use a compact unboxed vector as the+-- internal representation.  As such QuickSets are always strict in the+-- values.++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+++-- | Convert a list to a 'QuickSet'.++fromList :: (Ord a, Unbox a) => [a] -> QuickSet a+fromList = fromVector . Vu.fromList+++-- | Convert a prefix of the given length of the given list to a+-- 'QuickSet'.++fromListN :: (Ord a, Unbox a) => Int -> [a] -> QuickSet a+fromListN n = fromVector . Vu.fromListN n+++-- | Convert an unboxed vector to a 'QuickSet'.++fromVector :: (Ord a, Unbox a) => Vu.Vector a -> QuickSet a+fromVector = QuickSet . Vu.modify Va.sort+++-- | Check whether the given value is in the set.++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)

@@ -0,0 +1,32 @@+quickset license+Copyright (c) 2012, Ertugrul Soeylemez++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are+met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above copyright+      notice, this list of conditions and the following disclaimer in+      the documentation and/or other materials provided with the+      distribution.++    * Neither the name of the author nor the names of any contributors+      may be used to endorse or promote products derived from this+      software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS+IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED+TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A+PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER+OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,+EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,+PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,12 @@+quickset setup script+Copyright (C) 2012, Ertugrul Soeylemez++Please see the LICENSE file for terms and conditions of use,+modification and distribution of this package, including this file.++> module Main where+>+> import Distribution.Simple+>+> main :: IO ()+> main = defaultMain

@@ -0,0 +1,41 @@+Name:          quickset+Version:       0.1.0+Category:      Data, Data Structures+Synopsis:      Very fast and memory-compact query-only set and map structures+Maintainer:    Ertugrul Söylemez <es@ertes.de>+Author:        Ertugrul Söylemez <es@ertes.de>+Copyright:     (c) 2012 Ertugrul Söylemez+License:       BSD3+License-file:  LICENSE+Build-type:    Simple+Stability:     experimental+Cabal-version: >= 1.10+Description:+    Very fast and memory-compact query-only set and map structures.++Source-repository head+    type:     darcs+    location: http://darcs.ertes.de/quickset/++Library+    Build-depends:+        base              >= 4.0 && < 5,+        vector            >= 0.9 && < 1,+        vector-algorithms >= 0.5 && < 1+    Default-language: Haskell2010+    Default-extensions:+        DeriveDataTypeable+    GHC-Options: -W+    Exposed-modules:+        Data.QuickMap+        Data.QuickSet++-- Executable quickset-test+--     Build-depends:+--         base >= 4 && < 5,+--         quickset+--     Default-language: Haskell2010+--     Default-extensions:+--     Hs-source-dirs: test+--     Main-is: Main.hs+--     GHC-Options: -threaded -rtsopts