#!/usr/local/bin/gawk -f
# @(#) proctree.gawk 1.4.1 97/07/19
# 96/05/29 john h. dubois iii
# 96/08/27 Make field list case insensitive
# 96/12/01 Print tree in a nice format.  Changed -w to -C; added new -was.
# 97/04/15 Let command names be given as args, not just with -n
# 97/07/16 1.4 Added AOp options.  Made "both" be default; removed b option.
# 97/07/19 1.4.1 Added header & HI options.

BEGIN {
    SUBSEP = ","	# To make debugging printout clearer
    Name = "proctree"
    Usage = "Usage: " Name \
" [-hHrsacpN] [-w<width>] [-i<indent>] [-C<columns>] [-t<tty,...>]\n"\
"       [-n<pattern>] [-u<user,...>] [-P<ps-field,...>] [-I<max-equ-indent>]\n"\
"       [-A<ancestor-distance>] [-O<offspring-distance>] [process-ID|name ...]"
    rcFile = ".proctree"
    ARGC = Opts(Name,Usage,"i>C<P:u:t:n:cpw>saA<O<I#Hhx>",0,
    "~/" rcFile ":$HOME/" rcFile,
    "INDENT,COLUMNS,FIELDS,USERS,TTYS,NAMES,CHILDREN,PARENTS,WIDTH,SPACES,"\
    "ASCII,ANCESTORS,OFFSPRING,MAXEQUINDENT,NOHEADER",0,"N",0,"","I,w")
    nIndent = 2		# Default indent is 2 spaces
    
    # Put UID first because unlike PID it is left-adjusted, so the indenting
    # is consistent.
    FieldList = "UID,PID,TTY,ARGS"
    if ("h" in Options) {
	printf \
"%s: Print a process tree.\n"\
"%s\n"\
"%s prints a tree of processes executing on the system, arranged according\n"\
"to parent-child relationships.  Each process is printed, followed by an\n"\
"indented list of its children, then a further indented list of that\n"\
"process' children, etc.  If any process IDs are given, only those\n"\
"processes and their ancestors and children are displayed.  Any argument that is not a\n"\
"non-negative integer is taken to be a process name and is merged with any\n"\
"pattern given with -n.  If both names and PIDs are given, a process must\n"\
"satisfy both types of selectors in order to be printed.\n"\
"Options:\n"\
"Some of the following options can also be set by assigning values to\n"\
"variables in a configuration file named %s, which is searched for in the\n"\
"invoking user's home directory and in the directory specified by the\n"\
"environment variable UHOME, if it is set (if both files exist, values set\n"\
"in the former take precedence).  Variables are assigned to with the\n"\
"syntax:  varname=value  or in the case of flags, by simply putting the\n"\
"indicated variable name in the file without a value.  Variable names are\n"\
"given in parentheses in the option descriptions.\n"\
"-h: Print this help.\n"\
"-P<ps-field,...>: For each process, print the given fields.  The possible\n"\
"    fields are: UID (user ID), PPID (parent process ID), C (CPU scheduling\n"\
"    value), STIME (start time), TTY (TTY nam), TIME (CPU time used), CMD\n"\
"    (first element of arg vector), CMDT (like CMD, but only the final\n"\
"    pathname component), ARGS (command + arguments), and COMM (name of\n"\
"    command being executed).  The default is: %s\n"\
"    (FIELDS)\n"\
"-N: Do not read the configuration file.\n"\
"The following options control the manner in which the tree is drawn:\n"\
"-i<indent>: The number of character positions to indent when showing the\n"\
"    children of a process.  The minimum is 1.  The default is %d.  (INDENT)\n"\
"-I<max-equ-indent>: Attempt to equalize the total indentation of each line\n"\
"    so that the ps columns are aligned. <max-equ-indent> is the maximum\n"\
"    number of indent positions to equalize to.  If -1 is given, all lines\n"\
"    will be indented to the same distance that the furthest indented line\n"\
"    is.  Otherwise, if the deepest indent is less than or equal to the\n"\
"    value given, the number of indents used will be the same as the\n"\
"    deepest indent.  If the deepest indent is larger than the value given,\n"\
"    those lines indented further will not line up.  (MAXEQUINDENT)\n"\
"-H: Do not print a header listing the names of the ps fields (NOHEADER)\n"\
"-C<columns>: The screen width to use.  Output is truncated to <columns>\n"\
"    columns.  The default is to use one fewer than the width of the user's\n"\
"    terminal. If -C0 is given, the output is not truncated.  (COLUMNS)\n"\
"-w<width>: The tree is drawn in an alternate format, with one of the\n"\
"    children of each process printed on the same line to save space\n"\
"    (reduce the number of lines printed).  The data to be printed for any\n"\
"    process that has children to be printed is truncated or padded to\n"\
"    <width> characters.  <width> must be at least 2.  (WIDTH)\n"\
"-a: Normally, the tree is drawn using box-drawing character appropriate to\n"\
"    the type of terminal the program is invoked from.  If the terminal\n"\
"    does not have box-drawing characters available or -a is given, the\n"\
"    tree is drawn using ASCII characters.  (ASCII)\n"\
"-s: Draw the tree using nothing but spaces for indentation.  (SPACES)\n"\
"The following options restrict the processes that are displayed to the\n"\
"processes they select and their ancestors and children:\n"\
"-u<user,...>: Select processed owned by any of the users in the\n"\
"    comma-separated list.  (USERS)\n"\
"-t<tty,...>: Select processed whose controlling TTY is one of those in\n"\
"    the comma-separated list.  (TTYS)\n"\
"-n<pattern>: Select processes whose name (basename of argv[0]) matches the\n"\
"    egrep(C)-style pattern <pattern>, which is implicitely anchored at the\n"\
"    start and end.  If COMM is given with -P, the executable name (trailing\n"\
"    pathname component of the file being executed) is used instead. (NAMES)\n"\
"The following options limit which processes among the ancestors and\n"\
"children of processes selected by process ID or the -u, -t, and -n options\n"\
"should be displayed (by default, all children and ancestors are displayed):\n"\
"-A<ancestor-distance>: Instead of displaying all ancestors of processes,\n"\
"    display only those that are within <ancestor-distance> generations of a\n"\
"    selected process.  Example: -A2 displays only selected processes, their\n"\
"    parents, and their grandparents (and if -p has not been given, their\n"\
"    children).  (ANCESTORS)\n"\
"-O<offspring-distance>: Like -A, but controls how many generations of\n"\
"    offspring are displayed.  (OFFSPRING)\n"\
"-c: Equivalent to -A0; print only the selected processes and their\n"\
"    children.  (CHILDREN)\n"\
"-p: Equivalent to -O0; print only the selected processes and their\n"\
"    parents.  (PARENTS)\n"\
"-cp causes only explicitly selected processes to be displayed.\n",
	Name,Usage,Name,rcFile,nIndent,FieldList
	exit 0
    }
## Option/argument processing
    if ("x" in Options)
	Debug = Options["x"]

    if ("A" in Options)	# Number of ancestors to print
	Ancestors = Options["A"]
    else
	Ancestors = -1
    if ("O" in Options)	# Number of generations of offspring to print
	Offspring = Options["O"]
    else
	Offspring = -1
    if ("c" in Options)
	Ancestors = 0
    if ("p" in Options)
	Offspring = 0

    if ("P" in Options)
	FieldList = toupper(Options["P"])
    MakeSet(GetFields,FieldList,",")
    GetFields["PPID"]	# always need this
    delete GetFields["PID"]

    if (SelectUsers = ("u" in Options)) {
	n = MakeSet(Users,Options["u"],",")
	if (Debug)
	    printf "%d users in user list.\n",n > "/dev/stderr"
	GetFields["UID"]
    }
    if (SelectTTYs = ("t" in Options)) {
	MakeSet(TTYs0,Options["t"],",")
	for (tty in TTYs0)
	    TTYs[canonTTY(tty)]
	GetFields["TTY"]
    }
    if (SelectNames = ("n" in Options))
	NamePat = Options["n"]

    if (ARGC > 1) {
	if (Debug)
	    printf "Got %d PID(s)/name(s)\n",ARGC-1 > "/dev/stderr"
	for (i = 1; i < ARGC; i++) {
	    arg = ARGV[i]
	    if (arg ~ /^[0-9]+$/) {
		SelectPIDs = 1
		givenPIDs[arg]
	    }
	    else if (SelectNames)
		NamePat = NamePat "|" arg
	    else {
		NamePat = arg
		SelectNames = 1
	    }
	}
    }
    if (SelectNames) {
	NamePat = "^(" NamePat ")$"
	# CMD is incompatible with COMM, so only get it if COMM not requested
	cmdField = ("COMM" in GetFields) ? "COMM" : "CMD"
	GetFields[cmdField]
    }

## Gather ps data
    if ((e = getPS(PIDs,Procs,set2list(GetFields,","),Children,Debug > 5)) < 0)
    {
	print (e == -2) ? "Bad field name given." : "ps failed." > "/dev/stderr"
	exit 1
    }
    delete PIDs["ps"]
## Process data
    # Make PIDs[] be a process -> process-parent map,
    # and deal with children with no parent found
    for (pid in PIDs) {
	PIDs[pid] = parent = Procs[pid,"PPID"]
	if (Debug > 2)
	    printf "Parent of %d is %d\n",pid,parent > "/dev/stderr"
	if (!(parent in PIDs)) {
	    # if parent is not in PIDs, assume it is due to ps snapshot failure
	    # and make the process be a child of init
	    PIDs[pid] = 1
	    Children[1] = Children[1] "," pid
	}
    }
    # If not all processes are to be displayed, mark those that should be.
    if (SelectUsers || SelectTTYs || SelectNames || SelectPIDs) {
	if (Debug)
	    print "Marking selected processes..." > "/dev/stderr"
	for (pid in PIDs)
	    # If a process is selected...
	    if ( (!SelectUsers || Procs[pid,"UID"] in Users) &&
	    (!SelectTTYs || canonTTY(Procs[pid,"TTY"]) in TTYs) &&
	    (!SelectNames || basename(Procs[pid,cmdField]) ~ NamePat) &&
	    (!SelectPIDs || pid in givenPIDs) ) {
		SelectedPIDs[pid]
		if (Debug > 1)
		    printf " +%d",pid > "/dev/stderr"
	    }
	if (Ancestors)
	    markParents(SelectedPIDs,DisplayPPIDs,PIDs,Ancestors)
	# Mark decendants of selected PIDs in DisplayCPIDs[]
	if (Offspring)
	    for (pid in SelectedPIDs)
		doChildren(pid,DisplayCPIDs,Children,Offspring)
	# Children & parents have been marked in separate arrays, so that
	# marking processes in one direction doesn't prevent marking in the
	# other when there is a common intermediate process.  Now merge marked
	# processes with explicitly selected processes.
	Union(DisplayCPIDs,DisplayPPIDs,SelectedPIDs)
    }
    else {
	# Mark all processes.
	SelectedPIDs[1]
	doChildren(1,SelectedPIDs,Children,-1)
    }
    if (Debug > 1)
	print "" > "/dev/stderr"

    split(FieldList,Fields,",")
    preOrderTraverse(1,Children,1,"",0)

    if ("C" in Options) {
	Cols = Options["C"]
	HeadTailInit(-1,Cols ? Cols : -1,0,0)
    }
    else
	HeadTailInit(-1)
    if ("i" in Options)
	nIndent = Options["i"]
    if ("I" in Options)
	equIndent = Options["I"]
    if (!("H" in Options))
	treeData["HEADER"] = makePSline(-1,Procs,Fields)
    if (Debug)
	print "" > "/dev/stderr"
    if ("a" in Options)
	delete ENVIRON["TERM"]
    DrawTrees(treeData,nIndent,("w" in Options) ? Options["w"] : 0,emptyArr,
    "s" in Options,term,1,COLUMNS ? (COLUMNS-1) : 0,0,0,equIndent)
    if (Debug)
	print "" > "/dev/stderr"
}

