12.2.3. Sorting the Entries

Now the output produced by input.idx is ready to be sorted. The easiest way to sort the entries is to use the standard UNIX sort program rather than write a custom script. In addition to sorting the entries, we want to remove any duplicates and for this task we use the uniq program.

Here's the command line we use:

sort -bdf -t: +0 -1 +1 -2 +3 -4 +2n -3n | uniq

As you can see, we use a number of options with the sort command. The first option, -b, specifies that leading spaces be ignored. The -d option specifies a dictionary sort in which symbols and special characters are ignored. -f specifies that lower- and uppercase letters are to be folded together; in other words, they are to be treated as the same character for purposes of the sort. The next argument is perhaps the most important: -t: tells the program to use a colon as a field delimiter for sort keys. The "+" options that follow specify the number of fields to skip from the beginning of the line. Therefore, to specify the first field as the primary sort key, we use "+0." Similarly, the "-" options specify the end of a sort key. "-1" specifies that the primary sort key ends at the first field, or the beginning of the second field. The second sort field is the secondary key. The fourth field ("+3") if it exists, contains the volume number. The last key to sort is the page number; this requires a numeric sort (if we did not tell sort that this key consists of numbers, then the number 1 would be followed by 10, instead of 2). Notice that we sort page numbers after sorting the volume numbers. Thus, all the page numbers for Volume I are sorted in order before the page numbers for Volume II. Finally, we pipe the output to uniq to remove identical entries. Processing the output from input.idx, the sort command produces:

graphics:CANVAS_X_PAINT_WINDOW:86
graphics:XView model:83
graphics:~zz(see also server image):
header file:Xlib.h:89 
macro:XV_INIT_ARGS:46
toolkit:(See X Window System).:
type:Xv_object:49
type:Xv_singlecolor:80
X Window System:events:84
X Window System:X Window ID for paint window:87
Xlib:repainting canvas:88
Xlib.h header file::89 
XView:programs; initialization:45
XV_INIT_ARGS macro::46
Xv_object type::49
Xv_singlecolor type::80

12.2.4. Handling Page Numbers

The pagenums.idx program looks for entries that differ only in page number and creates a list of page numbers for a single entry. The input to this program is four colon-separated fields:

PRIMARY:SECONDARY:PAGE:VOLUME

The fourth is optional. For now, we consider only the index for a single book, in which there are no volume numbers. Remember that the entries are now sorted.

The heart of this program compares the current entry to the previous one and determines what to output. The conditionals that implement the comparison can be extracted and expressed in pseudocode, as follows:

PRIMARY = $1
SECONDARY = $2
PAGE = $3
if (PRIMARY == prevPRIMARY)
	if (SECONDARY == prevSECONDARY)
		print PAGE
	else
		print PRIMARY:SECONDARY:PAGE
else
	print PRIMARY:SECONDARY:PAGE
prevPRIMARY = PRIMARY
prevSECONDARY = SECONDARY

Let's see how this code handles a series of entries, beginning with:

XView::18

The primary key doesn't match the previous primary key; the line is output as is:

XView::18

The next entry is:

XView:about:3

When we compare the primary key of this entry to the previous one, they are the same. When we compare secondary keys, they differ; we output the record as is:

XView:about:3

The next entry is:

XView:about:7

Because both the primary and secondary keys match the keys of the previous entry, we simply output the page number. (The printf function is used instead of print so that there is no automatic newline.) This page number is appended to the previous entry so that it looks like this:

XView:about:3,7

The next entry also matches both keys:

XView:about:10

Again, only the page number is output so that entry now looks like:

XView:about:3,7,10

In this way, three entries that differ only in page number are combined into a single entry.

The full script adds an additional test to see if the volume identifier matches. Here's the full pagenums.idx script:

#!/work/bin/nawk -f
# ------------------------------------------------
# pagenums.idx -- collect pages for common entries 
# Author:  Dale Dougherty
# Version 1.1   7/10/90
# 
# input should be PRIMARY:SECONDARY:PAGE:VOLUME
# ------------------------------------------------

BEGIN { FS = ":"; OFS = ""}

