-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Perfect minimal hashing implementation in native Haskell
--   
--   A <a>perfect hash function</a> for a set <tt>S</tt> is a hash function
--   that maps distinct elements in <tt>S</tt> to a set of integers, with
--   <b>no collisions</b>. A <a>minimal perfect hash function</a> is a
--   perfect hash function that maps <tt>n</tt> keys to <tt>n</tt>
--   <b>consecutive</b> integers, e.g. the numbers from <tt>0</tt> to
--   <tt>n-1</tt>.
--   
--   In contrast with the <a>PerfectHash package</a>, which is a binding to
--   a C-based library, this package is a fully-native Haskell
--   implementation.
--   
--   It is intended primarily for generating C code for embedded
--   applications (compare to <tt><a>gperf</a></tt>). The output of this
--   tool is a pair of arrays that can be included in generated C code for
--   <b><a>allocation-free</a> hash tables</b>.
--   
--   Though lookups also perform reasonably well for Haskell applications,
--   it hasn't been benchmarked thorougly with respect to other data
--   structures.
--   
--   This implementation was adapted from <a>Steve Hanov's Blog</a>.
--   
--   <h1>Usage</h1>
--   
--   The library is written generically to hash both strings and raw
--   integers according to the <a>FNV-1a algorithm</a>. Integers are split
--   by octets before hashing.
--   
--   <pre>
--   import Data.PerfectHash.Construction (createMinimalPerfectHash)
--   import qualified Data.HashMap.Strict as HashMap
--   
--   tuples = [
--      (1000, 1)
--    , (5555, 2)
--    , (9876, 3)
--    ]
--   
--   lookup_table = createMinimalPerfectHash $ HashMap.fromList tuples
--   </pre>
--   
--   Generation of C code based on the arrays in <tt>lookup_table</tt> is
--   left as an exercise to the reader. Algorithm documentation in the
--   <a>Data.PerfectHash.Hashing</a> and <a>Data.PerfectHash.Lookup</a>
--   modules will be helpful.
--   
--   See the <tt>hash-perfectly-strings-demo</tt> and
--   <tt>hash-perfectly-ints-demo</tt>, as well as the test suite, for
--   working examples.
--   
--   <pre>
--   $ stack build
--   $ stack exec hash-perfectly-strings-demo
--   </pre>
@package perfect-hash-generator
@version 0.2.0.6


-- | Implements the specialized hash function for this perfect hashing
--   algorithm.
--   
--   C code that makes use of the perfect hash table output must exactly
--   re-implement this <a>hash</a> function.
module Data.PerfectHash.Hashing

-- | This choice of prime number <tt>0x01000193</tt> was taken from the
--   Python implementation on <a>Steve Hanov's page</a>.
primeFNV :: Int

-- | Mechanism for a key to be decomposed into units processable by the
--   <a>FNV-1a</a> hashing algorithm.
class ToHashableChunks a
toHashableChunks :: ToHashableChunks a => a -> [Int]

-- | Uses the "FNV-1a" algorithm from the <a>FNV website</a>:
--   
--   <pre>
--   hash = offset_basis
--   for each octet_of_data to be hashed
--           hash = hash xor octet_of_data
--           hash = hash * FNV_prime
--   return hash
--   </pre>
--   
--   The interface is comparable to the <a>hashWithSalt</a> function from
--   the <tt>hashable</tt> package.
hash :: ToHashableChunks a => Int -> a -> Int
instance Data.PerfectHash.Hashing.ToHashableChunks GHC.Types.Int
instance Data.PerfectHash.Hashing.ToHashableChunks Data.Text.Internal.Text
instance Data.PerfectHash.Hashing.ToHashableChunks GHC.Base.String


-- | Note that what is referred to as a "nonce" in this library may be
--   better known as <a>"salt"</a>.
module Data.PerfectHash.Lookup

-- | Inputs for the lookup function.
--   
--   There are two arrays used in successive stages of the lookup. In this
--   implementation, both arrays are the same length.
data LookupTable a
LookupTable :: Vector Int -> Vector a -> LookupTable a

-- | This is the intermediate lookup table.
--   
--   In the lookup process, the key's hash is computed first with a nonce
--   of zero to obtain an index into this array.
--   
--   If the value at this index is negative, it is (after negating and
--   subtracting one) a direct index into the <a>values</a> array.
--   Otherwise, the value shall be used as a nonce in a second application
--   of the hashing function to compute the index into the <a>values</a>
--   array.
--   
--   See the documentation of <a>lookup</a> for details.
[nonces] :: LookupTable a -> Vector Int

-- | An array of values of arbitrary type.
--   
--   The objective of the perfect hash is to efficiently retrieve an index
--   into this array, given the key associated with the value at that
--   index.
[values] :: LookupTable a -> Vector a

-- | For embedded applications, this function would usually be
--   re-implemented in C code.
--   
--   <h2>Algorithm description</h2>
--   
--   The lookup procedure is three steps:
--   
--   <ol>
--   <li>Compute the <a>hash</a> (with a nonce of zero) of the "key",
--   modulo the length of the <a>values</a> array.</li>
--   <li>Use the resulting value as an index into the <a>nonces</a> array.
--   The value found there represents either a direct index into the
--   <a>values</a> array or a nonce for a second round of
--   hashing.<ul><li>If negative, it is the former. Negate it (to obtain a
--   positive value) and subtract one to obtain the actual
--   index.</li><li>Otherwise, re-compute the hash of the key, using this
--   value instead of zero as the nonce. Again, compute the modulus with
--   respect to the length of the <a>values</a> array.</li></ul></li>
--   <li>Use the result of (2) as the index into the <a>values</a>
--   array.</li>
--   </ol>
lookup :: (ToHashableChunks a, Unbox b) => LookupTable b -> a -> b


-- | Constructs a minimal perfect hash from a map of key-value pairs.
--   
--   Implementation was adapted from <a>Steve Hanov's Blog</a>.
--   
--   A refactoring of that Python implementation may be found <a>here</a>.
--   This Haskell implementation is transliterated from that refactoring.
module Data.PerfectHash.Construction

-- | Generates a minimal perfect hash for a set of key-value pairs.
--   
--   The keys must be instances of <a>ToHashableChunks</a>. The values may
--   be of arbitrary type.
--   
--   A <a>HashMap</a> is required as input to guarantee that there are no
--   duplicate keys.
createMinimalPerfectHash :: (Unbox b, Defaultable b, ToHashableChunks a, Eq a, Hashable a) => HashMap a b -> LookupTable b

-- | Used to fill empty slots when promoting a HashMap to a Vector
class Defaultable a
instance Data.PerfectHash.Construction.Defaultable GHC.Types.Int