# Globals: Debug
function markParents(SelectedPIDs,DisplayPPIDs,Parents,Ancestors,
pid,numAnc,p,p2) {
    for (pid in SelectedPIDs) {
	# Mark every proc up the chain as good by storing its pid
	# in DisplayPPIDs[], until we hit init or an already-marked
	# proc.
	numAnc = 0
	for (p = pid; p >= 1; p = Parents[p]) {
	    # If only marking ancestors for a limited distance up
	    # chain, must continue up chain even if this process
	    # is marked already because it may be marked due to
	    # one of its decendants, in which case the chain won't
	    # already be marked far enough.
	    if ((p in DisplayPPIDs) && (Ancestors == -1) ||
	    (Ancestors != -1) && (numAnc > Ancestors))
		break
	    numAnc++
	    if (Debug > 1 && numAnc > Ancestors)
		printf "\nHit ancestor limit\n" > "/dev/stderr"
	    DisplayPPIDs[p]
	    if (!(p in Parents)) {
		printf "No parent for process %s?\n",
		p > "/dev/stderr"
		for (p2 = pid; p2 != p; p2 = Parents[p2])
		    printf "%d <- ",p2 > "/dev/stderr"
		printf p > "/dev/stderr"
		break
	    }
	}
    }
}

# Mark decendants of pid in DisplayCPIDs[]
# Globals: DisplayCPIDs[], Children[]
function doChildren(pid,DisplayCPIDs,Children,numChildren,  Elem,child) {
    if (pid in Children) {	# If this process has children, mark them
	if (numChildren != -1)
	    numChildren -= 1
	MakeSet(Elem,Children[pid],",")
	for (child in Elem)
	    # If not marked yet...
	    if (!(child in DisplayCPIDs)) {
		DisplayCPIDs[child]
		if (numChildren) {
		    if (Debug)
			printf " c%d",child > "/dev/stderr"
		    doChildren(child,DisplayCPIDs,Children,numChildren)
		}
	    }
    }
}

# preOrderVisit: Build a tree data structure for use by DrawTrees().
# We will be visited in pre-order.
# Our mission: to identify marked subtrees within the process tree as a whole,
# and make a DrawTrees() style tree out of each one.
# This is done by completely processing each tree when its topmost node is
# found, and marking each processed node so that it will not be further
# processed when preOrderTraverse() calls us with the tree's subnodes.
# Input variables:
# Node:   PID to be checked for whether it is the top of a marked tree OR
#         PID to be checked for whether it is part of a marked tree (depending
#         on the value of Data).
# Index:  Index to store this process' data under in treeData[].
# Data is true if we are processing marked tree subnodes, false if we are
# searching for the top of a marked tree.
# Globals:
# ProcessedNodes[]: Maintained as the set of processed nodes.
# TopIndex is maintained as the number of the current tree being built.
# Procs[], Fields[]: For use in building a ps output line.
# treeData[]: DrawTrees()-style data structure to build.
# Children[]: Children of each process.
# Debug: If Debug is > 1, debugging info will be printed.
# Return value:
# True if the children of this node should be processed.
function preOrderVisit(NodeID,Node,Ind,Data,  ret,psLine) {
    if (Data) {	# Processing a marked node's subnodes
	ProcessedNodes[Node]
	if (ret = (Node in SelectedPIDs)) {
	    if (Debug > 1) 
		printf "Visiting marked node %d; index: %s\n",
		NodeID,Ind > "/dev/stderr"
	    psLine = makePSline(Node,Procs,Fields)
	    gsub("^[ \t]+|[ \t]+$","",psLine)	# discard leading/trailing ws
	    treeData[Ind] = psLine
	}
    }
    else {
	if ((Node in SelectedPIDs) && !(Node in ProcessedNodes)) {
	    # Start a new tree
	    if (Debug > 1) 
		printf "Starting new tree rooted at PID %d\n",
		Node > "/dev/stderr"
	    preOrderTraverse(Node,Children,1,++TopIndex,1)
	}
	ret = 1
    }
    return ret
}

### Begin ps lib
# getPS 1.1	
# 96/10/09	john h. dubois iii (john@armory.com)
# 96/02/11	Added Debug flag.
# 96/05/09	Added COMM field.
# 96/05/23	Added selection args, and saving of "ps" PID.
# 96/05/25	Added makePSline()
# 96/10/09	Added RUSER field.
# 96/12/14	Added CMDT field.

# Note: makePSline() needs assign() from array lib.
# to do: generalize based on -o args to 5.0 ps

# Do a ps -f and save the output into an array, indexed by pid and field name.
# Input vars:
# Fields: Comma-separated list of fields to put in Procs.
# If Debug is true, debugging info is output.
# selectionArgs may be set to ps options that will report on selected processes
# (e.g. -usomeone -ttty01)
# The default for selectionArgs is -e, which causes information on all
# processes to be recorded.
#
# Output vars:
# PIDs[]: the set of all PIDs seen.
# Also, the element with index "ps" is set to the PID for the ps process.
# Procs[pid,fieldname]: output by field.
#
# Possible fields are:
# UID: User ID; name if available, else number.
# RUSER: Real user ID; name if available, else number.  Only available under
#       5.0, and cannot be requested along with UID.
# PPID: Parent process ID.
# C: CPU scheduling.
# STIME: Start time.  If the start time in the ps output contains a space,
# it is replaced with a "-".  "-" is returned for a defunct process.
# TTY: tty name; may or may not have leading "tty" part.  "-" for defunct proc;
# "?" for proc with no controlling tty.
# TIME: CPU time used.
# CMD: First element of arg vector.
# CMDT: Like CMD, but just the tail (leading path components removed), unless
#       the path ends with /, in which case it is identical to CMD.
# ARGS: Entire (truncated) arg vector (command + args).
# LINE: Entire ps output line.
# COMM: Process accounting name of process: the name of the executable file,
#       without path.  This is only available under 5.0, and cannot be
#       requested along with CMD/CMDT or ARGS.
#
# The header line read is also put in Procs with the index "Header".
# The PIDs of the children of each process are put in a comma-separated list
# in Children[pid].
# Return value: the number of processes found, or -2 if an invalid field name
# is passed, or -1 if an error occurs reading from ps.
# Globals: FS is set to " "
#
# ps -f produces output in these forms, under various conditions & releases:
#     UID   PID  PPID  C    STIME     TTY        TIME CMD
#    root 10118 10107  2   Jan-03   ttyp0    00:00:05 -ksh
#    root 10118 10107  2   Jan 03   ttyp0    00:00:05 -ksh
#    root 18197     1  0 08:02:56   ttyp0    00:00:03 /usr/bin/X11/scoterm -geo
function getPS(PIDs,Procs,Fields,Children,Debug,selectionArgs,
stimeI,pidI,ttyI,ppidI,WantLine,psArgs,psSet,newPS,
FieldNames,Wanted,Cmd,getI,Field2Ind,i,Name,Lines,WantArgs,Header,CmdIndex,fn,
wantCmdt) {
    FS = " "	# magic pattern to reset FS to its default special behaviour
    split("UID,PID,PPID,C,STIME,TTY,TIME,CMD",FieldNames,",")
    # psSet[] maps field number to field name
    split("user,pid,ppid,c,stime,tty,time,args",psSet,",")
    # Alt[] maps new ps field names to field numbers
    Alt["RUSER"] = 1
    Alt["COMM"] = 8
    FieldNames[0] = "LINE"
    for (i in FieldNames)	# Field2Ind[] maps field names to field numbers
	Field2Ind[FieldNames[i]] = i
    split(Fields,Wanted,",")
    pidI = Field2Ind["PID"]
    ppidI = Field2Ind["PPID"]
    stimeI = Field2Ind["STIME"]
    ttyI = Field2Ind["TTY"]
    timeI = Field2Ind["TIME"]
    cmdI = Field2Ind["CMD"]
    psArgs = "-f"
    for (i in Wanted) {
	Name = Wanted[i]
	if (Debug)
	    printf "Asked for %s\n",Name > "/dev/stderr"
	# getI[] is made to contain the indices of fields to record
	if (Name == "ARGS")
	    WantArgs = 1
	else if (Name == "LINE")
	    WantLine = 1
	else if (Name == "CMDT")
	    wantCmdt = 1
	else if (Name in Alt) {		# New ps fields
	    newPS = 1
	    # Change the name of this field to that of the alternate requested
	    psSet[Alt[Name]] = tolower(Name)
	    fn = Field2Ind[Name] = Alt[Name] # Map this name to its field number
	    getI[fn]
	    FieldNames[fn] = Name
	}
	else if (Name in Field2Ind)
	    getI[Field2Ind[Name]]
	else
	    return -2
    }
    if (newPS) {
	psArgs = ""
	for (i = 1; i in psSet; i++)
	psArgs = psArgs " -o" psSet[i]
    }
    Lines = 0
    if (selectionArgs == "")
	selectionArgs = "-e"
    Cmd = "echo $$; exec /bin/ps " selectionArgs " " psArgs " < /dev/null"
    if ((Cmd | getline PIDs["ps"]) != 1)
	return -1
    if ((Cmd | getline Header) != 1)
	return -1
    Procs["Header"] = Header
    if (!(CmdIndex = index(Header,"CMD")) &&
    !(CmdIndex = index(Header,"COMMAND")))
	return -1
    while ((Cmd | getline) == 1) {
	PIDs[pid = $pidI]
	if (Debug)
	    printf "Process %d (%d fields): %s\n",pid,NF,$0 > "/dev/stderr"
	ppid = $ppidI
	if (ppid in Children)
	    Children[ppid] = Children[ppid] "," pid
	else
	    Children[ppid] = pid
	if (WantArgs)
	    Procs[pid,"ARGS"] = substr($0,CmdIndex)
	# Handle this as a special case so that it can be set before the
	# line is (possibly) modified
	if (WantLine)
	    Procs[pid,"LINE"] = $0
	# Time field with either contain a : (time), a - (new date format),
	# or neither, in which case it occupies 2 fields (old date format).
	if (NF == 6) {	# old ps defunct proc
	    # Assign new values to fields, from right to left to avoid
	    # overwriting fields before value is moved
	    $cmdI = $ttyI
	    $timeI = $stimeI
	    $ttyI = "-"
	    $stimeI = "-"
	}
	if ($stimeI !~ "[-:]") {
	    if (!timePos)
		timePos = index($0,$stimeI)
	    # Replace space in stime field with "-"
	    $0 = substr($0,1,timePos+2) "-" substr($0,timePos+5)
	}
	if (wantCmdt) {
	    Procs[pid,"CMDT"] = $cmdI
	    if ($cmdI !~ "/$")
		sub(".*/","",Procs[pid,"CMDT"])
	}
	for (i in getI) {
	    Procs[pid,FieldNames[i]] = $i
	    if (Debug)
		printf "%s=%s ",FieldNames[i],$i > "/dev/stderr"
	}
	if (Debug)
	    print "" > "/dev/stderr"
	Lines++
    }
    close(Cmd)
    return Lines
}

