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_long_assoc_tables:bool;
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 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 sharing-table.cecil:

template object sharing_table[`Key <= hashable[Key],
                              `Value <= comparable[Value]]
                isa m_table[Key, Value];
    field immutable_table(@:sharing_table[`Key, `Value]):m_table[Key, Value];
    field mutable_table(@:sharing_table[`Key, `Value]):m_table[Key, Value];
    field new_keys(@:sharing_table[`Key, `Value]):m_set[Key];
    method new_sharing_table[`Key <= hashable[Key],
                             `Value <= comparable[Value]]()
            :sharing_table[Key, Value];
    method new_sharing_table[`Key <= hashable[Key],
                             `Value <= comparable[Value]](
          init_table@:m_table[Key, Value]) : sharing_table[Key, Value];
    method copy_empty(t@:sharing_table[`Key, `Value])
                          : sharing_table[Key, Value];
    method copy(t@:sharing_table[`Key, `Value]) : sharing_table[Key, Value];
    method length(t@:sharing_table[`Key, `Value]):int;
    method is_empty(t@:sharing_table[`Key, `Value]):bool;
    method do_associations(t@:sharing_table[`Key, `Value],
                           c:&(Key,Value):void):void;
    method fetch(t@:sharing_table[`Key, `Value], key:Key,
               if_absent:&():Value):Value;
    method store(t@:sharing_table[`Key, `Value], key:Key, value:Value,
               if_absent:&():void):void;

- A sharing_table is a structure that behaves like a hash table, - but when you copy it, it only copies the elements of the table that - change. Thus, if your table is ``mostly immutable,'' this can be - considerably more efficient. A sample application is dataflow - analysis: many programs have a lot of immutable variables. - - NOTE: to use this data structure safely, it must be OK for ``extra'' - key-value mappings to appear in the table, due to adding elements to - copies of the table!