| 38 | |
| 39 | template <typename T> |
| 40 | size_t Permute(const std::vector<int64_t>& indices, std::vector<T>* values) { |
| 41 | if (indices.size() <= 1) { |
| 42 | return indices.size(); |
| 43 | } |
| 44 | |
| 45 | // mask indicating which of values are in the correct location |
| 46 | std::vector<bool> sorted(indices.size(), false); |
| 47 | |
| 48 | size_t cycle_count = 0; |
| 49 | |
| 50 | for (auto cycle_start = sorted.begin(); cycle_start != sorted.end(); |
| 51 | cycle_start = std::find(cycle_start, sorted.end(), false)) { |
| 52 | ++cycle_count; |
| 53 | |
| 54 | // position in which an element belongs WRT sort |
| 55 | auto sort_into = static_cast<int64_t>(cycle_start - sorted.begin()); |
| 56 | |
| 57 | if (indices[sort_into] == sort_into) { |
| 58 | // trivial cycle |
| 59 | sorted[sort_into] = true; |
| 60 | continue; |
| 61 | } |
| 62 | |
| 63 | // resolve this cycle |
| 64 | const auto end = sort_into; |
| 65 | for (int64_t take_from = indices[sort_into]; take_from != end; |
| 66 | take_from = indices[sort_into]) { |
| 67 | std::swap(values->at(sort_into), values->at(take_from)); |
| 68 | sorted[sort_into] = true; |
| 69 | sort_into = take_from; |
| 70 | } |
| 71 | sorted[sort_into] = true; |
| 72 | } |
| 73 | |
| 74 | return cycle_count; |
| 75 | } |
| 76 | |
| 77 | } // namespace internal |
| 78 | } // namespace arrow |