Concrete implementations

Several concrete implementations of tables exist: assoc_table is based on a linked-list of key/value associations (where the keys must be comparable), identity_assoc_table is like assoc_table but uses object identity (==) to compare keys, hash_table uses an open hashing algorithm, and chained_hash_table uses a closed hashing algorithm; the hashing versions require keys to be hashable.

The {assoc,identity_assoc,hash, chained_hash}_CR_table implementations change the printing behavior to print a newline between elements; this is useful for large tables. The ``_CR'' stands for ``carriage return''.

In assoc-table.cecil:

let var warn_for_assoc_tables_longer_than:int;
template object assoc[Key <= comparable[Key], Value];
  field key(@:assoc[`Key,`Value]):Key;
  var field value(@:assoc[`Key,`Value]):Value;
  extend assoc[`Key, `Value <= comparable[Value]]
                                        isa comparable[assoc[Key,Value]];
  method =(l@:assoc[`Key, `Value <= comparable[Value]],
           r@:assoc[`Key, `Value <= comparable[Value]]):bool;
  method print_string(a@:assoc[`Key,`Value]):string;
  method new_assoc[Key <= comparable[Key], Value](k:Key, v:Value
                                                  ):assoc[Key,Value];
  method copy(a@:assoc[`Key,`Value]):assoc[Key,Value];
  method ==>(k:`Key <= comparable[Key], v:`Value):assoc[Key,Value];
template object assoc_table[Key <= comparable[Key], Value]
                                        isa m_removable_table[Key,Value];
  method length(t@:assoc_table[`Key,`Value]):int;
  method is_empty(t@:assoc_table[`Key,`Value]):bool;
  method do_associations(t@:assoc_table[`Key,`Value],
                         c:&(Key,Value):void):void;
  method store(t@:assoc_table[`Key,`Value], key:Key, value:Value,
               if_absent:&():void):void;
  method store_no_dup(t@:assoc_table[`Key,`Value], key:Key, value:Value):void;
  method add_assoc(t@:assoc_table[`Key,`Value], a:assoc[Key,Value]):void;
  method remove_key(t@:assoc_table[`Key,`Value], key:Key,
                    if_absent:&():`Else):Value|Else;
  method remove_keys_if(t@:assoc_table[`Key,`Value], pred:&(Key):bool):int;
  method remove_if(t@:assoc_table[`Key,`Value], pred:&(Value):bool):int;
  method remove_all(t@:assoc_table[`Key,`Value]):void;
  method new_assoc_table[Key <= comparable[Key], Value]():assoc_table[Key,Value];
  method new_assoc_table_init_from(assocs@:collection[assoc[`Key <= comparable[Key],
                                                            `Value]]
                                   ):assoc_table[Key,Value];
  method copy_empty(t@:assoc_table[`Key,`Value]):assoc_table[Key,Value];
  method copy(t@:assoc_table[`Key,`Value]):assoc_table[Key,Value];
template object assoc_CR_table[Key <= comparable[Key], Value]
                        isa assoc_table[Key,Value];
  method elem_separator(t@:assoc_CR_table[`Key,`Value]):string;
  method new_assoc_CR_table[Key <= comparable[Key], Value]()
                           :assoc_CR_table[Key,Value];
  method copy_empty(c@:assoc_CR_table[`Key,`Value]):assoc_CR_table[Key,Value];
template object ordered_assoc_table[Key <= comparable[Key], Value]
                                        isa assoc_table[Key,Value];
  method add_assoc(t@:ordered_assoc_table[`Key,`Value],
                   a:assoc[Key,Value]):void;
  method new_ordered_assoc_table[Key <= comparable[Key], Value]()
                           :ordered_assoc_table[Key,Value];
  method copy_empty(c@:ordered_assoc_table[`Key,`Value]
                    ):ordered_assoc_table[Key,Value];
template object ordered_assoc_CR_table[Key <= comparable[Key], Value]
                        isa ordered_assoc_table[Key,Value];
  method elem_separator(t@:ordered_assoc_CR_table[`Key,`Value]):string;
  method new_ordered_assoc_CR_table[Key <= comparable[Key], Value]()
                           :ordered_assoc_CR_table[Key,Value];
  method copy_empty(c@:ordered_assoc_CR_table[`Key,`Value]
                    ):ordered_assoc_CR_table[Key,Value];

assoc_table is an implementation of tables based on a linked-list of key/value associations. The keys must be comparable. In identity-table.cecil:

template object identity_assoc[Key,Value]
                                isa comparable[identity_assoc[Key,Value]];
  field key(@:identity_assoc[`Key,`Value]):Key;
  var field value(@:identity_assoc[`Key,`Value]):Value;
  method =(l@:identity_assoc[`Key1,`Value1],
           r@:identity_assoc[`Key2,`Value2]):bool;
  method print_string(a@:identity_assoc[`Key,`Value]):string;
  method new_identity_assoc[Key,Value](k:Key, v:Value
                                       ):identity_assoc[Key,Value];
  method copy(a@:identity_assoc[`Key,`Value]):identity_assoc[Key,Value];
template object identity_assoc_table[Key,Value]
                isa m_removable_table[Key,Value];
  method length(t@:identity_assoc_table[`Key,`Value]):int;
  method is_empty(t@:identity_assoc_table[`Key,`Value]):bool;
  method do_associations(t@:identity_assoc_table[`Key,`Value],
                         c:&(Key,Value):void):void;
  method fetch(t@:identity_assoc_table[`Key,`Value], key:Key,
               if_absent:&():Value):Value;
  method store(t@:identity_assoc_table[`Key,`Value], key:Key, value:Value,
               if_absent:&():void):void;
  method store_no_dup(t@:identity_assoc_table[`Key,`Value],
                      key:Key, value:Value):void;
  method add_assoc(t@:identity_assoc_table[`Key,`Value],
                   a:identity_assoc[Key,Value]):void;
  method remove_key(t@:identity_assoc_table[`Key,`Value], key:Key,
                    if_absent:&():`Else):Value|Else;
  method remove_keys_if(t@:identity_assoc_table[`Key,`Value],
                          pred:&(Key):bool):int;
  method remove_all(t@:identity_assoc_table[`Key,`Value]):void;
  method new_identity_assoc_table[Key,Value](
        ):identity_assoc_table[Key,Value];
  method copy_empty(t@:identity_assoc_table[`Key,`Value]
                    ):identity_assoc_table[Key,Value];
  method copy(t@:identity_assoc_table[`Key,`Value]
              ):identity_assoc_table[Key,Value];
