Re: Scheme style auto-resizing hashtable (fwd)

[Jay Glascoe <jglascoe@jay.giss.nasa.gov>]

essential data-structure procedures:

I consider the following to be self-evident ;)
Let's say we have a data-structure called a "foo-bar".
Then we should have all of the following:

foo-bar? object

make-foo-bar

foo-bar->list foo-bar [unwrapper]
    I figure that the list is the greatest common divisor of all Scheme
    data structures (at least all "pure" Scheme extended types).
    So, "foo-bar" should admit to a list decomposition.
    [And I don't mean, e.g. (tree->list tree) == tree  darn it!!
     (tree->list) should of course give a list of nodes/leaves].

list->foo-bar list [wrapper]
    Yes, this a list oriented procedure, but until we have a MOP this
    should be defined in the foo-bar extension/module. Should
    be the inverse of foo-bar->list, i.e.
    (foo-bar->list (list->foo-bar list)) == list
    and
    (list->foo-bar (foo-bar->list foo-bar)) == foo-bar

    Should be equivalent to
    (define foo-bar (make-foo-bar))
    (foo-bar-insert-list! foo-bar list) ;; described below

foo-bar-map foo-bar [transformer]
    Return a new foo-bar object with entries: (transformer old-entry)

foo-bar-foreach foo-bar procedure
    Iterate over "foo-bar", applying "procedure" to all of "foo-bar"'s
    (possibly ordered) entries.

foo-bar-clear! foo-bar
    (equal? (foo-bar-clear! foo-bar) (make-foo-bar)) => #t
    or perhaps
    (equal? (foo-bar-clear! foo-bar)
            (let ((foo-bar (make-foo-bar)))
              (foo-bar-enable foo-bar 'option1)
              (foo-bar-disable foo-bar 'option2)
              ...
              foo-bar)) => #t

foo-bar-insert-list! foo-bar list [wrapper]
foo-bar-consume-list! foo-bar list [wrapper]
    (define foo-bar (make-foo-bar))
    (foo-bar-insert-list! foo-bar list)
    should be equivalent to 
    (list->foo-bar list)  ;;  described above...  :()

foo-bar-insert-foo-bar! foo-bar1 foo-bar2
foo-bar-consume-foo-bar! foo-bar1 foo-bar2
    self-descriptive

--------------------------------------------------------------------

And here's what my dictionary objects have:

dictionary?

make-dictionary
make-dictionaryv
make-dictionaryq
make-dictionaryx equality-predicate hasher-function
    You may notice that I removed the optional alist argument.
    That functionality is provided by "list->dictionary" and friends.

dictionary->list dictionary [unwrapper]
    "unwrapper" defaults to the identity function.
    (dictionary->alist dictionary)  == (dictionary->list dictionary)
    (dictionary->keys dictionary)   == (dictionary->list dictionary car)
    (dictionary->values dictionary) == (dictionary->list dictionary cdr)

list->dictionary list [wrapper]
list->dictionaryv list [wrapper]
list->dictionaryq list [wrapper]
list->dictionaryx list equality-predicate hasher-function [wrapper]
    if "list" is an alist, then wrapper defaults to the identity function.
    Otherwise, wrapper defaults to (lambda (x) (cons x '())).

    Should be equivalent to
    (define dictionary (make-dictionary))
    (dictionary-insert-list! dictionary list [wrapper]) ;; described below

dictionary-map dictionary [transformer]
    "transformer" defaults to (lambda (pair) (cons (car pair) (cdr pair)))
    Return a new dictionary.
    (dictionary-copy dictionary) == (dictionary-map dictionary)
    (dictionary-invert dictionary) ==
        (dictionary-map dictionary
			(lambda (pair) (cons (cdr pair) (car pair))))
    [yeah, you'll lose some pairs if the values aren't all unique, but
    this functionality is often useful]

dictionary-foreach dictionary procedure
    Iterate over all dictionary entries, applying "procedure" to
    the associated key-value pairs.  Return value is unspecified.
    [I can't think of any useful default for "procedure"].

dictionary-clear! dictionary
    considered essential because it may take three or more statements
    for the user to create and tune a new dictionary to their
    specific needs.  E.g.
     (define foo (make-dictionaryv)) ;; keys will be integers and symbols
     (dictionary-disable! foo 'auto-shrink)  ;; I'm a speed freak  ;)
     (dictionary-disable! foo 'store-hash)   ;; int's/symbols are 
					     ;;   their own hash value

dictionary-insert-list! dictionary list [wrapper]
dictionary-consume-list! dictionary list [wrapper]
    Okay, so "*-insert-list!" is a trivial application of a
    "for-each" application on a list.  But "*-consume-list!" is
    both useful and not entirely trivial.  (careful! don't consume
    constant lists... they're bad for you  ;)
    ...
    If "list" is an association list, then "wrapper" defaults
    to the identity function, (lambda (key-value-pair) key-value-pair),
    otherwise, "wrapper" defaults to (lambda (x) (cons x '())).
    [useful for "have I seen this key before?" functionality]

dictionary-insert-dictionary! dictionary1 dictionary2 [wrapper]
dictionary-consume-dictionary! dictionary1 dictionary2 [wrapper]
    once called "dictionary-update!", now self-descriptive  ;)


	Jay Glascoe
	jglascoe@jay.giss.nasa.gov