GEANT321/cgpack/cghtre.F

   1 *
   2 * $Id$
   3 *
   4 * $Log$
   5 * Revision 1.1.1.1  1995/10/24 10:19:44  cernlib
   6 * Geant
   7 *
   8 *
   9 #include "geant321/pilot.h"
  10 *CMZ :  3.21/02 29/03/94  15.41.31  by  S.Giani
  11 *-- Author :
  12       SUBROUTINE CGHTRE(NFACE,DFACE,IORDER,ITREE,ALEFT,ARIGHT)
  13 ************************************************************************
  14 *                                                                      *
  15 *     Name: CGHDFA                                                     *
  16 *     Author: E. Chernyaev                       Date:    07.08.88     *
  17 *                                                Revised:              *
  18 *                                                                      *
  19 *     Function: build tree of faces min-max                            *
  20 *                                                                      *
  21 *     References: none                                                 *
  22 *                                                                      *
  23 *     Input: NFACE      - number of faces                              *
  24 *            DFACE(6,*) - min-max of faces                             *
  25 *            IORDER     - work array                                   *
  26 *                                                                      *
  27 *     Output: ITREE(4,*) - tree of faces min-max                       *
  28 *             ALEFT(*)   - min-max of left subtree                     *
  29 *             ARIGHT(*)  - min-max of right subtree                    *
  30 *                                                                      *
  31 *     Errors: none                                                     *
  32 *                                                                      *
  33 ************************************************************************
  34       REAL            DFACE(6,*),ALEFT(*),ARIGHT(*)
  35       REAL            RNDM(1)
  36 *SG
  37       INTEGER         IORDER(*),ITREE(4,*)
  38       INTEGER         INDLFT(5),INDRGT(5)
  39 *SG
  40       DATA            INDLFT/3,4,5,1,2/,INDRGT/3,4,1,2,1/
  41 *-
  42       DO 100 I=1,NFACE
  43         IORDER(I)  = I
  44   100   CONTINUE
  45 *
  46 **           T R E E   B U I L D
  47 *
  48       K      = NFACE + 1
  49       IND    = 0
  50       JFREE  = 1
  51       DO 500 I=1,NFACE
  52         K      = K - 1
  53         CALL GRNDM(RNDM,1)
  54         IRNDM  = INT(RNDM(1)*K) + 1
  55         KF     = IORDER(IRNDM)
  56         IORDER(IRNDM) = IORDER(K)
  57         IF (I .EQ. 1)                   GOTO 400
  58         IT     = 1
  59   200   JT     = IT
  60         NF     = ITREE(1,JT)
  61         IND    = ITREE(4,JT)
  62         IF (DFACE(IND,KF) .GT. DFACE(IND,NF)) GOTO 300
  63 *             S T E P   T O   L E F T
  64         INDL    = INDLFT(IND)
  65         IF (DFACE(INDL,KF) .GT. ALEFT(JT))    ALEFT(JT)=DFACE(INDL,KF)
  66         IT     = ITREE(2,JT)
  67         IF (IT .NE. 0)                  GOTO 200
  68         ITREE(2,JT) = JFREE
  69         GOTO 400
  70 *             S T E P   T O   R I G H T
  71   300   INDR    = INDRGT(IND)
  72         IF (DFACE(INDR,KF) .GT. ARIGHT(JT))   ARIGHT(JT)=DFACE(INDR,KF)
  73         IT     = ITREE(3,JT)
  74         IF (IT .NE. 0)                  GOTO 200
  75         ITREE(3,JT) = JFREE
  76 *             S E T   N E W   T R E E   N O D E
  77   400   IND    = IND + 1
  78         IF (IND .EQ. 6)                 IND = 1
  79         ITREE(1,JFREE) = KF
  80         ITREE(2,JFREE) = 0
  81         ITREE(3,JFREE) = 0
  82         ITREE(4,JFREE) = IND
  83         ALEFT (JFREE)  =-99999.
  84         ARIGHT(JFREE)  =-99999.
  85         JFREE  = JFREE+1
  86   500   CONTINUE
  87   999 RETURN
  88       END