[u/mrichter/AliRoot.git] / GEANT321 / cgpack / cghtre.F

*
* $Id$
*
* $Log$
* Revision 1.1.1.1  1995/10/24 10:19:44  cernlib
* Geant
*
*
#include "geant321/pilot.h"
*CMZ :  3.21/02 29/03/94  15.41.31  by  S.Giani
*-- Author :
      SUBROUTINE CGHTRE(NFACE,DFACE,IORDER,ITREE,ALEFT,ARIGHT)
************************************************************************
*                                                                      *
*     Name: CGHDFA                                                     *
*     Author: E. Chernyaev                       Date:    07.08.88     *
*                                                Revised:              *
*                                                                      *
*     Function: build tree of faces min-max                            *
*                                                                      *
*     References: none                                                 *
*                                                                      *
*     Input: NFACE      - number of faces                              *
*            DFACE(6,*) - min-max of faces                             *
*            IORDER     - work array                                   *
*                                                                      *
*     Output: ITREE(4,*) - tree of faces min-max                       *
*             ALEFT(*)   - min-max of left subtree                     *
*             ARIGHT(*)  - min-max of right subtree                    *
*                                                                      *
*     Errors: none                                                     *
*                                                                      *
************************************************************************
      REAL            DFACE(6,*),ALEFT(*),ARIGHT(*)
      REAL            RNDM(1)
*SG
      INTEGER         IORDER(*),ITREE(4,*)
      INTEGER         INDLFT(5),INDRGT(5)
*SG
      DATA            INDLFT/3,4,5,1,2/,INDRGT/3,4,1,2,1/
*-
      DO 100 I=1,NFACE
        IORDER(I)  = I
  100   CONTINUE
*
**           T R E E   B U I L D
*
      K      = NFACE + 1
      IND    = 0
      JFREE  = 1
      DO 500 I=1,NFACE
        K      = K - 1
        CALL GRNDM(RNDM,1)
        IRNDM  = INT(RNDM(1)*K) + 1
        KF     = IORDER(IRNDM)
        IORDER(IRNDM) = IORDER(K)
        IF (I .EQ. 1)                   GOTO 400
        IT     = 1
  200   JT     = IT
        NF     = ITREE(1,JT)
        IND    = ITREE(4,JT)
        IF (DFACE(IND,KF) .GT. DFACE(IND,NF)) GOTO 300
*             S T E P   T O   L E F T
        INDL    = INDLFT(IND)
        IF (DFACE(INDL,KF) .GT. ALEFT(JT))    ALEFT(JT)=DFACE(INDL,KF)
        IT     = ITREE(2,JT)
        IF (IT .NE. 0)                  GOTO 200
        ITREE(2,JT) = JFREE
        GOTO 400
*             S T E P   T O   R I G H T
  300   INDR    = INDRGT(IND)
        IF (DFACE(INDR,KF) .GT. ARIGHT(JT))   ARIGHT(JT)=DFACE(INDR,KF)
        IT     = ITREE(3,JT)
        IF (IT .NE. 0)                  GOTO 200
        ITREE(3,JT) = JFREE
*             S E T   N E W   T R E E   N O D E
  400   IND    = IND + 1
        IF (IND .EQ. 6)                 IND = 1
        ITREE(1,JFREE) = KF
        ITREE(2,JFREE) = 0
        ITREE(3,JFREE) = 0
        ITREE(4,JFREE) = IND
        ALEFT (JFREE)  =-99999.
        ARIGHT(JFREE)  =-99999.
        JFREE  = JFREE+1
  500   CONTINUE
  999 RETURN
      END
Commit	Line	Data
fe4da5cc	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