------------------------------------------------------------------------------
--                                                                          --
--                         GNAT COMPILER COMPONENTS                         --
--                                                                          --
--          G N A T . P E R F E C T _ H A S H _ G E N E R A T O R S         --
--                                                                          --
--                                 S p e c                                  --
--                                                                          --
--                     Copyright (C) 2002-2021, AdaCore                     --
--                                                                          --
-- GNAT is free software;  you can  redistribute it  and/or modify it under --
-- terms of the  GNU General Public License as published  by the Free Soft- --
-- ware  Foundation;  either version 3,  or (at your option) any later ver- --
-- sion.  GNAT is distributed in the hope that it will be useful, but WITH- --
-- OUT ANY WARRANTY;  without even the  implied warranty of MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE.                                     --
--                                                                          --
-- As a special exception under Section 7 of GPL version 3, you are granted --
-- additional permissions described in the GCC Runtime Library Exception,   --
-- version 3.1, as published by the Free Software Foundation.               --
--                                                                          --
-- You should have received a copy of the GNU General Public License and    --
-- a copy of the GCC Runtime Library Exception along with this program;     --
-- see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see    --
-- <http://www.gnu.org/licenses/>.                                          --
--                                                                          --
-- GNAT was originally developed  by the GNAT team at  New York University. --
-- Extensive contributions were provided by Ada Core Technologies Inc.      --
--                                                                          --
------------------------------------------------------------------------------

--  This package provides a generator of static minimal perfect hash functions.
--  To understand what a perfect hash function is, we define several notions.
--  These definitions are inspired from the following paper:

--    Zbigniew J. Czech, George Havas, and Bohdan S. Majewski ``An Optimal
--    Algorithm for Generating Minimal Perfect Hash Functions'', Information
--    Processing Letters, 43(1992) pp.257-264, Oct.1992

--  Let W be a set of m words. A hash function h is a function that maps the
--  set of words W into some given interval I of integers [0, k-1], where k is
--  an integer, usually k >= m. h (w) where w is a word in W computes an
--  address or an integer from I for the storage or the retrieval of that
--  item. The storage area used to store items is known as a hash table. Words
--  for which the same address is computed are called synonyms. Due to the
--  existence of synonyms a situation called collision may arise in which two
--  items w1 and w2 have the same address. Several schemes for resolving
--  collisions are known. A perfect hash function is an injection from the word
--  set W to the integer interval I with k >= m.  If k = m, then h is a minimal
--  perfect hash function. A hash function is order preserving if it puts
--  entries into the hash table in a prespecified order.

--  A minimal perfect hash function is defined by two properties:

--    Since no collisions occur each item can be retrieved from the table in
--    *one* probe. This represents the "perfect" property.

--    The hash table size corresponds to the exact size of W and *no larger*.
--    This represents the "minimal" property.

--  The functions generated by this package require the words to be known in
--  advance (they are "static" hash functions). The hash functions are also
--  order preserving. If w2 is inserted after w1 in the generator, then h (w1)
--  < h (w2). These hashing functions are convenient for use with realtime
--  applications.

with System.Perfect_Hash_Generators;

package GNAT.Perfect_Hash_Generators is

   package SPHG renames System.Perfect_Hash_Generators;

   Default_K_To_V : constant Float  := 2.05;
   --  Default ratio for the algorithm. When K is the number of keys, V =
   --  (K_To_V) * K is the size of the main table of the hash function. To
   --  converge, the algorithm requires K_To_V to be strictly greater than 2.0.

   Default_Pkg_Name : constant String := "Perfect_Hash";
   --  Default package name in which the hash function is defined

   Default_Position : constant String := "";
   --  The generator allows selection of the character positions used in the
   --  hash function. By default, all positions are selected.

   Default_Tries : constant Positive := 20;
   --  This algorithm may not succeed to find a possible mapping on the first
   --  try and may have to iterate a number of times. This constant bounds the
   --  number of tries.

   type Optimization is new SPHG.Optimization;
   --  Optimize either the memory space or the execution time. Note: in
   --  practice, the optimization mode has little effect on speed. The tables
   --  are somewhat smaller with Memory_Space.

   Verbose : Boolean renames SPHG.Verbose;
   --  Output the status of the algorithm. For instance, the tables, the random
   --  graph (edges, vertices) and selected char positions are output between
   --  two iterations.

   procedure Initialize
     (Seed   : Natural;
      K_To_V : Float        := Default_K_To_V;
      Optim  : Optimization := Memory_Space;
      Tries  : Positive     := Default_Tries);
   --  Initialize the generator and its internal structures. Set the ratio of
   --  vertices over keys in the random graphs. This value has to be greater
   --  than 2.0 in order for the algorithm to succeed. The word set is not
   --  modified (in particular when it is already set). For instance, it is
   --  possible to run several times the generator with different settings on
   --  the same words.
   --
   --  A classical way of doing is to Insert all the words and then to invoke
   --  Initialize and Compute. If this fails to find a perfect hash function,
   --  invoke Initialize again with other configuration parameters (probably
   --  with a greater K_To_V ratio). Once successful, invoke Produce and then
   --  Finalize.

   procedure Finalize;
   --  Deallocate the internal structures and the words table

   procedure Insert (Value : String);
   --  Insert a new word into the table. ASCII.NUL characters are not allowed.

   Too_Many_Tries : exception renames SPHG.Too_Many_Tries;
   --  Raised after Tries unsuccessful runs

   procedure Compute (Position : String := Default_Position);
   --  Compute the hash function. Position allows the definition of selection
   --  of character positions used in the word hash function. Positions can be
   --  separated by commas and ranges like x-y may be used. Character '$'
   --  represents the final character of a word. With an empty position, the
   --  generator automatically produces positions to reduce the memory usage.
   --  Raise Too_Many_Tries if the algorithm does not succeed within Tries
   --  attempts (see Initialize).

   procedure Produce
     (Pkg_Name   : String  := Default_Pkg_Name;
      Use_Stdout : Boolean := False);
   --  Generate the hash function package Pkg_Name. This package includes the
   --  minimal perfect Hash function. The output is normally placed in the
   --  current directory, in files X.ads and X.adb, where X is the standard
   --  GNAT file name for a package named Pkg_Name. If Use_Stdout is True, the
   --  output goes to standard output, and no files are written.

end GNAT.Perfect_Hash_Generators;