Debian Codegraph @

packages/seacas/applications/nem_slice/elb_util.C

raw
1 /*
2 * Copyright(C) 1999-2024 National Technology & Engineering Solutions
3 * of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with
4 * NTESS, the U.S. Government retains certain rights in this software.
5 *
6 * See packages/seacas/LICENSE for details
7 */
8
9 /*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
10 *----------------------------------------------------------------------------
11 * Functions contained in this file:
12 * token_compare()
13 * strip_string()
14 * string_to_lower()
15 * clean_string()
16 * sort2()
17 * sort3()
18 * find_first_last()
19 * find_int()
20 * in_list()
21 * roundfloat()
22 * find_max()
23 * find_min()
24 * find_inter()
25 *+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
26 #include "elb_util.h"
27 #include <cassert> // for assert
28 #include <cctype> // for isupper, tolower
29 #include <cmath> // for ceil, floor
30 #include <cstddef> // for size_t
31 #include <cstring> // for strlen
32 #include <fmt/ostream.h>
33
34 /*****************************************************************************/
35 /*****************************************************************************/
36 /*****************************************************************************/
37 int token_compare(char *token, const char *key)
38 {
39
40 size_t kcnt = 0;
41
42 size_t key_len = strlen(key);
43
44 for (size_t i1 = 0; i1 < strlen(token); i1++) {
45 if (isupper(token[i1]) != 0) {
46 token[i1] = tolower(token[i1]);
47 }
48
49 if (token[i1] != ' ') {
50 if (token[i1] == key[kcnt]) {
51 kcnt++;
52 if (kcnt > key_len) {
53 return 0;
54 }
55 }
56 else {
57 return 0;
58 }
59 }
60 if (key[kcnt] == ' ') {
61 kcnt++;
62 }
63 }
64
65 if (kcnt == strlen(key)) {
66 return 1;
67 }
68 return 0;
69 } /*--------------End token_compare()-----------*/
70
71 /*****************************************************************************/
72 /*****************************************************************************/
73 /*****************************************************************************/
74 void strip_string(char inp_str[], const char *tokens)
75 {
76 int i = 0;
77 int ntokes = strlen(tokens);
78
79 while (inp_str[i] != '\0') {
80 int bval = 0;
81 for (int itok = 0; itok < ntokes; itok++) {
82 if (inp_str[i] == tokens[itok]) {
83 i++;
84 bval = 1;
85 break; /* out of for loop */
86 }
87 }
88 if (bval == 0) {
89 break; /* out of while loop */
90 }
91 }
92
93 /* Move real part of string to the front */
94 int j = 0;
95 while (inp_str[j + i] != '\0') {
96 inp_str[j] = inp_str[j + i];
97 j++;
98 }
99 inp_str[j] = inp_str[j + i];
100 j--;
101
102 /* Remove trailing tokens */
103 while (j != -1) {
104 int bval = 0;
105 for (int itok = 0; itok < ntokes; itok++) {
106 if (inp_str[j] == tokens[itok]) {
107 bval = 1;
108 j--;
109 break; /* out of for loop */
110 }
111 }
112 if (bval == 0) {
113 break; /* out of while loop */
114 }
115 }
116
117 inp_str[j + 1] = '\0';
118 }
119
120 /*****************************************************************************/
121 /*****************************************************************************/
122 /*****************************************************************************/
123 void string_to_lower(char in_string[], char cval)
124 {
125 int len = strlen(in_string);
126 for (int cnt = 0; cnt < len; cnt++) {
127 if (in_string[cnt] == cval) {
128 return;
129 }
130
131 if (isupper(in_string[cnt]) != 0) {
132 in_string[cnt] = tolower(in_string[cnt]);
133 }
134 }
135 }
136
137 /*****************************************************************************/
138 /*****************************************************************************/
139 /*****************************************************************************/
140 void clean_string(char inp_str[], const char *tokens)
141 {
142 int ntokes = strlen(tokens);
143 int inplen = strlen(inp_str);
144
145 int i = 0;
146 int bval = 0;
147 while (inp_str[i] != '\0') {
148 for (int itok = 0; itok < ntokes; itok++) {
149 if (i < 0) {
150 i = 0;
151 }
152 if (inp_str[i] == tokens[itok]) {
153 /* Find out if the next character is also a token */
154 for (int j = 0; j < ntokes; j++) {
155 if (inp_str[i + 1] == tokens[j]) {
156 bval = 1;
157 break;
158 }
159 }
160
161 if (bval == 1) {
162 for (int j = i + 1; j < inplen; j++) {
163 inp_str[j] = inp_str[j + 1];
164 }
165
166 inplen--;
167 bval = 0;
168 i--;
169 }
170 }
171 }
172
173 i++;
174
175 } /* End "while(inp_str[i] != '\0')" */
176
177 } /*---------------- End clean_string() -----------------*/
178
179 namespace {
180 /*
181 * The following 'qsort' routine is modified from Sedgewicks
182 * algorithm It selects the pivot based on the median of the left,
183 * right, and center values to try to avoid degenerate cases occurring
184 * when a single value is chosen. It performs a quicksort on
185 * intervals down to the GDS_QSORT_CUTOFF size and then performs a final
186 * insertion sort on the almost sorted final array. Based on data in
187 * Sedgewick, the GDS_QSORT_CUTOFF value should be between 5 and 20.
188 *
189 * See Sedgewick for further details
190 */
191
192 #define GDS_QSORT_CUTOFF 12
193
194 template <typename INT> inline void ISWAP(INT *V, size_t I, size_t J)
195 {
196 INT _t = V[I];
197 V[I] = V[J];
198 V[J] = _t;
199 }
200
201 template <typename INT> size_t gds_median3(INT v[], size_t left, size_t right)
202 {
203 size_t center;
204 center = (left + right) / 2;
205
206 if (v[left] > v[center]) {
207 ISWAP(v, left, center);
208 }
209 if (v[left] > v[right]) {
210 ISWAP(v, left, right);
211 }
212 if (v[center] > v[right]) {
213 ISWAP(v, center, right);
214 }
215
216 ISWAP(v, center, right - 1);
217 return right - 1;
218 }
219
220 template <typename INT> void gds_qsort(INT v[], size_t left, size_t right)
221 {
222 if (left + GDS_QSORT_CUTOFF <= right) {
223 size_t pivot = gds_median3(v, left, right);
224 size_t i = left;
225 size_t j = right - 1;
226
227 for (;;) {
228 while (v[++i] < v[pivot]) {
229 ;
230 }
231 while (v[--j] > v[pivot]) {
232 ;
233 }
234 if (i < j) {
235 ISWAP(v, i, j);
236 }
237 else {
238 break;
239 }
240 }
241
242 ISWAP(v, i, right - 1);
243 gds_qsort(v, left, i - 1);
244 gds_qsort(v, i + 1, right);
245 }
246 }
247
248 template <typename INT> void gds_isort(INT v[], size_t N)
249 {
250 if (N <= 1) {
251 return;
252 }
253
254 size_t ndx = 0;
255 INT small_val = v[0];
256 for (size_t i = 1; i < N; i++) {
257 if (v[i] < small_val) {
258 small_val = v[i];
259 ndx = i;
260 }
261 }
262 /* Put smallest value in slot 0 */
263 ISWAP(v, 0, ndx);
264
265 size_t j;
266 for (size_t i = 1; i < N; i++) {
267 INT tmp = v[i];
268 for (j = i; tmp < v[j - 1]; j--) {
269 v[j] = v[j - 1];
270 }
271 v[j] = tmp;
272 }
273 }
274
275 template <typename INT> void siftDowniii(INT *a, INT *b, INT *c, size_t start, size_t end)
276 {
277 size_t root = start;
278 while (root * 2 + 1 < end) {
279 size_t child = 2 * root + 1;
280 if ((child + 1 < end) &&
281 (a[child] < a[child + 1] || (a[child] == a[child + 1] && b[child] < b[child + 1]))) {
282 child += 1;
283 }
284 if (a[root] < a[child]) {
285 SWAP(a[child], a[root]);
286 SWAP(b[child], b[root]);
287 SWAP(c[child], c[root]);
288 root = child;
289 }
290 else {
291 return;
292 }
293 }
294 }
295
296 #ifndef NDEBUG
297 template <typename INT> void assert_sorted(INT *vector, size_t vecsize)
298 {
299 for (size_t i = 1; i < vecsize; i++) {
300 assert(vector[i - 1] <= vector[i]);
301 }
302 }
303 #endif
304 } // namespace
305
306 /*****************************************************************************
307 * Function to find the first and last entries of a given value that are
308 * consecutively present in an integer array.
309 * ASSUMES that 'vector' is sorted....
310 *****************************************************************************/
311 template void find_first_last(int val, size_t vecsize, int *vector, int *first, int *last);
312 template void find_first_last(int64_t val, size_t vecsize, int64_t *vector, int64_t *first,
313 int64_t *last);
314
315 template <typename INT>
316 void find_first_last(INT val, size_t vecsize, INT *vector, INT *first, INT *last)
317 {
318 #ifndef NDEBUG
319 assert_sorted(vector, vecsize);
320 #endif
321
322 *first = -1;
323 *last = -1;
324
325 /* See if value is in the vector */
326 int64_t i = bin_search2(val, vecsize, vector);
327 *first = i; /* Save this location */
328
329 if (i != -1) {
330 /* Value is in vector, find first occurrence */
331 while (i >= 0 && vector[i] == val) {
332 i--;
333 }
334 i++;
335
336 *last = *first; /* Use saved location */
337 *first = i;
338
339 size_t ii;
340 for (ii = (*last); ii < vecsize; ii++) {
341 if (vector[ii] != val) {
342 *last = ii - 1;
343 break;
344 }
345 }
346
347 if (ii == vecsize) {
348 *last = vecsize - 1;
349 }
350 }
351 }
352
353 /*****************************************************************************
354 * Find the value in the integer array. Return -1 if not found.
355 * New 1/21/97: change this so that it cross references a second
356 * array with a second value
357 *****************************************************************************/
358 template <typename INT>
359 int64_t find_int(INT value1, INT value2, size_t start, size_t stop, INT *vector1, INT *vector2)
360 {
361 for (size_t i = start; i <= stop; i++) {
362 if ((vector1[i] == value1) && (vector2[i] == value2)) {
363 return i;
364 }
365 }
366 return -1;
367 }
368
369 /*****************************************************************************/
370 /*****************************************************************************/
371 /*****************************************************************************/
372 /* Function in_list() begins:
373 *----------------------------------------------------------------------------
374 * This function searches a vector for the input value. If the value is
375 * found in the vector then it's index in that vector is returned, otherwise
376 * the function returns -1;
377 *****************************************************************************/
378 template int64_t in_list(int value, size_t count, const int *vector);
379 template int64_t in_list(int64_t value, size_t count, const int64_t *vector);
380 template int64_t in_list(int value, size_t count, const int64_t *vector);
381 template int64_t in_list(int64_t value, size_t count, const int *vector);
382
383 template <typename INT, typename INT2> int64_t in_list(INT value, size_t count, const INT2 *vector)
384 {
385 for (size_t i = 0; i < count; i++) {
386 if (vector[i] == value) {
387 return i;
388 }
389 }
390 return -1;
391 }
392
393 template int64_t in_list(int value, const std::vector<int> &vector);
394 template int64_t in_list(int64_t value, const std::vector<int64_t> &vector);
395 template int64_t in_list(int value, const std::vector<int64_t> &vector);
396 template int64_t in_list(int64_t value, const std::vector<int> &vector);
397
398 template <typename INT, typename INT2> int64_t in_list(INT value, const std::vector<INT2> &vector)
399 {
400 size_t count = vector.size();
401 for (size_t i = 0; i < count; i++) {
402 if (vector[i] == value) {
403 return i;
404 }
405 }
406 return -1;
407 }
408
409 /*****************************************************************************/
410 /*****************************************************************************/
411 /*****************************************************************************/
412 /* Function roundfloat() begins:
413 *----------------------------------------------------------------------------
414 * This function rounds off the float "value" to the nearest integer,
415 * and returns that integer.
416 *****************************************************************************/
417 int roundfloat(float value)
418 {
419 float high = std::ceil(value);
420 float low = std::floor(value);
421
422 int ans;
423 if ((value - low) < (high - value)) {
424 ans = static_cast<int>(low);
425 }
426 else {
427 ans = static_cast<int>(high);
428 }
429
430 return ans;
431 }
432
433 /*****************************************************************************/
434 /*****************************************************************************/
435 /*****************************************************************************/
436 /* Function find_inter() begins:
437 *----------------------------------------------------------------------------
438 * This function finds the intersection between two lists of integer values,
439 * and returns the number of values in the intersection.
440 *****************************************************************************/
441 template <typename INT>
442 size_t find_inter(const INT set1[], /* the first set of integers */
443 const INT set2[], /* the second set of integers */
444 size_t length1, /* the length of the first set */
445 size_t length2, /* the length of the second set */
446 INT inter_ptr[]) /* the values in the intersection */
447 /*
448 *
449 * Function which finds the intersection of two integer lists.
450 * The points in set1 that belong in the intersection set are
451 * returned in the vector inter_pts, starting at position inter_pts[0].
452 * Enough space in inter_pts[] (min(length1, length2)) must
453 * have already been allocated in the calling program before this
454 * function is called.
455 *
456 * Know that set1 and set2 are monotonically increasing
457 *
458 * On return, find_inter returns 0 if there is no intersection.
459 * It returns the number of points in the intersection, if there
460 * is an intersection.
461 */
462
463 {
464 size_t counter = 0;
465 size_t i = 0;
466 size_t j = 0;
467
468 while (i < length1 && j < length2) {
469 if (set1[i] < set2[j]) {
470 ++i;
471 }
472 else if (set2[j] < set1[i]) {
473 ++j;
474 }
475 else {
476 inter_ptr[counter++] = i;
477 ++i;
478 ++j;
479 }
480 }
481 return counter;
482 }
483
484 template size_t find_inter(const int set1[], const int set2[], size_t length1, size_t length2,
485 int inter_ptr[]);
486 template size_t find_inter(const int64_t set1[], const int64_t set2[], size_t length1,
487 size_t length2, int64_t inter_ptr[]);
488
489 #define QSORT_CUTOFF 12
490
491 namespace {
492 template <typename INT>
493 int is_less_than4(INT ra1, INT rb1, INT rc1, INT rd1, INT ra2, INT rb2, INT rc2, INT rd2)
494 {
495 if (ra1 < ra2) {
496 return 1;
497 }
498 if (ra1 > ra2) {
499 return 0;
500 }
501 assert(ra1 == ra2);
502
503 if (rb1 < rb2) {
504 return 1;
505 }
506 if (rb1 > rb2) {
507 return 0;
508 }
509 assert(rb1 == rb2);
510
511 if (rc1 < rc2) {
512 return 1;
513 }
514 if (rc1 > rc2) {
515 return 0;
516 }
517 assert(rc1 == rc2);
518
519 if (rd1 < rd2) {
520 return 1;
521 }
522
523 return 0;
524 }
525
526 template <typename INT> int is_less_than4v(INT *v1, INT *v2, INT *v3, INT *v4, size_t i, size_t j)
527 {
528 if (v1[i] < v1[j]) {
529 return 1;
530 }
531 if (v1[i] > v1[j]) {
532 return 0;
533 }
534 assert(v1[i] == v1[j]);
535
536 if (v2[i] < v2[j]) {
537 return 1;
538 }
539 if (v2[i] > v2[j]) {
540 return 0;
541 }
542 assert(v2[i] == v2[j]);
543
544 if (v3[i] < v3[j]) {
545 return 1;
546 }
547 if (v3[i] > v3[j]) {
548 return 0;
549 }
550 assert(v3[i] == v3[j]);
551
552 if (v4[i] < v4[j]) {
553 return 1;
554 }
555
556 return 0;
557 }
558
559 template <typename INT> void swap4(INT *v1, INT *v2, INT *v3, INT *v4, size_t i, size_t j)
560 {
561 ISWAP(v1, i, j);
562 ISWAP(v2, i, j);
563 ISWAP(v3, i, j);
564 ISWAP(v4, i, j);
565 }
566
567 template <typename INT>
568 size_t internal_median3_4(INT *v1, INT *v2, INT *v3, INT *v4, size_t left, size_t right)
569 {
570 size_t center;
571 center = (left + right) / 2;
572
573 if (is_less_than4v(v1, v2, v3, v4, center, left)) {
574 swap4(v1, v2, v3, v4, left, center);
575 }
576 if (is_less_than4v(v1, v2, v3, v4, right, left)) {
577 swap4(v1, v2, v3, v4, left, right);
578 }
579 if (is_less_than4v(v1, v2, v3, v4, right, center)) {
580 swap4(v1, v2, v3, v4, center, right);
581 }
582
583 swap4(v1, v2, v3, v4, center, right - 1);
584 return right - 1;
585 }
586
587 template <typename INT>
588 void internal_qsort_4(INT *v1, INT *v2, INT *v3, INT *v4, size_t left, size_t right)
589 {
590 if (left + QSORT_CUTOFF <= right) {
591 size_t pivot = internal_median3_4(v1, v2, v3, v4, left, right);
592 size_t i = left;
593 size_t j = right - 1;
594
595 for (;;) {
596 while (is_less_than4v(v1, v2, v3, v4, ++i, pivot)) {
597 ;
598 }
599 while (is_less_than4v(v1, v2, v3, v4, pivot, --j)) {
600 ;
601 }
602 if (i < j) {
603 swap4(v1, v2, v3, v4, i, j);
604 }
605 else {
606 break;
607 }
608 }
609
610 swap4(v1, v2, v3, v4, i, right - 1);
611 internal_qsort_4(v1, v2, v3, v4, left, i - 1);
612 internal_qsort_4(v1, v2, v3, v4, i + 1, right);
613 }
614 }
615
616 template <typename INT> void internal_isort_4(INT *v1, INT *v2, INT *v3, INT *v4, size_t N)
617 {
618 size_t ndx = 0;
619 for (size_t i = 1; i < N; i++) {
620 if (is_less_than4v(v1, v2, v3, v4, i, ndx)) {
621 ndx = i;
622 }
623 }
624 /* Put small_valest value in slot 0 */
625 swap4(v1, v2, v3, v4, 0, ndx);
626
627 for (size_t i = 1; i < N; i++) {
628 INT small_val1 = v1[i];
629 INT small_val2 = v2[i];
630 INT small_val3 = v3[i];
631 INT small_val4 = v4[i];
632 size_t j;
633 for (j = i; is_less_than4(small_val1, small_val2, small_val3, small_val4, v1[j - 1],
634 v2[j - 1], v3[j - 1], v4[j - 1]);
635 j--) {
636 v1[j] = v1[j - 1];
637 v2[j] = v2[j - 1];
638 v3[j] = v3[j - 1];
639 v4[j] = v4[j - 1];
640 }
641 v1[j] = small_val1;
642 v2[j] = small_val2;
643 v3[j] = small_val3;
644 v4[j] = small_val4;
645 }
646 }
647
648 template <typename INT> int is_less_than2(INT ra1, INT rb1, INT ra2, INT rb2)
649 {
650 if (ra1 < ra2) {
651 return 1;
652 }
653 if (ra1 > ra2) {
654 return 0;
655 }
656 assert(ra1 == ra2);
657
658 if (rb1 < rb2) {
659 return 1;
660 }
661
662 return 0;
663 }
664
665 template <typename INT> int is_less_than2v(INT *v1, INT *v2, size_t i, size_t j)
666 {
667 if (v1[i] < v1[j]) {
668 return 1;
669 }
670 if (v1[i] > v1[j]) {
671 return 0;
672 }
673 assert(v1[i] == v1[j]);
674
675 if (v2[i] < v2[j]) {
676 return 1;
677 }
678
679 return 0;
680 }
681
682 template <typename INT> void swap2(INT *v1, INT *v2, size_t i, size_t j)
683 {
684 ISWAP(v1, i, j);
685 ISWAP(v2, i, j);
686 }
687
688 template <typename INT> size_t internal_median3_2(INT *v1, INT *v2, size_t left, size_t right)
689 {
690 size_t center = (left + right) / 2;
691
692 if (is_less_than2v(v1, v2, center, left)) {
693 swap2(v1, v2, left, center);
694 }
695 if (is_less_than2v(v1, v2, right, left)) {
696 swap2(v1, v2, left, right);
697 }
698 if (is_less_than2v(v1, v2, right, center)) {
699 swap2(v1, v2, center, right);
700 }
701
702 swap2(v1, v2, center, right - 1);
703 return right - 1;
704 }
705
706 template <typename INT> void internal_qsort_2(INT *v1, INT *v2, size_t left, size_t right)
707 {
708 if (left + QSORT_CUTOFF <= right) {
709 size_t pivot = internal_median3_2(v1, v2, left, right);
710 size_t i = left;
711 size_t j = right - 1;
712
713 for (;;) {
714 while (is_less_than2v(v1, v2, ++i, pivot)) {
715 ;
716 }
717 while (is_less_than2v(v1, v2, pivot, --j)) {
718 ;
719 }
720 if (i < j) {
721 swap2(v1, v2, i, j);
722 }
723 else {
724 break;
725 }
726 }
727
728 swap2(v1, v2, i, right - 1);
729 internal_qsort_2(v1, v2, left, i - 1);
730 internal_qsort_2(v1, v2, i + 1, right);
731 }
732 }
733
734 template <typename INT> void internal_isort_2(INT *v1, INT *v2, size_t N)
735 {
736 size_t ndx = 0;
737 for (size_t i = 1; i < N; i++) {
738 if (is_less_than2v(v1, v2, i, ndx)) {
739 ndx = i;
740 }
741 }
742
743 /* Put small_valest value in slot 0 */
744 swap2(v1, v2, 0, ndx);
745
746 for (size_t i = 1; i < N; i++) {
747 INT small_val1 = v1[i];
748 INT small_val2 = v2[i];
749 size_t j;
750 for (j = i; is_less_than2(small_val1, small_val2, v1[j - 1], v2[j - 1]); j--) {
751 v1[j] = v1[j - 1];
752 v2[j] = v2[j - 1];
753 }
754 v1[j] = small_val1;
755 v2[j] = small_val2;
756 }
757 }
758 } // namespace
759
760 /*
761 * Sort the values in 'v'
762 */
763
764 template void qsort4(int *v1, int *v2, int *v3, int *v4, size_t N);
765 template void qsort4(int64_t *v1, int64_t *v2, int64_t *v3, int64_t *v4, size_t N);
766
767 template <typename INT> void qsort4(INT *v1, INT *v2, INT *v3, INT *v4, size_t N)
768 {
769 if (N <= 1) {
770 return;
771 }
772 internal_qsort_4(v1, v2, v3, v4, 0, N - 1);
773 internal_isort_4(v1, v2, v3, v4, N);
774
775 #if defined(DEBUG_QSORT)
776 fmt::print(stderr, "Checking sort of {} values\n", (size_t)N + 1);
777 for (size_t i = 1; i < N; i++) {
778 assert(is_less_than4v(v1, v2, v3, v4, i - 1, i));
779 }
780 #endif
781 }
782
783 template void qsort2(int *v1, int *v2, size_t N);
784 template void qsort2(int64_t *v1, int64_t *v2, size_t N);
785 template <typename INT> void qsort2(INT *v1, INT *v2, size_t N)
786 {
787 if (N <= 1) {
788 return;
789 }
790 internal_qsort_2(v1, v2, 0, N - 1);
791 internal_isort_2(v1, v2, N);
792
793 #if defined(DEBUG_QSORT)
794 fmt::print(stderr, "Checking sort of {} values\n", (size_t)N + 1);
795 for (size_t i = 1; i < N; i++) {
796 assert(is_less_than2v(v1, v2, i - 1, i));
797 }
798 #endif
799 }
800
801 template void sort3(int64_t count, int ra[], int rb[], int rc[]);
802 template void sort3(int64_t count, int64_t ra[], int64_t rb[], int64_t rc[]);
803 template <typename INT> void sort3(int64_t count, INT ra[], INT rb[], INT rc[])
804 {
805 if (count <= 1) {
806 return;
807 }
808 /* heapify */
809 for (int64_t start = (count - 2) / 2; start >= 0; start--) {
810 siftDowniii(ra, rb, rc, start, count);
811 }
812
813 for (size_t end = count - 1; end > 0; end--) {
814 SWAP(ra[end], ra[0]);
815 SWAP(rb[end], rb[0]);
816 SWAP(rc[end], rc[0]);
817 siftDowniii(ra, rb, rc, 0, end);
818 }
819 }
820
821 template int64_t bin_search2(int value, size_t num, int List[]);
822 template int64_t bin_search2(int64_t value, size_t num, int64_t List[]);
823 template <typename INT> int64_t bin_search2(INT value, size_t num, INT List[])
824 {
825
826 /*
827 * Searches a monotonic list of values for the value, value.
828 * It returns the index of the first position found, which matches value.
829 * The list is assumed to be monotonic, and
830 * consist of elements list[0], ..., list[n-1].
831 * If no position in list matches value, it returns the value -1.
832 *
833 */
834 size_t top = num - 1;
835 size_t bottom = 0;
836 while (bottom <= top) {
837 size_t middle = (bottom + top) >> 1;
838 INT g_mid = List[middle];
839 if (value < g_mid) {
840 top = middle - 1;
841 }
842 else if (value > g_mid) {
843 bottom = middle + 1;
844 }
845 else {
846 return middle; /* found */
847 }
848 }
849 return -1;
850 }
851
852 template void gds_qsort(int v[], size_t N);
853 template void gds_qsort(int64_t v[], size_t N);
854
855 template <typename INT> void gds_qsort(INT v[], size_t N)
856 {
857 if (N <= 1) {
858 return;
859 }
860 gds_qsort(v, 0, N - 1);
861 gds_isort(v, N);
862 }