compactmap (empty) → 0.1.1

raw patch · 5 files changed

+159/−0 lines, 5 filesdep +QuickCheckdep +basedep +compactmapsetup-changed

Dependencies added: QuickCheck, base, compactmap, containers, hspec, vector

Files

LICENSE +30/−0
Setup.hs +2/−0
compactmap.cabal +34/−0
src/Data/CompactMap.hs +63/−0
tests/tests.hs +30/−0

+ LICENSE view

@@ -0,0 +1,30 @@+Copyright (c) 2015, bartavelle++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 bartavelle nor the names of other+      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.

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

+ compactmap.cabal view

@@ -0,0 +1,34 @@+-- Initial compactmap.cabal generated by cabal init.  For further +-- documentation, see http://haskell.org/cabal/users-guide/++name:                compactmap+version:             0.1.1+synopsis:            A read-only memory-efficient key-value store.+-- description:         +license:             BSD3+license-file:        LICENSE+author:              bartavelle+maintainer:          bartavelle@gmail.com+-- copyright:           +category:            Data+build-type:          Simple+-- extra-source-files:  +cabal-version:       >=1.10++library+  exposed-modules:     Data.CompactMap+  -- other-modules:       +  -- other-extensions:    +  ghc-options:         -O2 -Wall+  build-depends:       base >=4.5 && <4.9, vector == 0.10.*+  hs-source-dirs:      src+  default-language:    Haskell2010++test-suite tests+  hs-source-dirs: tests+  type:           exitcode-stdio-1.0+  ghc-options:    -Wall -rtsopts -threaded+  build-depends:  base,compactmap,containers,hspec,QuickCheck+  main-is:        tests.hs+  default-language: Haskell2010+

+ src/Data/CompactMap.hs view

@@ -0,0 +1,63 @@+module Data.CompactMap+    ( CompactMap+    , fromList+    , toVector+    , lookup+    , getLE+    , getIndex+    ) where++import qualified Data.Vector as V+import GHC.Exts (sortWith)+import Data.Foldable as F+import Control.Applicative+import Prelude hiding (lookup)++data CompactMap k v = CompactMap (V.Vector v) (v -> k)++instance Show v => Show (CompactMap k v) where+    show = show . V.toList . getMap++instance Foldable (CompactMap k) where+    foldr f i = F.foldr f i . getMap+    foldMap f = F.foldMap f . getMap++getMap :: CompactMap k v -> V.Vector v+getMap (CompactMap lst _) = lst+{-# INLINE getMap #-}++fromList :: Ord k => [v] -> (v -> k) -> CompactMap k v+fromList lst f = CompactMap (V.fromList $ sortWith f lst) f++toVector :: CompactMap k v -> V.Vector v+toVector (CompactMap v _) = v++lookup :: Ord k => k -> CompactMap k v -> Maybe v+lookup k cm@(CompactMap _ f) = getLE k cm >>= \(_,r) -> if f r == k+                                                            then Just r+                                                            else Nothing++getLE :: Ord k => k -> CompactMap k v -> Maybe (Int, v)+getLE k (CompactMap lst f) = go 0 (sz - 1)+    where+        sz = V.length lst+        go l h+            | m < l     = Nothing+            | m > h     = Nothing+            | k' == k   = Just (m, x)+            | l >= h    = checkLower <|> Just (m, x)+            | k < k'    = checkLower <|> go l (m - 1)+            | otherwise = go (m + 1) h+            where+                checkLower+                    | m < 1 = Nothing+                    | k > k_1 = Just (m - 1, x_1)+                    | otherwise = Nothing+                m = (l + h) `div` 2+                x = lst V.! m+                k' = f x+                x_1 = lst V.! (m - 1)+                k_1 = f x_1++getIndex :: Int -> CompactMap k v -> Maybe v+getIndex i (CompactMap lst _) = lst V.!? i

+ tests/tests.hs view

@@ -0,0 +1,30 @@+module Main where++import Test.Hspec+import Test.QuickCheck+import qualified Data.CompactMap as CM+import qualified Data.Map.Strict as M+import Data.List (nubBy)+import Control.Applicative+import Data.Function (on)+import Prelude++listAndOtherkey :: Gen ([(Int,Int)], Int)+listAndOtherkey = do+    lst <- listOfInts+    let keys = map fst lst+    n <- suchThat arbitrary (`notElem` keys)+    return (lst, n)++listOfInts :: Gen [(Int, Int)]+listOfInts = nubBy ((==) `on` fst) <$> listOf ((,) <$> arbitrary <*> arbitrary)++main :: IO ()+main = hspec $+    describe "Data.CompactMap.lookup" $ do+        it "works like in containers when the key doesn't exist" $+            forAll listAndOtherkey $ \(list, k) -> M.lookup k (M.fromList list) == fmap snd (CM.lookup k (CM.fromList list fst))+        it "works like in containers when the key does exist" $+            forAll listOfInts $ \list -> let mp = M.fromList list+                                             cm = CM.fromList list fst+                                         in  all (\(k,_) -> M.lookup k mp == fmap snd (CM.lookup k cm)) list