Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!mcsun!ukc!tcdcs!csvax1.cs.tcd.ie!swift.cs.tcd.ie!csaran!emcmanus
From: emcmanus@cs.tcd.ie (Eamonn McManus)
Newsgroups: comp.text
Subject: Re: TeX index program available
Summary: How to do it in TeX, but not really
Keywords: TeX, index, Turing-complete
Message-ID: <1989Dec11.202013.25538@cs.tcd.ie>
Date: 11 Dec 89 20:20:13 GMT
References: <1989Dec8.184444.11467@cs.rochester.edu> <818@qmet.UUCP> <3530@jarthur.Claremont.EDU>
Reply-To: emcmanus@cs.tcd.ie (Eamonn McManus)
Organization: Computer Science Department, Trinity College Dublin
Lines: 31
To:	NEWSMGR@swift.cs.tcd.ie
CC:
Subj:

D.A. Hosek writes:
> Actually, it _is_ possible for TeX to sort an index.

Here is one way to do it, for example.  Let the index entry for word foo
be represented by the macro \csname I!foo\endcsname.  This macro expands
to the following tokens: the macro for the index entry for a word
alphabetically less than the current one; ditto for an alphabetically
greater word; and the index text itself (page numbers or whatever).
Either or both of the two pointers can be null.  Hence we are storing the
index entries in a binary tree, and the usual techniques can be used for
inserting new entries and for traversing the tree in order.  The method
can be expanded to allow for sub-entries etc.

For example, if entries foo:1, bar:2, and spletch:3 have been added we
might have the following macros:
\indexroot -> \I!foo
\I!foo -> \I!bar \I!spletch 1
\I!bar -> \null \null 2
\I!spletch -> \null \null 3

Of course this method is completely impractical, because the macros to
implement it would be very slow and very hard to write, and more
importantly because in any practical TeX implementation you will run out
of memory while indexing a work of any reasonable size.  Other
possibilities exist, such as storing the entries in a file and performing
an external sort on this file; it is just that TeX is not the most
suitable tool for the job.
-- 
Eamonn McManus				emcmanus@cs.tcd.ie
Distributed Systems Group, TCD		...!uunet!mcsun!cs.tcd.ie!emcmanus
   "Kea: A New Zealand parrot that sometimes kills sheep." -- Chambers