| 1 |
C Copyright(C) 1999-2020 National Technology & Engineering Solutions |
| 2 |
C of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with |
| 3 |
C NTESS, the U.S. Government retains certain rights in this software. |
| 4 |
C |
| 5 |
C See packages/seacas/LICENSE for details |
| 6 |
|
| 7 |
SUBROUTINE SRCHGE( LBLK,NE,X,IND,XV,IMIN,IMAX,NDIM,I, |
| 8 |
* IL,IU,IT,INDX1,INDX2,XTST ) |
| 9 |
|
| 10 |
C----------------------------------------------------------------------- |
| 11 |
|
| 12 |
C DESCRIPTION: |
| 13 |
|
| 14 |
C PERFORM A BINARY SEARCH TO FIND THE ELEMENT NUMBER I |
| 15 |
C OF A SORTED ARRAY FOR WHICH ALL ELEMENTS AT I OR ABOVE ARE |
| 16 |
C GREATER OR EQUAL TO THAN SOME VALUE XV, |
| 17 |
C WHILE ALL ELEMENTS BELOW I ARE LESS THAN THE VALUE. |
| 18 |
|
| 19 |
C X(I-2) X(I-1) X(I) X(I+1) X(I+2) |
| 20 |
C XV X> |
| 21 |
|
| 22 |
C ASSUMED THAT THE ARRAY X HAS BEEN SORTED IN INCREASING ORDER, |
| 23 |
C BUT THE ELEMENTS HAVE NOT BEEN MOVED. |
| 24 |
C THE SORTED LIST IS DETERMINED BY THE ARRAY INDX, |
| 25 |
C WHICH POSITIONS THE ORIGINAL UNSORTED X ARRAY ELEMENTS |
| 26 |
C IN THE SORTED LIST. THUS, THE 5TH ELEMENT IN THE SORTED LIST IS |
| 27 |
C X(IND(5)) |
| 28 |
|
| 29 |
C----------------------------------------------------------------------- |
| 30 |
|
| 31 |
C INPUT: |
| 32 |
|
| 33 |
C X - ARRAY IN UNSORTED ORDER |
| 34 |
C IND - INDEX ARRAY GIVING THE ELEMENT ORDER IN THE SORTED LIST |
| 35 |
C XV - X VALUE TO TEST AGAINST |
| 36 |
C IMIN - THE LOWEST NUMBERED POSITION IN THE SORTED LIST TO TEST |
| 37 |
C IMAX - THE HIGHEST NUMBERED POSITION IN THE SORTED LIST TO TEST |
| 38 |
C NDIM - THE DIMENSION OF THE ARRAYS |
| 39 |
|
| 40 |
C OUTPUT: |
| 41 |
|
| 42 |
C I - THE FIRST POSITION IN THE SORTED LIST .GT. XV |
| 43 |
|
| 44 |
C SCRATCH: |
| 45 |
|
| 46 |
C IL |
| 47 |
C IU |
| 48 |
C IT |
| 49 |
C INDX1 |
| 50 |
C INDX2 |
| 51 |
C XTST |
| 52 |
|
| 53 |
C----------------------------------------------------------------------- |
| 54 |
|
| 55 |
DIMENSION |
| 56 |
* X(NDIM), IND(NDIM), XV(LBLK), I(LBLK) |
| 57 |
DIMENSION |
| 58 |
* IL(LBLK),IU(LBLK),IT(LBLK),INDX1(LBLK),INDX2(LBLK), |
| 59 |
* XTST(LBLK) |
| 60 |
|
| 61 |
IF (IMAX.EQ.0.OR.NDIM.EQ.0) THEN |
| 62 |
DO J = 1, NE |
| 63 |
I(J) = 0 |
| 64 |
ENDDO |
| 65 |
RETURN |
| 66 |
ENDIF |
| 67 |
DO 25 J = 1, NE |
| 68 |
IL(J) = IMIN |
| 69 |
IU(J) = IMAX |
| 70 |
INDX1(J) = J |
| 71 |
25 CONTINUE |
| 72 |
ILOOP = NE |
| 73 |
1000 CONTINUE |
| 74 |
|
| 75 |
DO 50 JJ = 1, ILOOP |
| 76 |
INDX2(JJ) = INDX1(JJ) |
| 77 |
J = INDX1(JJ) |
| 78 |
IT(J) = (IU(J) + IL(J)) / 2 |
| 79 |
50 CONTINUE |
| 80 |
DO 35 J = 1, NE |
| 81 |
XTST(J) = X( IND(IT(J)) ) |
| 82 |
35 CONTINUE |
| 83 |
|
| 84 |
IF ( ILOOP .GT. 64) THEN |
| 85 |
|
| 86 |
ILP = 0 |
| 87 |
DO 60 JJ = 1, ILOOP |
| 88 |
J = INDX2(JJ) |
| 89 |
IF( XTST(J) .LT. XV(J) )THEN |
| 90 |
IL(J) =IT(J) + 1 |
| 91 |
ELSE |
| 92 |
IU(J) =IT(J) - 1 |
| 93 |
ENDIF |
| 94 |
IF( IL(J) .LE. IU(J)) THEN |
| 95 |
ILP = ILP + 1 |
| 96 |
INDX1(ILP) = J |
| 97 |
ENDIF |
| 98 |
60 CONTINUE |
| 99 |
ELSE |
| 100 |
|
| 101 |
ILP = 0 |
| 102 |
DO 51 JJ = 1, ILOOP |
| 103 |
J = INDX2(JJ) |
| 104 |
IF( XTST(J) .LT. XV(J) )THEN |
| 105 |
IL(J) =IT(J) + 1 |
| 106 |
ELSE |
| 107 |
IU(J) =IT(J) - 1 |
| 108 |
ENDIF |
| 109 |
IF( IL(J) .LE. IU(J)) THEN |
| 110 |
ILP = ILP + 1 |
| 111 |
INDX1(ILP) = J |
| 112 |
ENDIF |
| 113 |
51 CONTINUE |
| 114 |
ENDIF |
| 115 |
|
| 116 |
ILOOP = ILP |
| 117 |
|
| 118 |
IF(ILOOP .NE. 0 )GO TO 1000 |
| 119 |
C RANGE HAD NARROWED TO 1 LOCATION. HOWEVER, THE POINT LAST TESTED |
| 120 |
C COULD BE ABOVE, BELOW, OR ON THE SEARCH POINT. CHECK FOR PROPER CASE |
| 121 |
DO 200 J = 1, NE |
| 122 |
IF( XTST(J) .LT. XV(J) )THEN |
| 123 |
I(J) = IT(J) + 1 |
| 124 |
ELSE |
| 125 |
I(J) = IT(J) |
| 126 |
ENDIF |
| 127 |
200 CONTINUE |
| 128 |
|
| 129 |
RETURN |
| 130 |
END |