1 /* lstlti.f -- translated by f2c (version 19980913).
2 You must link the resulting object file with the libraries:
3 -lf2c -lm (in that order)
4 */
5
6 #include "f2c.h"
7
8 /* $Procedure LSTLTI ( Last integer element less than ) */
lstlti_(integer * x,integer * n,integer * array)9 integer lstlti_(integer *x, integer *n, integer *array)
10 {
11 /* System generated locals */
12 integer ret_val;
13
14 /* Local variables */
15 integer j, begin, items, middle, end;
16
17 /* $ Abstract */
18
19 /* Given a number X and an array of non-decreasing numbers, */
20 /* find the index of the largest array element less than X. */
21
22 /* $ Disclaimer */
23
24 /* THIS SOFTWARE AND ANY RELATED MATERIALS WERE CREATED BY THE */
25 /* CALIFORNIA INSTITUTE OF TECHNOLOGY (CALTECH) UNDER A U.S. */
26 /* GOVERNMENT CONTRACT WITH THE NATIONAL AERONAUTICS AND SPACE */
27 /* ADMINISTRATION (NASA). THE SOFTWARE IS TECHNOLOGY AND SOFTWARE */
28 /* PUBLICLY AVAILABLE UNDER U.S. EXPORT LAWS AND IS PROVIDED "AS-IS" */
29 /* TO THE RECIPIENT WITHOUT WARRANTY OF ANY KIND, INCLUDING ANY */
30 /* WARRANTIES OF PERFORMANCE OR MERCHANTABILITY OR FITNESS FOR A */
31 /* PARTICULAR USE OR PURPOSE (AS SET FORTH IN UNITED STATES UCC */
32 /* SECTIONS 2312-2313) OR FOR ANY PURPOSE WHATSOEVER, FOR THE */
33 /* SOFTWARE AND RELATED MATERIALS, HOWEVER USED. */
34
35 /* IN NO EVENT SHALL CALTECH, ITS JET PROPULSION LABORATORY, OR NASA */
36 /* BE LIABLE FOR ANY DAMAGES AND/OR COSTS, INCLUDING, BUT NOT */
37 /* LIMITED TO, INCIDENTAL OR CONSEQUENTIAL DAMAGES OF ANY KIND, */
38 /* INCLUDING ECONOMIC DAMAGE OR INJURY TO PROPERTY AND LOST PROFITS, */
39 /* REGARDLESS OF WHETHER CALTECH, JPL, OR NASA BE ADVISED, HAVE */
40 /* REASON TO KNOW, OR, IN FACT, SHALL KNOW OF THE POSSIBILITY. */
41
42 /* RECIPIENT BEARS ALL RISK RELATING TO QUALITY AND PERFORMANCE OF */
43 /* THE SOFTWARE AND ANY RELATED MATERIALS, AND AGREES TO INDEMNIFY */
44 /* CALTECH AND NASA FOR ALL THIRD-PARTY CLAIMS RESULTING FROM THE */
45 /* ACTIONS OF RECIPIENT IN THE USE OF THE SOFTWARE. */
46
47 /* $ Required_Reading */
48
49 /* None. */
50
51 /* $ Keywords */
52
53 /* SEARCH, ARRAY */
54
55 /* $ Declarations */
56 /* $ Brief_I/O */
57
58 /* VARIABLE I/O DESCRIPTION */
59 /* -------- --- -------------------------------------------------- */
60 /* X I Value to search against. */
61 /* ARRAY I Array of possible lower bounds. */
62 /* N I Number elements in ARRAY. */
63 /* LSTLTI O the index of the last element of ARRAY < X. */
64
65 /* $ Detailed_Input */
66
67 /* X Integer for which one desires to find */
68 /* the last ARRAY element less than X. */
69
70 /* N Total number of elements in ARRAY. */
71
72 /* ARRAY Array of integers that forms a */
73 /* non-decreasing sequence. We will find the last element */
74 /* of the sequence that is less than X. */
75
76 /* $ Detailed_Output */
77
78 /* LSTLTI Index of the last element of the non-decreasing sequence: */
79 /* {ARRAY(I) : 0 < I < N + 1} that is less than X. */
80 /* (Note that LSTLTI = I for some I in the range 1 to */
81 /* N unless X is less than or equal to all of these */
82 /* elements, in which case LSTLTI = 0.) */
83
84 /* In the case that N is input with value less than or equal */
85 /* to zero, LSTLTI is returned as zero. */
86
87 /* $ Parameters */
88
89 /* None. */
90
91 /* $ Particulars */
92
93
94 /* An array of integers is given. The array */
95 /* ARRAY(I) (0 < I < N+1 ) forms a non-decreasing sequence of */
96 /* numbers. Given a real number X, there will be a last one of */
97 /* these numbers that is less than X. This routine */
98 /* finds the index LSTLTI such that ARRAY(LSTLTI) is that number. */
99
100 /* If X is not greater than ARRAY(1), INDEX will be set to zero. */
101
102 /* This routine uses a binary search algorithm and so requires */
103 /* at most LOG_2(N) steps to find the value of LSTLTI. */
104
105 /* Note: If you need to find the first element of the array that */
106 /* is greater than or equal to X, simply add 1 to the */
107 /* result returned by this function and check to see if the */
108 /* result is within the array bounds given by N. */
109
110 /* $ Examples */
111
112 /* Suppose that you have an reasonably large ordered array of */
113 /* integers, into which you want to insert a few more without */
114 /* destroying the ordering. */
115
116 /* Depending upon your application, it may be desirable to */
117 /* not insert duplicates, to insert duplicates before */
118 /* existing entries or to insert them after existing entries. */
119
120 /* The code fragment below, illustrates an insertion scheme */
121 /* that will insert duplicate items before existing items */
122 /* and simultaneously update a second parallel array of */
123 /* double precision numbers. */
124
125 /* get the pair to insert */
126
127 /* READ (*,*) KEY, VALUE */
128
129 /* locate the place to insert the new KEY into the sorted */
130 /* array of keys. */
131
132 /* LOC = LSTLTI ( KEY, NKEYS, KEYS ) + 1 */
133
134 /* insert the key and its associated value into the */
135 /* KEYS and VALUES arrays at location LOC */
136
137 /* CALL INSLAI ( KEY, 1, LOC, NKEYS, KEYS ) */
138 /* CALL INSLAD ( VALUE, 1, LOC, NVALS, VALUES ) */
139
140 /* If at the READ statement the arrays KEYS and VALUES looked like: */
141
142 /* KEYS VALUES NKEYS = 6, NVALS = 6 */
143 /* ---- ------- */
144 /* 2 3.00D0 */
145 /* 5 1.00D0 */
146 /* 7 3.14D0 */
147 /* 16 7.11D0 */
148 /* 18 2.14D0 */
149 /* 23 12.12D0 */
150
151 /* and 9 and 33.33D3 were read into KEY and VALUE respectively */
152 /* then LSTLEI (KEY, NKEYS, KEYS ) would be 3 and LOC would be 4. */
153 /* After the calls to the routines INSLAI and INSLAD we would have */
154
155 /* KEYS VALUES NKEYS = 7, NVALS = 7 */
156 /* ---- ------- */
157 /* 2 3.00D0 */
158 /* 5 1.00D0 */
159 /* 7 3.14D0 */
160 /* 9 33.33D3 <===== inserted items. */
161 /* 16 7.11D0 */
162 /* 18 2.14D0 */
163 /* 23 12.12D0 */
164
165 /* If 7 and 33.33D3 were read into KEY and VALUE respectively */
166 /* then again LSTLEI (KEY, NKEYS, KEYS ) would be 2 and LOC would */
167 /* be 3. After the calls to the routines INSLAI and INSLAD we */
168 /* would have: */
169
170 /* KEYS VALUES NKEYS = 7, NVALS = 7 */
171 /* ---- ------- */
172 /* 2 3.00D0 */
173 /* 5 1.00D0 */
174 /* 7 33.33D3 <===== inserted items. */
175 /* 7 3.14D0 */
176 /* 16 7.11D0 */
177 /* 18 2.14D0 */
178 /* 23 12.12D0 */
179
180 /* If we replaced the line of code */
181
182 /* LOC = LSTLTI ( KEY, NKEYS, KEYS ) + 1 */
183 /* by */
184
185 /* LOC = LSTLEI ( KEY, NKEYS, KEYS ) + 1 */
186
187 /* we would obtain a routine that inserted duplicates before */
188 /* existing entries. (LSTLEI is similar to LSTLTI except it finds */
189 /* the last occurrance of an integer less than or equal to a value.) */
190 /* Using 7 and 33.33D3 for KEY and VALUE again, the modified code */
191 /* fragment would yield the results shown below. */
192
193 /* KEYS VALUES NKEYS = 7, NVALS = 7 */
194 /* ---- ------- */
195 /* 2 3.00D0 */
196 /* 5 1.00D0 */
197 /* 7 3.14D0 */
198 /* 7 33.33D3 <===== inserted items. */
199 /* 16 7.11D0 */
200 /* 18 2.14D0 */
201 /* 23 12.12D0 */
202
203
204 /* Note: you should NOT use the code outlined above as the basis of */
205 /* a sorting algorithm. The NAIF routines SHELLI, SHELLD, SHELLC, */
206 /* ORDERI, ORDERD, ORDERC, REORDI, REORDD and REORDC are much more */
207 /* efficient routines for sorting arrays or sorting a set of */
208 /* parallel arrays using one of the set as a key. The fragment */
209 /* presented here is useful for performing update insertions into */
210 /* previously ordered arrays. */
211
212 /* For more ideas regarding the use of this routine, see LSTLEC */
213 /* and LSTLTC */
214
215 /* $ Restrictions */
216
217 /* If the sequence is not non-decreasing, the program will run */
218 /* to completion but the index found will not mean anything. */
219
220 /* $ Exceptions */
221
222 /* Error free. */
223
224 /* $ Files */
225
226 /* None. */
227
228 /* $ Author_and_Institution */
229
230 /* H.A. Neilan (JPL) */
231 /* W.L. Taber (JPL) */
232
233 /* $ Literature_References */
234
235 /* None. */
236
237 /* $ Version */
238
239 /* - SPICELIB Version 1.0.1, 10-MAR-1992 (WLT) */
240
241 /* Comment section for permuted index source lines was added */
242 /* following the header. */
243
244 /* - SPICELIB Version 1.0.0, 31-JAN-1990 (WLT) */
245
246 /* -& */
247 /* $ Index_Entries */
248
249 /* last integer element less_than */
250
251 /* -& */
252 /* $ Revisions */
253
254 /* - Beta Version 1.1.0, 9-MAR-1989 (HAN) */
255
256 /* Declaration of the variable I was removed from the code. The */
257 /* variable was declared but not used. */
258
259 /* - Beta Version 1.0.1, 1-FEB-1989 (WLT) */
260
261 /* Example section of header upgraded. */
262
263 /* -& */
264
265 /* Local variables */
266
267 items = *n;
268 begin = 1;
269 end = *n;
270 if (*n <= 0) {
271
272 /* There's nobody home---that is there is nothing in the array */
273 /* to compare against. Zero is the only sensible thing to return */
274
275 ret_val = 0;
276 } else if (*x <= array[begin - 1]) {
277
278 /* None of the array elements are less than X */
279
280 ret_val = 0;
281 } else if (array[end - 1] < *x) {
282
283 /* X is greater than all elements of the array. Thus the last */
284 /* element of the array is the last item less than X. */
285
286 ret_val = end;
287 } else {
288
289 /* X lies between some pair of elements of the array */
290
291 while(items > 2) {
292 j = items / 2;
293 middle = begin + j;
294 if (array[middle - 1] < *x) {
295 begin = middle;
296 } else {
297 end = middle;
298 }
299 items = end - begin + 1;
300 }
301 ret_val = begin;
302 }
303 return ret_val;
304 } /* lstlti_ */
305
306