# makePSline: generate a line containing desired fields from ps data.
# pid is the ID of the process to generate a line for.
# If a pid of -1 is passed, a header line is returned.
# Procs[] is the ps data, as generated by getPS().
# Fields[] is the set of fields desired in the output, with indexes starting
#    at 1.  The values are field names as e.g. passed to getPS().
# Sep is the separator to put between fields.  If null, a single space is used.
# Return value: a line consisting of the fields requested, in the order of
# their indices in Fields[].
# Example:
# split("UID,PID,PPID,C,STIME,TTY,TIME,CMD",FieldNames,",")
# makePSline(pid,psOut,FieldNames)
function makePSline(pid,Procs,Fields,Sep,  i,fieldName,line,width,value) {
    if (Sep == "")
	Sep = " "
    if (!("PID" in _makePSlineWidths))
	# Make TIME before right-adjusted; some versions of ps drop leading
	# 0 fields from it.
	Assign(_makePSlineWidths,
	"UID=-8 PID=5 PPID=5 C=1 STIME=-8 TTY=-4 TIME=8 COMM=-8"," ","=")
    for (i = 1; i in Fields; i++) {
	fieldName = Fields[i]
	if (fieldName in _makePSlineWidths)
	    width = _makePSlineWidths[fieldName]
	else
	    width = ""
	if (pid == -1)
	    value = fieldName
	else if (fieldName == "PID")
	    value = pid
	else
	    value = Procs[pid,fieldName]
	if (fieldName == "TTY")
	    sub("^tty","",value)
	line = line Sep sprintf("%" width "s",value)
    }
    return substr(line,length(Sep)+1)
}

### End ps lib
### Begin array routines

# InitArr: Initialize an array with values.
# Ind and Vals are separated into lists on Sep.
# For each item in Ind, an index with that name is created in Arr[],
# and the value with the same position in Vals is stored in it.
# Global variables: none.
function InitArr(Arr,Ind,Vals,sep,  numind,indnames,values) {
    split(Ind,indnames,sep)
    split(Vals,values,sep)
    for (numind in indnames)
	Arr[indnames[numind]] = values[numind]
}

function ClearArr(Arr,  Elem) {
    for (Elem in Arr)
	delete Arr[Elem]
}
# Subtract the values in Subtrahend from those in Minuend
function SubtractArr(Minuend,Subtrahend,  Elem) {
    for (Elem in Subtrahend)
	Minuend[Elem] -= Subtrahend[Elem]
}
# For each element of the array In, an element is created in Out having
# an index equal to the value of the element in In and a value equal to 
# the index of the element in In.
function Invert(In,Out,  Index) {
    for (Index in In)
	Out[In[Index]] = Index
}

# Assign: make an array from a list of assignments.
# An index with the name of each variable in the list is created in the array.
# Its value is set to the value given for it.
# Input variables: 
# Elements is a string containing the list of variable-value pairs.
# Sep is the string that separates the pairs in the list.
# AssignOp is the string that separates variables from values.
# Output variables:
# Arr is the array.
# Return value: the number of elements added to the set.
# Example:
# Assign(Arr,"foo=blot bar=blat baz=blit"," ","=")
function Assign(Arr,Elements,Sep,AssignOp,
Num,Names,Elem,Assignments,Assignment,i) {
    Num = split(Elements,Assignments,Sep)
    for (i = 1; i <= Num; i++) {
	Assignment = Assignments[i]
	Ind = index(Assignment,AssignOp)
	Arr[substr(Assignment,1,Ind - 1)] = substr(Assignment,Ind + 1)
    }
    return Num
}

### End array routines
### Begin head-tail routines

# @(#) HeadTail.awk 96/05/09
# 95/04/28 Added tail routines.
# 96/05/09 Added all args to HeadTailInit()

# Turn on screen-bounded printing.
# Current implementation sets global vars LINES, COLUMNS, LINEGAP, and COLGAP.
# Sets the number of screen lines and rows to Lines and Rows.
# If -1 is passed for either, turns off bounding in that dimension.
# If either is not set or 0 is passed for it, its value is taken from the
# environment, or if not set there, from terminfo, or if not set there, from
# the defaults (24 and 80).
# By default, the other functions in this library leave a "grace space" of
# 1 column and 1 line.  If LineGap or ColGap is passed and is a non-negative
# value, the line gap is set to it.
function HeadTailInit(Lines,Cols,LineGap,ColGap,  Cmd) {
    # tput will use values in environment, but we want to avoid running
    # it if possible.
    if (Cols > 0)
	COLUMNS = Cols
    else if (!Cols)
	if ("COLUMNS" in ENVIRON)
	    COLUMNS = ENVIRON["COLUMNS"]
	else {
	    Cmd = "exec tput cols"
	    Cmd | getline COLUMNS
	    close(Cmd)
	    if (COLUMNS == "")
		COLUMNS = 80
	}
    if (Lines > 0)
	LINES = Lines
    else if (!Lines)
	if ("LINES" in ENVIRON)
	    LINES = ENVIRON["LINES"]
	else {
	    Cmd = "exec tput lines"
	    Cmd | getline LINES
	    close(Cmd)
	    if (LINES == "")
		LINES = 24
	}
    LINEGAP = (LineGap != "" && LineGap >= 0) ? LineGap : 1
    COLGAP = (ColGap != "" && ColGap >= 0) ? ColGap : 1
}

# Do screen-bound printing.  
# If LINES  is >0, the last LINES-LINEGAP lines are kept in a circular buffer.  
# When TailFlush() is called, they are printed.
# If LINES = 0, all lines are printed immediately.
# If COLUMNS is >0, truncates Line to COLUMNS-COLGAP characters before printing
# it.
# Global vars: uses LINES & COLUMNS; sets/uses TailPtr;
# saves lines in TailLines[] from 1..LINES-LINEGAP
# Embedded newlines split the line into multiple lines; trailing newlines are
# stripped.  Tabs are expanded to spaces.
function TailPrint(Line) {
    if (!LINES)
	print Line
    else {
	if (++TailPtr > (LINES-LINEGAP))
	    TailPtr = 1
	TailLines[TailPtr] = Line
    }
}

function TailFlush(  NumPrinted,Lines,Line,i,Buffer,PrintLines) {
    if (!LINES)
	return
    NumPrinted = 0
    PrintLines = LINES-LINEGAP
    # Since lines may contain multiple lines, we must create a buffer to be
    # printed by reading line buffer backwards.
    # Stop when we have copied enough lines, or if we wrap around to the end
    # and find that the entire line buffer was not used.
    while (NumPrinted < PrintLines && TailPtr in TailLines) {
	# Split line into individual lines, then process them last to first
	Num = split(TailLines[TailPtr],Lines,"\n")
	for (i = Num; i >= 1; i--) {
	    Line = Lines[i]
	    if (i == Num && Line == "")	# discard trailing newline
		continue
	    # Put this line at the front of the print buffer
	    if (COLUMNS)
		Buffer = substr(TabEx(Line),1,COLUMNS - COLGAP) "\n" Buffer
	    else
		Buffer = Line "\n" Buffer
	    if (++NumPrinted == PrintLines)
		break
	}
	if (!--TailPtr)	# Wrap pointer if neccessary
	    TailPtr = PrintLines
    }
    printf "%s",Buffer
}

# Do screen-bound printing.  
# If LINES >0, returns 0 when LINES-LINEGAP lines have been printed by
# HeadPrint().  Otherwise returns 1.
# If COLUMNS is >0, truncates Line to COLUMNS-COLGAP characters before printing
# it.
# Global vars: uses LINES, COLUMNS, LINEGAP, COLGAP; sets/uses LinesPrinted.
# Line should not include newlines.
function HeadPrint(Line) {
    # Check first, in case some calls of this function to not check return
    # value, and in case LINES is 1.
    if (LINES && LinesPrinted >= (LINES-LINEGAP))
	return 0
    if (COLUMNS)
	print substr(Line,1,COLUMNS - COLGAP)
    else
	print Line
    if (LINES && ++LinesPrinted >= (LINES-LINEGAP))
	return 0
    return 1
}

function ColPrint(Line) {
    if (COLUMNS)
	print substr(Line,1,COLUMNS - COLGAP)
    else
	print Line
    return 1
}

### End head-tail routines
### Start of ProcArgs library
# @(#) ProcArgs 1.11 96/12/08
# 92/02/29 john h. dubois iii (john@armory.com)
# 93/07/18 Added "#" arg type
# 93/09/26 Do not count -h against MinArgs
# 94/01/01 Stop scanning at first non-option arg.  Added ">" option type.
#          Removed meaning of "+" or "-" by itself.
# 94/03/08 Added & option and *()< option types.
# 94/04/02 Added NoRCopt to Opts()
# 94/06/11 Mark numeric variables as such.
# 94/07/08 Opts(): Do not require any args if h option is given.
# 95/01/22 Record options given more than once.  Record option num in argv.
# 95/06/08 Added ExclusiveOptions().
# 96/01/20 Let rcfiles be a colon-separated list of filenames.
#          Expand $VARNAME at the start of its filenames.
#          Let varname=0 and -option- turn off an option.
# 96/05/05 Changed meaning of 7th arg to Opts; now can specify exactly how many
#          of the vars should be searched for in the environment.
#          Check for duplicate rcfiles.
# 96/05/13 Return more specific error values.  Note: ProcArgs() and InitOpts()
#          now return various negatives values on error, not just -1, and
#          Opts() may set Err to various positive values, not just 1.
#          Added AllowUnrecOpt.
# 96/05/23 Check type given for & option
# 96/06/15 Re-port to awk
# 96/10/01 Moved file-reading code into ReadConfFile(), so that it can be
#          used by other functions.
# 96/10/15 Added OptChars
# 96/11/01 Added exOpts arg to Opts()
# 96/11/16 Added ; type
# 96/12/08 Added Opt2Set() & Opt2Sets()
# 96/12/27 Added CmdLineOpt()

