(********************************************************************)
(*                                                                  *)
(*  hash.s7i      Hash map support library                          *)
(*  Copyright (C) 1989 - 2013, 2022, 2024  Thomas Mertes            *)
(*                                                                  *)
(*  This file is part of the Seed7 Runtime Library.                 *)
(*                                                                  *)
(*  The Seed7 Runtime Library is free software; you can             *)
(*  redistribute it and/or modify it under the terms of the GNU     *)
(*  Lesser General Public License as published by the Free Software *)
(*  Foundation; either version 2.1 of the License, or (at your      *)
(*  option) any later version.                                      *)
(*                                                                  *)
(*  The Seed7 Runtime Library is distributed in the hope that it    *)
(*  will be useful, but WITHOUT ANY WARRANTY; without even the      *)
(*  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR *)
(*  PURPOSE.  See the GNU Lesser General Public License for more    *)
(*  details.                                                        *)
(*                                                                  *)
(*  You should have received a copy of the GNU Lesser General       *)
(*  Public License along with this program; if not, write to the    *)
(*  Free Software Foundation, Inc., 51 Franklin Street,             *)
(*  Fifth Floor, Boston, MA  02110-1301, USA.                       *)
(*                                                                  *)
(********************************************************************)


(**
 *  Abstract data type, describing hash maps.
 *  A hash map stores key-value pairs. A hash map guarantees that a
 *  key can be mapped quickly to its corresponding value. The keys
 *  of a hash map have the type ''keyType'' and the value have the
 *  type ''baseType''. A hash map is only possible, if ''keyType''
 *  supports the functions ''hashCode'' and ''compare''.
 *)
