seed7/lib/hash.s7i

(********************************************************************)
(*                                                                  *)
(*  hash.s7i      Hash map support library                          *)
(*  Copyright (C) 1989 - 2012  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;
  begin
    hashType := get_type(getfunc(hash [ (attr keyType) ] (attr baseType)));
    if hashType = void then
      global
      hashType := newtype;
      IN_PARAM_IS_REFERENCE(hashType);
      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) . 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: (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 RANGE_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''.
       *  @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''.
       *  @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;

      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);

(*
      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''.
       *)
      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 of the hash map ''aHashMap''.
       *)
      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''.
       *)
      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''.
       *  @return 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''.
       *  @return the values of the hash map.
       *)
      const func array baseType: values (in hashType: aHashMap) is
        return VALUES(aHashMap, hashType.dataCreate, hashType.dataDestroy);

      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 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;