# optlist is a string which contains all of the possible command line options.
# A character followed by certain characters indicates that the option takes
# an argument, with type as follows:
# :	String argument
# ;	Non-empty string argument
# *	Floating point argument
# (	Non-negative floating point argument
# )	Positive floating point argument
# #	Integer argument
# <	Non-negative integer argument
# >	Positive integer argument
# The only difference the type of argument makes is in the runtime argument
# error checking that is done.

# The & option is a special case used to get numeric options without the
# user having to give an option character.  It is shorthand for [-+.0-9].
# If & is included in optlist and an option string that begins with one of
# these characters is seen, the value given to "&" will include the first
# char of the option.  & must be followed by a type character other than ":"
# or ";".
# Note that if e.g. &> is given, an option of -.5 will produce an error.

# Strings in argv[] which begin with "-" or "+" are taken to be
# strings of options, except that a string which consists solely of "-"
# or "+" is taken to be a non-option string; like other non-option strings,
# it stops the scanning of argv and is left in argv[].
# An argument of "--" or "++" also stops the scanning of argv[] but is removed.
# If an option takes an argument, the argument may either immediately
# follow it or be given separately.
# "-" and "+" options are treated the same.  "+" is allowed because most awks
# take any -options to be arguments to themselves.  gawk 2.15 was enhanced to
# stop scanning when it encounters an unrecognized option, though until 2.15.5
# this feature had a flaw that caused problems in some cases.  See the OptChars
# parameter to explicitly set the option-specifier characters.

# If an option that does not take an argument is given,
# an index with its name is created in Options and its value is set to the
# number of times it occurs in argv[].

# If an option that does take an argument is given, an index with its name is
# created in Options and its value is set to the value of the argument given
# for it, and Options[option-name,"count"] is (initially) set to the 1.
# If an option that takes an argument is given more than once,
# Options[option-name,"count"] is incremented, and the value is assigned to
# the index (option-name,instance) where instance is 2 for the second occurance
# of the option, etc.
# In other words, the first time an option with a value is encountered, the
# value is assigned to an index consisting only of its name; for any further
# occurances of the option, the value index has an extra (count) dimension.

# The sequence number for each option found in argv[] is stored in
# Options[option-name,"num",instance], where instance is 1 for the first
# occurance of the option, etc.  The sequence number starts at 1 and is
# incremented for each option, both those that have a value and those that
# do not.  Options set from a config file have a value of 0 assigned to this.

# Options and their arguments are deleted from argv.
# Note that this means that there may be gaps left in the indices of argv[].
# If compress is nonzero, argv[] is packed by moving its elements so that
# they have contiguous integer indices starting with 0.
# Option processing will stop with the first unrecognized option, just as
# though -- was given except that unlike -- the unrecognized option will not be
# removed from ARGV[].  Normally, an error value is returned in this case.
# If AllowUnrecOpt is true, it is not an error for an unrecognized option to
# be found, so the number of remaining arguments is returned instead.
# If OptChars is not a null string, it is the set of characters that indicate
# that an argument is an option string if the string begins with one of the
# characters.  A string consisting solely of two of the same option-indicator
# characters stops the scanning of argv[].  The default is "-+".
# argv[0] is not examined.
# The number of arguments left in argc is returned.
# If an error occurs, the global string OptErr is set to an error message
# and a negative value is returned.
# Current error values:
# -1: option that required an argument did not get it.
# -2: argument of incorrect type supplied for an option.
# -3: unrecognized (invalid) option.
function ProcArgs(argc,argv,OptList,Options,compress,AllowUnrecOpt,OptChars,
ArgNum,ArgsLeft,Arg,ArgLen,ArgInd,Option,Pos,NumOpt,Value,HadValue,specGiven,
NeedNextOpt,GotValue,OptionNum,Escape,dest,src,count,c,OptTerm,OptCharSet)
{
# ArgNum is the index of the argument being processed.
# ArgsLeft is the number of arguments left in argv.
# Arg is the argument being processed.
# ArgLen is the length of the argument being processed.
# ArgInd is the position of the character in Arg being processed.
# Option is the character in Arg being processed.
# Pos is the position in OptList of the option being processed.
# NumOpt is true if a numeric option may be given.
    ArgsLeft = argc
    NumOpt = index(OptList,"&")
    OptionNum = 0
    if (OptChars == "")
	OptChars = "-+"
    while (OptChars != "") {
	c = substr(OptChars,1,1)
	OptChars = substr(OptChars,2)
	OptCharSet[c]
	OptTerm[c c]
    }
    for (ArgNum = 1; ArgNum < argc; ArgNum++) {
	Arg = argv[ArgNum]
	if (length(Arg) < 2 || !((specGiven = substr(Arg,1,1)) in OptCharSet))
	    break	# Not an option; quit
	if (Arg in OptTerm) {
	    delete argv[ArgNum]
	    ArgsLeft--
	    break
	}
	ArgLen = length(Arg)
	for (ArgInd = 2; ArgInd <= ArgLen; ArgInd++) {
	    Option = substr(Arg,ArgInd,1)
	    if (NumOpt && Option ~ /[-+.0-9]/) {
		# If this option is a numeric option, make its flag be & and
		# its option string flag position be the position of & in
		# the option string.
		Option = "&"
		Pos = NumOpt
		# Prefix Arg with a char so that ArgInd will point to the
		# first char of the numeric option.
		Arg = "&" Arg
		ArgLen++
	    }
	    # Find position of flag in option string, to get its type (if any).
	    # Disallow & as literal flag.
	    else if (!(Pos = index(OptList,Option)) || Option == "&") {
		if (AllowUnrecOpt) {
		    Escape = 1
		    break
		}
		else {
		    OptErr = "Invalid option: " specGiven Option
		    return -3
		}
	    }

	    # Find what the value of the option will be if it takes one.
	    # NeedNextOpt is true if the option specifier is the last char of
	    # this arg, which means that if the option requires a value it is
	    # the next arg.
	    if (NeedNextOpt = (ArgInd >= ArgLen)) { # Value is the next arg
		if (GotValue = ArgNum + 1 < argc)
		    Value = argv[ArgNum+1]
	    }
	    else {	# Value is included with option
		Value = substr(Arg,ArgInd + 1)
		GotValue = 1
	    }

	    if (HadValue = AssignVal(Option,Value,Options,
	    substr(OptList,Pos + 1,1),GotValue,"",++OptionNum,!NeedNextOpt,
	    specGiven)) {
		if (HadValue < 0)	# error occured
		    return HadValue
		if (HadValue == 2)
		    ArgInd++	# Account for the single-char value we used.
		else {
		    if (NeedNextOpt) {	# option took next arg as value
			delete argv[++ArgNum]
			ArgsLeft--
		    }
		    break	# This option has been used up
		}
	    }
	}
	if (Escape)
	    break
	# Do not delete arg until after processing of it, so that if it is not
	# recognized it can be left in ARGV[].
	delete argv[ArgNum]
	ArgsLeft--
    }
    if (compress != 0) {
	dest = 1
	src = argc - ArgsLeft + 1
	for (count = ArgsLeft - 1; count; count--) {
	    ARGV[dest] = ARGV[src]
	    dest++
	    src++
	}
    }
    return ArgsLeft
}

# Assignment to values in Options[] occurs only in this function.
# Option: Option specifier character.
# Value: Value to be assigned to option, if it takes a value.
# Options[]: Options array to return values in.
# ArgType: Argument type specifier character.
# GotValue: Whether any value is available to be assigned to this option.
# Name: Name of option being processed.
# OptionNum: Number of this option (starting with 1) if set in argv[],
#     or 0 if it was given in a config file or in the environment.
# SingleOpt: true if the value (if any) that is available for this option was
#     given as part of the same command line arg as the option.  Used only for
#     options from the command line.
# specGiven is the option specifier character use, if any (e.g. - or +),
# for use in error messages.
# Global variables: OptErr
# Return value: negative value on error, 0 if option did not require an
# argument, 1 if it did & used the whole arg, 2 if it required just one char of
# the arg.
# Current error values:
# -1: Option that required an argument did not get it.
# -2: Value of incorrect type supplied for option.
# -3: Bad type given for option &
function AssignVal(Option,Value,Options,ArgType,GotValue,Name,OptionNum,
SingleOpt,specGiven,  UsedValue,Err,NumTypes) {
    # If option takes a value...    [
    NumTypes = "*()#<>]"
    if (Option == "&" && ArgType !~ "[" NumTypes) {	# ]
	OptErr = "Bad type given for & option"
	return -3
    }

    if (UsedValue = (ArgType ~ "[:;" NumTypes)) {	# ]
	if (!GotValue) {
	    if (Name != "")
		OptErr = "Variable requires a value -- " Name
	    else
		OptErr = "option requires an argument -- " Option
	    return -1
	}
	if ((Err = CheckType(ArgType,Value,Option,Name,specGiven)) != "") {
	    OptErr = Err
	    return -2
	}
	# Mark this as a numeric variable; will be propogated to Options[] val.
	if (ArgType != ":" && ArgType != ";")
	    Value += 0
	if ((Instance = ++Options[Option,"count"]) > 1)
	    Options[Option,Instance] = Value
	else
	    Options[Option] = Value
    }
    # If this is an environ or rcfile assignment & it was given a value...
    else if (!OptionNum && Value != "") {
	UsedValue = 1
	# If the value is "0" or "-" and this is the first instance of it,
	# do not set Options[Option]; this allows an assignment in an rcfile to
	# turn off an option (for the simple "Option in Options" test) in such
	# a way that it cannot be turned on in a later file.
	if (!(Option in Options) && (Value == "0" || Value == "-"))
	    Instance = 1
	else
	    Instance = ++Options[Option]
	# Save the value even though this is a flag
	Options[Option,Instance] = Value
    }
    # If this is a command line flag and has a - following it in the same arg,
    # it is being turned off.
    else if (OptionNum && SingleOpt && substr(Value,1,1) == "-") {
	UsedValue = 2
	if (Option in Options)
	    Instance = ++Options[Option]
	else
	    Instance = 1
	Options[Option,Instance]
    }
    # If this is a flag assignment without a value, increment the count for the
    # flag unless it was turned off.  The indicator for a flag being turned off
    # is that the flag index has not been set in Options[] but it has an
    # instance count.
    else if (Option in Options || !((Option,1) in Options))
	# Increment number of times this flag seen; will inc null value to 1
	Instance = ++Options[Option]
    Options[Option,"num",Instance] = OptionNum
    return UsedValue
}

