Sorting (was Re: How do I do this in dsssl/jade?)

[kubek@xxxxxxxxxxxx (kubek)]

>>>>> "N.W." == Norman Walsh <ndw@xxxxxxxxxx> writes:

    N.W.> / "Glenn R. Kronschnabl" <grk@xxxxxxxxxxxxxxxx> was heard to
    N.W.> say: | I have an xml file that looks something like: [...] |
              [Q1 snipped ...]

    N.W.> Q2: Right now I am sorting/reordering
    N.W.> via perl-xml, but I assume I could | reorder the nodelist
    N.W.> using dsssl/jade. Anyone have some code I peruse? | | (Q1 is
    N.W.> more MUCH more important)

    N.W.> Are you saying that all the vcards are already in sorted
    N.W.> order? If so, what you want's not too hard. Sorting, that
    N.W.> would be a different kettle of fish altogether.


Here is simple code for quicksort able to sort both lists and
node-lists (sorry I forget the initial author for this scheme thing,
maybe in Slib ??).

As sorting a node-list or a simple list is essentially the same
problem, i.e. sort a sequence of elements, there is a first function
(called quicksort::generic) which acts as a "quicksort procedure
maker".

Thid first procedure  defines a general quicksort operation for abstract 
sequences defined through the following procedures:
	- is-null? tests if the sequence is empty 
	- first extracts the first element from the sequence
	- others gives all the elements from the sequence, except the first
	- concat is used for combining two sequences
	- add is used to add an element to the sequence
	- empty is the empty sequence

 The sorts for list and node-lists are then
defined using this function by :

(define quicksort
  (quicksort::generic null? car cdr append cons '()))

(define nl-quicksort
  (quicksort::generic node-list-empty?
		      node-list-first
		      node-list-rest
		      node-list
		      node-list
		      (empty-node-list)))

(define quicksort::generic
  (lambda(is-null? first others concat add empty)
    (letrec ((collect
	;; Collect is an helper function doing the real work

	      (lambda (pivot ls lgroup rgroup less?)
		(if (is-null? ls)
		    (concat (impl lgroup less?)
			    (add pivot (impl rgroup less?)))
		    (if (less? pivot (first ls))
			(collect pivot (others ls) lgroup 
				 (add (first ls) rgroup) 
				 less?)
			(collect pivot (others ls) 
				 (add (first ls) lgroup) 
				 rgroup 
				 less?)))))
	     (impl	
	      ;; impl first test some trivial sorting case and then call
	      ;; the procedure collect
	      (lambda (ls less?)	
		(if (or (is-null? ls) (is-null? (others ls)))
		    ls
		    (collect (first ls) (others ls) empty empty less?)))))
	;; we return the new defined procedure
      impl)))
	    



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

J.-M.
Computing Center
INSA Toulouse
France


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