packages feed

perfect-hash-generator 0.2.0.3 → 0.2.0.4

raw patch · 8 files changed

+153/−159 lines, 8 files

Files

− demo/Ints/Main.hs 
@@ -1,66 +0,0 @@-module Ints.Main where--import           System.Random                 (RandomGen, mkStdGen, random)--import           Data.IntSet                   (IntSet)-import qualified Data.IntSet                   as IntSet-import qualified Data.PerfectHash.Construction as Construction-import qualified Data.PerfectHash.Lookup       as Lookup-import qualified Data.Vector.Unboxed           as Vector-import qualified Exercise---valueCount = 250000---data RandIntAccum t = RandIntAccum-  t -- ^ random number generator-  Int -- ^ max count-  IntSet -- ^ accumulated unique random numbers----- | Since computing the size of the set is O(N), we--- maintain the count separately.-getUniqueRandomIntegers :: RandomGen t => RandIntAccum t -> IntSet-getUniqueRandomIntegers (RandIntAccum std_gen count current_set) =--  if count == 0-    then current_set-    else getUniqueRandomIntegers newstate--  where-    (next_int, next_std_gen) = random std_gen--    a = RandIntAccum next_std_gen-    newstate = if IntSet.member next_int current_set-      then a count current_set-      else a (count - 1) (IntSet.insert next_int current_set)---intMapTuples :: [(Int, Int)]-intMapTuples = zip random_ints [1..]-  where-    seed_value = RandIntAccum (mkStdGen 0) valueCount IntSet.empty-    random_ints = IntSet.toList $ getUniqueRandomIntegers seed_value---main = do-  putStrLn $ unwords ["Keys size:", show $ length intMapTuples]--  let lookup_table = Construction.createMinimalPerfectHash intMapTuples--  putStrLn $ unwords [-      "Finished computing lookup table with"-    , show $ Lookup.size lookup_table-    , "entries."-    ]--  let direct_mapping_nonces = Vector.filter (< 0) $ Lookup.nonces lookup_table--  putStrLn $ unwords [-      "There were"-    , show $ Vector.length direct_mapping_nonces-    , "lookup entries with direct mappings."-    ]--  Exercise.eitherExit $ Exercise.testLookups lookup_table intMapTuples
− demo/Strings/Main.hs 
@@ -1,33 +0,0 @@-module Strings.Main where--import           Control.Monad                 (when)--import qualified Data.PerfectHash.Construction as Construction-import qualified Data.PerfectHash.Lookup       as Lookup-import qualified Exercise---enableDebug = False--dictionaryPath = "/usr/share/dict/words"---main = do--  word_index_tuples <- Exercise.wordsFromFile dictionaryPath--  putStrLn $ unwords ["Words size:", show $ length word_index_tuples]--  let lookup_table = Construction.createMinimalPerfectHash word_index_tuples--  putStrLn $ unwords [-      "Finished computing lookup table with"-    , show $ Lookup.size lookup_table-    , "entries."-    ]--  when enableDebug $ do-    putStrLn $ unwords ["Vector G:", show $ Lookup.nonces lookup_table]-    putStrLn $ unwords ["Vector V:", show $ Lookup.values lookup_table]--  Exercise.eitherExit $ Exercise.testLookups lookup_table word_index_tuples
+ demo/ints/Main.hs view
@@ -0,0 +1,66 @@+module Main where++import           System.Random                 (RandomGen, mkStdGen, random)++import           Data.IntSet                   (IntSet)+import qualified Data.IntSet                   as IntSet+import qualified Data.PerfectHash.Construction as Construction+import qualified Data.PerfectHash.Lookup       as Lookup+import qualified Data.PerfectHash.TestUtils    as Exercise+import qualified Data.Vector.Unboxed           as Vector+++valueCount = 250000+++data RandIntAccum t = RandIntAccum+  t -- ^ random number generator+  Int -- ^ max count+  IntSet -- ^ accumulated unique random numbers+++-- | Since computing the size of the set is O(N), we+-- maintain the count separately.+getUniqueRandomIntegers :: RandomGen t => RandIntAccum t -> IntSet+getUniqueRandomIntegers (RandIntAccum std_gen count current_set) =++  if count == 0+    then current_set+    else getUniqueRandomIntegers newstate++  where+    (next_int, next_std_gen) = random std_gen++    a = RandIntAccum next_std_gen+    newstate = if IntSet.member next_int current_set+      then a count current_set+      else a (count - 1) (IntSet.insert next_int current_set)+++intMapTuples :: [(Int, Int)]+intMapTuples = zip random_ints [1..]+  where+    seed_value = RandIntAccum (mkStdGen 0) valueCount IntSet.empty+    random_ints = IntSet.toList $ getUniqueRandomIntegers seed_value+++main = do+  putStrLn $ unwords ["Keys size:", show $ length intMapTuples]++  let lookup_table = Construction.createMinimalPerfectHash intMapTuples++  putStrLn $ unwords [+      "Finished computing lookup table with"+    , show $ Lookup.size lookup_table+    , "entries."+    ]++  let direct_mapping_nonces = Vector.filter (< 0) $ Lookup.nonces lookup_table++  putStrLn $ unwords [+      "There were"+    , show $ Vector.length direct_mapping_nonces+    , "lookup entries with direct mappings."+    ]++  Exercise.eitherExit $ Exercise.testLookups lookup_table intMapTuples
+ demo/strings/Main.hs view
@@ -0,0 +1,33 @@+module Main where++import           Control.Monad                 (when)++import qualified Data.PerfectHash.Construction as Construction+import qualified Data.PerfectHash.Lookup       as Lookup+import qualified Data.PerfectHash.TestUtils    as Exercise+++enableDebug = False++dictionaryPath = "/usr/share/dict/words"+++main = do++  word_index_tuples <- Exercise.wordsFromFile dictionaryPath++  putStrLn $ unwords ["Words size:", show $ length word_index_tuples]++  let lookup_table = Construction.createMinimalPerfectHash word_index_tuples++  putStrLn $ unwords [+      "Finished computing lookup table with"+    , show $ Lookup.size lookup_table+    , "entries."+    ]++  when enableDebug $ do+    putStrLn $ unwords ["Vector G:", show $ Lookup.nonces lookup_table]+    putStrLn $ unwords ["Vector V:", show $ Lookup.values lookup_table]++  Exercise.eitherExit $ Exercise.testLookups lookup_table word_index_tuples
perfect-hash-generator.cabal view
@@ -2,10 +2,10 @@ -- -- see: https://github.com/sol/hpack ----- hash: 1698f1d36979cbf05571994d0eceb9f922608eac19a6c04d98a86117dc5f37cf+-- hash: 3429fd1131c7e55998ad9391be6e8af0010ce07ec53e20ea840551bc47a942ac  name:           perfect-hash-generator-version:        0.2.0.3+version:        0.2.0.4 synopsis:       Perfect minimal hashing implementation in native Haskell description:     A <https://en.wikipedia.org/wiki/Perfect_hash_function perfect hash function> for a set @S@ is a hash function that maps distinct elements in @S@ to a set of integers, with __no collisions__. A <https://en.wikipedia.org/wiki/Perfect_hash_function#Minimal_perfect_hash_function minimal perfect hash function> is a perfect hash function that maps @n@ keys to @n@ __consecutive__ integers, e.g. the numbers from @0@ to @n-1@.                 .@@ -70,15 +70,15 @@       Data.PerfectHash.Construction       Data.PerfectHash.Hashing       Data.PerfectHash.Lookup+      Data.PerfectHash.TestUtils   other-modules:       Paths_perfect_hash_generator   default-language: Haskell2010  executable hash-perfectly-ints-demo-  main-is: Ints/Main.hs+  main-is: Main.hs   hs-source-dirs:-      demo-      test+      demo/ints   ghc-options: -fwarn-tabs -W   build-depends:       base >=4.5 && <5@@ -93,17 +93,13 @@     , unordered-containers     , vector   other-modules:-      Strings.Main-      Exercise-      Main       Paths_perfect_hash_generator   default-language: Haskell2010  executable hash-perfectly-strings-demo-  main-is: Strings/Main.hs+  main-is: Main.hs   hs-source-dirs:-      demo-      test+      demo/strings   ghc-options: -fwarn-tabs -W   build-depends:       base >=4.5 && <5@@ -117,9 +113,6 @@     , unordered-containers     , vector   other-modules:-      Ints.Main-      Exercise-      Main       Paths_perfect_hash_generator   default-language: Haskell2010 @@ -143,6 +136,5 @@     , unordered-containers     , vector   other-modules:-      Exercise       Paths_perfect_hash_generator   default-language: Haskell2010
+ src/Data/PerfectHash/TestUtils.hs view
@@ -0,0 +1,46 @@+-- | This module is not used by the main library for constructing perfect hashes;+-- it just provides convenience functions for use by the tests and demonstration executables.+module Data.PerfectHash.TestUtils where++import           Control.Monad            (unless)+import           Data.Foldable            (traverse_)+import qualified Data.Vector.Unboxed      as Vector++import qualified Data.PerfectHash.Hashing as Hashing+import qualified Data.PerfectHash.Lookup  as Lookup+++testLookups :: (Show b, Eq b, Show a, Hashing.ToHashableChunks a, Vector.Unbox b) =>+     Lookup.LookupTable b+  -> [(a, b)]+  -> Either String ()+testLookups lookup_table =+  traverse_ check_entry+  where+    check_entry (word, source_index) = unless (lookup_result == source_index) $+      Left $ unwords [+          "Result for key"+        , show word+        , "had incorrect index"+        , show lookup_result+        , "; should have been"+        , show source_index+        ]+      where+        lookup_result = Lookup.lookupPerfect lookup_table word+++-- | Generate a map of words from a file to their line numbers.+--+-- Intended for use with @\"/usr/share/dict/words\"@.+wordsFromFile :: FilePath -> IO [(String, Int)]+wordsFromFile path = do+  file_lines <- readFile path+  let word_index_tuples = zip (lines file_lines) [1..]+  return word_index_tuples+++eitherExit :: Either String b -> IO ()+eitherExit x = case x of+  Left err -> error err+  Right _ -> return ()
− test/Exercise.hs 
@@ -1,44 +0,0 @@-module Exercise where--import           Control.Monad            (unless)-import           Data.Foldable            (traverse_)-import qualified Data.Vector.Unboxed      as Vector--import qualified Data.PerfectHash.Hashing as Hashing-import qualified Data.PerfectHash.Lookup  as Lookup---testLookups :: (Show b, Eq b, Show a, Hashing.ToHashableChunks a, Vector.Unbox b) =>-     Lookup.LookupTable b-  -> [(a, b)]-  -> Either String ()-testLookups lookup_table =-  traverse_ check_entry-  where-    check_entry (word, source_index) = unless (lookup_result == source_index) $-      Left $ unwords [-          "Result for key"-        , show word-        , "had incorrect index"-        , show lookup_result-        , "; should have been"-        , show source_index-        ]-      where-        lookup_result = Lookup.lookupPerfect lookup_table word----- | Generate a map of words from a file to their line numbers.------ Intended for use with @\"/usr/share/dict/words\"@.-wordsFromFile :: FilePath -> IO [(String, Int)]-wordsFromFile path = do-  file_lines <- readFile path-  let word_index_tuples = zip (lines file_lines) [1..]-  return word_index_tuples---eitherExit :: Either String b -> IO ()-eitherExit x = case x of-  Left err -> error err-  Right _ -> return ()
test/Main.hs view
@@ -12,7 +12,7 @@  import qualified Data.PerfectHash.Construction  as Construction import qualified Data.PerfectHash.Hashing       as Hashing-import qualified Exercise+import qualified Data.PerfectHash.TestUtils     as Exercise   testHashComputation :: (Hashing.ToHashableChunks a, Show a) =>