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

(* Last modified on Tue Apr 24 22:41:53 1990 by muller        *)
(*      modified on Fri Mar 16 14:12:28 1990 by mcjones       *)

INTERFACE SIntTable;

 (* Sorted, dynamically growing table with integer keys 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 SortedTable and SortedTextTable for a generalized version
    and a version for texts; see IntTable for a hash table (faster
    searches, but no enumeration of ordered subsets).

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

IMPORT List;

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

PROCEDURE New (): 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 := FIRST(Key)
  ): 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=FIRST(Key) (the default) is interpreted as LAST(Key), 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 := FIRST (Key)
  ): 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 SIntTable.