template object identity_assoc_CR_table[Key,Value]
                        isa identity_assoc_table[Key,Value];
  method elem_separator(t@:identity_assoc_CR_table[`Key,`Value]):string;
  method new_identity_assoc_CR_table[Key,Value]()
                           :identity_assoc_CR_table[Key,Value];
  method copy_empty(c@:identity_assoc_CR_table[`Key,`Value]
                    ):identity_assoc_CR_table[Key,Value];

identity_assoc_table is an implementation of tables based on a linked-list of key/value associations. It uses object identity (==) to compare keys. In small-table.cecil:

template object small_table[K <= hashable[K], V] isa m_removable_table[K,V];
method collection_name(@:small_table[`K,`V]):string;
method do(t@:small_table[`K,`V], c:&(V):void):void;
method do_allowing_updates(t@:small_table[`K,`V], c:&(V):void):void;
method keys_do(t@:small_table[`K,`V], c:&(K):void):void;
method keys_do_allowing_updates(t@:small_table[`K,`V], c:&(K):void):void;
method do_associations(t@:small_table[`K,`V], c:&(K,V):void):void;
method do_associations_allowing_updates(t@:small_table[`K,`V],
                                        c:&(K,V):void):void;
method length(t@:small_table[`K,`V]):int;
method is_empty(t@:small_table[`K,`V]):bool;
method fetch(t@:small_table[`K,`V], k:K, if_absent:&():V):V;
method store(t@:small_table[`K,`V], k:K, v:V, if_absent:&():void):void;
method store_no_dup(t@:small_table[`K,`V], k:K, v:V):void;
method includes_key(t@:small_table[`K,`V], k:K):bool;
method includes(t@:small_table[`K,`V <= comparable[V]], v:V):bool;
method remove_key(t@:small_table[`K,`V], k:K, if_absent:&():`T):V|T;
method remove_keys_if(t@:small_table[`K,`V], pred:&(K):bool):int;
method remove_if(t@:small_table[`K,`V], pred:&(V):bool):int;
method remove_all(t@:small_table[`K,`V]):void;
method copy_empty(t@:small_table[`K,`V]):small_table[K,V];
method copy(t@:small_table[`K,`V]):small_table[K,V];
method shrink_table(t@:small_table[`K,`V]):void;
method new_small_table[K <= hashable[K], V]():small_table[K,V];
type synonym big_table[`K,`V] = m_removable_table[K,V]|absent_table[K,V];
signature do(t:big_table[`K,`V], c:&(V):void):void;
signature do_allowing_updates(t:big_table[`K,`V], c:&(V):void):void;
signature keys_do(t:big_table[`K,`V], c:&(K):void):void;
signature keys_do_allowing_updates(t:big_table[`K,`V], c:&(K):void):void;
signature do_associations(t:big_table[`K,`V], c:&(K,V):void):void;
signature do_associations_allowing_updates(t:big_table[`K,`V],
                                           c:&(K,V):void):void;
signature length(t:big_table[`K,`V]):int;
signature is_empty(t:big_table[`K,`V]):bool;
signature fetch(t:big_table[`K,`V], k:K, if_absent:&():V):V;
signature store(t:big_table[`K,`V], k:K, v:V, if_absent:&():void):void;
signature store_no_dup(t:big_table[`K,`V], k:K, v:V):void;
signature includes_key(t:big_table[`K,`V], k:K):bool;
signature includes(t:big_table[`K,`V <= comparable[V]], x:V):bool;
signature remove_key(t:big_table[`K,`V], k:K, if_absent:&():`T):V|T;
signature remove_keys_if(t:big_table[`K,`V], pred:&(K):bool):int;
signature remove_if(t:big_table[`K,`V], pred:&(V):bool):int;
signature remove_all(t:big_table[`K,`V]):void;
signature copy(t:big_table[`K,`V]):big_table[K,V];
concrete object absent_table[K <= hashable[K], V];
implementation do(t@:absent_table[`K,`V], c:&(V):void):void;
implementation do_allowing_updates(t@:absent_table[`K,`V],
                                   c:&(V):void):void;
