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