ISR-9
August, 1965

IV-1

XV. HIERARCHY SET-UP AND HIERARCHY AND (JONGEPT-CONCEPTEXPANSION PROCEDURES
M. Razar and G. Shapiro

1.

Introduction
The present section describes a system for setting up a concept'

hierarchy and for expanding document vectors using this hierarchy andthe concept-concept correlations produced by link 9 of SMART.
The hierarchy consists of a tree-like structure where, in
general, several related concepts appear under one item of greater
generality.

Provision is made for having a concept number appear inseveral places by allowing any concept in the hierarchy to cross-referr
any other. Cross-referencing is unidirectional and implies no hierarchical relation. For a description of the considerations involved inconstructing a hierarchy, the reader is referred to Sec. Ill ofReport ISR-7.
Instead of being based on a treelike structure in core, thepresent version of SMART uses a hierarchy stored on tape in list format.
Though this format (described in part 2) is highly redundant, it does
permit hierarchies of unlimited size to be used.
restrictions to less than one core-load(Compare with theeffective in Sec. V of ISR-7).

If hierarchy expansion is requested, link 10 of SMART adds theappropriate entries to the document vectors of each document. There are
four possible modes of expansion:by parents, brothers, sons and cross-XV-2

references, corresponding to weight parameters ROOTWT, BRANWT, LEAFWTand GROSWT. Any or all of these may be requested simultaneously. It
was thought to be more efficient to do concept-concept expansion at
the same time as hierarchical expansions, since this permits theexecution of one pass through the sorted document vector tape for both
expansions.
Parts 2 and 3 of this section describe the routines used forgenerating the hierarchy file on the SMART library tape. Part 4
describes the expansion programs. The production of the concept-concept
correlation tape and its format are described in Sec. XIV of this report.

2oCard and Tape Formats; Size Limitations
The SETUP program reads information punched on cards in a

special format, constructs a tree, and writes some information pertaining to each node on tape. In particular, the following information
is provided for each nodes

its concept number (i.e. node value) andthe concept numbers of its parent, sons, brothers and cross-references.
The individual nodes are not numbered as such but are referred to solely
by the concept numbers assigned to them*,
The card format used by SETUP is fairly simple. The firstnumber on a card is the concept number of a node in the tree. All
succeeding numbers on the card are cross-references to it. The positionof the node in the tree is determined by the position of the firstnumber on the card. The column in which the rightmost digit of thisXV-3

first number is punched is r^f^rred to as the level of the node. The
level of a node is compared with the levels of the nodes on preceding
cards until one is found with a lower level (i.e. punched further tothe left).

The first sucn preceding node is its parent. In preparing

a rfeck of car^s to be processed by SETUP, the most esthetic approachis to punch the concept number of a card at the same level as its
brothers and at a certain fixed level higher than its parent. This
is not necessary, however. As long as the parent of a node is thefirst preceding no^e punched to the left of it SETUP will handle itproperly.

(See Fig. 1.)

The tree (a) can be punched ineither of the following
equivalent formats (as well asothers).

(a)
*

2«
6vi

2
3

or
6
7
Sample Card Format
Figure 1
When punching extremely deep hierarchies or nodes with longlists of cross-references, one carr! per node may not suffice. If
desired, a card may be continued to the following one by any punchin column 72. On each successive continuation card the level is

7

XV~4

incremented by 70 sc that column k on the nth card represents aneffective level of 70(n~ 1) + k.

Column 71 is always left blank.

Therefore a concept number and its cross-references should be confined to columns 1~7Q.

A single blank card terminates a bush* Twoconsecutive blanks terminate the whole tree and prevent any further
data from being read in. To insure proper functioning, all concept
numbers should be at a higher level than the root of the bush. Roots
have no parent. SETUP identifies roots by giving them the fictitious
parent 0.
SETUP i3 designed with two criteria in mind. First, therelevant information concerning each node (i.e. parent, sons,brothers* cross-references) should be readily accessible by means ofa fast and efficient search. Second, the hierarchy in the tree
structure should be easy to update. Since each node is completely
described by a single card (with, perhaps, some continuation cards),
insertions and deletions can be made, without massive changes. To
insert a r.ode one merely adds a card in the right place. To delete anode, one removes the card and all its descendants.
To meet the requirement of accessibility, SETUP writes
information on tape sorted In order by increasing concept numbers.
The actual, format used in preparing the tape is as follows. Eachword on tape contains two numbers packed into it, the first in bite
1-17* and the second in bits 19-35*

The first word of each logicalrecord contains the concept number in its first half and the parent in
its second half* The second and third words of each logical record

give information as to the number and nature of the succeeding words inthe record. The second word has, in its first half, the total numberof words which will contain brothers, sons and cross-references; in its
second half it contains the number of words of brothers and sons. The
third word contains the number of words containing brothers; its second
half is filled out with zeros. Thus if there are five brothers, foursons and three cross-references we will have three words of brothers
and two words each of sons and cross-references.

2

1(See Fig. 2.)0This r e f e r s t o the case when there are five brothers,
four sons and three cross-references.
Sample of Words 2 and 3
Figure 2
The remainder of each l o g i c a l record (words 4 and after) cons i s t s of the l i s t s of brothers, sons and cross-references packed two
to a word.

If n l , n2, n3 respectively represent the numbers packed

into words 2 and 3> then the next n3 words (4- to n3 + 3) contain thebrothers; the following n 2 - n3 words (n3+ 1+ to n2+ 3) the sons; thenext n l - n2 words (n2+ 4 t o nl+ 3) the cross-references.
As an example, suppose t h a t the node labeled "3" in Fig. 1
had cross-references t o 4 1 , 42, 56, 71, 103.
the l o g i c a l record indicated i n F i g . 3 below.

Then i t would produce

XV-6

1

L

3"

2

!

5

3

i

x~

4

L...2

5

[

6

L .41 _

7I...

56 ;1 "7l'~l

S

1

103

l

1

L..A__ J" ..o_J
r 4... ~\

"5

1

0

i

Sample Logical Record
Figure 3
Two facts about this format should be mentioned*

First, any-

extra half-words are simply filled out with zeros. Second, the orderof the lists of brothers, sons and cross-references is determined by
the order of the data cards. As nc attempt is made to sort theselists, they may appear in any permutation (e<»g., a list bl, b2, b3 ofbrothers might appear in the order b2, bl, b3) •Finally, although each logical record consists of nl+ 3 words,
it is more efficient to have somewhat larger physical records on tape.
A physical record will contain up to 1000 words. As many logicalrecords as can fit within this limit will be contained in each physicalrecord*A word should be said about the size limitations of SETUP• No
mere than ten cross-references, twenty sons and twenty brothers can beIVaccommodated.

Moreover, as each logical record is limited to 25 words,

only 22 words can be used for these lists. Hence the maximum total
number of sons, brothers, and cross-references must not exceed thislimit.

If the total number of references never exceeds 4-2, no trouble

can arise.
Also, bushes of more than 100 nodes may cause difficulties(in practice, much larger bushes usually can be handled adequately).
If more space is desired the first dimension of each of the following
should be changed:

IND(lOO), NCJ0N(1OO), LCR0(1OO), NCR£)(100,10),NSjeiN(100,20). Neither of these limitations bothers SMART as none of
the trees presently used is complex enough to require any additional
space•

3.

Description of Algorithms Used by SETUP
Most of the work of SETUP is done by a subroutine TRESET,

which is design^ 1 bo Ictermine all the required information about
the tree structure and write it on tape without sorting it or compressing it. TKESET roads the r^ata cards with a subroutine NEWCRD
which is described below.
NEWCRD has five arguments:

NCj0NC, LEVEL, LCRJ0S, NCR0S,

LTEST. These are all used to return information to TRESETj they
are never used to give NEWCRD information. The first argument gives
the concept number and the second its level. The third and fourtharguments are the length of the cross-reference list and the list

XV-8

itself. The fifth argument is a flag indicating whether or not the card
just read was blank.
To determine LEVEL, NEWCRD reads a card (with A-format), character by character, into a vector CARD of dimension 72. Then it looks fornonblank characters in columns 1-70.

If it finds one, it continues tolook until it finds the next blank-column (say, column k).

Then LEVEL

is set at k- 1 to indicate the position of the last digit of the concept
number-If CARD (1-70) is blank, NEWCRD checks column 72. If it too isblank, then the card, is considered blank and NEWCRD returns with LTEST = 0.
If column 72 is not blank, it goes to the next card, adding 70(n- 1) tothe level (when it is on the nth card for this node).
On the nonblank cards, once NEWCRD determines LEVEL, it checks
column 72 for continuations and sets a flag to record the fact. Then it
calls a subroutine REREAD which causes the current card to be read again.
The numbers on the card are then read into a vector NUMB (by means of
SAO G-format).

NUMB(l) becomes NCJ0NC and the vector NCR0S of cross-references is filled from the remaining nonzero entries in NUMB. A
count is kept in LCR0S. If continuations are needed, subsequent cards
are read immediately into NUMB and then transferred into NCR£iS. Afterreading all the continuation cards pertaining to the node, LTEST is set
equal to 1 and NEWCRD returns.
The operation of TRESET is centered around two push-down stores.
One contains the concept number read in before the one that just cameback from NEWCRD. It is referred to as the current-node pushdown
store or P.D.S. 1.

The other contains the concept number of the last

XV

node to qualify as a parent.
store or simply P.D.S.2.

It is called the current parent push-down

Til'-* algorithm used by TitESET can then be out-line^ as follows:(1)

Read iri a no v. card via I'MEWCKD.

If blank, set LEVEL = 0.

(2)

Is it a son of *--he last node before it (i.e. the topof P.D.S.I)?
(a)

If so, push down P.D.S.2 and a"1 the top of
P.D.S.1 to it.

Then ru?>}i down P.D.S.I and put

