{-# OPTIONS_HADDOCK prune #-}

-- | Note that what is referred to as a \"nonce\" in this library may be
-- better known as a \"<https://en.wikipedia.org/wiki/Salt_(cryptography) salt>\".
module Data.PerfectHash.Lookup (
    LookupTable (LookupTable, nonces, values)
  , size
  , encodeDirectEntry
  , lookup
  ) where

import           Data.Vector      (Vector, (!))
import qualified Data.Vector      as Vector
import           Prelude                  hiding (lookup)

import Data.PerfectHash.Types.Nonces (Nonce (Nonce))
import qualified Data.PerfectHash.Hashing as Hashing
import qualified Data.PerfectHash.Types.Nonces as Nonces


-- | 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 {
    nonces :: Vector Int
    -- ^ 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 'values' array.
    -- Otherwise, the value shall be used as a nonce in a second application of
    -- the hashing function to compute the index into the 'values' array.
    --
    -- See the documentation of 'lookup' for details.
  , values :: Vector a
    -- ^ 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.
  }


size :: LookupTable a -> Hashing.ArraySize
size = Hashing.ArraySize . Vector.length . values


-- NOTE: We subtract one to ensure it's negative even if the
-- zeroeth slot was used. This lets us test for "direct encoding"
-- by checking of the value is negative.
encodeDirectEntry :: Hashing.SlotIndex -> Int
encodeDirectEntry (Hashing.SlotIndex val) =
  subtract 1 $ negate val


-- | NOTE: negation, followed by subtracting 1 is its own self-inverse.
--
-- Example:
-- > a = 7
-- > f(a) = -7 - 1
-- >      = -8
-- >
-- > a' = -8
-- > f(a') = -(-8) - 1
-- >      = 8 - 1
-- >      = 7
decodeDirectEntry :: Int -> Hashing.SlotIndex
decodeDirectEntry val =
  Hashing.SlotIndex $ encodeDirectEntry $ Hashing.SlotIndex val


-- | For embedded applications, this function would usually be re-implemented
-- in C code.
--
-- == Procedure description
-- The lookup procedure is three steps:
--
--     1. Compute the 'Hashing.hash' (with a nonce of zero) of the "key", modulo
--        the length of the 'values' array.
--     2. Use the resulting value as an index into the 'nonces' array.  The value
--        found there represents either a direct index into the 'values' array
--        or a nonce for a second round of hashing.
--
--         * If negative, it is the former.  Negate it (to obtain a positive
--           value) and subtract one to obtain the actual index.
--         * 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 'values' array.
--
--     3. Use the result of (2) as the index into the 'values' array.
lookup
  :: (Hashing.ToHashableChunks a)
  => LookupTable b
  -> a -- ^ key
  -> b -- ^ value
lookup lookup_table key =

  values lookup_table ! v_key

  where
    table_size = size lookup_table

    Hashing.SlotIndex nonce_index = Hashing.hashToSlot (Nonce 0) table_size key
    nonce = nonces lookup_table ! nonce_index

    -- Negative nonce value indicates that we don't need extra lookup layer
    Hashing.SlotIndex v_key = if Nonces.isDirectSlot nonce
      then decodeDirectEntry nonce
      else Hashing.hashToSlot (Nonces.Nonce nonce) table_size key