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.diesel:

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

extend module Stdlib;

module Assoc;
class assoc[Key <= comparable[Key], Value];
  field key(:assoc[`Key,`Value]):Key;
  var field value(:assoc[`Key,`Value]):Value;
  extend class assoc[`Key, `Value <= comparable[Value]]
                                        isa comparable[assoc[Key,Value]];
  fun new_assoc[Key <= comparable[Key], Value](k:Key, v:Value
                                                      ):assoc[Key,Value];
  fun ==>(k:`Key <= comparable[Key], v:`Value):assoc[Key,Value];

end module Assoc;

module AssocTable;
let var warn_for_assoc_tables_longer_than:int;
class assoc_table[Key <= comparable[Key], Value]
                                        isa m_removable_table[Key,Value];
  fun new_assoc_table[Key <= comparable[Key], Value](
        ):assoc_table[Key,Value];
  fun new_assoc_table_init_from(
        assocs:collection[assoc[`Key <= comparable[Key], `Value]]
        ):assoc_table[Key,Value];
class assoc_CR_table[Key <= comparable[Key], Value]
                                                isa assoc_table[Key,Value];
  fun new_assoc_CR_table[Key <= comparable[Key], Value](
        ):assoc_CR_table[Key,Value];
class ordered_assoc_table[Key <= comparable[Key], Value]
                                        isa assoc_table[Key,Value];
  fun new_ordered_assoc_table[Key <= comparable[Key], Value](
        ):ordered_assoc_table[Key,Value];
class ordered_assoc_CR_table[Key <= comparable[Key], Value]
                        isa ordered_assoc_table[Key,Value];
  fun new_ordered_assoc_CR_table[Key <= comparable[Key], Value](
        ):ordered_assoc_CR_table[Key,Value];

end module AssocTable;

In identity-table.diesel:

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

extend module Stdlib;

module IdentityAssoc;
class 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;
  fun new_identity_assoc[Key,Value](k:Key, v:Value
                                           ):identity_assoc[Key,Value];

end module IdentityAssoc;

module IdentityTable;
class identity_assoc_table[Key,Value]
                isa m_removable_table[Key,Value];
  fun new_identity_assoc_table[Key,Value]()
                                        :identity_assoc_table[Key,Value];
class identity_assoc_CR_table[Key,Value]
                        isa identity_assoc_table[Key,Value];
  fun new_identity_assoc_CR_table[Key,Value]()
                           :identity_assoc_CR_table[Key,Value];

end module IdentityTable;

In small-table.diesel:

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.

extend module Stdlib;

module SmallTable;
class small_table[K <= hashable[K], V] isa m_removable_table[K,V];
fun shrink_table(t:small_table[`K,`V]):void;
fun new_small_table[K <= hashable[K], V]():small_table[K,V];
module AbsentTable;
synonym big_table[`K,`V] = m_removable_table[K,V]|absent_table[K,V];
object absent_table[K <= hashable[K], V];

end module AbsentTable;

end module SmallTable;