The table-extensions Module

The Collections library’s table-extensions module extends the Dylan language’s standard table features.

Note

Open Dylan provides a slightly different table implementation from that described by the DRM. See Language Differences for details of these differences.

Basics

The table-extensions module exports the classes <string-table> and <case-insensitive-string-table>; the type <hash-state>; the constructor macro table; the generic function remove-all-keys! and two methods thereon; and the functions collection-hash, sequence-hash, string-hash, values-hash, case-insensitive-string-hash, and case-insensitive-equal.

The <string-table> class is a class of tables that use strings for keys. <case-insensitive-string-table> is similar, but the keys are considered to be case insensitive.

The <hash-state> type implements hash states. A hash state is defined by the DRM, page 123, as “an implementation-dependent type that is associated with a hash id and can be used by the implementation to determine whether the hash id has been invalidated.” See pages 122–123 of the DRM for more details.

The various hash functions and the case-insensitive-equal equivalence predicate are convenient building blocks for creating new table classes and hash functions.

Hash functions

Different hash functions are not required to return the same hash code for equal or even identical objects. For instance,

collection-hash(#(), object-hash, object-hash);

is not guaranteed to return the same values as

sequence-hash(#(), object-hash);

Furthermore, collection-hash with ordered: #t is not guaranteed to return the same hash code as collection-hash with ordered: #f. Such a requirement would render the ordered: keyword useless.

Weak tables

Open Dylan allows all general instances of the built-in class <table> to be weak. See weak tables of this volume for information about weakness.

You can create weak tables with the <table> class’s weak: init-keyword. The legal values for this keyword are:

  • #"key" Creates a table with weak keys. When there are no longer any strong references to a key, the table entry of which it is part becomes eligible for garbage collection.

  • #"value" Creates a table with weak values. When there are no longer any strong references to a value, the table entry of which it is a part becomes eligible for garbage collection.

  • #f Creates a table with strong keys and values. This is the default value.

The table-extensions Module

This section contains a reference description for each item exported from the module table-extensions.

<string-table> Sealed Class

A table class that uses strings for keys.

Superclasses:

<table>

Discussion:

The <string-table> class is the class of tables that use instances of <string> for their keys. It is an error to use a key that is not an instance of <string>.

Keys are compared with the equivalence predicate \=.

The elements of the table are instances of <object>.

Modifying the key once it has been used to add an element to a <string-table> results in undefined behavior.

<case-insensitive-string-table> Sealed Class

A table class that uses case-insensitive strings for keys.

Superclasses:

<table>

Discussion:

The <string-table> class is the class of tables that use instances of <string> for their keys. It is an error to use a key that is not an instance of <string>.

Keys are compared with the equivalence predicate case-insensitive-equal.

The elements of the table are instances of <object>.

Modifying the key once it has been used to add an element to a <case-insensitive-string-table> results in undefined behavior.

<hash-state> Class

A hash state.

Superclasses:

<object>

Discussion:

Anything that the Dylan Reference Manual describes as a hash state is an instance of this type.

Examples of hash states include the second argument and second return value of object-hash.

collection-hash Function

Hashes the elements of a collection.

Signature:

collection-hash key-hash-function elt-hash-function collection initial-state #key ordered => hash-id hash-state

Parameters:
  • key-hash-function – An instance of <function>.

  • elt-hash-function – An instance of <function>.

  • collection – An instance of <collection>.

  • initial-state – An instance of <hash-state>.

  • ordered (#key) – An instance of <boolean>. Default value: #f.

Values:
  • hash-id – An instance of <integer>.

  • result-state – An instance of <hash-state>.

Discussion:

Hashes every element of collection using key-hash-function on the keys and elt-hash-function on the elements, and merges the resulting hash codes in order.

The ordered keyword is passed on to merge-hash-ids.

The functions key-hash-function and elt-hash-function must be suitable for use as hash functions. See page 123 of the DRM.

sequence-hash Function

Hashes the elements of a sequence.

Signature:

sequence-hash elt-hash-function sequence initial-state #key ordered => hash-id result-state

Parameters:
  • elt-hash-function – An instance of <function>.

  • sequence – An instance of <sequence>.

  • initial-state – An instance of <hash-state>.

  • ordered (#key) – An instance of <boolean>. Default value: #f.

Values:
  • hash-id – An instance of <integer>.

  • result-state – An instance of <hash-state>.

Discussion:

Hashes every element of sequence using elt-hash-function, and merges the resulting hash codes in order.

The function elt-hash-function must be suitable for use as a hash function. See page 123 of the DRM.

The ordered keyword is passed on to merge-hash-ids.

values-hash Function

Hashes the values passed to it.

Signature:

values-hash elt-hash-function initial-state #rest arguments => hash-id result-state

Parameters:
  • elt-hash-function – An instance of <function>.

  • hash-state – An instance of <hash-state>.

  • initial-state – An instance of <hash-state>.

  • arguments (#rest) – Instances of <object>.

Values:
  • hash-id – An instance of <integer>.

  • result-state – An instance of <hash-state>.

Discussion:

Hashes every object in arguments using elt-hash-function, and merges the resulting hash codes in order.

The function elt-hash-function must be suitable for use as a hash function. See page 123 of the DRM.

The ordered keyword is passed on to merge-hash-ids.

string-hash Function

Hashes a string.

Signature:

string-hash string initial-state => hash-id result-state

Parameters:
  • string – An instance of <string>.

  • initial-state – An instance of <hash-state>.

Values:
  • hash-id – An instance of <integer>.

  • result-state – An instance of <hash-state>.

Discussion:

Produces a hash code for a string, using the equivalence predicate \=.

case-insensitive-string-hash Function

Hashes a string, without considering case information.

Signature:

case-insensitive-string-hash string initial-state => hash-id result-state

Parameters:
  • string – An instance of <string>.

  • initial-state – An instance of <hash-state>.

Values:
  • hash-id – An instance of <integer>.

  • result-state – An instance of <hash-state>.

Discussion:

Produces a hash code for a string using the equivalence predicate case-insensitive-equal, which does not consider the case of the characters in the strings it compares.

See also:

case-insensitive-equal Function

Compares two strings for equality, ignoring case differences between them.

Signature:

case-insensitive-equal string1 string2 => boolean

Parameters:
Values:
Discussion:

Compares string1 and string2 for equality, ignoring any case differences between them. Returns true if they are equal and false otherwise.

The function has the same behavior as Dylan’s standard method on = for sequences, except that when comparing alphabetical characters, it ignores any case differences.

This function is used as an equivalence predicate by case-insensitive-string-hash.

This function uses as-uppercase or as-lowercase to convert the characters in its string arguments.

Example:

The case-insensitive-equal function returns true if passed the following strings:

"The Cat SAT ON the Mat"
"The cat sat on the Mat"

Conversely, the standard method on = returns false when passed those strings.

See also:

remove-all-keys! Open Generic function

Removes all keys from a collection and leaves it empty.

Signature:

remove-all-keys! collection => collection

Parameters:
Values:
Discussion:

Modifies collection by removing all its keys and elements, and leaves it empty.

Note

To empty collections that are not instances of <mutable-explicit-key-collection>, use size-setter.

remove-all-keys!(<mutable-explicit-key-collection>) Method

Removes all keys from a collection and leaves it empty.

Signature:

remove-all-keys! collection => collection

Parameters:
Values:
Discussion:

Modifies collection by removing all its keys and elements, and leaves it empty. This method implements the generic function by making repeated calls to remove-key!.

Note

To empty collections that are not instances of <mutable-explicit-key-collection>, use size-setter.

remove-all-keys!(<table>) Method

Removes all keys from a table and leaves it empty.

Signature:

remove-all-keys! table => table

Parameters:
Discussion:

Modifies table by removing all its keys and elements, and leaves it empty.

This method does not use remove-key!.

Note

To empty collections that are not instances of <mutable-explicit-key-collection>, use size-setter.

tabling Function Macro

Creates a table and populates it with keys and values.

Macro Call:

tabling( [ class, ] key => value, ...)

Parameters:
  • class – An instance of <class>. Optional.

  • key – An expression.

  • value – An expression.

Values:
  • table – A new instance of class.

Discussion:

Creates a table of type class and populates it with key/value pairs. If class is omitted, creates a table of type <table>.

Example:
let my-table = tabling(#"red" => "stop", #"green" => "go");
let my-table = tabling(<string-table>, "red" => "stop", "green" => "go");