Re: Scheme style auto-resizing hashtable (fwd)

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

On Tue, 3 Nov 1998, Jay Glascoe wrote:

> On Tue, 3 Nov 1998, Ian Bicking wrote:
> 
> > Jay Glascoe writes:
> > ...
> > > dictionary-consume-alist!       -- delete alist while inserting pairs
> > 
> > Isn't it impossible to destroy an alist without doing a set! on the
> > thing that points to the alist?
> 
> this one's for Maciej.  Look! a tail-recursive imperative procedure!  :()

<snip>

oops!  you win.  my procedure reduces alist to

(cons <last pair in alist> ())  <->  (<last pair in alist>)

which is kind of ugly.  This is much weirder, but how about

(cons (cons '() '()) '())       <->  ((()))

which is smaller than

(cons (cons big-key big-value) '())

it's still an alist, and dictionary is left with sole ownership of the
key-value pairs in the old alist (assuming nobody else is holding on to
them).


(define dictionary-consume-alist!
  (lambda (dictionary alist)
    (if (not (null? alist))
	(let* ((pair (car alist))
	       (key (car pair))
	       (value (cdr pair))
	       (alist-cdr (cdr alist)))
	  (dictionary-insert! dictionary key value)
	  (if (null? alist-cdr)
	      (begin
		(set-car! alist (cons '() '()))
		*unspecified*)
	      (begin
		(set-car! alist (car alist-cdr))
		(set-cdr! alist (cdr alist-cdr))
		(dictionary-consume-alist! dictionary alist)))))))


	Jay Glascoe
	jglascoe@jay.giss.nasa.gov