const func type: hash [ (in type: keyType) ] (in type: baseType) is func
  result
    var type: hashType is void;
  local
    var type: keyValueType is void;
  begin
    hashType := get_type(getfunc(hash [ (attr keyType) ] (attr baseType)));
    if hashType = void then
      global
      hashType := newtype;
      IN_PARAM_IS_REFERENCE(hashType);
      keyValueType := newtype;
      IN_PARAM_IS_REFERENCE(keyValueType);
      const boolean: isHashType (attr hashType)                                is TRUE;
      const type: hash [ (attr keyType) ] (attr baseType)                      is hashType;
      const type: key_type (attr hashType)                                     is keyType;
      const type: base_type (attr hashType)                                    is baseType;

      const reference: (attr hashType) . keyHashCode is getfunc(hashCode(in keyType: anElem));
      const reference: (attr hashType) . keyCreate   is getfunc((ref keyType: dest) ::= (in keyType: source));
      const reference: (attr hashType) . keyDestroy  is getfunc(destroy(ref keyType: aValue));
      const reference: (attr hashType) . keyCopy     is getfunc((inout keyType: dest) := (in keyType: source));
      const reference: (attr hashType) . keyCompare  is getfunc(compare(in keyType: key1, in keyType: key2));
      const reference: (attr hashType) . dataCreate  is getfunc((ref baseType: dest) ::= (in baseType: source));
      const reference: (attr hashType) . dataDestroy is getfunc(destroy(ref baseType: aValue));
      const reference: (attr hashType) . dataCopy    is getfunc((inout baseType: dest) := (in baseType:source));

      const proc: CREATE (ref hashType: dest, in hashType: source,
                          in reference: keyCreate, in reference: keyDestroy,
                          in reference: dataCreate, in reference: dataDestroy) is action "HSH_CREATE";
      const proc: DESTROY (ref hashType: aValue, in reference: keyDestroy,
                           in reference: dataDestroy)                          is action "HSH_DESTR";
      const proc: COPY (inout hashType: dest, in hashType: source,
                        in reference: keyCreate, in reference: keyDestroy,
                        in reference: dataCreate, in reference: dataDestroy)   is action "HSH_CPY";
      const proc: FOR_DATA (inout baseType: forVar, in hashType: aHashMap,
                            in proc: statements, in reference: dataCopy)       is action "HSH_FOR";
      const proc: FOR_KEY (inout keyType: keyVar, in hashType: aHashMap,
                           in proc: statements, in reference: keyCop)          is action "HSH_FOR_KEY";
      const proc: FOR_DATA_KEY (inout baseType: forVar, inout keyType: keyVar,
                                in hashType: aHashMap, in proc: statements,
                                in reference: dataCopy, in reference: keyCopy) is action "HSH_FOR_DATA_KEY";
      const func array keyType: KEYS (in hashType: aHashMap, in reference: keyCreate,
                                      in reference: keyDestroy)                is action "HSH_KEYS";
      const func array baseType: VALUES (in hashType: aHashMap, in reference: dataCreate,
                                         in reference: dataDestroy)            is action "HSH_VALUES";

      const proc: (ref hashType: dest) ::= (in hashType: source) is func
        begin
          CREATE(dest, source, hashType.keyCreate, hashType.keyDestroy,
              hashType.dataCreate, hashType.dataDestroy);
        end func;

      const proc: destroy (ref hashType: oldHash) is func
        begin
          DESTROY(oldHash, hashType.keyDestroy, hashType.dataDestroy);
        end func;

      const proc: (inout hashType: dest) := (in hashType: source) is func
        begin
          COPY(dest, source, hashType.keyCreate, hashType.keyDestroy,
              hashType.dataCreate, hashType.dataDestroy);
        end func;

      (**
       *  Number of elements in the hash map ''aHashMap''.
       *  @return the number of elements in ''aHashMap''.
       *)
      const func integer: length (in hashType: aHashMap)                       is action "HSH_LNG";

      const func baseType: INDEX (in hashType: aHashMap, in keyType: aKey,
                                  in integer: hashCode,
                                  in reference: keyCompare)                    is action "HSH_IDX";
      const varfunc baseType: INDEX (inout hashType: aHashMap, in keyType: aKey,
                                     in integer: hashCode,
                                     in reference: keyCompare)                 is action "HSH_IDX";

      const func baseType: INDEX2 (in hashType: aHashMap, in keyType: aKey,
                                   in integer: hashCode, in baseType: defaultValue,
                                   in reference: keyCompare,
                                   in reference: dataCreate)                   is action "HSH_IDX2";

      const func ptr baseType: REFINDEX (in hashType: aHashMap, in keyType: aKey,
                                         in integer: hashCode,
                                         in reference: keyCompare)             is action "HSH_REFIDX";
      const proc: INCL (inout hashType: aHashMap, in keyType: aKey,
                        in baseType: anElem, in integer: hashCode,
                        in reference: keyCompare, in reference: keyCreate,
                        in reference: dataCreate, in reference: dataCopy)      is action "HSH_INCL";
      const proc: EXCL (inout hashType: aHashMap, in keyType: aKey,
                        in integer: hashCode, in reference: keyCompare,
                        in reference: keyDestroy, in reference: dataDestroy)   is action "HSH_EXCL";
      const func baseType: UPDATE (inout hashType: aHashMap, in keyType: aKey,
                                   in baseType: anElem, in integer: hashCode,
                                   in reference: keyCompare, in reference: keyCreate,
                                   in reference: dataCreate)                   is action "HSH_UPDATE";
      const func boolean: CONTAINS (in hashType: aHashMap, in keyType: aKey,
                                    in integer: hashCode,
                                    in reference: keyCompare)                  is action "HSH_CONTAINS";
      const func hashType: GEN_HASH (in keyValueType: keyValuePairs,
                                     in reference: keyHashCode,
                                     in reference: keyCompare,
                                     in reference: keyDestroy,
                                     in reference: dataDestroy)                is action "HSH_GEN_HASH";
