Next: Hash tables
Up: Tables (maps)
Previous: Tables (maps)
Index
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.
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];
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];
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.
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.
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];
Subsections
Next: Hash tables
Up: Tables (maps)
Previous: Tables (maps)
Index
Cecil/Vortex Project