107 const RanSeqs& begin_seqs,
const RanSeqs& end_seqs,
108 const RankType& rank,
109 RankIterator begin_offsets,
110 Comparator comp = Comparator()) {
112 using iterator =
typename std::iterator_traits<RanSeqs>
113 ::value_type::first_type;
114 using diff_type =
typename std::iterator_traits<iterator>
116 using value_type =
typename std::iterator_traits<iterator>
119 using SamplePair = std::pair<value_type, diff_type>;
124 lexicographic<value_type, diff_type, Comparator> lcomp(comp);
125 lexicographic_rev<value_type, diff_type, Comparator> lrcomp(comp);
129 const diff_type m = std::distance(begin_seqs, end_seqs);
133 for (diff_type i = 0; i < m; ++i)
135 N += std::distance(begin_seqs[i].first, begin_seqs[i].second);
136 assert(std::distance(begin_seqs[i].first, begin_seqs[i].second) > 0);
141 for (diff_type i = 0; i < m; ++i)
142 begin_offsets[i] = begin_seqs[i].second;
146 assert(m != 0 && N != 0 && rank < N);
150 seqlen[0] = std::distance(begin_seqs[0].first, begin_seqs[0].second);
152 for (diff_type i = 1; i < m; ++i)
154 seqlen[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second);
155 nmax = std::max(nmax, seqlen[i]);
164 for (diff_type i = 0; i < m; ++i)
174 std::vector<SamplePair> sample;
176 for (diff_type i = 0; i < m; ++i) {
179 sample.push_back(SamplePair(begin_seqs[i].first[n], i));
183 std::sort(sample.begin(), sample.end(), lcomp);
185 for (diff_type i = 0; i < m; ++i) {
187 if (n >= seqlen[i]) {
190 SamplePair(begin_seqs[i].first[0] , i));
194 size_t localrank =
static_cast<size_t>(rank / l);
197 for (j = 0; j < localrank && ((n + 1) <= seqlen[sample[j].second]); ++j)
198 a[sample[j].second] += n + 1;
199 for ( ; j < static_cast<size_t>(m); ++j)
200 b[sample[j].second] -= n + 1;
208 const value_type* lmax =
nullptr;
209 for (diff_type i = 0; i < m; ++i)
214 lmax = &(begin_seqs[i].first[a[i] - 1]);
218 if (!comp(begin_seqs[i].first[a[i] - 1], *lmax))
219 lmax = &(begin_seqs[i].first[a[i] - 1]);
224 for (diff_type i = 0; i < m; ++i)
226 diff_type middle = (b[i] + a[i]) / 2;
227 if (lmax && middle < seqlen[i] &&
228 comp(begin_seqs[i].first[middle], *lmax))
229 a[i] = std::min(a[i] + n + 1, seqlen[i]);
234 diff_type leftsize = 0;
235 for (diff_type i = 0; i < m; ++i)
236 leftsize += a[i] / (n + 1);
238 diff_type skew = rank / (n + 1) - leftsize;
244 SamplePair, std::vector<SamplePair>,
245 lexicographic_rev<value_type, diff_type, Comparator> >
248 for (diff_type i = 0; i < m; ++i) {
249 if (b[i] < seqlen[i])
250 pq.push(SamplePair(begin_seqs[i].first[b[i]], i));
253 for ( ; skew != 0 && !pq.empty(); --skew)
255 diff_type src = pq.top().second;
258 a[src] = std::min(a[src] + n + 1, seqlen[src]);
261 if (b[src] < seqlen[src])
262 pq.push(SamplePair(begin_seqs[src].first[b[src]], src));
269 SamplePair, std::vector<SamplePair>,
270 lexicographic<value_type, diff_type, Comparator> >
273 for (diff_type i = 0; i < m; ++i) {
275 pq.push(SamplePair(begin_seqs[i].first[a[i] - 1], i));
278 for ( ; skew != 0; ++skew)
280 diff_type src = pq.top().second;
287 pq.push(SamplePair(begin_seqs[src].first[a[src] - 1], src));
299 value_type* maxleft =
nullptr, * minright =
nullptr;
300 for (diff_type i = 0; i < m; ++i)
306 maxleft = &(begin_seqs[i].first[a[i] - 1]);
311 if (!comp(begin_seqs[i].first[a[i] - 1], *maxleft))
312 maxleft = &(begin_seqs[i].first[a[i] - 1]);
315 if (b[i] < seqlen[i])
319 minright = &(begin_seqs[i].first[b[i]]);
324 if (comp(begin_seqs[i].first[b[i]], *minright))
325 minright = &(begin_seqs[i].first[b[i]]);
330 for (diff_type i = 0; i < m; ++i)
331 begin_offsets[i] = begin_seqs[i].first + a[i];