implementation keys_do(t@:absent_table[`K,`V], c:&(K):void):void;
implementation keys_do_allowing_updates(t@:absent_table[`K,`V],
                                        c:&(K):void):void;
implementation do_associations(t@:absent_table[`K,`V],
                               c:&(K,V):void):void;
implementation do_associations_allowing_updates(t@:absent_table[`K,`V],
                                                c:&(K,V):void):void;
implementation length(t@:absent_table[`K,`V]):int;
implementation is_empty(t@:absent_table[`K,`V]):bool;
implementation fetch(t@:absent_table[`K,`V], k:K, if_absent:&():V):V;
implementation store(t@:absent_table[`K,`V], k:K, v:V,
                     if_absent:&():void):void;
implementation store_no_dup(t@:absent_table[`K,`V], k:K, v:V):void;
implementation includes_key(t@:absent_table[`K,`V], k:K):bool;
implementation includes(t@:absent_table[`K,`V <= comparable[V]], x:V):bool;
implementation remove_key(t@:absent_table[`K,`V], k:K,
                          if_absent:&():`T):V|T;
implementation remove_keys_if(t@:absent_table[`K,`V], pred:&(K):bool):int;
implementation remove_if(t@:absent_table[`K,`V], pred:&(V):bool):int;
implementation remove_all(t@:absent_table[`K,`V]):void;
implementation copy(t@:absent_table[`K,`V]):big_table[K,V];

An implementation of m_removable_table that is space efficient when there are only a few elements, but scales well when there are a large number of elements. Keys of small tables are required to be hashable.