| 111 | } |
| 112 | |
| 113 | NPY_NO_EXPORT int |
| 114 | npy_aheapsort(void *vv, npy_intp *tosort, npy_intp n, void *varr) |
| 115 | { |
| 116 | char *v = (char *)vv; |
| 117 | PyArrayObject *arr = (PyArrayObject *)varr; |
| 118 | npy_intp elsize = PyArray_ITEMSIZE(arr); |
| 119 | PyArray_CompareFunc *cmp = PyArray_DESCR(arr)->f->compare; |
| 120 | npy_intp *a, i, j, l, tmp; |
| 121 | |
| 122 | /* The array needs to be offset by one for heapsort indexing */ |
| 123 | a = tosort - 1; |
| 124 | |
| 125 | for (l = n >> 1; l > 0; --l) { |
| 126 | tmp = a[l]; |
| 127 | for (i = l, j = l << 1; j <= n;) { |
| 128 | if (j < n && |
| 129 | cmp(v + a[j] * elsize, v + a[j + 1] * elsize, arr) < 0) { |
| 130 | ++j; |
| 131 | } |
| 132 | if (cmp(v + tmp * elsize, v + a[j] * elsize, arr) < 0) { |
| 133 | a[i] = a[j]; |
| 134 | i = j; |
| 135 | j += j; |
| 136 | } |
| 137 | else { |
| 138 | break; |
| 139 | } |
| 140 | } |
| 141 | a[i] = tmp; |
| 142 | } |
| 143 | |
| 144 | for (; n > 1;) { |
| 145 | tmp = a[n]; |
| 146 | a[n] = a[1]; |
| 147 | n -= 1; |
| 148 | for (i = 1, j = 2; j <= n;) { |
| 149 | if (j < n && |
| 150 | cmp(v + a[j] * elsize, v + a[j + 1] * elsize, arr) < 0) { |
| 151 | ++j; |
| 152 | } |
| 153 | if (cmp(v + tmp * elsize, v + a[j] * elsize, arr) < 0) { |
| 154 | a[i] = a[j]; |
| 155 | i = j; |
| 156 | j += j; |
| 157 | } |
| 158 | else { |
| 159 | break; |
| 160 | } |
| 161 | } |
| 162 | a[i] = tmp; |
| 163 | } |
| 164 | |
| 165 | return 0; |
| 166 | } |
| 167 | |
| 168 | /*************************************** |
| 169 | * C > C++ dispatch |
no test coverage detected