Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!munnari!moncskermit!basser!john
From: john@basser.oz (John Mackin)
Newsgroups: net.text
Subject: Re: sorting in troff(nroff)
Message-ID: <719@basser.oz>
Date: Mon, 28-Jul-86 02:11:47 EDT
Article-I.D.: basser.719
Posted: Mon Jul 28 02:11:47 1986
Date-Received: Mon, 28-Jul-86 21:15:30 EDT
References: <320@cord.UUCP>
Reply-To: john@basser.oz (John Mackin)
Organization: Dept of Comp Sci, Uni of Sydney, Australia
Lines: 666
Summary: troff can do anything

In article <320@cord.UUCP> miker@cord.UUCP (Mike Roberson) writes:

> how can items be sorted in troff(nroff)?

This got a friend and I to thinking.  Once we worked out a way to
compare strings (for other than (in)equality) an insertion sort
was easy, but we were dissatisfied with its performance, so
we wrote a merge-based sort that is n log n.  Both versions follow.

The insertion sort took 55 minutes of user-time on our 780 to sort
a 300 element list; the merge sort does the same list in 17 minutes
(and a 1000 element list in 72 minutes).  Bear in mind, people, troff
isn't sort!  The insertion sort is far simpler and is perfectly adequate
(and considerably faster) for small lists (say up to 20 or so elements
on a 780).

Each sort has the same interface:

	.LS			\" list start
	.LI "key" "data"	\" list item - will be sorted on the key,
				\" and the data goes with it.  they key must
				\" not contain spaces or backslashes.  if
				\" you want a space in the key, put in a
				\" control-E at that point.
	...
	.LE			\" list end - sort the list and invoke
				\" .lo "key" "data"	\" list output
				\" for every item, in order.  the user can
				\" redefine lo to get whatever format is
				\" desired; a basic one is provided.

We make no apology for this code; we wrote it to establish that it
could be done.  It is unfortunate that we did not adopt a more
consistent naming convention; adapting this for use with any
existing macro package is up to you.

If you have spaces in the key, replace them with control-E characters;
they will be output as spaces.

The only other macro in these sources (it is the same in both) that
you are likely to want to call is .sc, the string comparison macro.

	.sc "string1" "string2"

sets the number register R to 1, 0, or -1, depending on whether string1
is lexically less than, equal to, or greater than string2.

Extract the following shell archive using sh.  Then, BEFORE TRYING TO
USE THE MACROS, edit "insert" and "merge" with an editor capable of
handling control characters.  Globally change the string CTRL-E into
a control-E, and the string CTRL-F into a control-F.

To test the macros, try "nroff insert demo | sed 10q | cmp - demo.out".
(The sed is needed because I stripped the traling newlines from demo.out
for posting.)

Have fun!

John Mackin, Basser Department of Computer Science,
	     University of Sydney, Sydney, Australia

john%basser.oz@SEISMO.CSS.GOV
{seismo,hplabs,mcvax,ukc,nttlab}!munnari!basser.oz!john

The following code is the product of a collaboration between
Mark Shand and John Mackin.  You can do what you like with it,
as long as you don't mail us and ask how it works!

