| 67 | |
| 68 | template <typename indexT> |
| 69 | void split_segment(range<seg<indexT>*> segOut, |
| 70 | indexT start, |
| 71 | sequence<indexT> &ranks, |
| 72 | range<ipair<indexT>*> Cs) { |
| 73 | indexT l = segOut.size(); |
| 74 | if (l < 5000) { // sequential version |
| 75 | |
| 76 | indexT name = 0; |
| 77 | ranks[Cs[0].second] = name + start + 1; |
| 78 | for (indexT i=1; i < l; i++) { |
| 79 | if (Cs[i-1].first != Cs[i].first) name = i; |
| 80 | ranks[Cs[i].second] = name + start + 1; |
| 81 | } |
| 82 | |
| 83 | name = 0; |
| 84 | for (indexT i=1; i < l; i++) { |
| 85 | if (Cs[i-1].first != Cs[i].first) { |
| 86 | segOut[i-1] = seg<indexT>(name+start,i-name); |
| 87 | name = i; |
| 88 | } else segOut[i-1] = seg<indexT>(0,0); |
| 89 | } |
| 90 | segOut[l-1] = seg<indexT>(name+start,l-name); |
| 91 | |
| 92 | } else { // parallel version |
| 93 | sequence<indexT> names(l); |
| 94 | |
| 95 | // mark start of each segment with equal keys |
| 96 | parallel_for (1, l, [&] (size_t i) { |
| 97 | names[i] = (Cs[i].first != Cs[i-1].first) ? i : 0;}); |
| 98 | names[0] = 0; |
| 99 | |
| 100 | // scan start i across each segment |
| 101 | scan_inplace(names.slice(), maxm<indexT>(), fl_scan_inclusive); |
| 102 | |
| 103 | // write new rank into original location |
| 104 | parallel_for (0, l, [&] (size_t i) { |
| 105 | ranks[Cs[i].second] = names[i]+start+1;}); |
| 106 | |
| 107 | // get starts and lengths of new segments |
| 108 | parallel_for (1, l, [&] (size_t i) { |
| 109 | if (names[i] == i) |
| 110 | segOut[i-1] = seg<indexT>(start+names[i-1],i-names[i-1]); |
| 111 | else segOut[i-1] = seg<indexT>(0,0); |
| 112 | }); |
| 113 | segOut[l-1] = seg<indexT>(start+names[l-1],l-names[l-1]); |
| 114 | } |
| 115 | } |
| 116 | |
| 117 | template <class indexT> |
| 118 | sequence<ipair<indexT>> |
no test coverage detected