the new node on top.
(b)
(3)

Then ,jo back to(l).

If no f go on to (.3) .

Is it a son of f n ^ current parent (i.e. th* top of
P.D.S.2)?
(a)If so, push down P.D.S.1 and put ^he new node
on top.

(b)

Go back to (1).

If not, we have the total set of sons of thecurrent parent.

Go on to (4.) for processing.

(4.) Set up a list of sons for the current parent.

Choosenodes from this list one at- a time.
(5)

Process each in turn, taking the remainder of the list
as its brothers.

Namely, pack into a buffer the lengthsof the brother, son and cross-reference lists, together
with the concept number and parent of the chosen nodeand the actual lists.

Every time the buffer is full,write it onto tape and, after clearing it, continue.
(6)

When the whole list of sons has been processed, determineth^ status of the pointer to P.D.S.2.

XV-10(a) If it has not hit the bottom of P.D.S.2, pop up one
level (i.e. lower the pointer) and return to step(3).
(b) If we are at the bottom (i.e. no parents are left
in P.D.S.2), the root, of the bush must be processed.
To do so, its parent is set equal to zero, andafter lowering the pointer beneath the bottom of
P.DeS.2, one must go to step (5) • (This will
only occur if a blank card was read in.)(c) If we have gone through the bottom (i.e. if the rootof the bush has been processed), another card isread*

