Table
is a generic interface defining partial maps that support
update and iteration.
\index{map!updatable}
GENERIC INTERFACETable (Key, Value);
WhereKey.T
andValue.T
are types that are not open array types, bothKey
andValue
contain
CONST Brand = <text-constant>;andKey
additionally contains
PROCEDURE Equal(k1, k2: Key.T): BOOLEAN; PROCEDURE Hash(k: Key.T): Word.T;Brand
must be a text constant. It will be used to construct a brand for the opaque typeTable.Default
and any generic types instantiated with theTable
interface. For a non-generic interface, we recommend choosing the name of the interface.
Equal
must be an equivalence relation andHash
must respect that equivalence relation, in other words, ifEqual(k1, k2)
, thenHash(k1)=Hash(k2)
.
Hash
andEqual
may be declared with a parameter mode of eitherVALUE
orREADONLY
, but notVAR
.
IMPORT Word; CONST Brand = "(Table " & Key.Brand & " " & Value.Brand & ")"; DefaultBrand = "(Default " & Brand & ")"; (* A "Table.Default" is revealed to have the brand "DefaultBrand". *) TYPE T = OBJECT METHODS get(READONLY k: Key.T; VAR v: Value.T): BOOLEAN; put(READONLY k: Key.T; READONLY v: Value.T): BOOLEAN; delete(READONLY k: Key.T; VAR v: Value.T): BOOLEAN; size(): CARDINAL; iterate(): Iterator END; Iterator = OBJECT METHODS init(): Iterator; next(VAR k: Key.T; VAR v: Value.T): BOOLEAN END; Default <: T OBJECT METHODS init(sizeHint: CARDINAL := 0): Default; keyEqual(READONLY k1, k2: Key.T): BOOLEAN; keyHash(READONLY k: Key.T): Word.T END; END Table.A
Table(Key, Value).T
, or table, is a partial map from Key.T
s
to Value.T
s. Actually, it turns out to be useful for a table to
treat two different keys as if they are the same whenever they are
equivalent according to some specified equivalence relation. For
example, if you are creating a table with a Key.T
of TEXT
, you
are likely to want Text.Equal
as the equivalence relation.
Formally, a table tbl
has the components:
canon(tbl) a map on elements of Key.T map(tbl) a map from elements of Key.T to elements of Value.T
canon(tbl)
represents an equivalence relation: canon(tbl)(k)
is
the {\em canonical representative} of all the keys that are
equivalent to k
. The domain of map(tbl)
includes only
canonical representatives, that is, elements in the range of
canon(tbl)
. The equivalence relation underlying canon(tbl)
must be time-invariant. For example, it can't depend on the values
of particular references since some garbage collectors move REF
values.
The methods of an object tbl
of type Table.T
have the following
specifications:
The call tbl.get(k, v)
sets v
to map(tbl)(canon(tbl)(k))
and
returns TRUE
if canon(tbl)(k)
is in dom(map(tbl))
. Otherwise,
it returns FALSE
without changing v
.
The call tbl.put(k, v)
changes map(tbl)(canon(tbl)(k))
to v
and returns TRUE
if canon(k)
is in dom(map(tbl))
. Otherwise,
it sets the value of map(tbl)(canon(tbl)(k))
to v
, and returns
FALSE
.
The call tbl.delete(k, v)
sets v
to map(tbl)(canon(tbl)(k))
,
removes (canon(tbl)(k), v)
from map(tbl)
, and returns TRUE
if
canon(tbl)(k)
is in dom(map(tbl))
. Otherwise, it returns
FALSE
without changing v
.
The call tbl.size()
returns the size of dom(map(tbl))
, that is,
the number of entries in tbl
.
The call tbl.iterate()
returns an iterator, which is an object
that can be used to iterate over the key-value pairs in tbl
. See
the definition of the type Iterator
below.
If i
is the result of the call tbl.iterate()
, then the call
it.next(k, v)
selects an entry from tbl
that has not already
been returned by i
, sets k
and v
to its key and value, and
returns TRUE
. If no entries remain, the call returns FALSE
without setting k
or v
. It is a checked runtime error to call
next
after it has returned FALSE
. The client must ensure that
while an iterator is in use, the parent table is not modified.
i
may be reset to iterate over all the values of a table by
reinitializing it with init
. tbl.iterate()
is equivalent to
NEW(Iterator).init()
.
The type Default
is an implementation of T
using chained
hashing. The methods specific to an object dflt
of type
Default
have the following specifications:
The call dflt.init(sizeHint)
returns dflt
after initializing it
to a table with an empty map(dflt)
. If sizeHint
is greater
than 0, init
assumes that put
will subsequently be called with
at least sizeHint
different keys; these calls on put
may
execute somewhat faster than if sizeHint
was 0. The init
method has side-effects on the table.
The call dflt.keyEqual(k1, k2)
returns Key.Equal(k1, k2)
and
the call dflt.keyHash(k)
returns Key.Hash(k)
. The other
methods call keyEqual
and keyHash
whenever they need to consult
the table's equivalence relation. This means a subtype of Default
can determine the equivalence relation by overriding keyEqual
and
keyHash
, providing keyEqual
implements an equivalence relation
and keyHash
respects that relation.
For efficiency, tables and their iterators are not monitored, so a
client accessing a table from multiple threads must ensure that if
two operations are active concurrently, then neither of them has
side effects on the same table or iterator. The T.put
,
T.delete
, and Default.init
methods are the only ones with side
effects on the table. An iterator's next
method has side-effects
on the iterator.