101 const RanSeqs& begin_seqs,
const RanSeqs& end_seqs,
102 const RankType& rank,
104 Comparator comp = Comparator()) {
106 using iterator =
typename std::iterator_traits<RanSeqs>
107 ::value_type::first_type;
108 using diff_type =
typename std::iterator_traits<iterator>
111 using SamplePair = std::pair<ValueType, diff_type>;
116 lexicographic<ValueType, diff_type, Comparator> lcomp(comp);
117 lexicographic_rev<ValueType, diff_type, Comparator> lrcomp(comp);
121 const diff_type m = std::distance(begin_seqs, end_seqs);
125 for (diff_type i = 0; i < m; ++i)
126 N += std::distance(begin_seqs[i].first, begin_seqs[i].second);
128 if (m == 0 || N == 0 || rank < 0 || rank >= N)
130 throw std::exception();
134 seqlen[0] = std::distance(begin_seqs[0].first, begin_seqs[0].second);
136 for (diff_type i = 1; i < m; ++i)
138 seqlen[i] = std::distance(begin_seqs[i].first, begin_seqs[i].second);
139 nmax = std::max(nmax, seqlen[i]);
148 for (diff_type i = 0; i < m; ++i)
158 std::vector<SamplePair> sample;
160 for (diff_type i = 0; i < m; ++i) {
162 sample.push_back(SamplePair(begin_seqs[i].first[n], i));
165 std::sort(sample.begin(), sample.end(), lcomp);
167 for (diff_type i = 0; i < m; ++i) {
171 SamplePair(begin_seqs[i].first[0] , i));
174 size_t localrank =
static_cast<size_t>(rank / l);
177 for (j = 0; j < localrank && ((n + 1) <= seqlen[sample[j].second]); ++j)
178 a[sample[j].second] += n + 1;
179 for ( ; j < static_cast<size_t>(m); ++j)
180 b[sample[j].second] -= n + 1;
188 const ValueType* lmax =
nullptr;
189 for (diff_type i = 0; i < m; ++i)
195 lmax = &(begin_seqs[i].first[a[i] - 1]);
200 if (comp(*lmax, begin_seqs[i].first[a[i] - 1]))
201 lmax = &(begin_seqs[i].first[a[i] - 1]);
206 for (diff_type i = 0; i < m; ++i)
208 diff_type middle = (b[i] + a[i]) / 2;
209 if (lmax && middle < seqlen[i] &&
210 comp(begin_seqs[i].first[middle], *lmax))
211 a[i] = std::min(a[i] + n + 1, seqlen[i]);
216 diff_type leftsize = 0;
217 for (diff_type i = 0; i < m; ++i)
218 leftsize += a[i] / (n + 1);
220 diff_type skew = rank / (n + 1) - leftsize;
226 SamplePair, std::vector<SamplePair>,
227 lexicographic_rev<ValueType, diff_type, Comparator> >
230 for (diff_type i = 0; i < m; ++i) {
231 if (b[i] < seqlen[i])
232 pq.push(SamplePair(begin_seqs[i].first[b[i]], i));
235 for ( ; skew != 0 && !pq.empty(); --skew)
237 diff_type src = pq.top().second;
240 a[src] = std::min(a[src] + n + 1, seqlen[src]);
243 if (b[src] < seqlen[src])
244 pq.push(SamplePair(begin_seqs[src].first[b[src]], src));
251 SamplePair, std::vector<SamplePair>,
252 lexicographic<ValueType, diff_type, Comparator> >
255 for (diff_type i = 0; i < m; ++i) {
257 pq.push(SamplePair(begin_seqs[i].first[a[i] - 1], i));
260 for ( ; skew != 0; ++skew)
262 diff_type src = pq.top().second;
269 pq.push(SamplePair(begin_seqs[src].first[a[src] - 1], src));
281 ValueType* maxleft =
nullptr, * minright =
nullptr;
282 for (diff_type i = 0; i < m; ++i)
288 maxleft = &(begin_seqs[i].first[a[i] - 1]);
293 if (comp(*maxleft, begin_seqs[i].first[a[i] - 1]))
294 maxleft = &(begin_seqs[i].first[a[i] - 1]);
297 if (b[i] < seqlen[i])
301 minright = &(begin_seqs[i].first[b[i]]);
306 if (comp(begin_seqs[i].first[b[i]], *minright))
307 minright = &(begin_seqs[i].first[b[i]]);
314 if (!maxleft || comp(*minright, *maxleft))
324 for (diff_type i = 0; i < m; ++i)
326 diff_type lb = std::lower_bound(
327 begin_seqs[i].first, begin_seqs[i].first + seqlen[i],
328 *minright, comp) - begin_seqs[i].first;