| 132 | |
| 133 | template <typename Tag, typename type> |
| 134 | static npy_intp |
| 135 | count_run_(type *arr, npy_intp l, npy_intp num, npy_intp minrun) |
| 136 | { |
| 137 | npy_intp sz; |
| 138 | type vc, *pl, *pi, *pj, *pr; |
| 139 | |
| 140 | if (NPY_UNLIKELY(num - l == 1)) { |
| 141 | return 1; |
| 142 | } |
| 143 | |
| 144 | pl = arr + l; |
| 145 | |
| 146 | /* (not strictly) ascending sequence */ |
| 147 | if (!Tag::less(*(pl + 1), *pl)) { |
| 148 | for (pi = pl + 1; pi < arr + num - 1 && !Tag::less(*(pi + 1), *pi); |
| 149 | ++pi) { |
| 150 | } |
| 151 | } |
| 152 | else { /* (strictly) descending sequence */ |
| 153 | for (pi = pl + 1; pi < arr + num - 1 && Tag::less(*(pi + 1), *pi); |
| 154 | ++pi) { |
| 155 | } |
| 156 | |
| 157 | for (pj = pl, pr = pi; pj < pr; ++pj, --pr) { |
| 158 | std::swap(*pj, *pr); |
| 159 | } |
| 160 | } |
| 161 | |
| 162 | ++pi; |
| 163 | sz = pi - pl; |
| 164 | |
| 165 | if (sz < minrun) { |
| 166 | if (l + minrun < num) { |
| 167 | sz = minrun; |
| 168 | } |
| 169 | else { |
| 170 | sz = num - l; |
| 171 | } |
| 172 | |
| 173 | pr = pl + sz; |
| 174 | |
| 175 | /* insertion sort */ |
| 176 | for (; pi < pr; ++pi) { |
| 177 | vc = *pi; |
| 178 | pj = pi; |
| 179 | |
| 180 | while (pl < pj && Tag::less(vc, *(pj - 1))) { |
| 181 | *pj = *(pj - 1); |
| 182 | --pj; |
| 183 | } |
| 184 | |
| 185 | *pj = vc; |
| 186 | } |
| 187 | } |
| 188 | |
| 189 | return sz; |
| 190 | } |
| 191 | |