Tables (maps)

In table.diesel:

Tables map from keys to values (in other words, a table is a set of key/value pairs) such that a given key maps to at most one value. A table can be viewed as a collection of values, in some unspecified order. As such, operations like length, is_empty, do, pick_any, includes, find, copy, etc., are inherited from collection, and operate on the values part of the table.

A table is comparable if both its keys and values are comparable. Two tables are equal (=) if they have the same set of keys and corresponding keys map to equal values.

extend module Stdlib;

module Table;

first, a simple abstraction that supports fetch-like behavior, but not necessarily iterating, etc.

abstract class table_like[Key,Value]
                                - Value type parameter is covariant:
                                isa table_like[Key, `Value1 >= Value];
abstract class table_like_exactly[Key,Value] isa table_like[Key,Value];

The fetch methods support table lookup; the optional closure argument is invoked if the key isn't found. The infix ! operator can be used instead of fetch, e.g.:

   t!n1 + t!n2

  fun fetch(:table_like[`Key,`Value], key:Key,
                   if_absent:&():`Else):Value|Else;
  fun fetch(t:table_like[`Key,`Value], key:Key):Value;
  fun !(t:table_like[`Key,`Value], key:Key):Value;

The fetch_and_do method does a fetch on the key and invokes either the if_present closure on the corresponding value or the if_absent closure if the key isn't found.

  fun fetch_and_do(t:table_like[`Key,`Value], key:Key,
                          if_present:&(Value):`T1, if_absent:&():`T2):T1|T2;

now, the main table abstraction

abstract class table[Key, Value] isa collection[Value],
                                            table_like[Key, Value],
                                            - Value type param is covariant:
                                            table[Key, `Value1 >= Value];
abstract class table_exactly[Key, Value]
                                        isa collection_exactly[Value],
                                            table_like_exactly[Key, Value],
                                            table[Key, Value];

The control structure do_associations[_allowing_updates] forms the heart of a table, iterating through the keys and values of the table in pairs. The keys_do[_allowing_updates] methods iterate through just the keys.

fun do_associations(:table[`Key,`Value], :&(Key,Value):void):void;
fun do_associations_allowing_updates(t:table[`Key,`Value],
                                            c:&(Key,Value):void):void;

The do_associations_exit et al. control structures are like the do_exit et al. control structures in that they allow premature exiting and continuing of an iteration.

fun do_associations_exit(t:table[`Key,`Value],
                                closure:&(Key, Value, &():none):void):void;
fun do_associations_exit_continue(t:table[`Key,`Value],
                                         closure:&(Key, Value,
                                                   &():none, &():none):void
                                         ):void;
fun do_associations_continue(t:table[`Key,`Value],
                                    closure:&(Key, Value, &():none):void
                                    ):void;
fun keys_do(t:table[`Key,`Value], c:&(Key):void):void;
fun keys_do_allowing_updates(t:table[`Key,`Value], c:&(Key):void):void;
fun copy_mutable(:table_exactly[`Key,`Value]):m_table[`Key,Value];

The find_key method does reverse table lookup: given a value, find a key that maps to that value. The includes_key method tests whether a key is defined, and the keys[_{set,list}] operations return the collection of keys in the table.

fun find_key(t:table_exactly[`Key,`Value], value:Value):Key
                                                where =(:Value,:Value):bool;
fun find_key(t:table_exactly[`Key,`Value],
                    value:Value, if_absent:&():`Else):Key|Else
                                                where =(:Value,:Value):bool;
fun find_key_generically(t:table[`Key,`Value], value:Value):Key
                                                where =(:Value,:Value):bool;
fun find_key_generically(t:table[`Key,`Value], value:Value,
                                if_absent:&():`Else):Key|Else
                                                where =(:Value,:Value):bool;