If it is blank (the second consecutive onel)

the buffer is written on tape and one returns to theprogram.

If not, return is made to (1) to processa new bush.
TRESET writes tapes in the following ways

250 words make up aphysical record. Each physical record is subdivided into ten 25-wordlogical records. Each logical record contains the information as
described in part 2 of this section and is then filled out with zeros.
After calling TRESET, SETUP calls a sorting routine SPECTR,
which breaks up the physical records into their logical components andsorts them in ascending order according to the value of NCJ0NC (which isin the first half of the first word, of the logical record).
A short subroutinep called SQUASH, then removes the extra
zeros at the end of each record (hence, the name) and packs them into
physical records of under 1000 words. This is the final output of
SETUP.

XV-11The THESET and NEWGRD programs are described in Flowcharts 1
and 2, respectively.

4.

The Expansion Programs
The main program of link 10, XPAND, performs the hierarchy andconcept-concept expansions (either or both depending on the parameters
C0NC0N and HIER).

The expansion part of the program assumes that the

document vector tape, the concept-concept correlation tape, and thehierarchy file of the library tape are in order, sorted by concept
numbers. This is always true of the last two of the tapes mentioned.
Thus expansion is essentially a two or three-way mprge along with someformat juggling.
The document vector tape may not have been sorted into concept
order before link 10 is called.

If C0NC0N is on, then link 9 has tosort the document vector tape in order to calculate the correlations(cf. Sec. XIV). In this case, the tape and its number are left for
XPAND, unless only requpsts are to be expanded. In this last case thesorted tape produced by link 9 contains document vectors as well as
request vectors, and thus includes much extraneous information.
Therefore when this optionisactive,XPAND reads the request(and "LIKE") files of tape Bl, and sorts them internally using theroutine SORTDC; this can be done since all the requests must fit intocore. This sorted information is then written out onto a tape which
is used as input for the expansions proper. If only documents are toXV-12

be expanded, the requests are saved on the end of tape kU> since itwould be quite time-consuming to redo the sort already done bylink 9-Note that this permits tape Bl to be used as a scratch

