In article <·············@WINTERMUTE.eagle> SDS <···········@cctrading.com> writes:
>
> (defun sync-lists (lists &keys key)
> "LISTS is a list of lists. KEY is applied to the elements of the lists
> to get the comparison key. Make all the lists have the record for each
> key. Lists are sorted already."
> ...)
I will sketch out a potential solution. It involves three passes
through the list of lists, but you can get that down to two by combining
the second and third steps.
1. Apply KEY to the first element of each list. Find the smallest key.
2. Go through the lists again, skipping over those which have the key
and destructively modifying those that need the key.
3. Go through the lists again, advancing to the next element in the
list.
REPEAT until done.
There a a number of picky details that can be troublesome. The hardest
one is dealing with the need to add items to the end of the list. This
either requires checking to see that all lists end together before
advancing (and adding bogus entries to those that don't); or retaining a
pointer that is one further back, so you will have something to modify.
You can't destructively modify NIL, so you will need to take care at the
end of the list.
Some helping functions:
(defun find-smallest-key (lists key)
(let ((smallest (funcall key (caar lists))))
;; Iterative version:
(loop for item in (rest lists)
when (< (funcall key (first item)) smallest)
do (setq smallest (funcall key (first item))))
;; Functional version:
(mapc #'(lambda (item)
(when (< (funcall key (first item)) smallest)
(setq smallest (funcall key (first item)))))
(rest lists))
smallest))
(defmacro insert (item list)
(let ((listvar (gensym "LIST")))
`(if ,listvar
(setf (cdr ,listvar) (cons (car ,listvar) (cdr ,listvar))
(car ,listvar) ,item)
(error "Can't insert ~A into NIL list!" ,item)) ))
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu