Debian Codegraph @

packages/seacas/applications/ejoin/EJ_index_sort.C

raw
1 // Copyright(C) 1999-2021, 2023, 2024 National Technology & Engineering Solutions
2 // of Sandia, LLC (NTESS). Under the terms of Contract DE-NA0003525 with
3 // NTESS, the U.S. Government retains certain rights in this software.
4 //
5 // See packages/seacas/LICENSE for details
6 /*!
7 * The following 'indexed qsort' routine is modified from Sedgewicks
8 * algorithm It selects the pivot based on the median of the left,
9 * right, and center values to try to avoid degenerate cases occurring
10 * when a single value is chosen. It performs a quicksort on
11 * intervals down to the EX_QSORT_CUTOFF size and then performs a final
12 * insertion sort on the almost sorted final array. Based on data in
13 * Sedgewick, the EX_QSORT_CUTOFF value should be between 5 and 20.
14 *
15 * See Sedgewick for further details
16 * Define DEBUG_QSORT at the top of this file and recompile to compile
17 * in code that verifies that the array is sorted.
18 */
19
20 #include <EJ_CodeTypes.h>
21 #include <cstdint>
22 #include <numeric>
23 #include <unistd.h>
24
25 #include "EJ_index_sort.h"
26
27 #define EX_QSORT_CUTOFF 12
28
29 namespace {
30 /* swap - interchange v[i] and v[j] */
31 template <typename T, typename INT> void ex_swap(T *v, INT i, INT j)
32 {
33 T temp = v[i];
34 v[i] = v[j];
35 v[j] = temp;
36 }
37
38 template <typename T, typename INT> INT ex_int_median3(T *v, INT iv[], size_t left, size_t right)
39 {
40 size_t center = (left + right) / 2;
41
42 if (v[iv[left]] > v[iv[center]]) {
43 ex_swap(iv, left, center);
44 }
45 if (v[iv[left]] > v[iv[right]]) {
46 ex_swap(iv, left, right);
47 }
48 if (v[iv[center]] > v[iv[right]]) {
49 ex_swap(iv, center, right);
50 }
51
52 ex_swap(iv, center, right - 1);
53 return iv[right - 1];
54 }
55
56 template <typename T, typename INT> void ex_int_iqsort(T *v, INT iv[], size_t left, size_t right)
57 {
58 if (left + EX_QSORT_CUTOFF <= right) {
59 INT pivot = ex_int_median3(v, iv, left, right);
60 size_t i = left;
61 size_t j = right - 1;
62
63 for (;;) {
64 while (v[iv[++i]] < v[pivot]) {
65 ;
66 }
67 while (v[iv[--j]] > v[pivot]) {
68 ;
69 }
70 if (i < j) {
71 ex_swap(iv, i, j);
72 }
73 else {
74 break;
75 }
76 }
77
78 ex_swap(iv, i, right - 1);
79 ex_int_iqsort(v, iv, left, i - 1);
80 ex_int_iqsort(v, iv, i + 1, right);
81 }
82 }
83
84 template <typename T, typename INT> void ex_int_iisort(T *v, INT iv[], size_t N)
85 {
86 if (N == 0) {
87 return;
88 }
89
90 size_t ndx = 0;
91
92 using TT = typename std::remove_cv_t<T>;
93 TT small = v[iv[0]];
94 for (size_t i = 1; i < N; i++) {
95 if (v[iv[i]] < small) {
96 small = v[iv[i]];
97 ndx = i;
98 }
99 }
100 /* Put smallest value in slot 0 */
101 ex_swap(iv, static_cast<size_t>(0), ndx);
102
103 size_t j;
104 for (size_t i = 1; i < N; i++) {
105 INT tmp = iv[i];
106 for (j = i; v[tmp] < v[iv[j - 1]]; j--) {
107 iv[j] = iv[j - 1];
108 }
109 iv[j] = tmp;
110 }
111 }
112
113 template <typename T, typename INT> void exi_iqsort(T *v, INT iv[], size_t N)
114 {
115 if (N <= 1) {
116 return;
117 }
118
119 ex_int_iqsort(v, iv, 0, N - 1);
120 ex_int_iisort(v, iv, N);
121
122 #if defined(DEBUG_QSORT)
123 fprintf(stderr, "Checking sort of %lu values\n", N + 1);
124 int i;
125 for (i = 1; i < N; i++) {
126 assert(v[iv[i - 1]] <= v[iv[i]]);
127 }
128 #endif
129 }
130 } // namespace
131
132 template <typename INT>
133 void index_coord_sort(const std::vector<double> &xyz, std::vector<INT> &index, int axis)
134 {
135 // For now, let's extract the component we want to sort on into a separate vector.
136 std::vector<double> comp(xyz.size() / 3);
137 size_t j = 0;
138 for (size_t i = axis; i < xyz.size(); i += 3) {
139 comp[j++] = xyz[i];
140 }
141 exi_iqsort(Data(comp), Data(index), index.size());
142 }
143
144 template <typename INT> void index_sort(const std::vector<INT> &ids, std::vector<INT> &index)
145 {
146 index.resize(ids.size());
147 std::iota(index.begin(), index.end(), (INT)0);
148 exi_iqsort(Data(ids), Data(index), index.size());
149 }
150
151 template void index_coord_sort(const std::vector<double> &xyz, std::vector<int> &index, int axis);
152 template void index_coord_sort(const std::vector<double> &xyz, std::vector<int64_t> &index,
153 int axis);
154
155 template void index_sort(const std::vector<int> &ids, std::vector<int> &index);
156 template void index_sort(const std::vector<int64_t> &ids, std::vector<int64_t> &index);