SortedTable
is a generic interface defining partial maps over
a totally ordered domain.
\index{map!updatable}
GENERIC INTERFACESortedTable (Key, Tbl);
WhereKey.T
is not an open array type,Tbl
is a generic instanceTable(Key, Value)
(for someValue
defining a typeT
that is not an open array type), bothKey
andTbl
contain
CONST Brand = <text-constant>;andKey
additionally contains
PROCEDURE Compare(k1, k2: Key.T): [-1..1];Brand
must be a text constant. It will be used to construct a brand for the opaque typeSortedTable.Default
and any generic types instantiated with theSortedTable
interface. For a non-generic interface, we recommend choosing the name of the interface.
Compare
must be a total order.
Compare
may be declared with a parameter mode of eitherVALUE
orREADONLY
, but notVAR
.
CONST Brand = "(Sorted " & Tbl.Brand & ")"; DefaultBrand = "(Default " & Brand & ")"; (* A "SortedTable.Default" is revealed to have the brand "DefaultBrand". *) TYPE T = Tbl.T OBJECT METHODS iterateOrdered(up: BOOLEAN := TRUE): Iterator END; Iterator = Tbl.Iterator OBJECT METHODS seek(READONLY key: Key.T) END; Default <: T OBJECT METHODS init(): Default; keyCompare(READONLY k1, k2: Key.T): [-1..1] END; END SortedTable.A
SortedTable(Key, Table(Key, Value)).T
, or sorted table, is a
Table(Key, Value).T
together with a total (linear) order on the
keys of the table. Formally, a sorted table tbl
has the
additional component:
le(tbl) a total order on the values of Key.TThe total order
le(tbl)
must be time-invariant.
The methods have the following specifications:
The call tbl.iterateOrdered(up)
returns an iterator, which is an
object that can be used to iterate over all the key-value pairs in
tbl
, ordered by key. The order is increasing if up
is TRUE
,
decreasing otherwise.
If i
is the result of the call tbl.iterateOrdered(up)
, then the
call i.next(k, v)
sets k
and v
to the key and value of the
next pair 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
or seek
after next
has returned
FALSE
. The client must ensure that while an iterator is in use,
the parent table is not modified.
The call i.seek(k)
skips past zero or more key-value pairs
(either forward or backward) so that a subsequent call of next
returns the first pair with key greater than or equal to k
if i
is in increasing order or with key less than or equal to k
if i
is in decreasing order.
The type Default
is an implementation of T
using randomized
heap-ordered binary trees or ``treaps'' (see \cite{Aragon}). In
this implementation, seeking forward (relative to the iterator's
order) is more efficient than seeking backward. If a forward seek
skips over d
key-value pairs, the expected time for the seek is
O(log d)
. The time for a backward seek is
O(log(table.size()))
, no matter how far back it skips.
The call dflt.init()
returns dflt
after initializing it to an
empty table.
The call dflt.keyCompare(k1, k2)
returns Key.Compare(k1, k2)
.
The other methods call keyCompare
whenever they need to consult
le(tbl)
. This means a subtype of Default
can determine
le(tbl)
by overriding keyCompare
, providing keyCompare
implements a total order.
For efficiency, sorted 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.