tape if necessary*
If only HIER is on, Bl will not have been sorted. In thiscase, XPAND used the trap-controlled tape sort, SPBCTR, to sort theappropriate files of Bl (unless, again, only requests are to be
expanded so that SORTDC may be used).

Perhaps the following tableclarifies these considerations;
"\.

To be
"\Bxpanded

ALL

DjeJcs

REQS

Method ° ± \ ^Expansion"~~\J

CjeSN«5N

X

X

X

Bl (reqs,docs)

Y (docs)

Y (reqs,docs)

A4. (reqs)
HIER

BtfTH

Bl (reqs,docs)

Bl (reqs,docs)

Bl (reqs,docs)

X

X

X

Bl (reqs,docs)

Y (docs)

Y (reqs,docs)

M (reqs)
The tapes in the boxes are those left by the previous link (except for
the library tape which is not mentioned as it is always available)•
X stands for the concept-concept correlation tape and Y for the conceptordered vector tapeo

Before proceeding to the expansion proper, XPAND must also
figure out what tape is to be used as (temporary) output tape. Because of the large number of possible combination of options, andbecause it is impossible to determine on which tape SPECTR (either
in link 9 or 10) will leave its output, this is not a simple task.
XPAND in fact attempts, during expansion, to perform the difficultfeat of keeping 3 or U tapes (on two channels) in operation
simultaneously. To facilitate what overlap is possible, XPAND
picks the output tape in such a way that the tapes are divided as
evenly as possible between the two channels, either two on each, or
two on one and one on the other.
The following discussion assumes that both the HIER and
G0NC0N indicators are on; if one is off, the procedure is the same
except that the part relevant to the missing option is skipped. The
basic procedure is to read a half-buffer load of input (from thesorted document vector tape) and then to read in as much of thehierarchy followed by the concept-concept tape as is needed to expand
this buffer load.

Output is accumulated in a buffer, supervised bysubroutine LAUGH, and is written out each time a half-buffer isfilled*All input-output is handled by the trap-controlled routine

INOUT (through several interfaces). Each of the four tape operations
involved uses two half-buffers, and before switching half-buffers
and starting a new transmission, the IOEND entry to INOUT is called
to insure that the previous transmission on this particular unit
has been completed•In this way, as much overlap as is possible iseffected with a minimum of bookkeeping on XPAND1s part.

xv-H
The item size on the output tape is two words. 500 items arepacked to a physical record• The format of the item is;
17 18 - 20 21

S12 3
Con No.

T

35
WEIGHT

Doc No.

FLAG

where Con. No. is the 18 bit concept number, Doc. No. is the document
number, WEIGHT is the weight of this concept in document Doc. No., andFLAG is a bit which is on if and only if this item is a document
identifier. In this case, the rest of the entry is BCD and is merely
copied onto the output tape for later use in identification.
During expansion* the weight of an output item is set equal
to the weight of the input concept number which it is expanding. On
expansion
T = 1 for a C0NC0N expansion
T = 2

»

• parent

«

T = 3

"

" brother

»

T = 4

»

" son

»

T a 5

«

« crossreference"

The input concept number is always copied onto the output
tape (with a tag of zero), except if the HIER option calls for
replacement of the items in the original vector by the expanded
items, and C0NC0N is off. These tags are used by programs inlink 8, when the program is called again so that it can weight
each different type of item correctly according to the values of

XV-J^( i n o r ^ e r o f t a g s ) COCCWT, ItQOTWT, bKaNUIT, LEAFWT, and ORQSWT.
XPAND, a t + tin start of the expansion code, i n i t i a l i z e s a l lrelevant input-output an^ the following pointers:IN^ which points

to the next location in input half-buffer number INB which i s to be
used; IHtni which points to the next location in the hierarchy half-buffer
number IHB which is to be used; IG^ which points to the next locationin the concept-concept half-buffer number ICB which is to be used; an^
I0y which points to the next location in the output half-buffer number
IQb which is to be used-

a l l the counts start at their maximum value

and count flown since FuaTKaN arrays are ordered inversely with respect
to tape or^er.
Control then passes to the hierarchy expansion section•The

current element of th« input buffer i s compare^ to the current elementof the hierarchy buffer.
i s called.

If the former is greater, subroutine HIERN

On return, IHQ and IHB point to the appropriate next itemof the hierarchy buffer.