# Option is the option letter
# Value is the value being assigned
# Name is the var name of the option, if any
# ArgType is one of:
# :	String argument
# ;	Non-null string argument
# *	Floating point argument
# (	Non-negative floating point argument
# )	Positive floating point argument
# #	Integer argument
# <	Non-negative integer argument
# >	Positive integer argument
# specGiven is the option specifier character use, if any (e.g. - or +),
# for use in error messages.
# Returns null on success, err string on error
function CheckType(ArgType,Value,Option,Name,specGiven,  Err,ErrStr) {
    if (ArgType == ":")
	return ""
    if (ArgType == ";") {
	if (Value == "")
	    Err = "must be a non-empty string"
    }
    # A number begins with optional + or -, and is followed by a string of
    # digits or a decimal with digits before it, after it, or both
    else if (Value !~ /^[-+]?([0-9]+|[0-9]*\.[0-9]+|[0-9]+\.)$/)
	Err = "must be a number"
    else if (ArgType ~ "[#<>]" && Value ~ /\./)
	Err = "may not include a fraction"
    else if (ArgType ~ "[()<>]" && Value < 0)
	Err = "may not be negative"
    # (
    else if (ArgType ~ "[)>]" && Value == 0)
	Err = "must be a positive number"
    if (Err != "") {
	ErrStr = "Bad value \"" Value "\".  Value assigned to "
	if (Name != "")
	    return ErrStr "variable " substr(Name,1,1) " " Err
	else {
	    if (Option == "&")
		Option = Value
	    return ErrStr "option " specGiven substr(Option,1,1) " " Err
	}
    }
    else
	return ""
}

# Note: only the above functions are needed by ProcArgs.
# The rest of these functions call ProcArgs() and also do other
# option-processing stuff.

# Opts: Process command line arguments.
# Opts processes command line arguments using ProcArgs()
# and checks for errors.  If an error occurs, a message is printed
# and the program is exited.
#
# Input variables:
# Name is the name of the program, for error messages.
# Usage is a usage message, for error messages.
# OptList the option description string, as used by ProcArgs().
# MinArgs is the minimum number of non-option arguments that this
# program should have, non including ARGV[0] and +h.
# If the program does not require any non-option arguments,
# MinArgs should be omitted or given as 0.
# rcFiles, if given, is a colon-seprated list of filenames to read for
# variable initialization.  If a filename begins with ~/, the ~ is replaced
# by the value of the environment variable HOME.  If a filename begins with
# $, the part from the character after the $ up until (but not including)
# the first character not in [a-zA-Z0-9_] will be searched for in the
# environment; if found its value will be substituted, if not the filename will
# be discarded.
# rcfiles are read in the order given.
# Values given in them will not override values given on the command line,
# and values given in later files will not override those set in earlier
# files, because AssignVal() will store each with a different instance index.
# The first instance of each variable, either on the command line or in an
# rcfile, will be stored with no instance index, and this is the value
# normally used by programs that call this function.
# VarNames is a comma-separated list of variable names to map to options,
# in the same order as the options are given in OptList.
# If EnvSearch is given and nonzero, the first EnvSearch variables will also be
# searched for in the environment.  If set to -1, all values will be searched
# for in the environment.  Values given in the environment will override
# those given in the rcfiles but not those given on the command line.
# NoRCopt, if given, is an additional letter option that if given on the
# command line prevents the rcfiles from being read.
# See ProcArgs() for a description of AllowUnRecOpt and optChars, and
# ExclusiveOptions() for a description of exOpts.
# Special options:
# If x is made an option and is given, some debugging info is output.
# h is assumed to be the help option.

# Global variables:
# The command line arguments are taken from ARGV[].
# The arguments that are option specifiers and values are removed from
# ARGV[], leaving only ARGV[0] and the non-option arguments.
# The number of elements in ARGV[] should be in ARGC.
# After processing, ARGC is set to the number of elements left in ARGV[].
# The option values are put in Options[].
# On error, Err is set to a positive integer value so it can be checked for in
# an END block.
# Return value: The number of elements left in ARGV is returned.
# Must keep OptErr global since it may be set by InitOpts().
function Opts(Name,Usage,OptList,MinArgs,rcFiles,VarNames,EnvSearch,NoRCopt,
AllowUnrecOpt,optChars,exOpts,  ArgsLeft,e) {
    if (MinArgs == "")
	MinArgs = 0
    ArgsLeft = ProcArgs(ARGC,ARGV,OptList NoRCopt,Options,1,AllowUnrecOpt,
    optChars)
    if (ArgsLeft < (MinArgs+1) && !("h" in Options)) {
	if (ArgsLeft >= 0) {
	    OptErr = "Not enough arguments"
	    Err = 4
	}
	else
	    Err = -ArgsLeft
	printf "%s: %s.\nUse -h for help.\n%s\n",
	Name,OptErr,Usage > "/dev/stderr"
	exit 1
    }
    if (rcFiles != "" && (NoRCopt == "" || !(NoRCopt in Options)) &&
    (e = InitOpts(rcFiles,Options,OptList,VarNames,EnvSearch)) < 0)
    {
	print Name ": " OptErr ".\nUse -h for help." > "/dev/stderr"
	Err = -e
	exit 1
    }
    if ((exOpts != "") && ((OptErr = ExclusiveOptions(exOpts,Options)) != ""))
    {
	printf "%s: Error: %s\n",Name,OptErr > "/dev/stderr"
	Err = 1
	exit 1
    }
    return ArgsLeft
}

# ReadConfFile(): Read a file containing var/value assignments, in the form
# <variable-name><assignment-char><value>.
# Whitespace (spaces and tabs) around a variable (leading whitespace on the
# line and whitespace between the variable name and the assignment character) 
# is stripped.  Lines that do not contain an assignment operator or which
# contain a null variable name are ignored, other than possibly being noted in
# the return value.  If more than one assignment is made to a variable, the
# first assignment is used.
# Input variables:
# File is the file to read.
# Comment is the line-comment character.  If it is found as the first non-
#     whitespace character on a line, the line is ignored.
# Assign is the assignment string.  The first instance of Assign on a line
#     separates the variable name from its value.
# If StripWhite is true, whitespace around the value (whitespace between the
#     assignment char and trailing whitespace on the line) is stripped.
# VarPat is a pattern that variable names must match.  
#     Example: "^[a-zA-Z][a-zA-Z0-9]+$"
# If FlagsOK is true, variables are allowed to be "set" by being put alone on
#     a line; no assignment operator is needed.  These variables are set in
#     the output array with a null value.  Lines containing nothing but
#     whitespace are still ignored.
# Output variables:
# Values[] contains the assignments, with the indexes being the variable names
#     and the values being the assigned values.
# Lines[] contains the line number that each variable occured on.  A flag set
#     is record by giving it an index in Lines[] but not in Values[].
# Return value:
# If any errors occur, a string consisting of descriptions of the errors
# separated by newlines is returned.  In no case will the string start with a
# numeric value.  If no errors occur,  the number of lines read is returned.
function ReadConfigFile(Values,Lines,File,Comment,Assign,StripWhite,VarPat,
FlagsOK,
Line,Status,Errs,AssignLen,LineNum,Var,Val) {
    if (Comment != "")
	Comment = "^" Comment
    AssignLen = length(Assign)
    if (VarPat == "")
	VarPat = "."	# null varname not allowed
    while ((Status = (getline Line < File)) == 1) {
	LineNum++
	sub("^[ \t]+","",Line)
	if (Line == "")		# blank line
	    continue
	if (Comment != "" && Line ~ Comment)
	    continue
	if (Pos = index(Line,Assign)) {
	    Var = substr(Line,1,Pos-1)
	    Val = substr(Line,Pos+AssignLen)
	    if (StripWhite) {
		sub("^[ \t]+","",Val)
		sub("[ \t]+$","",Val)
	    }
	}
	else {
	    Var = Line	# If no value, var is entire line
	    Val = ""
	}
	if (!FlagsOK && Val == "") {
	    Errs = Errs \
	    sprintf("\nBad assignment on line %d of file %s: %s",
	    LineNum,File,Line)
	    continue
	}
	sub("[ \t]+$","",Var)
	if (Var !~ VarPat) {
	    Errs = Errs sprintf("\nBad variable name on line %d of file %s: %s",
	    LineNum,File,Var)
	    continue
	}
	if (!(Var in Lines)) {
	    Lines[Var] = LineNum
	    if (Pos)
		Values[Var] = Val
	}
    }
    if (Status)
	Errs = Errs "\nCould not read file " File
    close(File)
    return Errs == "" ? LineNum : substr(Errs,2)	# Skip first newline
}

# Variables:
# Data is stored in Options[].
# rcFiles, OptList, VarNames, and EnvSearch are as as described for Opts().
# Global vars:
# Sets OptErr.  Uses ENVIRON[].
# If anything is read from any of the rcfiles, sets READ_RCFILE to 1.
function InitOpts(rcFiles,Options,OptList,VarNames,EnvSearch,
Line,Var,Pos,Vars,Map,CharOpt,NumVars,TypesInd,Types,Type,Ret,i,rcFile,
fNames,numrcFiles,filesRead,Err,Values,retStr) {
    split("",filesRead,"")	# make awk know this is an array
    NumVars = split(VarNames,Vars,",")
    TypesInd = Ret = 0
    if (EnvSearch == -1)
	EnvSearch = NumVars
    for (i = 1; i <= NumVars; i++) {
	Var = Vars[i]
	CharOpt = substr(OptList,++TypesInd,1)
	if (CharOpt ~ "^[:;*()#<>&]$")
	    CharOpt = substr(OptList,++TypesInd,1)
	Map[Var] = CharOpt
	Types[Var] = Type = substr(OptList,TypesInd+1,1)
	# Do not overwrite entries from environment
	if (i <= EnvSearch && Var in ENVIRON &&
	(Err = AssignVal(CharOpt,ENVIRON[Var],Options,Type,1,Var,0)) < 0)
	    return Err
    }

    numrcFiles = split(rcFiles,fNames,":")
    for (i = 1; i <= numrcFiles; i++) {
	rcFile = fNames[i]
	if (rcFile ~ "^~/")
	    rcFile = ENVIRON["HOME"] substr(rcFile,2)
	else if (rcFile ~ /^\$/) {
	    rcFile = substr(rcFile,2)
	    match(rcFile,"^[a-zA-Z0-9_]*")
	    envvar = substr(rcFile,1,RLENGTH)
	    if (envvar in ENVIRON)
		rcFile = ENVIRON[envvar] substr(rcFile,RLENGTH+1)
	    else
		continue
	}
	if (rcFile in filesRead)
	    continue
	# rcfiles are liable to be given more than once, e.g. UHOME and HOME
	# may be the same
	filesRead[rcFile]
	if ("x" in Options)
	    printf "Reading configuration file %s\n",rcFile > "/dev/stderr"
	retStr = ReadConfigFile(Values,Lines,rcFile,"#","=",0,"",1)
	if (retStr > 0)
	    READ_RCFILE = 1
	else if (ret != "") {
	    OptErr = retStr
	    Ret = -1
	}
	for (Var in Lines)
	    if (Var in Map) {
		if ((Err = AssignVal(Map[Var],
		Var in Values ? Values[Var] : "",Options,Types[Var],
		Var in Values,Var,0)) < 0)
		    return Err
	    }
	    else {
		OptErr = sprintf(\
		"Unknown var \"%s\" assigned to on line %d\nof file %s",Var,
		Lines[Var],rcFile)
		Ret = -1
	    }
    }

    if ("x" in Options)
	for (Var in Map)
	    if (Map[Var] in Options)
		printf "(%s) %s=%s\n",Map[Var],Var,Options[Map[Var]] > \
		"/dev/stderr"
	    else
		printf "(%s) %s not set\n",Map[Var],Var > "/dev/stderr"
    return Ret
}

