Trailing-Edge
-
PDP-10 Archives
-
decus_20tap5_198111
-
decus/20-0141/datree.for
There are 2 other files named datree.for in the archive. Click here to see a list.
SUBROUTINE DATREE(KLIMB ,KOMPAR,ITYPE ,MINNOD,MAXNOD,
1 NODES ,MINCLM,MAXCLM,NOWCLM,KOLUMN,INITAL,KIND ,
2 NEWCLM)
C RENBR(/NODES IN NEXT LINE OF TREE REPRESENTATION)
C
C DONALD BARTH, HARVARD BUSINESS SCHOOL
C
C ROUTINE TO RETURN THE NODES WHICH WOULD BE IN NEXT
C LINE OF THE REPRESENTATION OF A SIMPLE TREE
C STRUCTURE. THE NODES ARE IDENTIFIED TO CALLING
C PROGRAM BY SUBSCRIPTS, AND ARE NOT REPRESENTED IN A
C FORM WHICH CAN BE DIRECTLY WRITTEN WITH A MULTIPLE OF
C AN A1 FORMAT.
C
C KLIMB = 0, ENTIRE TREE IS TO BE REPRESENTED
C = 1, ONLY PORTION OF TREE STARTING AT NODE
C HAVING IDENTIFICATION NUMBER IN NODES ARRAY
C EQUAL TO INPUT VALUE OF KOMPAR IS TO BE
C REPRESENTED
C KOMPAR = IF KLIMB=1, THEN KOMPAR IS EQUAL TO NUMBER
C IN NODES ARRAY WHICH IDENTIFIES NODE AT BASE
C OF TREE. PORTION OF TREE BELOW THIS NODE
C WILL NOT BE REPRESENTED.
C ITYPE = 0, EACH GROUP IN NODES ARRAY CONSISTS OF
C NUMBER OF ITEMS WHICH ARE IDENTIFIED IN
C GROUP FOLLOWED BY IDENTIFICATION OF CALLING
C ITEM AND THEN BY IDENTIFICATIONS OR SOME OR
C ALL OF ITEMS WHICH IT CALLS. NODES ARRAY IS
C TERMINATED BY GROUP CONTAINING ONLY SINGLE
C ZERO. IF ITEM 10 CALLS 11 AND 12, AND ITEM
C 11 CALLS 12 AND 13, THEN NODES ARRAY WOULD
C CONTAIN
C 3, 10, 11, 12, 3, 11, 12, 13 AND 0
C = 1, EACH GROUP IN NODES ARRAY CONSISTS OF
C NUMBER OF ITEMS IDENTIFIED IN GROUP FOLLOWED
C BY IDENTIFICATION OF ITEM CALLED AND THEN BY
C IDENTIFICATIONS OF SOME OR ALL OF ITEMS
C CALLING IT. NODES ARRAY IS TERMINATED BY
C GROUP CONTAINING ONLY SINGLE ZERO. FOR
C ABOVE EXAMPLE IN WHICH 12 IS CALLED BY BOTH
C 10 AND 11, IN WHICH 11 IS CALLED BY 10 AND
C IN WHICH 13 IS CALLED BY 11, NODES ARRAY
C WOULD CONTAIN
C 3, 12, 10, 11, 2, 11, 10, 2, 13, 11 AND 0
C MINNOD = LOWEST SUBSCRIPT TO USE IN NODES ARRAY
C MAXNOD = DIMENSION OF NODES ARRAY
C NODES = ARRAY CONTAINING NODE IDENTIFIERS
C MINCLM = SUBSCRIPT OF FIRST LOCATION IN KOLUMN ARRAY
C MAXCLM = SUBSCRIPT OF FINAL LOCATION IN KOLUMN ARRAY
C WHICH IS AVAILABLE FOR USE
C NOWCLM = MUST BE SET TO MINCLM-1 BEFORE THIS ROUTINE
C IS FIRST CALLED TO REPRESENT PARTICULAR
C TREE. RETURNED CONTAINING HIGHEST SUBSCRIPT
C USED IN KOLUMN ARRAY TO REPRESENT CURRENT
C LINE AND MUST BE SENT TO SUBSEQUENT CALL OF
C THIS ROUTINE UNCHANGED
C KOLUMN = ARRAY RETURNED CONTAINING SUBSCRIPTS IN
C NODES ARRAY OF THOSE NODES ON CURRENT LINE.
C CONTENTS OF KOLUMN ARRAY MUST BE SENT TO
C SUBSEQUENT CALL OF THIS ROUTINE UNCHANGED.
C CONTENTS OF KOLUMN ARRAY ARE IGNORED WHEN
C THIS ROUTINE IS CALLED WITH NOWCLM LESS THAN
C MINCLM
C INITAL = ARRAY DIMENSIONED SAME AS KOLUMN ARRAY, BUT
C WHICH IS USED ONLY FOR TRANSFER OF VALUES
C FROM ONE CALL OF THIS ROUTINE TO NEXT.
C CONTENTS OF THIS ARRAY MUST NOT BE CHANGED
C BETWEEN CALLS TO THIS ROUTINE UNTIL KIND IS
C RETURNED CONTAINING 1 INDICATING THAT TREE
C HAS BEEN COMPLETED.
C KIND = 1, RETURNED IF REPRESENTATION OF TREE HAD
C BEEN FINISHED BY PREVIOUS CALL
C = 2, LINE IN REPRESENTATION IS BEING RETURNED
C IN KOLUMN(MINCLM) THROUGH AND INCLUDING
C KOLUMN(NOWCLM)
C = 3, SAME AS KIND=2 EXCEPT THAT REPRESENTATION
C IS TERMINATED AT LOOP END
C = 4, SAME AS KIND=2 EXCEPT THAT NOT ALL NODES
C COULD BE REPRESENTED DUE TO TOO LITTLE ROOM
C IN KOLUMN ARRAY
C = 5, KLIMB WAS INPUT CONTAINING 1 AND NOWCLM
C CONTAINING MINCLM-1 INDICATING THAT PARTIAL
C TREE WAS DESIRED, BUT NODE IDENTIFIED BY
C KOMPAR COULD NOT BE FOUND IN NODES ARRAY.
C NO NODES ARE BEING RETURNED IN KOLUMN ARRAY,
C AND NOWCLM IS RETURNED CONTAINING MINCLM-1.
C NEWCLM = RETURNED CONTAINING LOWEST SUSCRIPT OF
C KOLUMN ARRAY WHICH HAS BEEN RETURNED
C CHANGED. INPUT VALUE IS IGNORED
C
DIMENSION NODES(MAXNOD),KOLUMN(MAXCLM),INITAL(MAXCLM)
C
KIND=1
IF(NOWCLM.GE.MINCLM)GO TO 21
NOWCLM=MINCLM-1
NEWCLM=MINCLM
LIMIT=MINNOD
IF(KLIMB.EQ.0)GO TO 3
C
C FIND ROOT IF SPECIFIED BY CALLING PROGRAM
1 ISIZE=NODES(LIMIT)
IF(ISIZE.LE.0)GO TO 25
JTEST=LIMIT
LOWER=LIMIT
LIMIT=LIMIT+ISIZE+1
IF(LIMIT.GT.MAXNOD)GO TO 25
2 LOWER=LOWER+1
IF(LOWER.GE.LIMIT)GO TO 1
IF(NODES(LOWER).NE.KOMPAR)GO TO 2
GO TO 14
C
C FIND NEXT ROOT IF NOT SPECIFIED BY CALLING PROGRAM
3 ISIZE=NODES(LIMIT)
IF(ISIZE.LE.0)GO TO 26
JTEST=LIMIT
LOWER=LIMIT+1
LIMIT=LOWER+ISIZE
IF(LIMIT.GT.MAXNOD)GO TO 26
IF(ITYPE.EQ.0)GO TO 9
IF(ISIZE.LE.1)GO TO 5
4 LOWER=LOWER+1
IF(LOWER.GE.LIMIT)GO TO 3
5 IDNTFY=NODES(LOWER)
6 NODTST=MINNOD
7 ISIZE=NODES(NODTST)
IF(ISIZE.LE.0)GO TO 10
ITEST=NODTST+1
NODTST=ITEST+ISIZE
IF(NODTST.GT.MAXNOD)GO TO 10
IF(ITYPE.EQ.0)GO TO 8
IF(ISIZE.LE.1)GO TO 7
8 IF(NODES(ITEST).NE.IDNTFY)GO TO 7
IF(ITYPE.NE.0)GO TO 4
IF(ITEST.LT.LOWER)GO TO 3
GO TO 14
9 IDNTFY=NODES(LOWER)
10 NODTST=MINNOD
11 ISIZE=NODES(NODTST)
IF(ISIZE.LE.0)GO TO 6
ITEST=NODTST+1
NODTST=ITEST+ISIZE
IF(NODTST.GT.MAXNOD)GO TO 6
IF(ITYPE.EQ.0)GO TO 12
IF(ISIZE.LE.1)GO TO 13
12 ITEST=ITEST+1
IF(ITEST.GE.NODTST)GO TO 11
13 IF(NODES(ITEST).NE.IDNTFY)GO TO 12
IF(ITYPE.EQ.0)GO TO 3
IF(ITEST.LT.LOWER)GO TO 4
C
C INSERT NEW NODE ONTO BRANCH
14 IF(NOWCLM.GE.MAXCLM)GO TO 24
NOWCLM=NOWCLM+1
KOLUMN(NOWCLM)=LOWER
INITAL(NOWCLM)=JTEST
IDNTFY=NODES(LOWER)
LIMIT=MINNOD
KIND=2
C
C CHECK THAT BRANCH DOES NOT CONTAIN A LOOP
J=MINCLM
15 IF(J.GE.NOWCLM)GO TO 16
I=KOLUMN(J)
IF(NODES(I).EQ.NODES(LOWER))GO TO 23
J=J+1
GO TO 15
C
C SEARCH FOR NEXT NODE ALONG BRANCH
16 ISIZE=NODES(LIMIT)
IF(ISIZE.LE.0)GO TO 20
JTEST=LIMIT
LOWER=LIMIT+1
LIMIT=LOWER+ISIZE
IF(LIMIT.GT.MAXNOD)GO TO 20
IF(ITYPE.EQ.0)GO TO 18
ITEST=LOWER
17 ITEST=ITEST+1
IF(ITEST.GE.LIMIT)GO TO 16
IF(NODES(ITEST).NE.IDNTFY)GO TO 17
GO TO 14
18 IF(NODES(LOWER).NE.IDNTFY)GO TO 16
19 LOWER=LOWER+1
IF(LOWER.GE.LIMIT)GO TO 16
GO TO 14
C
C BACK UP TO PREVIOUS NODE IF CURRENT NODE COMPLETED
20 IF(KIND.NE.1)GO TO 26
21 LOWER=KOLUMN(NOWCLM)
JTEST=INITAL(NOWCLM)
LIMIT=JTEST+NODES(JTEST)+1
NEWCLM=NOWCLM
NOWCLM=NOWCLM-1
IF(NOWCLM.LT.MINCLM)GO TO 22
I=KOLUMN(NOWCLM)
IDNTFY=NODES(I)
IF(ITYPE.EQ.0)GO TO 19
GO TO 16
22 IF(KLIMB.NE.0)GO TO 26
IF(ITYPE.EQ.0)GO TO 3
GO TO 4
C
C RETURN TO CALLING PROGRAM
23 KIND=3
GO TO 26
24 KIND=4
GO TO 26
25 KIND=5
26 RETURN
C660045846000
END