(*
      const func hashType: (attr hashType) conv (in hashType: aHashMap)        is action "HSH_CONV";
      const varfunc hashType: (attr hashType) conv (inout hashType: aHashMap)  is action "TYP_VARCONV";
*)
      const func hashType: (attr hashType) . _GENERATE_EMPTY_HASH              is action "HSH_EMPTY";
      const hashType: (attr hashType) . EMPTY_HASH                             is hashType._GENERATE_EMPTY_HASH;
      const hashType: (attr hashType) . value                                  is hashType._GENERATE_EMPTY_HASH;

      (**
       *  Access one value from the hash table ''aHashMap''.
       *  @return the element with the key ''aKey'' from ''aHashMap''.
       *  @exception INDEX_ERROR If ''aHashMap'' does not have an element
       *             with the key ''aKey''.
       *)
      const func baseType: (in hashType: aHashMap) [ (in keyType: aKey) ] is
        return INDEX(aHashMap, aKey, hashCode(aKey), hashType.keyCompare);

      const varfunc baseType: (inout hashType: aHashMap) [ (in keyType: aKey) ] is
        return var INDEX(aHashMap, aKey, hashCode(aKey), hashType.keyCompare);

      (**
       *  Access one value from the hash table ''aHashMap''.
       *  @return the element with the key ''aKey'' from ''aHashMap'' or
       *          ''defaultValue'' if ''aHashMap'' does not have an element
       *          with the key ''aKey''.
       *)
      const func baseType: (in hashType: aHashMap) [ (in keyType: aKey) default (in baseType: defaultValue) ] is
        return INDEX2(aHashMap, aKey, hashCode(aKey), defaultValue,
                      hashType.keyCompare, hashType.dataCreate);

      (**
       *  Hash membership test.
       *  Determine if ''aKey'' is a member of the hash map ''aHashMap''.
       *  @return TRUE if ''aKey'' is a member of ''aHashMap'',
       *          FALSE otherwise.
       *)
      const func boolean: (in keyType: aKey) in (in hashType: aHashMap) is
        return CONTAINS(aHashMap, aKey, hashCode(aKey), hashType.keyCompare);

      (**
       *  Negated hash membership test.
       *  Determine if ''aKey'' is not a member of the hash map ''aHashMap''.
       *  @return FALSE if ''aKey'' is a member of ''aHashMap'',
       *          TRUE otherwise.
       *)
      const func boolean: (in keyType: aKey) not in (in hashType: aHashMap) is
        return not CONTAINS(aHashMap, aKey, hashCode(aKey), hashType.keyCompare);

      (**
       *  Add ''anElem'' with the key ''aKey'' to the hash map ''aHashMap''.
       *  If an element with the key ''aKey'' already exists,
       *  it is overwritten with ''anElem''.
       *   incl(aHash, aKey, aValue);
       *  @exception MEMORY_ERROR If there is not enough memory.
       *)
      const proc: incl (inout hashType: aHashMap, in keyType: aKey, in baseType: anElem) is func
        begin
          INCL(aHashMap, aKey, anElem, hashCode(aKey), hashType.keyCompare,
              hashType.keyCreate, hashType.dataCreate, hashType.dataCopy);
        end func;

      (**
       *  Remove the element with the key ''aKey'' from the hash map ''aHashMap''.
       *)
      const proc: excl (inout hashType: aHashMap, in keyType: aKey) is func
        begin
          EXCL(aHashMap, aKey, hashCode(aKey), hashType.keyCompare,
              hashType.keyDestroy, hashType.dataDestroy);
        end func;

      (**
       *  Add ''anElem'' with the key ''aKey'' to the hash map ''aHashMap''.
       *  If an element with the key ''aKey'' already exists,
       *  it is overwritten with ''anElem''.
       *   aHash @:= [aKey] aValue;
       *  @exception MEMORY_ERROR If there is not enough memory.
       *)
      const proc: (inout hashType: aHashMap) @:= [ (in keyType: aKey) ] (in baseType: anElem) is func
        begin
          INCL(aHashMap, aKey, anElem, hashCode(aKey), hashType.keyCompare,
              hashType.keyCreate, hashType.dataCreate, hashType.dataCopy);
        end func;

      (**
       *  Add ''anElem'' with the key ''aKey'' to the hash map ''aHashMap''.
       *  If an element with the key ''aKey'' already exists,
       *  it is overwritten with ''anElem'' and the old value is returned.
       *   oldValue := update(aHash, aKey, newValue);
       *  @param aHashMap Hash map to be updated.
       *  @param aKey Key of the value to be updated.
       *  @param anElem Data value to be added to the hash map.
       *  @return the old element with the key ''aKey'' or
       *          ''anElem'' if no old element existed.
       *  @exception MEMORY_ERROR If there is not enough memory.
       *)
      const func baseType: update (inout hashType: aHashMap, in keyType: aKey, in baseType: anElem) is
        return UPDATE(aHashMap, aKey, anElem, hashCode(aKey), hashType.keyCompare,
                      hashType.keyCreate, hashType.dataCreate);

      (**
       *  Create a key-value pair to be used in a hash literal.
       *  A key-value pair with the key "one" and the value 1 is created with
       *   ["one" : 1]
       *  A key-value pair can only be used inside a hash literal. E.g.:
       *   [] (["one" : 1], ["two" : 2])
       *  This hash literal defines a hash with the keys "one" and "two"
       *  and the corresponding values 1 and 2.
       *)
      const func keyValueType: [ (in keyType: aKey) : (in baseType: aValue) ]  is action "HSH_GEN_KEY_VALUE";

      const func keyValueType: (in keyValueType: element1) ,
                               (in keyValueType: element2)                     is action "HSH_CONCAT_KEY_VALUE";

      (**
       *  Declare a hash literal from key-value pairs.
       *  One or many key-value pairs are used to create a hash literal:
       *   [] (["one" : 1], ["two" : 2])
       *  This hash literal defines a hash with the keys "one" and "two"
       *  and the corresponding values 1 and 2.
       *)
      const func hashType: [] (in func keyValueType: keyValuePairs) is
        return GEN_HASH(keyValuePairs, hashType.keyHashCode, hashType.keyCompare,
                        hashType.keyDestroy, hashType.dataDestroy);

