Google
 

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