Table Extensions
The Table Extensions Library
1. Introduction
The Table-Extensions library contains extensions to Dylan <table>s. It exports one module named Table-Extensions.
2. The Table-Extensions Module
<string-table> [Instantiable Sealed Class]
This class is a subclass of <table>. It is a table that has <string>s for keys (compared with \=) and <object>s for elements. It is an error to use a key that is not a <string>. It is an error to modify a key once it has been used to add an element to a <string-table>.
<case-insensitive-string-table> [Instantiable Sealed Class]
This class is a subclass of <table>. It is a table that has <string>s for keys (compared with case-insensitive-equal) and <object>s for elements. It is an error to use a key that is not a <string>. It is an error to modify a key once it has been used to add an element to a <case-insensitive-string-table>.
<hash-state> [Type]
Anything the DRM describes as a hash state is an instance of this type. This includes the second return value of merge-hash-codes and of all hash functions, and the second and fourth parameters to merge-hash-codes.
collection-hash [Function]
- Arguments
- key-hash-function :: <function>
- elt-hash-function :: <function>
- Values
- hash-state :: <hash-state>
- Description
This function hashes every element of collection using key-hash-function on the keys and elt-hash-function on the elements. This function is equivalent to the following reference implementation:
sequence-hash [Function]
- Arguments
- elt-hash-function :: <function>
- Values
- hash-state :: <hash-state>
- Description
This function hashes every element of sequence using elt-hash-function, merging the resulting hash codes in order.
values-hash [Function]
- Arguments
- elt-hash-function :: <function>
- Values
- hash-state :: <hash-state>
- Description
This function hashes each object in the #rest arguments using elt-hash-function, merging the resulting hash codes in order.
string-hash [Function]
- Arguments
- Values
- hash-state :: <hash-state>
- Description
This function produces hash codes for strings using the equality test \=.
case-insensitive-string-hash [Function]
- Arguments
- Values
- hash-state :: <hash-state>
- Description
This function produces hash codes for strings using the equality test case-insensitive-equal.
case-insensitive-equal [Function]
- Arguments
- Values
- Description
Performes a case insensitive comparison of the strings.
remove-all-keys! [Open Generic Function]
- Arguments
- coll :: <mutable-explicit-key-collection>
- Values
- coll :: <mutable-explicit-key-collection>
- Description
Modifies collection so that the collection no longer contains any keys or elements (i.e., is empty).
remove-all-keys! [G. F. Method]
- Arguments
- coll :: <mutable-explicit-key-collection>
- Values
- coll :: <mutable-explicit-key-collection>
- Description
This method implements remove-all-keys! by repeated calls to remove-key!.
remove-all-keys! [Sealed G. F. Method]
- Arguments
- Values
- Description
There is a predefined method on <table> which does not necessarily use remove-key.
Different hash functions are not required to return the same hash code for equal or even identical objects. For instance,
is not guaranteed to return the same values as
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).
3. Extensions
The Gwydion Project hopes that other Dylan implementations will also implement our Table-Extensions library. However, there are certain things that we realize other implementors are not so likely to implement; we call these things "extensions" to the Table-Extensions proposal.
The following definitions are part of the Gwydion Table-Extensions library, but are not part of the current Table-Extensions proposal.
<equal-table> [Class]
This class is a subclass of <table> that uses the \= function to compare keys and the equal-hash function to generate hash codes. If you define your own classes and \= methods specialized on those classes, then you should define a method for the equal-hash function specialized to your classes (see function equal-hash [Generic Function]).
<value-table> [Abstract Class]
This class is a subclass of <table>. Users can define subclasses of this class and provide a method for table-protocol that is specialized to their new subclass. Any subclass of <value-table> must use a hash function that never uses an object's identity (that is, its location in the heap) as a means of computing a hash ID. In practice, this means hash IDs must be constructed using only value-hash and merge-hash-codes. These tables are specifically designed to save overhead in testing hash states and whether the table needs to be rehashed after garbage collections. The second value of the hash function should always be $permanent-hash-state. For example:
define class <my-table> (<value-table>)
end class;
define method table-protocol (table :: <my-table>)
values(\=, string-hash);
end method;
The Extensions module exports the following functions to make it easier for users to use <equal-table>s and <value-table>s:
equal-hash [Generic Function]
- Arguments
- Values
- Description
This function returns a hash ID and hash state for use with <equal-table>s. If you define your own classes and \= methods specialized on those classes, then you should define a method for the equal-hash function specialized to your classes. Specialized methods exist for <number>, <character>, <function>, <symbol>, and <collection>. The method for <object> returns the integer 42 and $permanent-hash-state. This function may use an object's identity (that is, its location in the heap) to produce a hash ID.
value-hash [Generic Function]
- Arguments
- Values
- Description
This function produces hash codes for objects without using the objects' identities. This function is suitable for use with <value-table>s. Table-Extensions provides methods specialized for the following types: <string>, <integer>, <float>, <character>, <symbol>, and <boolean>.
Caveat: This generic function is not related to the similarly named values-hash.
Copyright 1994, 1995, 1996, 1997 Carnegie Mellon University. All rights reserved.
Send comments and bug reports to gwydion-bugs@cs.cmu.edu