HIERN steps IH^ (by the amount required by

the pointer built into the hierarchy entry, as described in part 2)
anr* checks to see if the buffer has been exhausted; if i t has, i t calls
IOEND, switches IHB and resets IHQ, and starts another read.
If the two concepts match, each of th» four possible hierarchy expansion option weights i s examined in turn, and for each one
that i s nonzero, the appropriate entries are written onto the output
tape*

The pointer to the input buffer i s then advanced as described•in the next paragraph.

XV-16
If the input concept number is less than the hierarchy concept
number, INQ is stepped (down) and a test is made to see whether the
input buffer is finished*

If not, the comparison mentioned above isrepeated.
When the input buffer has been exhausted by the hierarchy
expansion section of code, INQ is reset and a very similar process isperformed for the CONCON expansion. In this case, the operations are
somewhat simplified since there is but one type of expansion to be
performed, and since pointers don't have to be unpacked as they do in
the hierarchy case.
When both hierarchy and concept-concept expansion have been
performed for one input half-buffer, INB is switched, the next input
buffer is read, and processing continues.
If either the hierarchy or concept-concept tape is exhausted
before the input tape is exhausted, switches are set so that therelevant sections of code are no longer executed. At any rate, any
excess on the input tape is copied onto the output tape (unless theoption is HIER replace only).
After the output tape has been completely written, it must be
sorted back into order according first to document number and thenconcept number*This sort sends the document identifier to the endof the expanded document vector, making it possible for MERVEC, inlink 8, to identify the document properly. Again, some care must be
taken in choosing the scratch tapes for the sort. The output tapeniunber of the sort is left in a CCMMON location for MERVEC.

XV

The main subroutine:-- called by X P A N D are:
. (1)INOUT routine- through interfaces ANIBIN, XOBIN,
WAIT2 and '*VAlT3.

(2)

LAUGH (a, B) which enters A and B into the output
buffer and controls output tape operation.

(3)

HIERN which sets pointer IH^ and IHB and controls
the hierarchy tape operations.

(4)

CONIN which sets pointers IC^ and ICB and controls
concept-concept tape operation.

(5)

HUP(I,N,T) which writes onto the output tape (using
LAUGH)

the expansion of the current item in the

input buffers by items in the hierarchy buffer,
starting at index I and proceeding through N packed
words, giving each output item a ta£ o f T.

Thisroutine is used for all hierarchy expansions, except
parent expansion, since the latter, in general,
require a list, rather than a single item, to be
added to the output tape.
Flowchart III describes XP&ND.

IEXPAN = 1 , 2, or 3 according

as requests, documents or all must be expanded*tape number for the expansion proper.
left by link 9-

II is the sorted tape number

IX is the CONCON tape number.

number of the library tape.

ITP is the input

IB5 = 10 is the

INP, dimensioned 2 X 500 X 2 is the input

buffer; the last subscript determines which buffer half is being used.

XV-18NHIB is set to IHIER, the parameter which is 0,1,2 according as HIER
is offc, expand or replace. Note that, if both HIER and C0NC0N are on
and NHIE =* 1, the HIER section puts the input concept number out ontape (but C0NC0N doesnBt since it ought not to be written out twice)•
If the hierarchy is exhausted before the concept-concept tape isterminated, NHIE is set to zero so that G0NC0N will be forced to writeout these concept numbers. LCON, similarly, is set to C0NC0N originally.
If the C0NC0N tape is finished before the hierarchy tape, LCON is set
to zero and NHIE to 1 so that the hierarchy section will continue
writing out the input concept numbers. LI and L2 are switches corresponding to FORTRAN assigned G0 3 s.

IHCNT, ICGNT and ICCNT are set

negative if and only if an end of file is read on the hierarchy,
concept-concept, or input tapes, respectively. INCNT negative will,
therefore terminate the expansion.
Note also that XISTF(N) masks out the low order IS bits of theargument.

XV-19IEJNTERI0

i 3

ihear! i n a car.
with MEWCRD

LEVEL = LTEST*LEVEL)<-.nu<i i n a c a r
with NEWCRDv
I s card blank?_no

