Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!nbires!rcd
From: rcd@nbires.UUCP (Dick Dunn)
Newsgroups: net.text
Subject: Re: sorting in troff(nroff)
Message-ID: <484@opus.nbires.UUCP>
Date: Wed, 30-Jul-86 01:55:26 EDT
Article-I.D.: opus.484
Posted: Wed Jul 30 01:55:26 1986
Date-Received: Fri, 1-Aug-86 03:19:06 EDT
References: <320@cord.UUCP> <174@cs.qmc.ac.uk>
Organization: NBI,Inc, Boulder CO
Lines: 56
Keywords: troff, nroff, sorting, macros
Summary: Yes, it's a serious question

> >abstract: how can items be sorted in troff(nroff)?
> >
> >explanation: given the definition of the list-begin, list-item,
> >       and list-end macros, how can i generate a sorted list of
> >       the first arguments to the list-item macros?
> 
> (You are joking, aren't you?)

The original posting MIGHT have been a joke, but I don't think so.  It's a
good question.  Generating indices is very hard to do with troff, since you
can't feed a piece of text out through a pipe to a program and catch the
result.  (At least, I can't find a way to do it.)  You can try to make
multiple passes somehow, but you end up with a messy makefile for your
document that's peculiar to the document structure.  If you try to piece
the document together from files troff'ed separately, it's a mess to get
the page numbering right and entering the index/indices in the TOC is even
worse.  So--if you're not making a humongous index, it would be worth
trying to do it with troff.

> Ignoring the fact that troff doesn't have string comparisons,...

But OUCH!  That, as far as I can see, is the crux of the problem.  Once you
get the comparison, you've obviously got the power you need; the rest is
just a matter of finding the best way to do it.

> ...what you need is a way of imitating arrays
> in troff so you can do quicksort/bubblesort or whatever.

Arrays aren't really necessary.  You could keep the text in a diversion and
use something as simple as an insertion sort:
	List-start initializes the diversion (probably with a dummy entry)
	  and sets up macros to be used to enter the text.
	Each list-item shuffles text from one diversion to a second,
	  inserting its argument at the appropriate point.  The key here is
	  that the diversion contains macro calls for each item entered so
	  far.  The macro that is called compares its argument (the
	  already-entered string) with the new candidate.  If the new
	  candidate sorts ahead, the macro tosses it into the diversion
	  being created (and might reset some macro definitions to speed up
	  the rest of the copy).  In any case, it then tosses its argument
	  into the diversion (appropriately protected and as a macro call).
	  The diversion needs to have a tail entry to force insertion at
	  the end of the list.
	List-end redefines the macro used in the diversion to be something
	  that outputs text appropriately and cleans up the mess.
The insertion sort is, of course, quadratic in the number of items--and the
unit of work is pretty large.  But anything you could come up with at this
level would be expensive for a list of any substantial size (say, more than
a couple dozen items).  At least it doesn't stop working when you run out
of number registers; the limit on diversions is not too bad.

And anyway, it's all just an entertaining exercise unless somebody knows
how to do the string comparison...
-- 
Dick Dunn	{hao,ucbvax,allegra}!nbires!rcd		(303)444-5710 x3086
   ...Never attribute to malice what can be adequately explained by stupidity.