Changes between Version 6 and Version 7 of HashTablesCowan


Ignore:
Timestamp:
11/30/12 00:48:43 (4 years ago)
Author:
cowan
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • HashTablesCowan

    v6 v7  
    44 
    55   * Is disjoint from all other types. 
    6    * Provides a mapping from some set of ''keys'' to some set of ''values'' associated to those keys. 
     6   * Provides a mapping from objects known as ''keys'' to corresponding objects known as ''values''. 
    77     * Keys may be any Scheme objects in some kinds of hash tables, but are restricted in other kinds. 
    88     * Values may be any Scheme objects. 
    9    * Has no intrinsic order for the key-value ''associations'' it contains. 
     9   * Has no intrinsic order for the key-value ''associations'' it contains, though an order may be defined as an extension. 
    1010   * Provides an ''equivalence function'' which defines when a proposed key is the same as an existing key.  No table may contain more than one value for a given key. 
    1111   * Supports mutation as the primary means of setting the contents of a table. 
     
    3939Note that there are no hash tables whose equivalence function is `eqv?`, because SRFI 69 does not support them.  Users will have to live with `eq?` or `equal?` hash tables as the case may be. 
    4040 
     41'''Issue''':  add `(hash-table-unfold `''p f g key-seed value-seed''`)`?  Or possibly just one seed and let `f` generate the two values from a single value. 
    4142 
    4243== Copiers == 
     
    4546 
    4647Returns a newly allocated hash table with the same equivalence predicate and associations as ''hash-table''. (SRFI-69 `hash-table-copy`; R6RS `(hashtable-copy `''hash-table''` #t)`) 
    47  
    4848 
    4949== Predicates == 
     
    5959== Accessors == 
    6060 
    61 `(hash-table-ref `''hash-table''` `''key'' ''default''`)` 
     61`(hash-table-ref `''hash-table''` `''key'' ''default-proc''`)` 
    6262 
    63 Returns the value associated to ''key'' in ''table''. If no value is associated to ''key'', ''default'' is returned.  Must execute in amortized O(1) time.  (SRFI-69 `hash-table-ref/default`; R6RS `hashtable-ref`) 
     63Returns the value associated to ''key'' in ''table''. If no value is associated to ''key'', ''default-proc'' is applied to no arguments and the result is returned.  Must execute in amortized O(1) time, not counting the time to call ''default-proc'' if necessary.  (SRFI-69 `hash-table-ref/default`; R6RS `hashtable-ref`) 
    6464 
    6565`(hash-table-size `''table''`)` 
     
    6767Returns the number of associations in ''hash-table''.  Must execute in amortized O(1) time.  (SRFI-69 `hash-table-size`; R6RS `hashtable-size`) 
    6868 
    69  
    7069== Mutators == 
    7170 
    7271`(hash-table-set! `''hash-table''` `''key''` `''value''`)` 
    7372 
    74 Creates a new association in ''hash-table'' that associates ''key'' with ''value''. The previous association (if any) is removed.  It is an error if ''table'' is a string or string-ci hash table and ''key'' is not a string.  Must execute in amortized O(1) time.  (SRFI-69 `hash-table-set!`; R6RS `hashtable-set!`) 
     73Creates a new association in ''hash-table'' that associates ''key'' with ''value''. The previous association (if any) is removed.  It is an error if ''hash-table'' is a string or string-ci hash table and ''key'' is not a string.  Must execute in amortized O(1) time.  Returns an unspecified value.  (SRFI-69 `hash-table-set!`; R6RS `hashtable-set!`) 
    7574 
    7675`(hash-table-delete! `''hash-table''` `''key''`)` 
    7776 
    78 Removes any association to ''key'' in ''hash-table''. It is not an error if no association for that ''key'' exists.    Must execute in amortized O(1) time.  (SRFI-69 `hash-table-delete!`; R6RS `hashtable-delete!`) 
     77Removes any association to ''key'' in ''hash-table''. It is not an error if no association for that ''key'' exists.    Must execute in amortized O(1) time.  Returns an unspecified value.  (SRFI-69 `hash-table-delete!`; R6RS `hashtable-delete!`) 
    7978 
    80 `(hash-table-update! `''hash-table''` `''key''` `''procedure'' ''default'' ]`)` 
     79`(hash-table-update! `''hash-table''` `''key''` `''procedure'' ''default-proc'' ]`)` 
    8180 
    8281Semantically equivalent to, but may be implemented more efficiently than, the following code: 
    8382 
    84 `(hash-table-set! `''hash-table''` `''key''` (`''procedure'' `(hash-table-ref `''hash-table''` `''key''` `''default''`)))` 
     83`(hash-table-set! `''hash-table''` `''key''` (`''procedure'' `(hash-table-ref `''hash-table''` `''key''` `''default-proc''`)))` 
    8584 
    86 Must execute in amortized O(1) time.  (SRFI-69 `hash-table-update!/default`; R6RS `hashtable-update!`) 
     85Must execute in amortized O(1) time.  Returns an unspecified value.  (SRFI-69 `hash-table-update!/default`; R6RS `hashtable-update!`) 
     86 
     87'''Issue''':  add `hash-table-clear`? 
    8788 
    8889 
    8990== Iterators == 
    9091 
    91 `(hash-table-fold `''hash-table''` `''procedure''` `''init''`)` 
     92`(hash-table-fold `''procedure''` `''init''` `''hash-table''`)` 
    9293 
    93 Calls ''procedure'' for every association in ''hash-table'' with three arguments: the key of the association, the value of the association, and an accumulated value ''val''.  ''Val'' is ''init'' for the first invocation of ''procedure'', and for subsequent invocations of ''procedure'', the return value of the previous invocation.  The value returned by `hash-table-fold` is the return value of the last invocation of f. The order in which ''procedure'' is called for different associations is unspecified.  (SRFI-69 `hash-table-fold`; not in R6RS but easily implemented: see below.) 
     94Calls ''procedure'' for every association in ''hash-table'' with three arguments: the key of the association, the value of the association, and an accumulated value ''val''.  ''Val'' is ''init'' for the first invocation of ''procedure'', and for subsequent invocations of ''procedure'', the return value of the previous invocation.  The value returned by `hash-table-fold` is the return value of the last invocation of f. The order in which ''procedure'' is called for different associations is unspecified.  (SRFI-69 `hash-table-fold`; not in R6RS but trivially implemented: see below.) 
    9495 
    9596