fun pick_any_key(t:table[`Key,`Value]):Key;
fun pick_any_key(t:table[`Key,`Value], if_empty:&():`Else):Key|Else;
fun includes_key(t:table[`Key,`Value], key:Key):bool;
fun keys(t:table[`Key,`Value]):collection_exactly[Key];
fun keys_set(t:table[`Key <= comparable[Key],`Value]):set[Key];
fun keys_list(t:table[`Key,`Value]):ordered_collection_exactly[Key];
extend class table_exactly[`Key, `Value <= comparable[Value]]
                                isa comparable[table_exactly[Key,Value]];
fun values_print_string(t:table[`Key,`Value]):string;

Tables are refined into immutable and mutable varieties. An i_table is immutable.

abstract class i_table[Key, Value] isa table[Key, Value],
                                              - type param is covariant:
                                              i_table[Key, `Value1 >= Value];
abstract class i_table_exactly[Key, Value]
                                                isa table_exactly[Key, Value],
                                                    i_table[Key, Value];

a simple thing that supports fetch & store, but not necessarily iterating

abstract class m_table_like[Key,Value]
                                        isa table_like_exactly[Key,Value];
  fun store(:m_table_like[`Key,`Value], :Key, :Value):void;
  fun set_!(t:m_table_like[`Key,`Value], key:Key, value:Value):void;

An m_table supports changing bindings of keys to values through the store or set_! method, but not necessarily adding new keys or removing old ones. (See removable_table for operations for removing keys from tables.)

abstract class m_table[Key, Value] isa table_exactly[Key, Value],
                                              m_table_like[Key, Value];
fun store(:m_table[`Key,`Value], key:Key, value:Value,
                 if_absent:&():void):void;
fun store_no_dup(t:m_table[`Key,`Value], key:Key, value:Value):void;
fun store(t:m_table[`Key <= comparable[Key],`Value],
                 assocs:collection[assoc[Key,Value]]):void;

An m_table also supports a variation of fetch, fetch_or_init, that, if the key is not found, computes and adds a default value to the table and returns that value; fetch_or_init abstracts a very common table-manipulation idiom.

fun fetch_or_init(t:m_table[`Key,`Value], key:Key,
                         if_init:&():Value):Value;

store_all stores all the key/value bindings of the second table into the first table

fun store_all(t1:m_table[`Key,`Value], t2:table[`Key,`Value]):void;

replace_any replaces some occurrence of a value in a table with some other value

fun replace_any(t:m_table[`Key,`Value <= comparable[Value]],
                       old_value:Value, new_value:Value):void;
fun replace_any(t:m_table[`Key,`Value <= comparable[Value]],
                       old_value:Value, new_value:Value,
                       if_absent:&():void):void;

replace_all replaces all occurrences of a value in a table with some other value, returning the number of replacements made

fun replace_all(t:m_table[`Key,`Value],
                       old_value:Value, new_value:Value):int
        where signature =(:Value,:Value):bool;

replace_if replaces all occurrences of a value in a table that passes a predicate with some other value computed by a different function, returning the number of replacements made

fun replace_if(t:m_table[`Key,`Value],
                      pred:&(Value):bool, new_value_cl:&(Value):Value):int;

A removable_table supports removing bindings from the table, given the key to remove. (A table that inherits from removable_collection, on the other hand, supports removing bindings from the table, given the value.)

abstract class removable_table[Key, Value] isa table_exactly[Key,Value];
fun remove_key(:removable_table[`Key,`Value], key:Key,
                      if_absent:&():`Else):Value|Else;
fun remove_key(t:removable_table[`Key,`Value], key:Key):Value;
fun remove_keys_if(t:removable_table[`Key,`Value],
                          pred:&(Key):bool):int;

m_removable_table is the commonly used kind of table, which supports addition, removal, and modification of key-to-value bindings. Both addition and modification of bindings is done via store or set_!. (For non-table collections, addition of elements is done via add methods.) The set_! method can be invoked using the assignment message sugar:

    t ! key := value;

Removal of bindings is done via the inherited remove_key et al. methods.

abstract class m_removable_table[Key, Value]
        isa m_table[Key, Value], removable_table[Key, Value];

end module Table;