INTERFACE HashText;

(***************************************************************************)
(*                      Copyright (C) Olivetti 1989                        *)
(*                          All Rights reserved                            *)
(*                                                                         *)
(* Use and copy of this software and preparation of derivative works based *)
(* upon this software are permitted to any person, provided this same      *)
(* copyright notice and the following Olivetti warranty disclaimer are     *) 
(* included in any copy of the software or any modification thereof or     *)
(* derivative work therefrom made by any person.                           *)
(*                                                                         *)
(* This software is made available AS IS and Olivetti disclaims all        *)
(* warranties with respect to this software, whether expressed or implied  *)
(* under any law, including all implied warranties of merchantibility and  *)
(* fitness for any purpose. In no event shall Olivetti be liable for any   *)
(* damages whatsoever resulting from loss of use, data or profits or       *)
(* otherwise arising out of or in connection with the use or performance   *)
(* of this software.                                                       *)
(***************************************************************************)

(*
  HashText supports the manipulation of tables of <Key, Value> pairs,
  where Keys are Text.T and where Values are REFANYs.

  The implementation of HashText is not revealed. To guarantee good
  performance, the user must ensure that tables are kept appropriately
  loaded. However, the package will not fail if a table becomes full.
  Thus clients may assume that the implementation either (i) uses a
  chained overflow structure (which merely becomes slower if overloaded)
  or (ii) reallocates a larger table on overflow (which also becomes
  slower as overflow approaches).

  HashText support iteration over their contents. 'Snapshot semantics' are
  not supported; if a new entry is made during the course of iterating over a
  table the iterator will raise an exception.

  It is the clients responsibility to control concurrent access to table by 
  multiple threads.  Failure to do so will likely produce a checked runtime 
  error or unpredictable results. A table contains a mutex which can be used
  to serialize access.
*)

IMPORT Thread;

TYPE
  Table <: Thread.Mutex;  (* The type of a hash table. *)
  Id <: REFANY;           (* The type of an entry in the hash table *)

PROCEDURE New(size: CARDINAL := 0): Table RAISES {};
(* 
  Create a new hash table identified by the returned value.
  The number of entries in the table is unlimited, but the efficiency
  will fall once the number nears 'size'.
  If 'size' is zero a default value is used, which is chosen to be
  adequate for a wide range of applications; it may be insufficient for
  large numbers of entries and it may require too much memory if many
  default sized tables are created.
*)

PROCEDURE CINew(size: CARDINAL := 0): Table RAISES {};
(*
  As for New(size), except that all keys are processed in a
  case-insensitive way (during computations of hash values and
  key comparisons) by converting upper-case letters to their
  lower-case equivalents.
*)

PROCEDURE Enter(ht: Table; t: TEXT; VAR (*out*) h: Id): BOOLEAN RAISES {};
(*
  If an entry with key 't' already exists then return FALSE,
  otherwise enter a copy of 't' into 'ht' and RETURN TRUE. (see also 'Lookup').
  In both cases the returned value of 'h' identifies the <key,value> pair,
  the key of  which is matched by 't'. Note that a new entry has a value of
  NIL.
*)

PROCEDURE Lookup(ht: Table; t: TEXT; VAR (*out*) h: Id): BOOLEAN RAISES {};
(*
  If an entry with key 't' exists return TRUE, setting 'h' to a
  value which identifies the entry.
  Otherwise, return FALSE, leaving 'h' undefined.
  (see also 'Enter').
*)

PROCEDURE Associate(ht: Table; h: Id; w: REFANY) RAISES {};
(*
  Associate the value 'w' with the entry identified by 'h' in the table 'ht'.
  After Associate(ht, h, w), Value(ht, h) = w.
*)

PROCEDURE Value(ht: Table; h: Id): REFANY RAISES {};
(*
  Return the value component of the <key,value> pair identified
  by 'h' in table 'ht'.
*)

PROCEDURE Key(ht: Table; h: Id): TEXT RAISES {};
(* 
  Return (a reference to) the key component of the <key,value> pair
  identified by 'h' in the table 'ht'.
*)

PROCEDURE Remove(ht: Table; id: Id) RAISES {};
(* 
  Remove the given entry from the hash table. It is a checked runtime error if
  'id' is not in 't'.
*)


(*----------------- Iterators over tables -----------------------------*)

TYPE
  Iter <: REFANY;

(* Example usage:

  VAR
    i: HashText.Iter;
    t: HashText.Table;
  BEGIN
    ......
    i := HashText.NewIterator(t);
    ......
    WHILE HashText.Next(i, key, val) DO
      (* Process <key,value> *)
    END;
*)

PROCEDURE NewIterator(t: Table): Iter RAISES {};
(* Create an iterator on 't'. *)

EXCEPTION Broken;

PROCEDURE Next(
    iter: Iter;
    VAR (*out*) key: TEXT;
    VAR (*out*) val: REFANY)
    : BOOLEAN
    RAISES {Broken};
(* If there is a next <key,value> pair in the table 'table' then
   return TRUE, setting 'key' and 'value' to its components.
   Otherwise return FALSE. If the table has been updated since
   the iterator was created, 'Broken' is raised. *)

END HashText.