(*
      const proc: clear (inout hashType: aHashMap) is func
        local
          var baseType: anElem is baseType.value;
        begin
          for anElem range source do
            excl(dest, anElem);
          end for;
        end func;
*)

      (**
       *  For-loop where ''forVar'' loops over the values of the hash map ''aHashMap''.
       *  The succession of values is unordered and not related to the order
       *  in which the values have been added to the hash map. E.g.:
       *   for aValue range aHash do ...
       *  In many cases it is okay to process the values unordered.
       *  The values can be processed in an ordered way by using ''values'' and ''sort'':
       *   for aValue range sort(values(aHash)) do ...
       *)
      const proc: for (inout baseType: forVar) range (in hashType: aHashMap) do
                    (in proc: statements)
                  end for is func
        begin
          FOR_DATA(forVar, aHashMap, statements, hashType.dataCopy);
        end func;

      (**
       *  For-loop where ''keyVar'' loops over the keys (indices) of the hash map ''aHashMap''.
       *  The succession of keys (indices) is unordered and not related to
       *  the order in which the keys have been added to the hash map. E.g.:
       *   for aKey range aHash do ...
       *  In many cases it is okay to process the keys (indices) unordered.
       *  The keys can be processed in an ordered way by using ''keys'' and ''sort'':
       *   for aKey range sort(keys(aHash)) do ...
       *)
      const proc: for key (inout keyType: keyVar) range (in hashType: aHashMap) do
                    (in proc: statements)
                  end for is func
        begin
          FOR_KEY(keyVar, aHashMap, statements, hashType.keyCopy);
        end func;

      (**
       *  For-loop where ''forVar'' and ''keyVar'' loop over the hash map ''aHashMap''.
       *  The variable ''forVar'' loops over the values of ''aHashMap''
       *  and ''keyVar'' loops over the keys (indices) of ''aHashMap''.
       *  The succession of keys (indices) and values is unordered and not related
       *  to the order in which they have been added to the hash map. E.g.:
       *   for aValue key aKey range aHash do ...
       *  In many cases it is okay to process the keys (indices) and values unordered.
       *  The keys and values can be processed in an ordered way by using ''keys'' and ''sort'':
       *   for aKey range sort(keys(aHash)) do
       *     value := aHash[aKey];
       *     ...
       *)
      const proc: for (inout baseType: forVar) key (inout keyType: keyVar) range (in hashType: aHashMap) do
                    (in proc: statements)
                  end for is func
        begin
          FOR_DATA_KEY(forVar, keyVar, aHashMap, statements, hashType.dataCopy, hashType.keyCopy);
        end func;

      (**
       *  Obtain the keys of the hash map ''aHashMap''.
       *  The returned array of keys is unordered and the succession of
       *  keys is not related to the order in which the keys have been
       *  added to the hash map. A loop over the keys like
       *   for aKey range keys(aHash) do ...
       *  is equal to the following for-each loop
       *   for key aKey range aHash do ...
       *  The keys can be processed in an ordered way by using ''sort'':
       *   for aKey range sort(keys(aHash)) do ...
       *  @return an unordered array with the keys of the hash map.
       *)
      const func array keyType: keys (in hashType: aHashMap) is
        return KEYS(aHashMap, hashType.keyCreate, hashType.keyDestroy);

      (**
       *  Obtain the values of the hash map ''aHashMap''.
       *  The returned array of values is unordered and the succession of
       *  values is not related to the order in which the values have been
       *  added to the hash map. A loop over the values like
       *   for aValue range values(aHash) do ...
       *  is equal to the following for-each loop
       *   for aValue range aHash do ...
       *  The values can be processed in an ordered way by using ''sort'':
       *   for aValue range sort(values(aHash)) do ...
       *  @return an unordered array with the values of the hash map.
       *)
      const func array baseType: values (in hashType: aHashMap) is
        return VALUES(aHashMap, hashType.dataCreate, hashType.dataDestroy);

      if getobj((in baseType: element1) = (in baseType: element2)) <> NIL then

        const func boolean: (in hashType: hash1) = (in hashType: hash2) is func
          result
            var boolean: isEqual is TRUE;
          local
            var keyType: aKey is keyType.value;
            var baseType: aValue is baseType.value;
          begin
            if length(hash1) <> length(hash2) then
              isEqual := FALSE;
            else
              for aValue key aKey range hash1 do
                if not (aKey in hash2 and aValue = hash2[aKey]) then
                  isEqual := FALSE;
                end if;
              end for;
            end if;
          end func;

        const func boolean: (in hashType: hash1) <> (in hashType: hash2) is
          return not hash1 = hash2;
      end if;

      if getfunc(hashCode(in baseType: anElem)) <> NIL and
          getfunc(compare(in baseType: elem1, in baseType: elem2)) <> NIL then

        (**
         *  Create a hash map from ''aHashMap'' where key and value are exchanged.
         *  Since a hash value can correspond to many keys the type returned
         *  is ''hash [baseType] array keyType''.
         *   const type: stringIntegerHash is hash [string] integer;
         *   const type: integerStringHash is hash [integer] array string;
         *   ...
         *   var stringIntegerHash: aHash is [] (["zero" : 0], ["null" : 0], ["one" : 1]);
         *   var integerStringHash: stringsByIntValue is integerStringHash.value;
         *   var integer: number is 0;
         *   var string: stri is "";
         *   ...
         *   stringsByIntValue := flip(aHash);
         *   for number range sort(keys(stringsByIntValue)) do
         *     for stri range stringsByIntValue[number] do
         *       writeln(stri <& ": " <& number);
         *     end for;
         *   end for;
         *)
        const func hash [baseType] array keyType: flip (in hashType: aHashMap) is func
          result
            var hash [baseType] array keyType: inverseHash is (hash [baseType] array keyType).value;
          local
            var keyType: aKey is keyType.value;
            var baseType: aValue is baseType.value;
          begin
            for aValue key aKey range aHashMap do
              if aValue in inverseHash then
                inverseHash[aValue] &:= aKey;
              else
                inverseHash @:= [aValue] [] (aKey);
              end if;
            end for;
          end func;
      end if;

      end global;
    end if;
  end func;