# To unbundle, sh this file
echo insert 1>&2
sed 's/.//' >insert <<'//GO.SYSIN DD insert'
-.ds @CTRL-E "0 "
-.ds @! "1 "
-.ds @" "2 "
-.ds @# "3 "
-.ds @$ "4 "
-.ds @% "5 "
-.ds @& "6 "
-.ds @' "7 "
-.ds @( "8 "
-.ds @) "9 "
-.ds @* "10 "
-.ds @+ "11 "
-.ds @, "12 "
-.ds @- "13 "
-.ds @. "14 "
-.ds @/ "15 "
-.ds @0 "16 "
-.ds @1 "17 "
-.ds @2 "18 "
-.ds @3 "19 "
-.ds @4 "20 "
-.ds @5 "21 "
-.ds @6 "22 "
-.ds @7 "23 "
-.ds @8 "24 "
-.ds @9 "25 "
-.ds @: "26 "
-.ds @; "27 "
-.ds @< "28 "
-.ds @= "29 "
-.ds @> "30 "
-.ds @? "31 "
-.ds @@ "32 "
-.ds @A "33 "
-.ds @B "34 "
-.ds @C "35 "
-.ds @D "36 "
-.ds @E "37 "
-.ds @F "38 "
-.ds @G "39 "
-.ds @H "40 "
-.ds @I "41 "
-.ds @J "42 "
-.ds @K "43 "
-.ds @L "44 "
-.ds @M "45 "
-.ds @N "46 "
-.ds @O "47 "
-.ds @P "48 "
-.ds @Q "49 "
-.ds @R "50 "
-.ds @S "51 "
-.ds @T "52 "
-.ds @U "53 "
-.ds @V "54 "
-.ds @W "55 "
-.ds @X "56 "
-.ds @Y "57 "
-.ds @Z "58 "
-.ds @[ "59 "
-.\" this is a bit buggered ds @\e "60 "
-.ds @] "61 "
-.ds @^ "62 "
-.ds @_ "63 "
-.ds @` "64 "
-.ds @a "65 "
-.ds @b "66 "
-.ds @c "67 "
-.ds @d "68 "
-.ds @e "69 "
-.ds @f "70 "
-.ds @g "71 "
-.ds @h "72 "
-.ds @i "73 "
-.ds @j "74 "
-.ds @k "75 "
-.ds @l "76 "
-.ds @m "77 "
-.ds @n "78 "
-.ds @o "79 "
-.ds @p "80 "
-.ds @q "81 "
-.ds @r "82 "
-.ds @s "83 "
-.ds @t "84 "
-.ds @u "85 "
-.ds @v "86 "
-.ds @w "87 "
-.ds @x "88 "
-.ds @y "89 "
-.ds @z "90 "
-.ds @{ "91 "
-.ds @| "92 "
-.ds @} "93 "
-.ds @~ "94 "
-.\"
-.de sc
-.nr S 0
-.if '\\$1\\$2'' .nr R 0
-.if !'\\$1\\$2'' \{\
-.if '\\$1'' .nr R 0-1
-.if !'\\$1'' \{\
-.if '\\$2'' .nr R 1
-.if !'\\$2'' \{\
-.Sc a \\*(@\\$1
-.Sc b \\*(@\\$2
-.if \\*(Ha=\\*(Hb .sc "\\*(Ta" "\\*(Tb"
-.if !\\nS \{\
-.ie \\*(Ha>\\*(Hb .nr R 1
-.el .nr R 0-1
-'br\}
-'br\}
-'br\}
-'br\}
-.nr S 1
-..
-.de Sc
-.ds H\\$1 "\\$2
-.ds T\\$1 "\\$3
-..
-.de lo
-\\$1 --> \\$2
-..
-.de li
-.if \\n(is=0 \{\
-.sc "\\$1" "\\*(ik"
-.if \\nR=1 \{ .nr is 1
-\!.li "\\*(ik" "\\*(it"
-'br\}
-'br\}
-\!.li "\\$1" "\\$2"
-..
-.de LS
-.rm L
-..
-.de LI
-.nr is 0
-.di M
-.ds ik "\\$1
-.ds it "\\$2
-.L
-.di
-.rn M L
-.if \\n(is=0 \{\
-.da L
-\!.li "\\$1" "\\$2"
-.di
-'br\}
-..
-.de LE
-.rn li lt
-.rn lo li
-.nr F \\n(.u
-.nf
-.tr CTRL-E 
-.L
-.tr
-.if \\nF .fi
-.rn li lo
-.rn lt li
-..
//GO.SYSIN DD insert
echo merge 1>&2
sed 's/.//' >merge <<'//GO.SYSIN DD merge'
-.af ml a
-.af sl a
-.af rl a
-.af tl a
-.ds @CTRL-E "0 "
-.ds @! "1 "
-.ds @" "2 "
-.ds @# "3 "
-.ds @$ "4 "
-.ds @% "5 "
-.ds @& "6 "
-.ds @' "7 "
-.ds @( "8 "
-.ds @) "9 "
-.ds @* "10 "
-.ds @+ "11 "
-.ds @, "12 "
-.ds @- "13 "
-.ds @. "14 "
-.ds @/ "15 "
-.ds @0 "16 "
-.ds @1 "17 "
-.ds @2 "18 "
-.ds @3 "19 "
-.ds @4 "20 "
-.ds @5 "21 "
-.ds @6 "22 "
-.ds @7 "23 "
-.ds @8 "24 "
-.ds @9 "25 "
-.ds @: "26 "
-.ds @; "27 "
-.ds @< "28 "
-.ds @= "29 "
-.ds @> "30 "
-.ds @? "31 "
-.ds @@ "32 "
-.ds @A "33 "
-.ds @B "34 "
-.ds @C "35 "
-.ds @D "36 "
-.ds @E "37 "
-.ds @F "38 "
-.ds @G "39 "
-.ds @H "40 "
-.ds @I "41 "
-.ds @J "42 "
-.ds @K "43 "
-.ds @L "44 "
-.ds @M "45 "
-.ds @N "46 "
-.ds @O "47 "
-.ds @P "48 "
-.ds @Q "49 "
-.ds @R "50 "
-.ds @S "51 "
-.ds @T "52 "
-.ds @U "53 "
-.ds @V "54 "
-.ds @W "55 "
-.ds @X "56 "
-.ds @Y "57 "
-.ds @Z "58 "
-.ds @[ "59 "
-.\" this is a bit buggered ds @\e "60 "
-.ds @] "61 "
-.ds @^ "62 "
-.ds @_ "63 "
-.ds @` "64 "
-.ds @a "65 "
-.ds @b "66 "
-.ds @c "67 "
-.ds @d "68 "
-.ds @e "69 "
-.ds @f "70 "
-.ds @g "71 "
-.ds @h "72 "
-.ds @i "73 "
-.ds @j "74 "
-.ds @k "75 "
-.ds @l "76 "
-.ds @m "77 "
-.ds @n "78 "
-.ds @o "79 "
-.ds @p "80 "
-.ds @q "81 "
-.ds @r "82 "
-.ds @s "83 "
-.ds @t "84 "
-.ds @u "85 "
-.ds @v "86 "
-.ds @w "87 "
-.ds @x "88 "
-.ds @y "89 "
-.ds @z "90 "
-.ds @{ "91 "
-.ds @| "92 "
-.ds @} "93 "
-.ds @~ "94 "
-.ds @CTRL-F "95 "
-.\"
-.de sc
-.nr S 0
-.if '\\$1\\$2'' .nr R 0
-.if !'\\$1\\$2'' \{\
-.if '\\$1'' .nr R 0-1
-.if !'\\$1'' \{\
-.if '\\$2'' .nr R 1
-.if !'\\$2'' \{\
-.Sc a \\*(@\\$1
-.Sc b \\*(@\\$2
-.if \\*(Ha=\\*(Hb .sc "\\*(Ta" "\\*(Tb"
-.if !\\nS \{\
-.ie \\*(Ha>\\*(Hb .nr R 1
-.el .nr R 0-1
-'br\}
-'br\}
-'br\}
-'br\}
-.nr S 1
-..
-.de Sc
-.ds H\\$1 "\\$2
-.ds T\\$1 "\\$3
-..
-.de lo
-\\$1 --> \\$2
-..
-.de li
-.ds ik "<none>
-.lr "\\$1"
-.if !'\\$1'CTRL-F' \!.l0 "\\$1" "\\$2"
-.\"if !'\\$1'CTRL-F' .tm li: "\\$1" into \\n(.z
-..
-.\" lr ensures that %0 contains something (which it does by calling lS,
-.\" the logarithmic split macro); then it extracts the keyword
-.\" out of %0.  if the keyword precedes $1 then it outputs the entry, and
-.\" recurs.
-.de lr
-.if \\n(%0=0 .lS
-.rn l% l0
-.%0
-.rn l0 l%
-.sc "\\$1" "\\*(ik"
-.if \\nR=1 \{\
-\!.l0 "\\*(ik" "\\*(it"
-.\"tm lr: "\\*(ik" into \\n(.z
-.nr %0 0
-.lr "\\$1"
-'br\}
-..
-.de l%
-.ds ik "\\$1
-.ds it "\\$2
-..
-.de lS
-.nr sl 0
-.fs
-.rn re l0
-.nr rl 0
-.nr rc 0
-.nr op 0
-.di %0
-.%\\n(sl
-.di
-.rn l0 re
-.rm %\\n(sl
-.nr %\\n(sl 0
-..
-.de re
-\!.l0 "\\$1" "\\$2"
-.nr rc +1
-.if \\n(rc>=\\n(op \{\
-.di
-.nr %\\n(rl 1
-.nr rl +1
-.di %\\n(rl
-.ie \\n(op=0 .nr op 1
-.el .nr op \\n(op*2
-.nr rc 0
-'br\}
-..
-.de fs
-.nr sl +1
-.if \\n(%\\n(sl=0 .fs
-..
-.de LS
-.nr #a 0
-.nr #b 0
-.nr #c 0
-.nr #d 0
-.nr #e 0
-.nr #f 0
-.nr #g 0
-.nr #h 0
-.nr #i 0
-.nr #j 0
-.nr #k 0
-.nr #l 0
-.nr #m 0
-.nr #n 0
-.nr #o 0
-.nr #p 0
-.nr #q 0
-.nr #r 0
-.nr #s 0
-.nr #t 0
-.nr #u 0
-.nr #v 0
-.nr #w 0
-.nr #x 0
-.nr #y 0
-.nr #z 0
-.rm #a
-.rm #b
-.rm #c
-.rm #d
-.rm #e
-.rm #f
-.rm #g
-.rm #h
-.rm #i
-.rm #j
-.rm #k
-.rm #l
-.rm #m
-.rm #n
-.rm #o
-.rm #p
-.rm #q
-.rm #r
-.rm #s
-.rm #t
-.rm #u
-.rm #v
-.rm #w
-.rm #x
-.rm #y
-.rm #z
-..
-.de LI
-.di #0
-\!.l0 "\\$1" "\\$2"
-.di
-.nr ml 1
-.MG
-..
-.de LE
-.nr ml 1
-.rm #0
-.nr tl 27
-.Ft
-.nr tl +1
-.FM
-.rn lo l0
-.nr F \\n(.u
-.nf
-.tr CTRL-E 
-.#0
-.tr
-.if \\nF .fi
-.rn l0 lo
-..
-.\" this macro has one parameter: a single letter giving the name of the
-.\" diversion to merge with #0 producing #1, which is then moved to #0.
-.de Mg
-.nr %0 0
-.nr %a 0
-.nr %b 0
-.nr %c 0
-.nr %d 0
-.nr %e 0
-.nr %f 0
-.nr %g 0
-.nr %h 0
-.nr %i 0
-.nr %j 0
-.nr %k 0
-.nr %l 0
-.nr %m 0
-.nr %n 0
-.nr %o 0
-.nr %p 0
-.nr %q 0
-.nr %r 0
-.nr %s 0
-.nr %t 0
-.nr %u 0
-.nr %v 0
-.nr %w 0
-.nr %x 0
-.nr %y 0
-.nr %z 0
-.rm %a
-.rm %b
-.rm %c
-.rm %d
-.rm %e
-.rm %f
-.rm %g
-.rm %h
-.rm %i
-.rm %j
-.rm %k
-.rm %l
-.rm %m
-.rm %n
-.rm %o
-.rm %p
-.rm %q
-.rm %r
-.rm %s
-.rm %t
-.rm %u
-.rm %v
-.rm %w
-.rm %x
-.rm %y
-.rm %z
-.da #0
-\!.l0 "CTRL-FCTRL-F" "foobaz"
-.da
-.da #\\$1
-\!.li "CTRL-F" "foobaz"
-.da
-.#%
-.di #1
-.#\\$1
-.di
-.rn #1 #0
-..
-.de MG
-.nr M \\n(#\\n(ml
-.if !\\nM \{\
-.    RN \\n(ml
-.    nr #\\n(ml 1
-'br\}
-.if \\nM \{\
-.    Mg \\n(ml
-.    nr #\\n(ml 0
-.    nr ml +1
-.    MG
-'br\}
-..
-.de FM
-.if \\n(#\\n(ml .Mg \\n(ml
-.nr ml +1
-.if !'\\n(ml'\\n(tl' .FM
-..
-.de RN
-.rn lR l0
-.di #\\$1
-.#0
-.di
-.rn l0 lR
-..
-.de lR
-\!.li "\\$1" "\\$2"
-..
-.de #%
-.nr lC 0
-.rn lC l0
-.#0
-.rn l0 lC
-.nr sl 0
-.nr ol 0
-.nr op 0
-.rn ol l0
-.di %%
-.#0
-.di
-.rm %%
-.rn l0 ol
-..
-.de lC
-.nr lC +1
-..
-.de ol
-.if \\n(ol=\\n(op \{\
-.OL
-.di
-.di %\\n(sl
-.nr %\\n(sl 1
-'br\}
-\!.l0 "\\$1" "\\$2"
-.nr ol +1
-..
-.de OL
-.nr sl +1
-.nr ol 0
-.ie \\n(op=0 .nr op 1
-.el .nr op \\n(op*2
-.nr Lc \\n(lC%2
-.nr lC \\n(lC/2
-.if \\n(Lc=0&\\n(lC>0 .OL
-..
-.de Ft
-.nr tl -1
-.if \\n(#\\n(tl=0 .Ft
-..
//GO.SYSIN DD merge
# To unbundle, sh this file
echo demo 1>&2
sed 's/.//' >demo <<'//GO.SYSIN DD demo'
-.LS
-.LI root "Deus ex Machina"
-.LI daemon "System Daemon"
-.LI bin "System Owner"
-.LI sys "System Source"
-.LI s "System Source"
-.LI backup "Backup Spooler"
-.LI man "Unix Manual"
-.LI adm "System Administration"
-.LI usr "User Administration"
-.LI pascal "Pascal Source"
-.LE
//GO.SYSIN DD demo
echo demo.out 1>&2
sed 's/.//' >demo.out <<'//GO.SYSIN DD demo.out'
-adm --> System Administration
-backup --> Backup Spooler
-bin --> System Owner
-daemon --> System Daemon
-man --> Unix Manual
-pascal --> Pascal Source
-root --> Deus ex Machina
-s --> System Source
-sys --> System Source
-usr --> User Administration
//GO.SYSIN DD demo.out
exit 0