# OptSets is a semicolon-separated list of sets of option sets.
# Within a list of option sets, the option sets are separated by commas.  For
# each set of sets, if any option in one of the sets is in Options[] AND any
# option in one of the other sets is in Options[], an error string is returned.
# If no conflicts are found, nothing is returned.
# Example: if OptSets = "ab,def,g;i,j", an error will be returned due to
# the exclusions presented by the first set of sets (ab,def,g) if:
# (a or b is in Options[]) AND (d, e, or f is in Options[]) OR
# (a or b is in Options[]) AND (g is in Options) OR
# (d, e, or f is in Options[]) AND (g is in Options)
# An error will be returned due to the exclusions presented by the second set
# of sets (i,j) if: (i is in Options[]) AND (j is in Options[]).
# todo: make options given on command line unset options given in config file
# todo: that they conflict with.
function ExclusiveOptions(OptSets,Options,
Sets,SetSet,NumSets,Pos1,Pos2,Len,s1,s2,c1,c2,ErrStr,L1,L2,SetSets,NumSetSets,
SetNum,OSetNum) {
    NumSetSets = split(OptSets,SetSets,";")
    # For each set of sets...
    for (SetSet = 1; SetSet <= NumSetSets; SetSet++) {
	# NumSets is the number of sets in this set of sets.
	NumSets = split(SetSets[SetSet],Sets,",")
	# For each set in a set of sets except the last...
	for (SetNum = 1; SetNum < NumSets; SetNum++) {
	    s1 = Sets[SetNum]
	    L1 = length(s1)
	    for (Pos1 = 1; Pos1 <= L1; Pos1++)
		# If any of the options in this set was given, check whether
		# any of the options in the other sets was given.  Only check
		# later sets since earlier sets will have already been checked
		# against this set.
		if ((c1 = substr(s1,Pos1,1)) in Options)
		    for (OSetNum = SetNum+1; OSetNum <= NumSets; OSetNum++) {
			s2 = Sets[OSetNum]
			L2 = length(s2)
			for (Pos2 = 1; Pos2 <= L2; Pos2++)
			    if ((c2 = substr(s2,Pos2,1)) in Options)
				ErrStr = ErrStr "\n"\
				sprintf("Cannot give both %s and %s options.",
				c1,c2)
		    }
	}
    }
    if (ErrStr != "")
	return substr(ErrStr,2)
    return ""
}

# The value of each instance of option Opt that occurs in Options[] is made an
# index of Set[].
# The return value is the number of instances of Opt in Options.
function Opt2Set(Options,Opt,Set,  count) {
    if (!(Opt in Options))
	return 0
    Set[Options[Opt]]
    count = Options[Opt,"count"]
    for (; count > 1; count--)
	Set[Options[Opt,count]]
    return count
}

# The value of each instance of option Opt that occurs in Options[] that
# begins with "!" is made an index of nSet[] (with the ! stripped from it).
# Other values are made indexes of Set[].
# The return value is the number of instances of Opt in Options.
function Opt2Sets(Options,Opt,Set,nSet,  count,aSet,ret) {
    ret = Opt2Set(Options,Opt,aSet)
    for (value in aSet)
	if (substr(value,1,1) == "!")
	    nSet[substr(value,2)]
	else
	    Set[value]
    return ret
}

# Returns true if option Opt was given on the command line.
function CmdLineOpt(Options,Opt,  i) {
    for (i = 1; (Opt,"num",i) in Options; i++)
	if (Options[Opt,"num",i] != 0)
	    return 1
    return 0
}
### End of ProcArgs library
### Begin set library
# 96/05/23 added return values  jhdiii
# 96/05/25 added set2list()

# Return value: the number of new elements added to Inter
function Intersection(A,B,Inter,  Elem,Count) {
    for (Elem in A)
	if (Elem in B && !(Elem in Inter)) {
	    Inter[Elem]
	    Count++
	}
    return Count
}

# Return value: the number of new elements added to Both
function Union(A,B,Both) {
    return CopySet(A,Both) + CopySet(B,Both)
}

# Deletes any elements that are in both Minuend and Subtrahend from Minuend.
# Return value: the number of elements deleted.
function SubtractSet(Minuend,Subtrahend,  Elem,nDel) {
    for (Elem in Subtrahend)
	if (Elem in Minuend) {
	    delete Minuend[Elem]
	    nDel++
	}
    return nDel
}

# Return value: the number of new elements added to To
function CopySet(From,To,  Elem,n) {
    for (Elem in From)
	if (!(Elem in To)) {
	    To[Elem]
	    n++
	}
    return n
}

# Returns 1 if Set is empty, 0 if not.
function IsEmpty(Set,  i) {
    for (i in Set)
	return 0
    return 1
}

# MakeSet: make a set from a list.
# An index with the name of each element of the list is created in the given
# array.
# Input variables: 
# Elements is a string containing the list of elements.
# Sep is the character that separates the elements of the list.
# Output variables:
# Set is the array.
# Return value: the number of new elements added to the set.
function MakeSet(Set,Elements,Sep,  i,Num,Names,nFound,ind) {
    nFound = 0
    Num = split(Elements,Names,Sep)
    for (i = 1; i <= Num; i++) {
	ind = Names[i]
	if (!(ind in Set)) {
	    Set[ind]
	    nFound++
	}
    }
    return nFound
}

# Returns the number of elements in set Set
function NumElem(Set,  elem,Num) {
    for (elem in Set)
	Num++
    return Num
}

# Remove all elements from Set
function DeleteAll(Set,  i) {
    split("",Set,",")
}

# Returns a list of all of the elements in Set[], with each pair of elements
# separated by Sep.
function set2list(Set,Sep,  list,elem) {
    for (elem in Set)
	list = list Sep elem
    return substr(list,2)	# skip 1st separator
}
### End set library
### start canonTTY library
function nodevTTY(tty) {
    sub("^/dev/","",tty)
    return tty
}

function canonTTY(tty) {
    if (tty ~ "^/dev/")
	sub("^/dev/","",tty)
    else if (tty !~ /^tty/)
	tty = "tty" tty
    return tty
}

function shortTTY(tty) {
    sub("^/dev/","",tty)
    sub("^tty","",tty)
    return tty
}
### end canonTTY library
function basename(path) {
    sub(".*/","",path)
    return path
}
### Start of tinfo lib
# @(#) tinfo 1.0 96/11/30
# altInit(): Get alternate character set terminfo capabilities.
# term, noerror: see tiget().
# tinfo: contains the acsc capability, and any of the enacs, smacs, and rmacs
# capabilities that are defined for the terminal.  Each is indexed by its
# capability name.  enacs is used to enable the alternate character set;
# smacs starts it; rmacs ends it.  acsc is the mapping of vt100 alternate
# character codes to those appropriate for the given terminal.
# AltMap is the acsc string broken down with each alternate character indexed
# by its vt100 equivalent.  num is an ordered list of the vt100 characters
# indexed starting with 1, for applications that need to know what order they
# were given in.
# The global _macs[] is set up with _macs[0] = rmacs & _macs[1] = smacs, for
# use by altPrint().
# The alternate characters and their indexes (vt100 equivalents) are:
# 0  solid square block		a  checker board	f  degree symbol
# g  plus/minus			h  board of squares	j  lower right corner
# k  upper right corner		l  upper left corner	m  lower left corner
# n  plus			q  horizontal line	t  left tee
# u  right tee			v  bottom tee		w  top tee
# x  vertical line		+  arrow pointing right	.  arrow pointing down
# -  arrow pointing up		,  arrow pointing left	`  diamond
# ~  bullet			I  lantern symbol	o  scan line 1
# s  scan line 9
function altInit(tinfo,term,noerror,AltMap,num,  ret,caplist,acsc,len,j,i) {
    if (ret = tiget("acsc",tinfo,term)) {
	# All other types of errors cause tput to print an informative message
	# to stderr, which is not redirected.
	if (!noerror && ret == 1)
	    print "Terminal has no acsc capability." > "/dev/stderr"
	return ret
    }
    caplist = "enacs,smacs,rmacs"
    tiget(caplist,tinfo,term)
    acsc = tinfo["acsc"]
    len = length(acsc)
    j = 0
    for (i = 1; i < len; i += 2)
	AltMap[num[++j] = substr(acsc,i,1)] = substr(acsc,i+1,1)
    if ("rmacs" in tinfo)
	_macs[0] = tinfo["rmacs"]
    if ("smacs" in tinfo)
	_macs[1] = tinfo["smacs"]
}

# altPrint: Print characters in either the alternate or standard character set.
# string is the string to print.
# alt should be 1 if string is in the alternate character set; 0 if in the
# standard character set.
# tinfo contains the smacs and rmacs strings, if needed.
# altPrint keeps track of whether the terminal is in the standard or alternate
# character set, and issues smacs and rmacs as needed.
# It should always be called with alt false at the end of program execution to
# ensure that the terminal is left in the standard character set.
# Globals: The character set is tracked in _altPrintSet
function altPrint(string,alt,tinfo) {
    if (alt != _altPrintSet) {
	printf "%s%s",_macs[alt],string
	_altPrintSet = alt
    }
    else
	printf "%s",string
}

# tiget: get terminfo capabilities.
# capnames is a comma-separated list of terminfo capabilities to get.
# Each capability is put in tinfo[], indexed by capability name.
# If term is passed, it is the terminal type to get the capabilities for.
# If not, the value of the environment variable TERM is used.
# If noerror is true, error messages are suppressed.
# Return value: the exit status of the last tput, or -1 if term is not passed
# and there is no TERM environment variable.
function tiget(capnames,tinfo,term,noerror,  cmd,RS,ret,names,capname,i) {
    if (term == "")
	if ("TERM" in ENVIRON)
	    term = ENVIRON["TERM"]
	else
	    return -1
    split(capnames,names,",")
    RS = ""	# this makes the record separator be "\n\n", which hopefully
		# is not very common in terminfo capabilities
    for (i = 1; i in names; i++) {
	capname = names[i]
	cmd = "exec tput -T " term " " capname
	if (noerror)
	    cmd = cmd " 2>/dev/null"
	cmd | getline
	if (!(ret = close(cmd)))
	    # printf interprets many of the escape chars in the same manner that
	    # the terminfo library does... not perfect, but better than nothing
	    tinfo[capname] = sprintf($0)
    }
    return ret
}
### End of tinfo lib
### Begin qsort routines

# Arr[] is an array of values with arbitrary indices.
# k[] is returned with numeric indices 1..n.
# The values in k[] are the indices of Arr[],
# ordered so that if Arr[] is stepped through
# in the order Arr[k[1]] .. Arr[k[n]], it will be stepped
# through in order of the values of its elements.
# The return value is the number of elements in the arrays (n).
function qsortArbIndByValue(Arr,k,  ArrInd,ElNum) {
    ElNum = 0
    for (ArrInd in Arr)
	k[++ElNum] = ArrInd
    qsortSegment(Arr,k,1,ElNum)
    return ElNum
}