# main routine -- apply to all input lines
{
   # assign fields to variables
	PRIMARY = $1
	SECONDARY = $2
	PAGE = $3
	VOLUME = $4

   # check for a see also and collect it in array
	if (SECONDARY ~ /\([Ss]ee +[Aa]lso/) {
	# create tmp copy & remove "~zz" from copy 
		tmpSecondary = SECONDARY
		sub(/~zz\([Ss]ee +[Aa]lso */, "", tmpSecondary)
		sub(/\) */, "", tmpSecondary)
	# remove secondary key along with "~zz"
		sub(/^.*~zz\([Ss]ee +[Aa]lso */, "", SECONDARY)
		sub(/\) */, "", SECONDARY)
	# assign to next element of seeAlsoList
		seeAlsoList[++eachSeeAlso] = SECONDARY "; "
		prevPrimary = PRIMARY
	# assign copy to previous secondary key
		prevSecondary = tmpSecondary 
		next
	} # end test for see Also

   # Conditionals to compare keys of current record to previous
   #  record.  If Primary and Secondary keys are the same, only
   #  the page number is printed. 

   # test to see if each PRIMARY key matches previous key
	if (PRIMARY == prevPrimary) {

	# test to see if each SECONDARY key matches previous key
		if (SECONDARY == prevSecondary)
		# test to see if VOLUME matches;
		# print only VOLUME:PAGE
			if (VOLUME == prevVolume)
				printf (",%s", PAGE)
			else {
				printf ("; ")
				volpage(VOLUME, PAGE)
			}
		else{
		# if array of See Alsos, output them now
			if (eachSeeAlso) outputSeeAlso(2)
		# print PRIMARY:SECONDARY:VOLUME:PAGE
			printf ("\n%s:%s:", PRIMARY, SECONDARY)
			volpage(VOLUME, PAGE)
		}
	} # end of test for PRIMARY == prev
	else { # PRIMARY != prev
		# if we have an array of See Alsos, output them now
		if (eachSeeAlso) outputSeeAlso(1)
		if (NR != 1) 
			printf ("\n")
		if (NF == 1){
			printf ("%s:", $0)
		}
		else {
			printf ("%s:%s:", PRIMARY, SECONDARY)
			volpage(VOLUME, PAGE)
		}
	}
   	prevPrimary = PRIMARY
	prevSecondary = SECONDARY
	prevVolume = VOLUME

} # end of main routine

# at end, print newline
END { 
   # in case last entry has "see Also"
	if (eachSeeAlso) outputSeeAlso(1)
	printf("\n")
}

# outputSeeAlso function -- list elements of seeAlsoList 
function outputSeeAlso(LEVEL) {
	# LEVEL - indicates which key we need to output
	if (LEVEL == 1)
		printf ("\n%s:(See also ", prevPrimary)
	else {
		sub(/;.*$/, "", prevSecondary)
		printf ("\n%s:%s; (See also ", prevPrimary, prevSecondary)
	}

	sub(/; $/, ".):", seeAlsoList[eachSeeAlso])
	for (i = 1; i <= eachSeeAlso; ++i)
		printf ("%s", seeAlsoList[i]) 
	eachSeeAlso = 0
}

# volpage function -- determine whether or not to print volume info 
# 	two args: volume & page
 
function volpage(v, p)
{
   # if VOLUME is empty then print PAGE only 
	if ( v == "" ) 
		printf ("%s", p)
	else
   # otherwise print VOLUME^PAGE
		printf ("%s^%s",v, p)  
}

Remember, first of all, that the input to the program is sorted by its keys. The page numbers are also in order, such that an entry for "graphics" on page 7 appears in the input before one on page 10. Similarly, entries for Volume I appear in the input before Volume II. Therefore, this program need do no sorting; it simply compares the keys and if they are the same, appends the page number to a list. In this way, the entries are reduced.

This script also handles "see also" entries. Since the records are now sorted, we can remove the special sorting sequence "~zz." We also handle the case where we might encounter consecutive "see also" entries. We don't want to output:

Toolkit (see also Xt) (See also XView) (See also Motif).

Instead we'd like to combine them into a list such that they appear as:

Toolkit (see also Xt; XView; Motif)

To do that, we create an array named seeAlsoList. From SECONDARY, we remove the parentheses, the secondary key if it exists and the "see also" and then assign it to an element of seeAlsoList. We make a copy of SECONDARY with the secondary key and assign it to prevSecondary for making comparisons to the next entry.

The function outputSeeAlso() is called to read all the elements of the array and print them. The function volpage() is also simple and determines whether or not we need to output a volume number. Both of these functions are called from more than one place in the code, so the main reason for defining them as functions is to reduce duplication.

Here's an example of what it produces for a single-book index:

X Window System:Xlib:6
XFontStruct structure::317
Xlib::6
Xlib:repainting canvas:88
Xlib.h header file::89,294
Xv_Font type::310
XView::18
XView:about:3,7,10
XView:as object-oriented system:17

Here's an example of what it produces for a master index:

reserved names:table of:I^43
Xt:example of programming interface:I^44,65
Xt:objects; list of:I^43,58; II^40
Xt:packages:I^43,61; II^42
Xt:programs; initialization:I^45
Xt:reserved names:I^43,58
Xt:reserved prefixes:I^43,58
Xt:types:I^43,54,61

The "^" is used as a temporary delimiter between the volume number and the list of page numbers.

12.2.5. Merging Entries with the Same Keys

The pagenums.idx program reduced entries that were the same except for the page number. Now we'll to process entries that share the same primary key. We also want to look for consecutive page numbers and combine them in ranges.

The combine.idx is quite similar to the pagenums.idx script, making another pass through the index, comparing entries with the same primary key. The following pseudocode abstracts this comparison. (To make this discussion easier, we will omit tertiary keys and show how to compare primary and secondary keys.) After the entries are processed by pagenums.idx, no two entries exist that share the same primary and secondary keys. Therefore, we don't have to compare secondary keys.

PRIMARY = $1
SECONDARY = $2
PAGE = $3
if (PRIMARY == prevPRIMARY)
	print :SECONDARY:
else
	print PRIMARY:SECONDARY
prevPRIMARY = PRIMARY
prevSECONDARY = SECONDARY

If the primary keys match, we output only the secondary key. For instance, if there are three entries:

XView:18
XView:about:3, 7, 10
XView:as object-oriented system:17

they will be output as:

XView:18
:about:3, 7, 10
:as object-oriented system:17

We drop the primary key when it is the same. The actual code is a little more difficult because there are tertiary keys. We have to test primary and secondary keys to see if they are unique or the same, but we don't have to test tertiary keys. (We only need to know that they are there.)

You no doubt noticed that the above pseudocode does not output page numbers. The second role of this script is to examine page numbers and combine a list of consecutive numbers. The page numbers are a comma-separated list that can be loaded into an array, using the split() function.

To see if numbers are consecutive, we loop through the array comparing each element to 1 + the previous element.

eachpage[j-1]+1 == eachpage[j]

In other words, if adding 1 to the previous element produces the current element, then they are consecutive. The previous element becomes the first page number in the range and the current element becomes the last page in the range. This is done within a while loop until the conditional is not true, and the page numbers are not consecutive. Then we output the first page number and the last page number separated by a hyphen:

23-25

The actual code looks more complicated than this because it is called from a function that must recognize volume and page number pairs. It first has to split the volume from the list of page numbers and then it can call the function (rangeOfPages()) to process the list of numbers.

Here is the full listing of combine.idx:

#!/work/bin/nawk -f
# ------------------------------------------------
# combine.idx -- merge keys with same PRIMARY key
#		and combine consecutive page numbers
# Author:  Dale Dougherty
# Version 1.1   7/10/90
# 
# input should be PRIMARY:SECONDARY:PAGELIST
# ------------------------------------------------

BEGIN   { FS = ":"; OFS = ""}

# main routine -- applies to all input lines
#  It compares the keys and merges the duplicates.
{
   # assign first field
	PRIMARY=$1
   # split second field, getting SEC and TERT keys.
	sizeOfArray = split($2, array, ";") 
	SECONDARY = array[1]
	TERTIARY = array[2]
   # test that tertiary key exists
	if (sizeOfArray > 1) {
	# tertiary key exists
		isTertiary = 1 
	# two cases where ";" might turn up
	# check SEC key for list of "see also" 
		if (SECONDARY ~ /\([sS]ee also/){
			SECONDARY = $2
			isTertiary = 0
		}
	# check TERT key for "see also" 
		if (TERTIARY ~ /\([sS]ee also/){
			TERTIARY = substr($2, (index($2, ";") + 1))
		}	
	}
	else # tertiary key does not exist
		isTertiary = 0
   # assign third field
	PAGELIST = $3

   # Conditional to compare primary key of this entry to that
   #  of previous entry. Then compare secondary keys.  This 
   #  determines which non-duplicate keys to output.
	if (PRIMARY == prevPrimary) {
		if (isTertiary && SECONDARY == prevSecondary)
			printf (";\n::%s", TERTIARY)
		else
			if (isTertiary)
				printf ("\n:%s; %s", SECONDARY, TERTIARY)
			else
				printf ("\n:%s", SECONDARY)
	 }
	 else {
		if (NR != 1) 
			printf ("\n")
		if ($2 != "") 
			printf ("%s:%s", PRIMARY, $2)
		else 
			printf ("%s", PRIMARY)

		prevPrimary = PRIMARY
	}

	prevSecondary = SECONDARY
} # end of main procedure

# routine for "See" entries (primary key only)
NF == 1 { printf ("\n") }

# routine for all other entries
#  It handles output of the page number.

NF > 1  {
	if (PAGELIST)
	# calls function numrange() to look for 
 	# consecutive page numbers.
		printf (":%s", numrange(PAGELIST))  
	else
		if (! isTertiary || (TERTIARY && SECONDARY)) printf (":")  

} # end of NF > 1

# END procedure outputs newline
END {  printf ("\n") }

# Supporting Functions

# numrange -- read list of Volume^Page numbers, detach Volume
#		from Page for each Volume and call rangeOfPages 
#		to combine consecutive page numbers in the list. 
#	PAGE = volumes separated by semicolons; volume and page
#		separated by ^.

function numrange(PAGE,     listOfPages, sizeOfArray)
{
  # Split up list by volume.
	sizeOfArray = split(PAGE, howManyVolumes,";") 
  # Check to see if more than 1 volume.
	if (sizeOfArray > 1) {

	# if more than 1 volume, loop through list 
		for (i = 1; i <= sizeOfArray; ++i) {
		# for each Volume^Page element, detach Volume 
		# and call rangeOfPages function on Page to
		# separate page numbers and compare to find
		# consecutive numbers.
			if (split(howManyVolumes[i],volPage,"^") == 2)  
				listOfPages = volPage[1] "^"
				   rangeOfPages(volPage[2])
		# collect output in listOfPages
			if (i == 1) 
				result = listOfPages
			else
				result=result ";" listOfPages
		} # end for loop
	}
	else { # not more than 1 volume

	# check for single volume index with volume number 
	# if so, detach volume number.
	# Both call rangeOfPages on the list of page numbers.
		if (split(PAGE,volPage,"^") == 2 )  
		# if Volume^Page, detach volume and then call rangeOfPages 
			listOfPages = volPage[1] "^" rangeOfPages(volPage[2])
		else # No volume number involved 
			listOfPages = rangeOfPages(volPage[1])
		result = listOfPages
	} # end of else

	return result  # Volume^Page list

} # End of numrange function

# rangeOfPages -- read list of comma-separated page numbers,  
#		load them into an array, and compare each one
#		to the next, looking for consecutive numbers.
#	PAGENUMBERS = comma-separated list of page numbers

function rangeOfPages(PAGENUMBERS, pagesAll, sizeOfArray,pages,
                       listOfPages, d, p, j) {
   # close-up space on troff-generated ranges
	gsub(/ - /, ",-", PAGENUMBERS)

   # split list up into eachpage array.
	sizeOfArray = split(PAGENUMBERS, eachpage, ",")
   # if more than 1 page number
	if (sizeOfArray > 1){
	# for each page number, compare it to previous number + 1
		p = 0  # flag indicates assignment to pagesAll 
	# for loop starts at 2
		for (j = 2; j-1 <= sizeOfArray; ++j) {
		# start by saving first page in sequence (firstpage)    
		# and loop until we find last page (lastpage)
			firstpage = eachpage[j-1]
			d = 0  # flag indicates consecutive numbers found  
		# loop while page numbers are consecutive
			while ((eachpage[j-1]+1) == eachpage[j] ||
					eachpage[j] ~ /^-/) {
			# remove "-" from troff-generated range
				if (eachpage[j] ~ /^-/) {
					sub(/^-/, "", eachpage[j])
				}
				lastpage = eachpage[j]
			# increment counters
				++d
				++j
			} # end of while loop
		# use values of firstpage and lastpage to make range.
			if (d >= 1) {
			# there is a range
				pages = firstpage "-" lastpage 
			}
			else # no range; only read firstpage 
				pages = firstpage 
		# assign range to pagesAll 
			if (p == 0) {
				pagesAll = pages 
				p = 1
			}
			else {
				pagesAll = pagesAll "," pages
			}
		}# end of for loop

	# assign pagesAll to listOfPages
		listOfPages = pagesAll

	} # end of sizeOfArray > 1

	else # only one page 
		listOfPages = PAGENUMBERS

   # add space following comma
	gsub(/,/, ", ", listOfPages)
   # return changed list of page numbers
	return listOfPages
} # End of rangeOfPages function

This script consists of minimal BEGIN and END procedures. The main routine does the work of comparing primary and secondary keys. The first part of this routine assigns the fields to variables. The second field contains the secondary and tertiary keys and we use split() to separate them. Then we test that there is a tertiary key and set the flag isTertiary to either 1 or 0.

The next part of the main procedure contains the conditional expressions that look for identical keys. As we said in our discussion of the pseudocode for this part of the program, entries with wholly identical keys have already been removed by the pagenums.idx.

The conditionals in this procedure determine what keys to output based on whether or not each is unique. If the primary key is unique, it is output, along with the rest of the entry. If the primary key matches the previous key, we compare secondary keys. If the secondary key is unique, then it is output, along with the rest of the entry. If the primary key matches the previous primary key, and the secondary key matches the previous secondary key, then the tertiary key must be unique. Then we only output the tertiary key, leaving the primary and secondary keys blank.

The different forms are shown below:

 primary

 primary:secondary

 :secondary

 :secondary:tertiary

 ::tertiary

 primary:secondary:tertiary

The main procedure is followed by two additional routines. The first of them is executed only when NF equals one. It deals with the first of the forms on the list above. That is, there is no page number so we must output a newline to finish the entry.

The second procedure deals with all entries that have page numbers. This is the procedure where we call a function to take apart the list of page numbers and look for consecutive pages. It calls the numrange() function, whose main purpose is to deal with a multivolume index where a list of page numbers might look like:

I^35,55; II^200

This function calls split() using a semicolon delimiter to separate each volume. Then we call split() using a "^" delimiter to detach the volume number from the list of page numbers. Once we have the list of pages, we call a second function rangeOfPages() to look for consecutive numbers. On a single-book index, such as the sample shown in this chapter, the numrange() function really does nothing but call rangeOfPages(). We discussed the meat of the rangeOfPages() function earlier. The eachpage array is created and a while loop is used to go through the array comparing an element to the one previous. This function returns the list of pages.

Sample output from this program follows:

Xlib:6
:repainting canvas:88
Xlib.h header file:89, 294
Xv_Font type:310
XView:18
:about:3, 7, 10
:as object-oriented system:17
:compiling programs:41
:concept of windows differs from X:25
:data types;  table of:20
:example of programming interface:44
:frames and subframes:26
:generic functions:21
:Generic Object:18, 24
:libraries:42
:notification:10, 35
:objects:23-24;
:: table of:20;
:: list of:43
:packages:18, 43
:programmer's model:17-23
:programming interface:41
:programs;  initialization:45
:reserved names:43
:reserved prefixes:43
:structure of applications:41
:subwindows:28
:types:43
:window objects:25

In particular, notice the entry for "objects" under "XView." This is an example of a secondary key with multiple tertiary keys. It is also an example of an entry with a consecutive page range.