Re: (dsssl) sorting a node list

Subject: Re: (dsssl) sorting a node list
From: Boris Smilga <boris@xxxxxxxxxx>
Date: 21 Jul 2002 16:05:38 -0400
Jany Quintard <jany.quintard@xxxxxxx> writes:

> I am looking in the spec and the archive (general archive is broken?) to
> find a way to sort a node list.
> Does anyone know a simple way to do it?

 Jany:

here's a simple and rather generic implementation of the mergesort
algorithm I found in one of my scripts:

  (define (mergesort l
            #!key precedes? first rest push empty? length sublist )
    (define (merge l1 l2)
      (cond ((empty? l1) l2)
            ((empty? l2) l1)
            (else (let ((e1 (first l1)) (e2 (first l2)))
                    (if (precedes? e1 e2)
                        (push e1 (merge (rest l1) l2))
                        (push e2 (merge l1 (rest l2))) )))))
    (define (sort l)
      (let ((l-length (length l)))
        (if (< l-length 2)
            l
            (let ((middle (quotient l-length 2)))
              (merge (sort (sublist l 0 middle))
                     (sort (sublist l middle l-length)) )))))
    (sort l) )

For node lists you would have to define an interface to it, something
along the lines of the following:

  (define (node-list-mergesort nl
            #!optional (node-precedes? grove-before?) )
    (mergesort nl
       precedes?: node-precedes?
       first: node-list-first
       rest: node-list-rest
       push: node-list
       empty?: node-list-empty?
       length: node-list-length
       sublist: node-list-sublist ))

The original was meant to work mainly on lists, thus I don't give a
100% guarantee that it shall be functioning properly with node lists.

                                                       Yours truly,
                                                         B.Smilga.

 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist

Current Thread