(* Copyright (C) 1990, Digital Equipment Corporation.         *)
(* All rights reserved.                                       *)
(* See the file COPYRIGHT for a full description.             *)

(* Last modified on Tue Apr 24 22:44:22 1990 by muller        *)
(*      modified on Fri Mar 16 14:10:17 1990 by mcjones       *)
(*      modified on Wed Feb  7 16:33:43 1990 by mhb           *)

INTERFACE STable;

  (* Sorted, dynamically growing table with REF keys and values whose
     internal representation is a balanced binary tree.

     The entries can be enumerated in ascending or descending key
     order in linear time.  The worst-case time for Get, Put, or Delete
     is proportional to the log of the number of entries in the table.

     The current implementation uses 2-3-4 trees.

     WARNING: Clients are responsible for synchronizing access to
     a table.  Procedures in this interface fall into two classes:

         those that write a table     -- Put, Delete, Clear
         those that only read a table -- all others

     A write procedure must not be invoked concurrently on a table
     with respect to any other procedure invocation on the same table.
     A read procedure may be invoked concurrently with respect to
     other read-procedure invocations.

     See also SortedIntTable and SortedTextTable for versions of this
     interface specialized for integers and texts; see Table for a
     hash table (faster searches, but no enumeration of ordered
     subsets).

     Index: sorted tables of REFs; tables, sorted *)

IMPORT List;

TYPE
  T <: REFANY;
  Key = REFANY;
  Value = REFANY;

TYPE
  CompareProc = PROCEDURE (arg: REFANY; key1: Key; key2: Key): INTEGER;
    (* Return the result (<0, =0, or >0) of comparing key1 to key2.
       "arg" is the compareArg parameter supplied to New.  It must be
       the case that NIL compares less or equal to every other key.
       *)

PROCEDURE New (compare: CompareProc; compareArg: REFANY := NIL): T RAISES {};
  (* Construct a new table. *)

PROCEDURE Get (table: T; key: Key; VAR value: Value): BOOLEAN RAISES {};
  (* Find the value in the table with the given key.  If the key is
     found, set "value" to the value and return true.  If the key is
     not found, return false without setting "value".  *)

PROCEDURE Put (table: T; key: Key; value: Value): BOOLEAN RAISES {};
  (* Enter a key/value pair into the table.  If there is already an
     entry with the given key, replace its value by the new one.  Return
     true if there was a previous entry, false otherwise.  *)

PROCEDURE Delete (table: T; key: Key; VAR value: Value): BOOLEAN RAISES {};
  (* Remove a key/value pair from the table.  If the key was present,
     set "value" to the deleted value and return true.  If the key was
     not present, return false without changing the table or "value".
     *)

PROCEDURE Clear (table: T) RAISES {};
  (* Remove all entries from the table. *)

PROCEDURE Copy (table: T): T RAISES {};
  (* Make a copy of the table with the same keys and values. *)

TYPE
  Stream <: REFANY;

PROCEDURE NewStream (table: T; ascending: BOOLEAN := TRUE; key0: Key := NIL)
    : Stream RAISES {};
  (* Return a stream of the all the entries in the table with key >=
     key0 if ascending is true, or with key <= key0 if ascending is
     false.  Note this special case: if "ascending" is false, key0=NIL
     (the default) is interpreted as "+Infinity", so the stream begins
     with the greatest key present in the table.  *)

PROCEDURE Next (s: Stream; VAR key: Key; VAR value: Value): BOOLEAN RAISES {};
  (* Return true and set "key" and "value" from the next entry if one
     remains; otherwise leave "key" and "value" unchanged and return
     false.  *)

TYPE
  Predicate = PROCEDURE (arg: REFANY; key: Key; value: Value): BOOLEAN;

PROCEDURE FindFirst (
      table: T;
      pred: Predicate;
      arg: REFANY;
  VAR key: Key;
  VAR value: Value;
      ascending: BOOLEAN := TRUE;
      key0: Key := NIL
  ): BOOLEAN (* RAISES{raises(pred)} *);
(* Equivalent to:
  VAR
    s: Stream;
    k: Key;
    v: Value;
  BEGIN
    s := NewStream(table, ascending, key0);
    LOOP
      IF NOT Next(s, k, v) THEN RETURN FALSE END;
      IF pred(arg, k, v) THEN
        key   := k;
        value := v;
        RETURN TRUE
      END
    END
  END FindFirst;
*)

PROCEDURE ToValuesList (table: T; ascending: BOOLEAN := TRUE): List.T
  RAISES {};
  (* Return an ordered list of all the values in the table. *)

PROCEDURE ToAssocList (table: T; ascending: BOOLEAN := TRUE): List.T
  RAISES {};
  (* Return an association list (see List.Assoc) of entries in the
     table, that is, a list of pairs (key value), ordered by key.  *)

END STable.