# Sort a segment of an array.
# Arr[] contains data with arbitrary indices.
# k[] has indices 1..nelem, with the indices of arr[] as values.
# This function sorts the elements of arr that are pointed to by
# k[start..end], swapping the values of elements of k[] so that
# when this function returns arr[k[start..end]] will be in order.
function qsortSegment(Arr,k,start,end,  left,right,sepval,tmp,tmpe,tmps) {
    # handle two-element case explicitly for a tiny speedup
    if ((end - start) == 1) {
	if (Arr[tmps = k[start]] > Arr[tmpe = k[end]]) {
	    k[start] = tmpe
	    k[end] = tmps
	}
	return
    }
    # Make sure comparisons act on these as numbers
    left = start+0
    right = end+0
    sepval = Arr[k[int((left + right) / 2)]]
    # Make every element <= sepval be to the left of every element > sepval
    while (left < right) {
	while (Arr[k[left]] < sepval)
	    left++
	while (Arr[k[right]] > sepval)
	    right--
	if (left < right) {
	    tmp = k[left]
	    k[left++] = k[right]
	    k[right--] = tmp
	}
    }
    if (left == right)
	if (Arr[k[left]] < sepval)
	    left++
	else
	    right--
    if (start < right)
	qsortSegment(Arr,k,start,right)
    if (left < end)
	qsortSegment(Arr,k,left,end)
}

# Arr[] is an array of values with arbitrary indices.
# k[] is returned with numeric indices 1..n.
# The values in k are the indices of Arr[],
# ordered so that if Arr[] is stepped through
# in the order Arr[k[1]] .. Arr[k[n]], it will be stepped
# through in order of the values of its indices.
# The return value is the number of elements in the arrays (n).
# If the indexes are numeric, Numeric should be true, so that they can be
# compared as such rather than as strings.  Numeric indexes do not have to be
# contiguous.
function qsortByArbIndex(Arr,k,Numeric,  ArrInd,ElNum) {
    ElNum = 0
    if (Numeric)
	# Indexes do not preserve numeric type, so must be forced
	for (ArrInd in Arr)
	    k[++ElNum] = ArrInd+0
    else
	for (ArrInd in Arr)
	    k[++ElNum] = ArrInd
    qsortNumIndByValue(k,1,ElNum)
    return ElNum
}

# Arr is an array of elements with contiguous numeric indexes to be sorted
# by value.
# start and end are the starting and ending indexes of the range to be sorted.
function qsortNumIndByValue(Arr,start,end,  left,right,sepval,tmp,tmpe,tmps) {
    # handle two-element case explicitly for a tiny speedup
    if ((start - end) == 1) {
	if ((tmps = Arr[start]) > (tmpe = Arr[end])) {
	    Arr[start] = tmpe
	    Arr[end] = tmps
	}
	return
    }
    left = start+0
    right = end+0
    sepval = Arr[int((left + right) / 2)]
    while (left < right) {
	while (Arr[left] < sepval)
	    left++
	while (Arr[right] > sepval)
	    right--
	if (left <= right) {
	    tmp = Arr[left]
	    Arr[left++] = Arr[right]
	    Arr[right--] = tmp
	}
    }
    if (start < right)
	qsortNumIndByValue(Arr,start,right)
    if (left < end)
	qsortNumIndByValue(Arr,left,end)
}

### End qsort routines
### Start of DrawTrees lib
# @(#) DrawTrees 1.1 97/07/19
# 96/11/30 john h. dubois iii (john@armory.com)
# 97/07/19 1.1 Added preOrderTraversal(), indentation equalization.
#
#    Data[] is a tree of data to draw.  The indexes consist of one or more
# integer values separated by SUBSEP.  The "depth" of the element determines
# how many integers (dimensions) are contained in the index.  For each set
# of node siblings, the integer describing the varying dimension varies from
# 1 through n where n is the number of siblings.  This shows the indexes
# used for the elements of a small tree with depth 3:
# 1----+-1,1--+-1,1,1
#      |      |-1,2,2
#      |      \-1,2,3
#      \-1,2--+-1,2,1
#             \-1,2,2
# 2------2,1--+-2,1,1
#             \-2,2,2
#       ^----^--see below
# The values of the elements are lines of data which constitute the nodes of
# the tree.
#    Offset & Width: By default, the tree is drawn with each node on a separate
# line. Offset is the horizonal offset of each child from its parent.  It
# must be at least 1.  If Width is non-0, the tree is instead drawn with the
# first child of each parent immediately to the right of its parent.  Width
# is the number of characters allocated to the node data for each level.  If
# the data for an interior node is longer than Width, the value is truncated
# to Width-1 characters and a left-tee is appended to indicate the
# truncation, so Width should be at least two.  If this style is used,
# Offset is the number of characters of additional horizontal separation to
# use after the "split point"; in the example tree above, Width is set to 1,
# causing the addition of the characters at the positions marked by ^ on the
# "see below" line.
#    AltChars[]: The tree is drawn using box-drawing characters appropriate to
# the terminal if they are available, and a default set of ASCII characters if
# not.  If AltChars[] contains all of the following elements, they are used to
# draw the tree.  I is the index to use; A is the ASCII default.
# I A Description
# x | Vertical bar
# q - Horizontal bar
# l / top left corner
# m \ bottom left corner
# w + Top tee 
# t } Left tee
# + > Right arrow (optional)
# ~ * Bullet (optional)
# If AltChars[] does not contain all of these elements and the alternate
# character set it used, AltChars[] is returned filled in with the
# characters used to draw the tree.  The same array can then be passed back
# to DrawTrees(), avoiding the need for it to use tput again to get the
# terminal's alternate character set capabilities.
#    If Spaces is true, indentation is done with spaces only; the effect is to
# set all of the above characters to be a space.
#    If term is passed, it overrides the TERM environment variable.  Pass "dumb"
# to force the ASCII values to be used.  
#    If useArrow is true and the terminal has a right-arrow character defined,
# it is used for the branch character to the left of node data.
#    If maxLength is non-0, output lines are truncated to maxLength characters.
#    If AddInd is true, in the output each value is preceded by its index.
#    If Sort is true, the tree is sorted by the lexicographical values of its
# elements, and the qsort library must be included in the program.
#    If maxBranchInd is non-0, an attempt is made to equalize the total
# indentation of each line due to the tree-drawing characters by using a
# string of horizontal bar characters, so that the lines in Data[] will
# be aligned with each other.  Width must be set to 0.  If maxBranchInd is
# -1, all lines will be indented to the same distance that the furthest
# indented line is.  If maxBranchInd is positive, it places a limit on how
# much indentation equalization is done.  The value sets the number of
# indents (each indent being Offset characters long) that may be used.  If the
# deepest indent is less than or equal to the value given, the number of
# indents used will be the same as the deepest indent.  If the deepest
# indent is larger than the value given, those lines indented further will
# not line up, resulting in ragged output.  When scanning the tree to determine
# its maximum depth, the indexes are examined directly rather than doing a
# proper tree traversal, so Data[] should not contain any extraneous elements
# except an option "HEADER" element.  If Data["HEADER"] is set, it is printed
# blank-indented to the equalization distance.  If "HEADER" is set, it will be
# printed even if maxBranchInd is 0, but will only be aligned with the data
# for the root nodes.
# Return value:
# A negative value is returned on error.
function DrawTrees(Data,Offset,Width,AltChars,Spaces,term,useArrow,maxLength,
AddInd,Sort,maxBranchInd,
i,tinfo,Strings,smacs,rmacs,BranchIndent,BlankIndent,bTail,veBar,hoBar,bLeft,
topTee,lTee,arrow,bullet,WidthBar,OffsetBar,ind,elem,n,maxDepth,Header) {
    if (Spaces) {
	veBar = hoBar = bLeft = topTee = lTee = arrow = " "
	bullet = "*"
    }
    else {
	if ("x" in AltChars && "q" in AltChars && "m" in AltChars && \
	"w" in AltChars && "t" in AltChars) {
	    tinfo["smacs"] = AltChars["smacs"]
	    tinfo["rmacs"] = AltChars["rmacs"]
	    if ("enacs" in AltChars)
		tinfo["enacs"] = AltChars["enacs"]
	}
	else
	    altInit(tinfo,term,1,AltChars)
	if ("x" in AltChars && "q" in AltChars && "m" in AltChars && \
	"w" in AltChars && "t" in AltChars) {
	    AltChars["smacs"] = smacs = Strings["smacs"] = tinfo["smacs"]
	    AltChars["rmacs"] = rmacs = Strings["rmacs"] = tinfo["rmacs"]
	    if ("enacs" in tinfo) {
		printf "%s",tinfo["enacs"]
		AltChars["enacs"] = tinfo["enacs"]
	    }
	    veBar = AltChars["x"]
	    hoBar = AltChars["q"]
	    bLeft = AltChars["m"]
	    tLeft = AltChars["l"]
	    topTee = AltChars["w"]
	    lTee = AltChars["t"]
	    arrow = "+" in AltChars ? AltChars["+"] : hoBar
	    bullet = "~" in AltChars ? AltChars["~"] : lTee
	}
	else {
	    # Do not attempt mixing of alt & regular char sets for tree drawing
	    veBar = "|"
	    hoBar = "-"
	    bLeft = "\\"
	    tLeft = "/"
	    topTee = "+"		# {
	    lTee = "}"
	    arrow = ">"
	    bullet = "*"
	}
    }
    # b: blank indent.  Will be preceded by newline & followed by branch char.
    # v: indent that includes a vertical branch on the left:  "|    "
    #    Will be preceded by newline or whitespace & followed by branch char.
    # l: lower left horizontal branch indent.                 "\---"
    # t: left tee horizontal branch indent.                   "}---"
    # l & t will be preceded by newline or whitespace & followed by either
    # branch tail (">") or indentation equalization.
    # p: Node padding.  Must be adjusted to fit, so is not
    #    surrounded by smacs/rmacs.  Preceded by node data; followed by branch.
    #    If Width is 0, the node padding will equal to the offset, so it is
    #    also used for unbranched indentation equalization.
    # bie: Branched indentation equalization.  Like p but with a top tee on the
    #    left.   "-+--"
    # n: Internode branch.  Preceded by branch; followed by node data.  "-->"
    # tn: Teed internode branch.  Preceded b/branch; followed b/node data."+->"
    # c: Node data truncation character.  Will be followed by branch char.
    # n, tn, and c are used only in "width" mode.
    # lt: Line truncation character.
    # bt: Branch tail.   ">"
    # r:  Tree root.  "/"
    for (i = Offset + Width; i > 0; i-=1) {
	BlankIndent = BlankIndent " "
	BranchIndent = BranchIndent hoBar
    }
    WidthIndent = substr(BlankIndent,1,Width)
    OffsetIndent = substr(BranchIndent,1,Offset)
    if (BranchIndent != "" && Offset > 1)
	bTail = useArrow ? arrow : hoBar
    Strings["c"] = smacs lTee
    Strings["lt"] = smacs bullet rmacs
    Strings["p"] = BranchIndent
    Strings["n"] = substr(BranchIndent,1,Offset-1) bTail rmacs
    Strings["tn"] = topTee substr(BranchIndent,1,Offset-2) bTail rmacs

    Strings["b"] = BlankIndent
    Strings["v"] = WidthIndent smacs veBar rmacs substr(BlankIndent,1,Offset-1)
    Strings["l"] = WidthIndent smacs bLeft substr(OffsetIndent,3)
    Strings["t"] = WidthIndent smacs lTee  substr(OffsetIndent,3)
    Strings["bt"] = bTail rmacs

    if ("HEADER" in Data)
	Header = Data["HEADER"]
    if (maxBranchInd) {
	if (Width)
	    return -1
	Strings["bie"] = (Offset > 1 ? hoBar : "") topTee substr(BranchIndent,3)
	for (ind in Data) {
	    n = split(ind,elem,SUBSEP)-1
	    if (n > maxDepth)
		maxDepth = n
	}
	if (maxBranchInd > 0 && maxBranchInd < maxDepth)
	    maxDepth = maxBranchInd
	for (i = 1; i < maxDepth; i++) {
	    Strings["r"] = Strings["r"] BranchIndent
	    if (Header != "")
		printf "%s",BlankIndent
	}
	Strings["r"] = \
	smacs tLeft substr(BranchIndent,3) Strings["r"] bTail rmacs
	if (Header != "")
	    printf "%s",BlankIndent
    }
    if (Header != "")
	print Header
    dtTraverse(Data,"",Strings,0,"",Width,maxLength,Offset+Width,AddInd,Sort,
    maxDepth)
    return 0
}

