Tables (maps)

In table.cecil:

abstract object table[Key, Value] isa collection[Value];
extend type table[`Key,`Value] subtypes table[Key, `Value1 >= Value];

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.

signature do_associations(table[`Key,`Value], &(Key,Value):void):void;
method do_associations_allowing_updates(t@:table[`Key,`Value],
                                        c:&(Key,Value):void):void;
method do(t@:table[`Key,`Value], c:&(Value):void):void;
method do_allowing_updates(t@:table[`Key,`Value],
                           c:&(Value):void):void;
method keys_do(t@:table[`Key,`Value], c:&(Key):void):void;
method keys_do_allowing_updates(t@:table[`Key,`Value], c:&(Key):void):void;
signature copy(`T <= table[`Key,`Value]):`T1 where signature copy_empty(T):T1;
signature copy_empty(table[`Key,`Value]):m_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.

signature fetch(table[`Key,`Value], key:Key, if_absent:&():Value):Value;
implementation fetch(t@:table[`Key <= comparable[Key], `Value], key:Key,
                     if_absent:&():Value):Value;
method fetch(t@:table[`Key,`Value], key:Key):Value;
abstract object table_like[Key,Value];
  signature fetch(table_like[`Key,`Value], Key):Value;
  method !(t@:table_like[`Key,`Value], key:Key):Value;
extend type table_like[`Key,`Value] subtypes table_like[Key, `Value1 >= Value];
extend table[`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

method find_key(t@:table[`Key,`Value <= comparable[Value]], value:Value):Key;
method find_key(t@:table[`Key,`Value <= comparable[Value]],
                value:Value, if_absent:&():Key):Key;
method pick_any_key(t@:table[`Key,`Value]):Key;
method pick_any_key(t@:table[`Key,`Value], if_empty:&():`T):Key|T;
method includes_key(t@:table[`Key,`Value], key:Key):bool;
method keys(t@:table[`Key,`Value]):collection[Key];
method keys_set(t@:table[`Key <= comparable[Key],`Value]):set[Key];
method keys_list(t@:table[`Key,`Value]):ordered_collection[Key];
extend table[`Key, `Value <= comparable[Value]]
                                        isa comparable[table[Key,Value]];
method =(t1@:table[`Key, `Value <= comparable[Value]],
         t2@:table[Key, Value]):bool;
method collection_name(@:table[`Key,`Value]):string;
method values_print_string(t@:table[`Key,`Value]):string;
method elems_print_string(t@:table[`Key,`Value]):string;
method elems_print(t@:table[`Key,`Value]):void;

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.

abstract object i_table[Key, Value] isa table[Key, Value];
  extend type i_table[`Key, `Value] subtypes i_table[Key, `Value1 >= Value];
  method copy(t@:`T <= i_table[`Key,`Value]):T;

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

abstract object m_table[Key, Value] isa table[Key, Value];
signature store(m_table[`Key,`Value], key:Key, value:Value,
                if_absent:&():void):void;
method store(t@:m_table[`Key,`Value], key:Key, value:Value):void;
method store_no_dup(t@:m_table[`Key,`Value], key:Key, value:Value):void;
method store(t@:m_table[`Key <= comparable[Key],`Value],
             assocs@:collection[assoc[Key,Value]]):void;
abstract object m_table_like[Key,Value] isa table_like[Key,Value];
  signature store(m_table_like[`Key,`Value], Key, Value):void;
  method set_!(t@:m_table_like[`Key,`Value], key:Key, value:Value):void;
extend m_table[`Key,`Value] isa m_table_like[Key,Value];

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.)

method fetch_or_init(t@:m_table[`Key,`Value], key:Key,
                     if_init:&():Value):Value;
method copy(t@:`T <= m_table[`Key,`Value]):`T1
                                        where signature copy_empty(T):T1;

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. Method copy_empty, given a (mutable) table, returns an empty mutable table of the same kind.

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

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

method replace_all(t@:m_table[`Key,`Value <= comparable[Value]],
                   old_value:Value, new_value:Value):int;

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

abstract object removable_table[Key, Value] isa table[Key, Value];
extend type removable_table[`Key,`Value]
                        subtypes removable_table[Key, `Value1 >= Value];
signature remove_key(removable_table[`Key,`Value], key:Key,
                     if_absent:&():`Value):Value;
method remove_key(t@:removable_table[`Key,`Value], key:Key):Value;
method remove_all(t@:removable_table[`Key,`Value]):void;
method remove_keys_if(t@:removable_table[`Key,`Value],
                      pred:&(Key):bool):int;
method remove_if(t@:removable_table[`Key,`Value],
                 pred:&(Value):bool):int;
signature copy_empty(removable_table[`Key,`Value]
                     ):m_removable_table[Key,Value];

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 object m_removable_table[Key, Value]
        isa m_table[Key, Value], removable_table[Key, Value];
  signature copy(m_removable_table[`Key,`Value]):m_removable_table[Key,Value];

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.