This is the mail archive of the guile@cygnus.com mailing list for the guile project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: Scheme style auto-resizing hashtable (fwd)


On Sun, 15 Nov 1998, Jay Glascoe wrote:

> The source code, a makefile, and test scripts are available at
> 
> http://www.giss.nasa.gov/~jglascoe/GUILE/hash-table.tar.gz


The hash-table API consists of 18 useful procedures,
not counting the 'v'/'q'/'x' variations.

	*** predicate: ***

hash-table? object
    your basic predicate.  Caution: this is not 100% fool-proof.

	*** constructors: ***

make-hash-table
make-hash-tablev
make-hash-tableq
make-hash-tablex user-equal? user-hasher

	*** translators: ***

list->hash-table list [wrapper]
list->hash-tablev list [wrapper]
list->hash-tableq list [wrapper]
list->hash-tablex list user-equal? user-hasher [wrapper]
    return a hash-table with key-value pairs (wrapper list-element)
    "wrapper" defaults to identity.
    (wrapper list-element) must be a pair for all list-elements.
	Think of these as list object methods; the list argument
    should appear first.  (With "list" up front and "wrapper" in
    back, "list->hash-tablex" winds up with a rather strange
    argument list.  Oh well, think of "hash-tablex"
    as the red-headed step-child of the hash-table types.)

list->hash-table! list [wrapper]
list->hash-tablev! list [wrapper]
list->hash-tableq! list [wrapper]
list->hash-tablex! list user-equal? user-hasher [wrapper]
    Similar to the non-destructive procedures above.
    Magically turn list "list" into a hash-table.  Return value
    is unspecified.  Note: "list" must be nonempty.

hash-table->list hash-table [unwrapper]
    return a list with elements (unwrapper key-value-pair)
    for all key-value pairs in hash-table "hash-table".
    "unwrapper" defaults to identity.
    ;;    Useful applications of this method include:
    ;; (define hash-table->keys
    ;;   (lambda (hash-table) (hash-table->list hash-table car)))
    ;; (define hash-table->values
    ;;   (lambda (hash-table) (hash-table->list hash-table cdr)))

hash-table->list! hash-table [unwrapper]
    Similar to the non-destructive "hash-table->list" above.
    Magically turn hash-table "hash-table" into a list.
    Return value is unspecified.  Note: "hash-table" must
    have at least one entry.

	*** behavior modifiers: ***

hash-table-enable! hash-table option
hash-table-disable! hash-table option
    "option" should be one of 'auto-shrink, 'store-hash.
    rebuild "hash-table" if the "store-hash" option is toggled.
	NOTE: all hash-table constructors and list->hash-table
    converters return a hash-table with both options ON.

	*** the "Big 3" basic operations: ***

hash-table-insert! hash-table key value
hash-table-lookup hash-table key [not-here]
hash-table-remove! hash-table key [not-here]

	*** unions and consumers: ***

hash-table-add-pair! hash-table pair
    Insert the key-value pair "pair" into hash-table
    "hash-table".  Of course, "pair" must be a pair.
    In particular, pair should be of the form (key . value)

hash-table-add-list! hash-table list [wrapper]
    Could be written as
    ;; (for-each (lambda (elt)
    ;;             (hash-table-add-pair! hash-table (wrapper elt)))
    ;;           list)
    "list" must be a list and "wrapper" should be
    a one argument procedure.  (wrapper list-element)
    must be a pair for all of "list"'s elements.
    "wrapper" defaults to the identity function.
    Return value is unspecified.

hash-table-consume-list! hash-table list [wrapper]
    Similar to the non-destructive "hash-table-add-list!" above.
    Delete list "list" while inserting (wrapper list-element)
    into hash-table "hash-table" for all of "list"'s elements.
    Return value is unspecified.

	*** other stuff: ***

hash-table-size hash-table
    return the number of entries in hash-table "hash-table".

hash-table-clear! hash-table
    remove all entries from hash-table "hash-table".
    return value is unspecified.

hash-table-map pair-transformer hash-table
    return a new dictionary with key-value-pairs
    (pair-transformer key-value-pair)
    The pair arguments given to the transformer
    are [shallow] copies of the key-value pairs in
    "hash-table".
	"map" and "for-each" are standard fare for functional
    languages.  Think of "hash-table-map" as a procedure object
    oriented method; so the procedure "pair-transformer"
    belongs in front.
    ;;    Useful applications of this method include:
    ;; (define hash-table-copy
    ;;   (let ((id (lambda (x) x)))
    ;;     (lambda (hash-table) (hash-table-map id hash-table))))
    ;; (define hash-table-invert
    ;;   (let ((inv (lambda (pair) (cons (cdr pair) (car pair)))))
    ;;     (lambda (hash-table) (hash-table-map inv hash-table))))

hash-table-for-each procedure hash-table
    apply "procedure", a procedure of two arguments, to all of
    "hash-table"'s keys and values  (lambda (key value) (...))
    return value is unspecified.  Return value is unspecified.
	Think of "hash-table-for-each" as a procedure object
    oriented method; so "procedure" belongs in front.


	Jay Glascoe
	original author of
	"The $ICPyramid Scheme"
	jglascoe@jay.giss.nasa.gov