# dtTraverse(): Traverse and print a subtree.
# Data[], Width, AddInd, Sort: as described for DrawTrees().
# catind: index into Data[] for the parent of this node, followed by a SUBSEP
#    char.
# Strings[]: Line drawing characters, and rmacs/smacs strings.
# level: The depth of this node, with tree roots at level 0.
# branch: An indentation string to print the vertical components of the
#    branches of the siblings of the parents of this node.
# Length: How many further characters may be added at this indentation level.
# levelWidth: How many characters the indentation for each level occupies.
# equIndent: How much levels' worth of indentation equalization to do.
function dtTraverse(Data,catind,Strings,level,branch,Width,Length,levelWidth,
AddInd,Sort,equIndent,
childNum,ind,siblings,children,nbranch,len,s,subLength,value,k,Arr,i) {
    if (Length && (subLength = Length - levelWidth) < 1)
	# Make sure subLength does not end up 0, which indicates no limit
	subLength = -1
    if (Sort) {
	# build a subtree level to sort
	for (childNum = 1; (ind = catind childNum) in Data; childNum++)
	    Arr[ind] = Data[ind]
	qsortArbIndByValue(Arr,k)
    }
    # If doing indentation equalization, there is less room for data
    if (level < equIndent)
	Length -= (equIndent - level) * levelWidth
    # A single instance of this function handles all of the immediate children
    # of a particular process.  They are iterated over here.
    for (childNum = 1; (ind = catind childNum) in Data; childNum++) {
	if (Sort)
	    ind = k[childNum]
	children = (ind,1) in Data
	if (level) {	# If this is not a root node, draw indentation string
	    # Determine whether this child has further siblings
	    siblings = (catind (childNum+1)) in Data
	    # If printing one node per line or this is not the first child,
	    # indent string for this node was not drawn when its parent's node
	    # data was printed, so print indent string now.
	    # If child has further siblings, need a left tee indent;
	    # otherwise need a lower left indent.
	    if (!Width || childNum != 1) {
		printf "%s",branch Strings[siblings ? "t" : "l"]
		if (level < equIndent) {
		    printf "%s",children ? Strings["bie"] : Strings["p"]
		    for (i = level+1; i < equIndent; i++)
			printf "%s",Strings["p"]
		}
		printf "%s", Strings["bt"]
	    }
	}
	else if (equIndent)
	    printf "%s",Strings["r"]
	# Done printing whatever indentation strings need to precede this
	# child's node data; now print node data and indentation for its
	# children, if any.
	value = Data[ind]	# Get node data
	if (AddInd)
	    value = ind ":" value
	if (Width && children) {
	    if (subLength == -1)
		# No room left to show children; indicate that by terminating
		# with line truncation char
		printf "%.*s%s\n",Length-1,value,Strings["lt"]
	    else {
		if ((len = length(value)) > Width)
		    printf "%.*s%s",Width-1,value,Strings["c"] # truncate
		else
		    printf "%s%s%.*s",value,Strings["smacs"], Width-len,
		    Strings["p"]	# pad on right
		# If this node has children, print offset branch
		printf "%s",Strings[((ind,2) in Data) ? "tn" : "n"]
	    }
	}
	else if (Length) {
	    if (length(value) > Length)
		printf "%.*s%s\n",Length-1,value,Strings["lt"]
	    else
		printf "%.*s\n",Length,value
	}
	else
	    print value
	if (children && subLength != -1) {
	    if (level)
		nbranch = branch Strings[siblings ? "v" : "b"]
	    dtTraverse(Data,ind SUBSEP,Strings,level+1,nbranch,Width,subLength,
	    levelWidth,AddInd,Sort,equIndent)
	}
    }
}

# buildTree: add nodes to a tree, find each of their children, and call
# buildTree() recursively for each child set.
# Tree[] is the tree being built, in the style described for DrawTrees().
# treeData[1..n] contains data that should be added to Tree[] (a string may
# modified by getChildren() if it is called for a node).
# Prefix is the string that the index of each element in treeData[] should be
# prefixed with when it is copied to Tree[].
# Depth is the current depth within the tree, with the top node at depth 1.
# It is used only to be passed to getChildren() in case it cares.
# childData[1..n] has two purposes.  buildTree() will only call getChildren()
# for those indexes of treeData[] that also exist in childData[].  In addition,
# additional data may be passed to getChildren() for a node by assigning a
# value to the node index in childData[].
#
# For each element in childData[], the function getChildren() is called with
# the parameters (treeData,childData[i],cTreeData,cChildData,i,Depth).
# cTreeData[] and cChildData[] are arrays which should be filled in the node
# has any children.
# The return value of getChildren() should be the number of children found.
# treeData[] is passed rather than the value of one of its elements so that
# the value of the element being processed may be modified before it is
# copied to Tree[].  If it is deleted from the array, it is skipped (not
# copied to Tree[]); in this case no children should be added.
# getChildren() must be defined elsewhere in the program.
function buildTree(Tree,treeData,childData,Prefix,Depth,
i,cTreeData,cChildData,j) {
    j = 1
    for (i = 1; i in treeData; i++) {
	split("",cTreeData)
	split("",cChildData)
	if (i in childData && \
	getChildren(treeData,childData[i],cTreeData,cChildData,i,Depth) && \
	i in treeData)
	    buildTree(Tree,cTreeData,cChildData,Prefix j SUBSEP,Depth+1)
	if (i in treeData)
	    Tree[Prefix j++] = treeData[i]
    }
}

# Breadth-first-search version of buildTree().  This is intended to flatten
# the tree representation of a possibly cyclic graph as much as possible.
# All nodes at each depth are visited before the nodes at the next depth are
# visited.
# All parameters are as for buildTree() except that the scalar Prefix is
# replaced by the array Prefixes[].  It has an element for each value in
# treeData[] (with the same index), with the value being the prefix for the
# index which that element should be stored in treeData[] with.
# getChildren() is called as by buildTree(), except that there is an additional
# argument telling getChildren() the first index in cTreeData[] and
# cChildData[] to use (instead of starting at 1).
function bfBuildTree(Tree,treeData,childData,Prefixes,Depth,
i,cTreeData,cChildData,j,childPos,cPrefixes,nChild,cIndex,l) {
    childPos = 1
    for (i = 1; i in treeData; i++) {
	nChild = (i in childData) ? \
	getChildren(treeData,childData[i],cTreeData,cChildData,i,Depth,
	childPos) : 0
	if (i in treeData) {	# if not skipping this node
	    if (i == 1 || Prefixes[i] != Prefixes[i-1])
		j = 1
	    cIndex = Prefixes[i] j SUBSEP
	    for (l = 1; l <= nChild; l++)
		cPrefixes[childPos++] = cIndex
	    Tree[Prefixes[i] j] = treeData[i]
	    j++
	}
    }
    if (childPos > 1)
	bfBuildTree(Tree,cTreeData,cChildData,cPrefixes,Depth+1)
}

# preOrderTraversal: Do a pre-order traversal of the tree described by Tree[]
# (the parent node is visited before any children).
# Tree[] is indexed by node name; the data for each node is a comma-separated
# list of the children of that node.  Nodes that do not have children need not
# appear in Tree[].  Node names may be any string that does not include a
# comma.
# Node is the node to start at.
# If nSort is true, child node names are expected to be numbers and are
# visited in numeric order.
# Ind is uses as the top level node in building indexes for a DrawTrees() style 
# tree.  The indexes are passed to preOrderVisit().  Ind would typically be 1.
# Data is an arbitrary parameter to be passed to the function that does node
# processing.  It may be a string or array, but must be consistent within a
# program, since awk will compile it as one or the other.
# Parents should be left null on the first call.
# For each node, preOrderVisit(node-id,node,ind,data) is called.
# node-id is concatenation of all of the names of the nodes that lead from the
# initial node to the node being processed, separated by commas, e.g.:
# initialnode,internode,thisnode
# node is the node name by itself.
# ind is a DrawTrees() style node index, for use if preOrderVisit() is building
# a tree for DrawTrees().  ind starts at 1 and is incremented by the amount
# that preOrderVisit() returns when called to process a subtree.  This is done
# by having preOrderVisit() return whatever value the preOrderVisit() it calls
# returns.  preOrderVisit() would typically return 0 if the index passed to it
# was not used, and 1 if it was used.
# Data is passed from the arguments to this function.
# If preOrderVisit() returns true, its children (if any) will be visited;
# if it returns false, they will not.
# preOrderVisit() should be constructed to process the node appropriately.
function preOrderTraverse(Node,Tree,nSort,Ind,Data,Parents,
Children,numChildren,childNum,subIndex,ret) {
    if ((ret = preOrderVisit(Parents Node,Node,Ind,Data)) && Node in Tree) {
	numChildren = split(Tree[Node],Children,",")
	if (nSort) {
	    for (i = 1; i <= numChildren; i++)
		Children[i] += 0	# mark as numeric, for qsort
	    qsortNumIndByValue(Children,1,numChildren)
	}
	Parents = Parents Node ","
	subIndex = 1
	for (childNum = 1; childNum <= numChildren; childNum++)
	    subIndex += preOrderTraverse(Children[childNum],Tree,nSort,
	    Ind SUBSEP subIndex,Data,Parents)
    }
    return ret
}
### End of DrawTrees lib