LEVEL;LEV(I) ) 2[initialize P.D.S.land P.D.S.2 byset t i ng I=J=Q. . _..

J=J+1
IND(J)=I!l2=IND_£jj

3

yes
Write buffer ontape if it is
not blank.

L_ _>J

1=1+1
LEV(I)=LEVEL
NC0N(I)=NC0NC
LCR0(l)=LCR0S
NCRO(l,L)=NCRQS(L)(For L=1,...,LCR0S)

RETURNIi

Set up lists of sonsand brothers:
LS0N(I2)=I-I2
LBRO=LSON(I2)
KPAB=NC0N(I2)
NS0N(I2,L)=NC0N(I2+L)
NBR0(L)=NS0N(I2,L)(For L=l,...,LBRO)\i/-

LEVEL:LEV(12)

1=12
M=l

A.

P r o c e s s t h e node I\iaR0(l2+M)
by loading t h e l i s t s and.
:their lengths into theibuffer.

;
to=M+le£-Write b u f f e r
onto t a p e .
Clear buffer.

.. i.

I s trie b u f f e r f u l l ?
no(¥ii tiRQ_V-

J=J-l|g-(a>-( J,:Q >b
12=0
LBRO=l
NPAR=0
NBR0(1)=NC0N(1)JI2=IND(J)

Note: Numbers r e f e r
t o t h e numbers of t h e
s t e p s o u t l i n e d on
page 9 .
Program for TRESET
Flowchart 1

17-20
ENTER-©-

LX = 0
READ (CARD(K),K=1,...,72)
K=l

3

(

CARD(Kj;BLANK3
K=K+1

I

(

CARD(K){BLANK ^*C CARD (72);BLANK ^>I

LE7EL=LX+K-1
LCRe)S=l
FLAG1=1

LTEST=0
IRETURN
LX=LX+70

CALL REREAD
FLAGaQ(CARD(72);BLANK > - , =FLAG=1|READ (NUMB(J) t J=l,...,20)
C FLAGlrO>-r-

NCjeiNC=NUMB(l)J=JI
NCReJS(LCR£5S+J)=|^.
NUMB (J)yNUMB(J);0 ^>LCR0S=J-l+LCRdSFLAG1=0|jl=l.
C FLAG; 0^ -LTEST=1

RETURN
Program for NEWCRD
Flowchart 2

READ NEXT CARD INTC(CARD(K),K=1,...,72

XV-21

EWTER

L-

<$
luiflGK - Jo TO L I

or 3

©

.iJJL'IGK ~.U T£5 L2'-1ZRea^ i n one or two f i l e s depending ion whether t h e r e a r e any LIKES on
B l . Sort w i t h SjeiRTDC, s e t
ITP = 5 • Write them out

I n i t i a l i s e ICB,ICQ. Head i n 1 s t
buffer h a l f of con-con from IX,:-t,..rt read of 2 n d .

(?)

1

USEIGW 300 T^ L2;-,A;

uO TO LI "( 1 3 J or 2 30)v<C0NCj0NjiTib

130
Ji*L-

1IW = 500

ITP = IY(G

i,0l - INPU,INw,INB)
LC2 = INP(l,INy,INB)|
3
A.ISTF(LCI): currentv__id r entry

Determine number of f i l e s of Bl t o
be s o r t e d . S o r t B l ; output t a p e ofs o r t becomes ITP*,*LL iilERNIIn'JMTxd®

lEXPAJi^
2
Skip f i l e on BL•V[Determine .vhich t a p e ITP i s t o be

<KLmi^P-rfori,. y p a s s i o n dependent on/ Lues of it£5^;<T,DliAWWT,LEaMT,^ivdSWT u s i n g LaUGH and HUP=^

ASSIGN 130 ?f6 ill

U n i t i a l i z e IHB,IHQj read i n

1st!

j b u f f e r l o a d of h i e r . from I B 5 , I
I s t a r t r e a d of <:nd »[VCJ0NC0N\^

XPAND
Flowchart

3

JfiJ

X5T-22|XNQ = INQ-]
Is input buffer exhausted[Do expansion u s i n g LAUGHJLX.

INQ = INQ-1, is inputj
buffer exhausted

tD

NjeJ

YES
&

tD

JZ
ASSIGN 300 T& L21
LC£JN = 0UHIEi

300 _«iL
Finish read of ITP. Switch
buffer halves, start next
read set NHIE = 1
NCNT:iGj0 Tj0 L2(210,300)

^©

J?
JZ
Finish copying ITP onto JTP
i f necessary

M-

JL.

210 %_

TD[Choose tapes for sort of JTP.
FTP
[End f i l e and rewind appropriate[tapes*-®

INQ = 5001

Or

J&L

Sort JTPj r e s u l t ends up on]tape with number stored in
ff$JT.
RETURN

Flowchart 3 (continued)

I

LCI = INP(2,INQ,INB)
LC2 = INP(1,INQ,INB)