webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp - Issue 2546863003: Delete unused spreadsort implementation.

Side by Side Diff: webrtc/system_wrappers/source/spreadsortlib/spreadsort.hpp

Issue 2546863003: Delete unused spreadsort implementation. (Closed)

Patch Set: Delete TestSort.cc too. Created 4 years ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

OLD	NEW
	(Empty)
1 //Templated spread_sort library

2

3 // Copyright Steven J. Ross 2001 - 2009.

4 // Distributed under the Boost Software License, Version 1.0.

5 // (See accompanying file LICENSE_1_0.txt or copy at

6 // http://www.boost.org/LICENSE_1_0.txt)

7

8 // See http://www.boost.org/ for updates, documentation, and revision history.

9

10 /*

11 Some improvements suggested by:

12 Phil Endecott and Frank Gennari

13 Cygwin fix provided by:

14 Scott McMurray

15 */

16

17 #ifndef BOOST_SPREAD_SORT_H

18 #define BOOST_SPREAD_SORT_H

19 #include <algorithm>

20 #include <cstring>

21 #include <vector>

22 #include "webrtc/system_wrappers/source/spreadsortlib/constants.hpp"

23

24 namespace boost {

25 namespace detail {

26 //This only works on unsigned data types

27 template <typename T>

28 inline unsigned

29 rough_log_2_size(const T& input)

30 {

31 unsigned result = 0;

32 //The && is necessary on some compilers to avoid infinite loops; it doesn't significantly impair performance

33 while((input >> result) && (result < (8*sizeof(T)))) ++result;

34 return result;

35 }

36

37 //Gets the maximum size which we'll call spread_sort on to control worst -case performance

38 //Maintains both a minimum size to recurse and a check of distribution s ize versus count

39 //This is called for a set of bins, instead of bin-by-bin, to avoid perf ormance overhead

40 inline size_t

41 get_max_count(unsigned log_range, size_t count)

42 {

43 unsigned divisor = rough_log_2_size(count);

44 //Making sure the divisor is positive

45 if(divisor > LOG_MEAN_BIN_SIZE)

46 divisor -= LOG_MEAN_BIN_SIZE;

47 else

48 divisor = 1;

49 unsigned relative_width = (LOG_CONST * log_range)/((divisor > MA X_SPLITS) ? MAX_SPLITS : divisor);

50 //Don't try to bitshift more than the size of an element

51 if((8*sizeof(size_t)) <= relative_width)

52 relative_width = (8*sizeof(size_t)) - 1;

53 return (size_t)1 << ((relative_width < (LOG_MEAN_BIN_SIZE + LOG_ MIN_SPLIT_COUNT)) ?

54 (LOG_MEAN_BIN_SIZE + LOG_MIN_SPLIT_COUNT) : relative_wi dth);

55 }

56

57 //Find the minimum and maximum using <

58 template <class RandomAccessIter>

59 inline void

60 find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAcc essIter & max, RandomAccessIter & min)

61 {

62 min = max = current;

63 //Start from the second item, as max and min are initialized to the first

64 while(++current < last) {

65 if(max < current)

66 max = current;

67 else if(current < min)

68 min = current;

69 }

70 }

71

72 //Uses a user-defined comparison operator to find minimum and maximum

73 template <class RandomAccessIter, class compare>

74 inline void

75 find_extremes(RandomAccessIter current, RandomAccessIter last, RandomAcc essIter & max, RandomAccessIter & min, compare comp)

76 {

77 min = max = current;

78 while(++current < last) {

79 if(comp(max, current))

80 max = current;

81 else if(comp(current, min))

82 min = current;

83 }

84 }

85

86 //Gets a non-negative right bit shift to operate as a logarithmic diviso r

87 inline int

88 get_log_divisor(size_t count, unsigned log_range)

89 {

90 int log_divisor;

91 //If we can finish in one iteration without exceeding either (2 to the MAX_SPLITS) or n bins, do so

92 if((log_divisor = log_range - rough_log_2_size(count)) <= 0 && l og_range < MAX_SPLITS)

93 log_divisor = 0;

94 else {

95 //otherwise divide the data into an optimized number of pieces

96 log_divisor += LOG_MEAN_BIN_SIZE;

97 if(log_divisor < 0)

98 log_divisor = 0;

99 //Cannot exceed MAX_SPLITS or cache misses slow down bin lookups dramatically

100 if((log_range - log_divisor) > MAX_SPLITS)

101 log_divisor = log_range - MAX_SPLITS;

102 }

103 return log_divisor;

104 }

105

106 template <class RandomAccessIter>

107 inline RandomAccessIter *

108 size_bins(std::vector<size_t> &bin_sizes, std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)

109 {

110 //Assure space for the size of each bin, followed by initializin g sizes

111 if(bin_count > bin_sizes.size())

112 bin_sizes.resize(bin_count);

113 for(size_t u = 0; u < bin_count; u++)

114 bin_sizes[u] = 0;

115 //Make sure there is space for the bins

116 cache_end = cache_offset + bin_count;

117 if(cache_end > bin_cache.size())

118 bin_cache.resize(cache_end);

119 return &(bin_cache[cache_offset]);

120 }

121

122 //Implementation for recursive integer sorting

123 template <class RandomAccessIter, class div_type, class data_type>

124 inline void

125 spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vect or<RandomAccessIter> &bin_cache, unsigned cache_offset

126 , std::vector<size_t> &bin_sizes)

127 {

128 //This step is roughly 10% of runtime, but it helps avoid worst- case behavior and improve behavior with real data

129 //If you know the maximum and minimum ahead of time, you can pas s those values in and skip this step for the first iteration

130 RandomAccessIter max, min;

131 find_extremes(first, last, max, min);

132 //max and min will be the same (the first item) iff all values a re equivalent

133 if(max == min)

134 return;

135 RandomAccessIter * target_bin;

136 unsigned log_divisor = get_log_divisor(last - first, rough_log_2 _size((size_t)(max >> 0) - (min >> 0)));

137 div_type div_min = *min >> log_divisor;

138 div_type div_max = *max >> log_divisor;

139 unsigned bin_count = div_max - div_min + 1;

140 unsigned cache_end;

141 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, bin_count);

142

143 //Calculating the size of each bin; this takes roughly 10% of ru ntime

144 for (RandomAccessIter current = first; current != last;)

145 bin_sizes[(*(current++) >> log_divisor) - div_min]++;

146 //Assign the bin positions

147 bins[0] = first;

148 for(unsigned u = 0; u < bin_count - 1; u++)

149 bins[u + 1] = bins[u] + bin_sizes[u];

150

151 //Swap into place

152 //This dominates runtime, mostly in the swap and bin lookups

153 RandomAccessIter nextbinstart = first;

154 for(unsigned u = 0; u < bin_count - 1; ++u) {

155 RandomAccessIter * local_bin = bins + u;

156 nextbinstart += bin_sizes[u];

157 //Iterating over each element in this bin

158 for(RandomAccessIter current = *local_bin; current < nex tbinstart; ++current) {

159 //Swapping elements in current into place until the correct element has been swapped in

160 for(target_bin = (bins + ((*current >> log_divis or) - div_min)); target_bin != local_bin;

161 target_bin = bins + ((*current >> log_di visor) - div_min)) {

162 //3-way swap; this is about 1% faster th an a 2-way swap with integers

163 //The main advantage is less copies are involved per item put in the correct place

164 data_type tmp;

165 RandomAccessIter b = (*target_bin)++;

166 RandomAccessIter * b_bin = bins + ((*b > > log_divisor) - div_min);

167 if (b_bin != local_bin) {

168 RandomAccessIter c = (*b_bin)++;

169 tmp = *c;

170 c = b;

171 }

172 else

173 tmp = *b;

174 b = current;

175 *current = tmp;

176 }

177 }

178 *local_bin = nextbinstart;

179 }

180 bins[bin_count - 1] = last;

181

182 //If we've bucketsorted, the array is sorted and we should skip recursion

183 if(!log_divisor)

184 return;

185

186 //Recursing; log_divisor is the remaining range

187 size_t max_count = get_max_count(log_divisor, last - first);

188 RandomAccessIter lastPos = first;

189 for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cach e[u], ++u) {

190 size_t count = bin_cache[u] - lastPos;

191 //don't sort unless there are at least two items to comp are

192 if(count < 2)

193 continue;

194 //using std::sort if its worst-case is better

195 if(count < max_count)

196 std::sort(lastPos, bin_cache[u]);

197 else

198 spread_sort_rec<RandomAccessIter, div_type, data _type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);

199 }

200 }

201

202 //Generic bitshift-based 3-way swapping code

203 template <class RandomAccessIter, class div_type, class data_type, class right_shift>

204 inline void inner_swap_loop(RandomAccessIter * bins, const RandomAccessI ter & nextbinstart, unsigned ii, right_shift &shift

205 , const unsigned log_divisor, const div_type div_min)

206 {

207 RandomAccessIter * local_bin = bins + ii;

208 for(RandomAccessIter current = *local_bin; current < nextbinstar t; ++current) {

209 for(RandomAccessIter * target_bin = (bins + (shift(*curr ent, log_divisor) - div_min)); target_bin != local_bin;

210 target_bin = bins + (shift(*current, log_divisor ) - div_min)) {

211 data_type tmp;

212 RandomAccessIter b = (*target_bin)++;

213 RandomAccessIter * b_bin = bins + (shift(*b, log _divisor) - div_min);

214 //Three-way swap; if the item to be swapped does n't belong in the current bin, swap it to where it belongs

215 if (b_bin != local_bin) {

216 RandomAccessIter c = (*b_bin)++;

217 tmp = *c;

218 c = b;

219 }

220 //Note: we could increment current once the swap is done in this case, but that seems to impair performance

221 else

222 tmp = *b;

223 b = current;

224 *current = tmp;

225 }

226 }

227 *local_bin = nextbinstart;

228 }

229

230 //Standard swapping wrapper for ascending values

231 template <class RandomAccessIter, class div_type, class data_type, class right_shift>

232 inline void swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbi nstart, unsigned ii, right_shift &shift

233 , const std::vector<size_t> &bin_sizes, const unsigned log_divis or, const div_type div_min)

234 {

235 nextbinstart += bin_sizes[ii];

236 inner_swap_loop<RandomAccessIter, div_type, data_type, right_shi ft>(bins, nextbinstart, ii, shift, log_divisor, div_min);

237 }

238

239 //Functor implementation for recursive sorting

240 template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>

241 inline void

242 spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vect or<RandomAccessIter> &bin_cache, unsigned cache_offset

243 , std::vector<size_t> &bin_sizes, right_ shift shift, compare comp)

244 {

245 RandomAccessIter max, min;

246 find_extremes(first, last, max, min, comp);

247 if(max == min)

248 return;

249 unsigned log_divisor = get_log_divisor(last - first, rough_log_2 _size((size_t)(shift(max, 0)) - (shift(min, 0))));

250 div_type div_min = shift(*min, log_divisor);

251 div_type div_max = shift(*max, log_divisor);

252 unsigned bin_count = div_max - div_min + 1;

253 unsigned cache_end;

254 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, bin_count);

255

256 //Calculating the size of each bin

257 for (RandomAccessIter current = first; current != last;)

258 bin_sizes[shift(*(current++), log_divisor) - div_min]++;

259 bins[0] = first;

260 for(unsigned u = 0; u < bin_count - 1; u++)

261 bins[u + 1] = bins[u] + bin_sizes[u];

262

263 //Swap into place

264 RandomAccessIter nextbinstart = first;

265 for(unsigned u = 0; u < bin_count - 1; ++u)

266 swap_loop<RandomAccessIter, div_type, data_type, right_s hift>(bins, nextbinstart, u, shift, bin_sizes, log_divisor, div_min);

267 bins[bin_count - 1] = last;

268

269 //If we've bucketsorted, the array is sorted and we should skip recursion

270 if(!log_divisor)

271 return;

272

273 //Recursing

274 size_t max_count = get_max_count(log_divisor, last - first);

275 RandomAccessIter lastPos = first;

276 for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cach e[u], ++u) {

277 size_t count = bin_cache[u] - lastPos;

278 if(count < 2)

279 continue;

280 if(count < max_count)

281 std::sort(lastPos, bin_cache[u], comp);

282 else

283 spread_sort_rec<RandomAccessIter, div_type, data _type, right_shift, compare>(lastPos, bin_cache[u], bin_cache, cache_end, bin_si zes, shift, comp);

284 }

285 }

286

287 //Functor implementation for recursive sorting with only Shift overridde n

288 template <class RandomAccessIter, class div_type, class data_type, class right_shift>

289 inline void

290 spread_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vect or<RandomAccessIter> &bin_cache, unsigned cache_offset

291 , std::vector<size_t> &bin_sizes, right_ shift shift)

292 {

293 RandomAccessIter max, min;

294 find_extremes(first, last, max, min);

295 if(max == min)

296 return;

297 unsigned log_divisor = get_log_divisor(last - first, rough_log_2 _size((size_t)(shift(max, 0)) - (shift(min, 0))));

298 div_type div_min = shift(*min, log_divisor);

299 div_type div_max = shift(*max, log_divisor);

300 unsigned bin_count = div_max - div_min + 1;

301 unsigned cache_end;

302 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, bin_count);

303

304 //Calculating the size of each bin

305 for (RandomAccessIter current = first; current != last;)

306 bin_sizes[shift(*(current++), log_divisor) - div_min]++;

307 bins[0] = first;

308 for(unsigned u = 0; u < bin_count - 1; u++)

309 bins[u + 1] = bins[u] + bin_sizes[u];

310

311 //Swap into place

312 RandomAccessIter nextbinstart = first;

313 for(unsigned ii = 0; ii < bin_count - 1; ++ii)

314 swap_loop<RandomAccessIter, div_type, data_type, right_s hift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);

315 bins[bin_count - 1] = last;

316

317 //If we've bucketsorted, the array is sorted and we should skip recursion

318 if(!log_divisor)

319 return;

320

321 //Recursing

322 size_t max_count = get_max_count(log_divisor, last - first);

323 RandomAccessIter lastPos = first;

324 for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cach e[u], ++u) {

325 size_t count = bin_cache[u] - lastPos;

326 if(count < 2)

327 continue;

328 if(count < max_count)

329 std::sort(lastPos, bin_cache[u]);

330 else

331 spread_sort_rec<RandomAccessIter, div_type, data _type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shif t);

332 }

333 }

334

335 //Holds the bin vector and makes the initial recursive call

336 template <class RandomAccessIter, class div_type, class data_type>

337 inline void

338 spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, dat a_type)

339 {

340 std::vector<size_t> bin_sizes;

341 std::vector<RandomAccessIter> bin_cache;

342 spread_sort_rec<RandomAccessIter, div_type, data_type>(first, la st, bin_cache, 0, bin_sizes);

343 }

344

345 template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>

346 inline void

347 spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, dat a_type, right_shift shift, compare comp)

348 {

349 std::vector<size_t> bin_sizes;

350 std::vector<RandomAccessIter> bin_cache;

351 spread_sort_rec<RandomAccessIter, div_type, data_type, right_shi ft, compare>(first, last, bin_cache, 0, bin_sizes, shift, comp);

352 }

353

354 template <class RandomAccessIter, class div_type, class data_type, class right_shift>

355 inline void

356 spread_sort(RandomAccessIter first, RandomAccessIter last, div_type, dat a_type, right_shift shift)

357 {

358 std::vector<size_t> bin_sizes;

359 std::vector<RandomAccessIter> bin_cache;

360 spread_sort_rec<RandomAccessIter, div_type, data_type, right_shi ft>(first, last, bin_cache, 0, bin_sizes, shift);

361 }

362 }

363

364 //Top-level sorting call for integers

365 template <class RandomAccessIter>

366 inline void integer_sort(RandomAccessIter first, RandomAccessIter last)

367 {

368 //Don't sort if it's too small to optimize

369 if(last - first < detail::MIN_SORT_SIZE)

370 std::sort(first, last);

371 else

372 detail::spread_sort(first, last, first >> 0, first);

373 }

374

375 //integer_sort with functors

376 template <class RandomAccessIter, class right_shift, class compare>

377 inline void integer_sort(RandomAccessIter first, RandomAccessIter last,

378 right_shift shift, compare comp) {

379 if(last - first < detail::MIN_SORT_SIZE)

380 std::sort(first, last, comp);

381 else

382 detail::spread_sort(first, last, shift(first, 0), first, shift , comp);

383 }

384

385 //integer_sort with right_shift functor

386 template <class RandomAccessIter, class right_shift>

387 inline void integer_sort(RandomAccessIter first, RandomAccessIter last,

388 right_shift shift) {

389 if(last - first < detail::MIN_SORT_SIZE)

390 std::sort(first, last);

391 else

392 detail::spread_sort(first, last, shift(first, 0), first, shift );

393 }

394

395 //------------------------------------------------------ float_sort source --- -----------------------------------

396 //Casts a RandomAccessIter to the specified data type

397 template<class cast_type, class RandomAccessIter>

398 inline cast_type

399 cast_float_iter(const RandomAccessIter & floatiter)

400 {

401 cast_type result;

402 std::memcpy(&result, &(*floatiter), sizeof(cast_type));

403 return result;

404 }

405

406 //Casts a data element to the specified datinner_float_a type

407 template<class data_type, class cast_type>

408 inline cast_type

409 mem_cast(const data_type & data)

410 {

411 cast_type result;

412 std::memcpy(&result, &data, sizeof(cast_type));

413 return result;

414 }

415

416 namespace detail {

417 template <class RandomAccessIter, class div_type, class right_shift>

418 inline void

419 find_extremes(RandomAccessIter current, RandomAccessIter last, div_type & max, div_type & min, right_shift shift)

420 {

421 min = max = shift(*current, 0);

422 while(++current < last) {

423 div_type value = shift(*current, 0);

424 if(max < value)

425 max = value;

426 else if(value < min)

427 min = value;

428 }

429 }

430

431 //Specialized swap loops for floating-point casting

432 template <class RandomAccessIter, class div_type, class data_type>

433 inline void inner_float_swap_loop(RandomAccessIter * bins, const RandomA ccessIter & nextbinstart, unsigned ii

434 , const unsigned log_divisor, const div_type div_min)

435 {

436 RandomAccessIter * local_bin = bins + ii;

437 for(RandomAccessIter current = *local_bin; current < nextbinstar t; ++current) {

438 for(RandomAccessIter * target_bin = (bins + ((cast_float _iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)); target_ bin != local_bin;

439 target_bin = bins + ((cast_float_iter<div_type, RandomAccessIter>(current) >> log_divisor) - div_min)) {

440 data_type tmp;

441 RandomAccessIter b = (*target_bin)++;

442 RandomAccessIter * b_bin = bins + ((cast_float_i ter<div_type, RandomAccessIter>(b) >> log_divisor) - div_min);

443 //Three-way swap; if the item to be swapped does n't belong in the current bin, swap it to where it belongs

444 if (b_bin != local_bin) {

445 RandomAccessIter c = (*b_bin)++;

446 tmp = *c;

447 c = b;

448 }

449 else

450 tmp = *b;

451 b = current;

452 *current = tmp;

453 }

454 }

455 *local_bin = nextbinstart;

456 }

457

458 template <class RandomAccessIter, class div_type, class data_type>

459 inline void float_swap_loop(RandomAccessIter * bins, RandomAccessIter & nextbinstart, unsigned ii

460 , const std::vector<size_t> &bin_sizes, const unsigned log_divis or, const div_type div_min)

461 {

462 nextbinstart += bin_sizes[ii];

463 inner_float_swap_loop<RandomAccessIter, div_type, data_type>(bin s, nextbinstart, ii, log_divisor, div_min);

464 }

465

466 template <class RandomAccessIter, class cast_type>

467 inline void

468 find_extremes(RandomAccessIter current, RandomAccessIter last, cast_type & max, cast_type & min)

469 {

470 min = max = cast_float_iter<cast_type, RandomAccessIter>(current );

471 while(++current < last) {

472 cast_type value = cast_float_iter<cast_type, RandomAcces sIter>(current);

473 if(max < value)

474 max = value;

475 else if(value < min)

476 min = value;

477 }

478 }

479

480 //Special-case sorting of positive floats with casting instead of a righ t_shift

481 template <class RandomAccessIter, class div_type, class data_type>

482 inline void

483 positive_float_sort_rec(RandomAccessIter first, RandomAccessIter last, s td::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

484 , std::vector<size_t> &bin_sizes)

485 {

486 div_type max, min;

487 find_extremes(first, last, max, min);

488 if(max == min)

489 return;

490 unsigned log_divisor = get_log_divisor(last - first, rough_log_2 _size((size_t)(max) - min));

491 div_type div_min = min >> log_divisor;

492 div_type div_max = max >> log_divisor;

493 unsigned bin_count = div_max - div_min + 1;

494 unsigned cache_end;

495 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, bin_count);

496

497 //Calculating the size of each bin

498 for (RandomAccessIter current = first; current != last;)

499 bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(c urrent++) >> log_divisor) - div_min]++;

500 bins[0] = first;

501 for(unsigned u = 0; u < bin_count - 1; u++)

502 bins[u + 1] = bins[u] + bin_sizes[u];

503

504 //Swap into place

505 RandomAccessIter nextbinstart = first;

506 for(unsigned u = 0; u < bin_count - 1; ++u)

507 float_swap_loop<RandomAccessIter, div_type, data_type>(b ins, nextbinstart, u, bin_sizes, log_divisor, div_min);

508 bins[bin_count - 1] = last;

509

510 //Return if we've completed bucketsorting

511 if(!log_divisor)

512 return;

513

514 //Recursing

515 size_t max_count = get_max_count(log_divisor, last - first);

516 RandomAccessIter lastPos = first;

517 for(unsigned u = cache_offset; u < cache_end; lastPos = bin_cach e[u], ++u) {

518 size_t count = bin_cache[u] - lastPos;

519 if(count < 2)

520 continue;

521 if(count < max_count)

522 std::sort(lastPos, bin_cache[u]);

523 else

524 positive_float_sort_rec<RandomAccessIter, div_ty pe, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);

525 }

526 }

527

528 //Sorting negative_ float_s

529 //Note that bins are iterated in reverse order because max_neg_float = m in_neg_int

530 template <class RandomAccessIter, class div_type, class data_type>

531 inline void

532 negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, s td::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

533 , std::vector<size_t> &bin_sizes)

534 {

535 div_type max, min;

536 find_extremes(first, last, max, min);

537 if(max == min)

538 return;

539 unsigned log_divisor = get_log_divisor(last - first, rough_log_2 _size((size_t)(max) - min));

540 div_type div_min = min >> log_divisor;

541 div_type div_max = max >> log_divisor;

542 unsigned bin_count = div_max - div_min + 1;

543 unsigned cache_end;

544 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, bin_count);

545

546 //Calculating the size of each bin

547 for (RandomAccessIter current = first; current != last;)

548 bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(c urrent++) >> log_divisor) - div_min]++;

549 bins[bin_count - 1] = first;

550 for(int ii = bin_count - 2; ii >= 0; --ii)

551 bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];

552

553 //Swap into place

554 RandomAccessIter nextbinstart = first;

555 //The last bin will always have the correct elements in it

556 for(int ii = bin_count - 1; ii > 0; --ii)

557 float_swap_loop<RandomAccessIter, div_type, data_type>(b ins, nextbinstart, ii, bin_sizes, log_divisor, div_min);

558 //Since we don't process the last bin, we need to update its end position

559 bin_cache[cache_offset] = last;

560

561 //Return if we've completed bucketsorting

562 if(!log_divisor)

563 return;

564

565 //Recursing

566 size_t max_count = get_max_count(log_divisor, last - first);

567 RandomAccessIter lastPos = first;

568 for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = b in_cache[ii], --ii) {

569 size_t count = bin_cache[ii] - lastPos;

570 if(count < 2)

571 continue;

572 if(count < max_count)

573 std::sort(lastPos, bin_cache[ii]);

574 else

575 negative_float_sort_rec<RandomAccessIter, div_ty pe, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);

576 }

577 }

578

579 //Sorting negative_ float_s

580 //Note that bins are iterated in reverse order because max_neg_float = m in_neg_int

581 template <class RandomAccessIter, class div_type, class data_type, class right_shift>

582 inline void

583 negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, s td::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

584 , std::vector<size_t> &bin_sizes, right_ shift shift)

585 {

586 div_type max, min;

587 find_extremes(first, last, max, min, shift);

588 if(max == min)

589 return;

590 unsigned log_divisor = get_log_divisor(last - first, rough_log_2 _size((size_t)(max) - min));

591 div_type div_min = min >> log_divisor;

592 div_type div_max = max >> log_divisor;

593 unsigned bin_count = div_max - div_min + 1;

594 unsigned cache_end;

595 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, bin_count);

596

597 //Calculating the size of each bin

598 for (RandomAccessIter current = first; current != last;)

599 bin_sizes[shift(*(current++), log_divisor) - div_min]++;

600 bins[bin_count - 1] = first;

601 for(int ii = bin_count - 2; ii >= 0; --ii)

602 bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];

603

604 //Swap into place

605 RandomAccessIter nextbinstart = first;

606 //The last bin will always have the correct elements in it

607 for(int ii = bin_count - 1; ii > 0; --ii)

608 swap_loop<RandomAccessIter, div_type, data_type, right_s hift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);

609 //Since we don't process the last bin, we need to update its end position

610 bin_cache[cache_offset] = last;

611

612 //Return if we've completed bucketsorting

613 if(!log_divisor)

614 return;

615

616 //Recursing

617 size_t max_count = get_max_count(log_divisor, last - first);

618 RandomAccessIter lastPos = first;

619 for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = b in_cache[ii], --ii) {

620 size_t count = bin_cache[ii] - lastPos;

621 if(count < 2)

622 continue;

623 if(count < max_count)

624 std::sort(lastPos, bin_cache[ii]);

625 else

626 negative_float_sort_rec<RandomAccessIter, div_ty pe, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_si zes, shift);

627 }

628 }

629

630 template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>

631 inline void

632 negative_float_sort_rec(RandomAccessIter first, RandomAccessIter last, s td::vector<RandomAccessIter> &bin_cache, unsigned cache_offset

633 , std::vector<size_t> &bin_sizes, right_ shift shift, compare comp)

634 {

635 div_type max, min;

636 find_extremes(first, last, max, min, shift);

637 if(max == min)

638 return;

639 unsigned log_divisor = get_log_divisor(last - first, rough_log_2 _size((size_t)(max) - min));

640 div_type div_min = min >> log_divisor;

641 div_type div_max = max >> log_divisor;

642 unsigned bin_count = div_max - div_min + 1;

643 unsigned cache_end;

644 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, bin_count);

645

646 //Calculating the size of each bin

647 for (RandomAccessIter current = first; current != last;)

648 bin_sizes[shift(*(current++), log_divisor) - div_min]++;

649 bins[bin_count - 1] = first;

650 for(int ii = bin_count - 2; ii >= 0; --ii)

651 bins[ii] = bins[ii + 1] + bin_sizes[ii + 1];

652

653 //Swap into place

654 RandomAccessIter nextbinstart = first;

655 //The last bin will always have the correct elements in it

656 for(int ii = bin_count - 1; ii > 0; --ii)

657 swap_loop<RandomAccessIter, div_type, data_type, right_s hift>(bins, nextbinstart, ii, shift, bin_sizes, log_divisor, div_min);

658 //Since we don't process the last bin, we need to update its end position

659 bin_cache[cache_offset] = last;

660

661 //Return if we've completed bucketsorting

662 if(!log_divisor)

663 return;

664

665 //Recursing

666 size_t max_count = get_max_count(log_divisor, last - first);

667 RandomAccessIter lastPos = first;

668 for(int ii = cache_end - 1; ii >= (int)cache_offset; lastPos = b in_cache[ii], --ii) {

669 size_t count = bin_cache[ii] - lastPos;

670 if(count < 2)

671 continue;

672 if(count < max_count)

673 std::sort(lastPos, bin_cache[ii], comp);

674 else

675 negative_float_sort_rec<RandomAccessIter, div_ty pe, data_type, right_shift, compare>(lastPos, bin_cache[ii], bin_cache, cache_en d, bin_sizes, shift, comp);

676 }

677 }

678

679 //Casting special-case for floating-point sorting

680 template <class RandomAccessIter, class div_type, class data_type>

681 inline void

682 float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vecto r<RandomAccessIter> &bin_cache, unsigned cache_offset

683 , std::vector<size_t> &bin_sizes)

684 {

685 div_type max, min;

686 find_extremes(first, last, max, min);

687 if(max == min)

688 return;

689 unsigned log_divisor = get_log_divisor(last - first, rough_log_2 _size((size_t)(max) - min));

690 div_type div_min = min >> log_divisor;

691 div_type div_max = max >> log_divisor;

692 unsigned bin_count = div_max - div_min + 1;

693 unsigned cache_end;

694 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, bin_count);

695

696 //Calculating the size of each bin

697 for (RandomAccessIter current = first; current != last;)

698 bin_sizes[(cast_float_iter<div_type, RandomAccessIter>(c urrent++) >> log_divisor) - div_min]++;

699 //The index of the first positive bin

700 div_type first_positive = (div_min < 0) ? -div_min : 0;

701 //Resetting if all bins are negative

702 if(cache_offset + first_positive > cache_end)

703 first_positive = cache_end - cache_offset;

704 //Reversing the order of the negative bins

705 //Note that because of the negative/positive ordering direction flip

706 //We can not depend upon bin order and positions matching up

707 //so bin_sizes must be reused to contain the end of the bin

708 if(first_positive > 0) {

709 bins[first_positive - 1] = first;

710 for(int ii = first_positive - 2; ii >= 0; --ii) {

711 bins[ii] = first + bin_sizes[ii + 1];

712 bin_sizes[ii] += bin_sizes[ii + 1];

713 }

714 //Handling positives following negatives

715 if((unsigned)first_positive < bin_count) {

716 bins[first_positive] = first + bin_sizes[0];

717 bin_sizes[first_positive] += bin_sizes[0];

718 }

719 }

720 else

721 bins[0] = first;

722 for(unsigned u = first_positive; u < bin_count - 1; u++) {

723 bins[u + 1] = first + bin_sizes[u];

724 bin_sizes[u + 1] += bin_sizes[u];

725 }

726

727 //Swap into place

728 RandomAccessIter nextbinstart = first;

729 for(unsigned u = 0; u < bin_count; ++u) {

730 nextbinstart = first + bin_sizes[u];

731 inner_float_swap_loop<RandomAccessIter, div_type, data_t ype>(bins, nextbinstart, u, log_divisor, div_min);

732 }

733

734 if(!log_divisor)

735 return;

736

737 //Handling negative values first

738 size_t max_count = get_max_count(log_divisor, last - first);

739 RandomAccessIter lastPos = first;

740 for(int ii = cache_offset + first_positive - 1; ii >= (int)cache _offset ; lastPos = bin_cache[ii--]) {

741 size_t count = bin_cache[ii] - lastPos;

742 if(count < 2)

743 continue;

744 if(count < max_count)

745 std::sort(lastPos, bin_cache[ii]);

746 //sort negative values using reversed-bin spread_sort

747 else

748 negative_float_sort_rec<RandomAccessIter, div_ty pe, data_type>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_sizes);

749 }

750

751 for(unsigned u = cache_offset + first_positive; u < cache_end; l astPos = bin_cache[u], ++u) {

752 size_t count = bin_cache[u] - lastPos;

753 if(count < 2)

754 continue;

755 if(count < max_count)

756 std::sort(lastPos, bin_cache[u]);

757 //sort positive values using normal spread_sort

758 else

759 positive_float_sort_rec<RandomAccessIter, div_ty pe, data_type>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes);

760 }

761 }

762

763 //Functor implementation for recursive sorting

764 template <class RandomAccessIter, class div_type, class data_type, class right_shift>

765 inline void

766 float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vecto r<RandomAccessIter> &bin_cache, unsigned cache_offset

767 , std::vector<size_t> &bin_sizes, right_ shift shift)

768 {

769 div_type max, min;

770 find_extremes(first, last, max, min, shift);

771 if(max == min)

772 return;

773 unsigned log_divisor = get_log_divisor(last - first, rough_log_2 _size((size_t)(max) - min));

774 div_type div_min = min >> log_divisor;

775 div_type div_max = max >> log_divisor;

776 unsigned bin_count = div_max - div_min + 1;

777 unsigned cache_end;

778 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, bin_count);

779

780 //Calculating the size of each bin

781 for (RandomAccessIter current = first; current != last;)

782 bin_sizes[shift(*(current++), log_divisor) - div_min]++;

783 //The index of the first positive bin

784 div_type first_positive = (div_min < 0) ? -div_min : 0;

785 //Resetting if all bins are negative

786 if(cache_offset + first_positive > cache_end)

787 first_positive = cache_end - cache_offset;

788 //Reversing the order of the negative bins

789 //Note that because of the negative/positive ordering direction flip

790 //We can not depend upon bin order and positions matching up

791 //so bin_sizes must be reused to contain the end of the bin

792 if(first_positive > 0) {

793 bins[first_positive - 1] = first;

794 for(int ii = first_positive - 2; ii >= 0; --ii) {

795 bins[ii] = first + bin_sizes[ii + 1];

796 bin_sizes[ii] += bin_sizes[ii + 1];

797 }

798 //Handling positives following negatives

799 if((unsigned)first_positive < bin_count) {

800 bins[first_positive] = first + bin_sizes[0];

801 bin_sizes[first_positive] += bin_sizes[0];

802 }

803 }

804 else

805 bins[0] = first;

806 for(unsigned u = first_positive; u < bin_count - 1; u++) {

807 bins[u + 1] = first + bin_sizes[u];

808 bin_sizes[u + 1] += bin_sizes[u];

809 }

810

811 //Swap into place

812 RandomAccessIter nextbinstart = first;

813 for(unsigned u = 0; u < bin_count; ++u) {

814 nextbinstart = first + bin_sizes[u];

815 inner_swap_loop<RandomAccessIter, div_type, data_type, r ight_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);

816 }

817

818 //Return if we've completed bucketsorting

819 if(!log_divisor)

820 return;

821

822 //Handling negative values first

823 size_t max_count = get_max_count(log_divisor, last - first);

824 RandomAccessIter lastPos = first;

825 for(int ii = cache_offset + first_positive - 1; ii >= (int)cache _offset ; lastPos = bin_cache[ii--]) {

826 size_t count = bin_cache[ii] - lastPos;

827 if(count < 2)

828 continue;

829 if(count < max_count)

830 std::sort(lastPos, bin_cache[ii]);

831 //sort negative values using reversed-bin spread_sort

832 else

833 negative_float_sort_rec<RandomAccessIter, div_ty pe, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_si zes, shift);

834 }

835

836 for(unsigned u = cache_offset + first_positive; u < cache_end; l astPos = bin_cache[u], ++u) {

837 size_t count = bin_cache[u] - lastPos;

838 if(count < 2)

839 continue;

840 if(count < max_count)

841 std::sort(lastPos, bin_cache[u]);

842 //sort positive values using normal spread_sort

843 else

844 spread_sort_rec<RandomAccessIter, div_type, data _type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shif t);

845 }

846 }

847

848 template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>

849 inline void

850 float_sort_rec(RandomAccessIter first, RandomAccessIter last, std::vecto r<RandomAccessIter> &bin_cache, unsigned cache_offset

851 , std::vector<size_t> &bin_sizes, right_ shift shift, compare comp)

852 {

853 div_type max, min;

854 find_extremes(first, last, max, min, shift);

855 if(max == min)

856 return;

857 unsigned log_divisor = get_log_divisor(last - first, rough_log_2 _size((size_t)(max) - min));

858 div_type div_min = min >> log_divisor;

859 div_type div_max = max >> log_divisor;

860 unsigned bin_count = div_max - div_min + 1;

861 unsigned cache_end;

862 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, bin_count);

863

864 //Calculating the size of each bin

865 for (RandomAccessIter current = first; current != last;)

866 bin_sizes[shift(*(current++), log_divisor) - div_min]++;

867 //The index of the first positive bin

868 div_type first_positive = (div_min < 0) ? -div_min : 0;

869 //Resetting if all bins are negative

870 if(cache_offset + first_positive > cache_end)

871 first_positive = cache_end - cache_offset;

872 //Reversing the order of the negative bins

873 //Note that because of the negative/positive ordering direction flip

874 //We can not depend upon bin order and positions matching up

875 //so bin_sizes must be reused to contain the end of the bin

876 if(first_positive > 0) {

877 bins[first_positive - 1] = first;

878 for(int ii = first_positive - 2; ii >= 0; --ii) {

879 bins[ii] = first + bin_sizes[ii + 1];

880 bin_sizes[ii] += bin_sizes[ii + 1];

881 }

882 //Handling positives following negatives

883 if((unsigned)first_positive < bin_count) {

884 bins[first_positive] = first + bin_sizes[0];

885 bin_sizes[first_positive] += bin_sizes[0];

886 }

887 }

888 else

889 bins[0] = first;

890 for(unsigned u = first_positive; u < bin_count - 1; u++) {

891 bins[u + 1] = first + bin_sizes[u];

892 bin_sizes[u + 1] += bin_sizes[u];

893 }

894

895 //Swap into place

896 RandomAccessIter nextbinstart = first;

897 for(unsigned u = 0; u < bin_count; ++u) {

898 nextbinstart = first + bin_sizes[u];

899 inner_swap_loop<RandomAccessIter, div_type, data_type, r ight_shift>(bins, nextbinstart, u, shift, log_divisor, div_min);

900 }

901

902 //Return if we've completed bucketsorting

903 if(!log_divisor)

904 return;

905

906 //Handling negative values first

907 size_t max_count = get_max_count(log_divisor, last - first);

908 RandomAccessIter lastPos = first;

909 for(int ii = cache_offset + first_positive - 1; ii >= (int)cache _offset ; lastPos = bin_cache[ii--]) {

910 size_t count = bin_cache[ii] - lastPos;

911 if(count < 2)

912 continue;

913 if(count < max_count)

914 std::sort(lastPos, bin_cache[ii]);

915 //sort negative values using reversed-bin spread_sort

916 else

917 negative_float_sort_rec<RandomAccessIter, div_ty pe, data_type, right_shift>(lastPos, bin_cache[ii], bin_cache, cache_end, bin_si zes, shift, comp);

918 }

919

920 for(unsigned u = cache_offset + first_positive; u < cache_end; l astPos = bin_cache[u], ++u) {

921 size_t count = bin_cache[u] - lastPos;

922 if(count < 2)

923 continue;

924 if(count < max_count)

925 std::sort(lastPos, bin_cache[u]);

926 //sort positive values using normal spread_sort

927 else

928 spread_sort_rec<RandomAccessIter, div_type, data _type, right_shift>(lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, shif t, comp);

929 }

930 }

931

932 template <class RandomAccessIter, class cast_type, class data_type>

933 inline void

934 float_Sort(RandomAccessIter first, RandomAccessIter last, cast_type, dat a_type)

935 {

936 std::vector<size_t> bin_sizes;

937 std::vector<RandomAccessIter> bin_cache;

938 float_sort_rec<RandomAccessIter, cast_type, data_type>(first, la st, bin_cache, 0, bin_sizes);

939 }

940

941 template <class RandomAccessIter, class div_type, class data_type, class right_shift>

942 inline void

943 float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data _type, right_shift shift)

944 {

945 std::vector<size_t> bin_sizes;

946 std::vector<RandomAccessIter> bin_cache;

947 float_sort_rec<RandomAccessIter, div_type, data_type, right_shif t>(first, last, bin_cache, 0, bin_sizes, shift);

948 }

949

950 template <class RandomAccessIter, class div_type, class data_type, class right_shift, class compare>

951 inline void

952 float_Sort(RandomAccessIter first, RandomAccessIter last, div_type, data _type, right_shift shift, compare comp)

953 {

954 std::vector<size_t> bin_sizes;

955 std::vector<RandomAccessIter> bin_cache;

956 float_sort_rec<RandomAccessIter, div_type, data_type, right_shif t>(first, last, bin_cache, 0, bin_sizes, shift, comp);

957 }

958 }

959

960 //float_sort with casting

961 //The cast_type must be equal in size to the data type, and must be a signed i nteger

962 template <class RandomAccessIter, class cast_type>

963 inline void float_sort_cast(RandomAccessIter first, RandomAccessIter last, cas t_type cVal)

964 {

965 if(last - first < detail::MIN_SORT_SIZE)

966 std::sort(first, last);

967 else

968 detail::float_Sort(first, last, cVal, *first);

969 }

970

971 //float_sort with casting to an int

972 //Only use this with IEEE floating-point numbers

973 template <class RandomAccessIter>

974 inline void float_sort_cast_to_int(RandomAccessIter first, RandomAccessIter la st)

975 {

976 int cVal = 0;

977 float_sort_cast(first, last, cVal);

978 }

979

980 //float_sort with functors

981 template <class RandomAccessIter, class right_shift>

982 inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_sh ift shift)

983 {

984 if(last - first < detail::MIN_SORT_SIZE)

985 std::sort(first, last);

986 else

987 detail::float_Sort(first, last, shift(first, 0), first, shift) ;

988 }

989

990 template <class RandomAccessIter, class right_shift, class compare>

991 inline void float_sort(RandomAccessIter first, RandomAccessIter last, right_sh ift shift, compare comp)

992 {

993 if(last - first < detail::MIN_SORT_SIZE)

994 std::sort(first, last, comp);

995 else

996 detail::float_Sort(first, last, shift(first, 0), first, shift, comp);

997 }

998

999 //------------------------------------------------- string_sort source ------- --------------------------------------

1000 namespace detail {

1001 //Offsetting on identical characters. This function works a character a t a time for optimal worst-case performance.

1002 template<class RandomAccessIter>

1003 inline void

1004 update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset)

1005 {

1006 unsigned nextOffset = char_offset;

1007 bool done = false;

1008 while(!done) {

1009 RandomAccessIter curr = first;

1010 do {

1011 //ignore empties, but if the nextOffset would ex ceed the length or not match, exit; we've found the last matching character

1012 if((curr).size() > char_offset && ((curr).size () <= (nextOffset + 1) \|\| (curr)[nextOffset] != (first)[nextOffset])) {

1013 done = true;

1014 break;

1015 }

1016 } while(++curr != finish);

1017 if(!done)

1018 ++nextOffset;

1019 }

1020 char_offset = nextOffset;

1021 }

1022

1023 //Offsetting on identical characters. This function works a character a t a time for optimal worst-case performance.

1024 template<class RandomAccessIter, class get_char, class get_length>

1025 inline void

1026 update_offset(RandomAccessIter first, RandomAccessIter finish, unsigned &char_offset, get_char getchar, get_length length)

1027 {

1028 unsigned nextOffset = char_offset;

1029 bool done = false;

1030 while(!done) {

1031 RandomAccessIter curr = first;

1032 do {

1033 //ignore empties, but if the nextOffset would ex ceed the length or not match, exit; we've found the last matching character

1034 if(length(curr) > char_offset && (length(curr) <= (nextOffset + 1) \|\| getchar((curr), nextOffset) != getchar((first), nextOf fset))) {

1035 done = true;

1036 break;

1037 }

1038 } while(++curr != finish);

1039 if(!done)

1040 ++nextOffset;

1041 }

1042 char_offset = nextOffset;

1043 }

1044

1045 //A comparison functor for strings that assumes they are identical up to char_offset

1046 template<class data_type, class unsignedchar_type>

1047 struct offset_lessthan {

1048 offset_lessthan(unsigned char_offset) : fchar_offset(char_offset ){}

1049 inline bool operator()(const data_type &x, const data_type &y) c onst

1050 {

1051 unsigned minSize = std::min(x.size(), y.size());

1052 for(unsigned u = fchar_offset; u < minSize; ++u) {

1053 if(static_cast<unsignedchar_type>(x[u]) < static _cast<unsignedchar_type>(y[u]))

1054 return true;

1055 else if(static_cast<unsignedchar_type>(y[u]) < s tatic_cast<unsignedchar_type>(x[u]))

1056 return false;

1057 }

1058 return x.size() < y.size();

1059 }

1060 unsigned fchar_offset;

1061 };

1062

1063 //A comparison functor for strings that assumes they are identical up to char_offset

1064 template<class data_type, class unsignedchar_type>

1065 struct offset_greaterthan {

1066 offset_greaterthan(unsigned char_offset) : fchar_offset(char_off set){}

1067 inline bool operator()(const data_type &x, const data_type &y) c onst

1068 {

1069 unsigned minSize = std::min(x.size(), y.size());

1070 for(unsigned u = fchar_offset; u < minSize; ++u) {

1071 if(static_cast<unsignedchar_type>(x[u]) > static _cast<unsignedchar_type>(y[u]))

1072 return true;

1073 else if(static_cast<unsignedchar_type>(y[u]) > s tatic_cast<unsignedchar_type>(x[u]))

1074 return false;

1075 }

1076 return x.size() > y.size();

1077 }

1078 unsigned fchar_offset;

1079 };

1080

1081 //A comparison functor for strings that assumes they are identical up to char_offset

1082 template<class data_type, class get_char, class get_length>

1083 struct offset_char_lessthan {

1084 offset_char_lessthan(unsigned char_offset) : fchar_offset(char_o ffset){}

1085 inline bool operator()(const data_type &x, const data_type &y) c onst

1086 {

1087 unsigned minSize = std::min(length(x), length(y));

1088 for(unsigned u = fchar_offset; u < minSize; ++u) {

1089 if(getchar(x, u) < getchar(y, u))

1090 return true;

1091 else if(getchar(y, u) < getchar(x, u))

1092 return false;

1093 }

1094 return length(x) < length(y);

1095 }

1096 unsigned fchar_offset;

1097 get_char getchar;

1098 get_length length;

1099 };

1100

1101 //String sorting recursive implementation

1102 template <class RandomAccessIter, class data_type, class unsignedchar_ty pe>

1103 inline void

1104 string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache

1105 , unsigned cache_offset, std::vector<size_t> &bin_sizes)

1106 {

1107 //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.

1108 //Iterate to the end of the empties. If all empty, return

1109 while((*first).size() <= char_offset) {

1110 if(++first == last)

1111 return;

1112 }

1113 RandomAccessIter finish = last - 1;

1114 //Getting the last non-empty

1115 for(;(*finish).size() <= char_offset; --finish) { }

1116 ++finish;

1117 //Offsetting on identical characters. This section works a char acter at a time for optimal worst-case performance.

1118 update_offset(first, finish, char_offset);

1119

1120 const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));

1121 //Equal worst-case between radix and comparison-based is when bi n_count = n*log(n).

1122 const unsigned max_size = bin_count;

1123 const unsigned membin_count = bin_count + 1;

1124 unsigned cache_end;

1125 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, membin_count) + 1;

1126

1127 //Calculating the size of each bin; this takes roughly 10% of ru ntime

1128 for (RandomAccessIter current = first; current != last; ++curren t) {

1129 if((*current).size() <= char_offset) {

1130 bin_sizes[0]++;

1131 }

1132 else

1133 bin_sizes[static_cast<unsignedchar_type>((*curre nt)[char_offset]) + 1]++;

1134 }

1135 //Assign the bin positions

1136 bin_cache[cache_offset] = first;

1137 for(unsigned u = 0; u < membin_count - 1; u++)

1138 bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];

1139

1140 //Swap into place

1141 RandomAccessIter nextbinstart = first;

1142 //handling empty bins

1143 RandomAccessIter * local_bin = &(bin_cache[cache_offset]);

1144 nextbinstart += bin_sizes[0];

1145 RandomAccessIter * target_bin;

1146 //Iterating over each element in the bin of empties

1147 for(RandomAccessIter current = *local_bin; current < nextbinstar t; ++current) {

1148 //empties belong in this bin

1149 while((*current).size() > char_offset) {

1150 target_bin = bins + static_cast<unsignedchar_typ e>((*current)[char_offset]);

1151 iter_swap(current, (*target_bin)++);

1152 }

1153 }

1154 *local_bin = nextbinstart;

1155 //iterate backwards to find the last bin with elements in it; th is saves iterations in multiple loops

1156 unsigned last_bin = bin_count - 1;

1157 for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }

1158 //This dominates runtime, mostly in the swap and bin lookups

1159 for(unsigned u = 0; u < last_bin; ++u) {

1160 local_bin = bins + u;

1161 nextbinstart += bin_sizes[u + 1];

1162 //Iterating over each element in this bin

1163 for(RandomAccessIter current = *local_bin; current < nex tbinstart; ++current) {

1164 //Swapping elements in current into place until the correct element has been swapped in

1165 for(target_bin = bins + static_cast<unsignedchar _type>((*current)[char_offset]); target_bin != local_bin;

1166 target_bin = bins + static_cast<unsigned char_type>((*current)[char_offset]))

1167 iter_swap(current, (*target_bin)++);

1168 }

1169 *local_bin = nextbinstart;

1170 }

1171 bins[last_bin] = last;

1172 //Recursing

1173 RandomAccessIter lastPos = bin_cache[cache_offset];

1174 //Skip this loop for empties

1175 for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {

1176 size_t count = bin_cache[u] - lastPos;

1177 //don't sort unless there are at least two items to comp are

1178 if(count < 2)

1179 continue;

1180 //using std::sort if its worst-case is better

1181 if(count < max_size)

1182 std::sort(lastPos, bin_cache[u], offset_lessthan <data_type, unsignedchar_type>(char_offset + 1));

1183 else

1184 string_sort_rec<RandomAccessIter, data_type, uns ignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache_end, bi n_sizes);

1185 }

1186 }

1187

1188 //Sorts strings in reverse order, with empties at the end

1189 template <class RandomAccessIter, class data_type, class unsignedchar_ty pe>

1190 inline void

1191 reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, u nsigned char_offset, std::vector<RandomAccessIter> &bin_cache

1192 , unsigned cache_offset, std::vector<size_t> &bin_sizes)

1193 {

1194 //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.

1195 RandomAccessIter curr = first;

1196 //Iterate to the end of the empties. If all empty, return

1197 while((*curr).size() <= char_offset) {

1198 if(++curr == last)

1199 return;

1200 }

1201 //Getting the last non-empty

1202 while((*(--last)).size() <= char_offset) { }

1203 ++last;

1204 //Offsetting on identical characters. This section works a char acter at a time for optimal worst-case performance.

1205 update_offset(curr, last, char_offset);

1206 RandomAccessIter * target_bin;

1207

1208 const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));

1209 //Equal worst-case between radix and comparison-based is when bi n_count = n*log(n).

1210 const unsigned max_size = bin_count;

1211 const unsigned membin_count = bin_count + 1;

1212 const unsigned max_bin = bin_count - 1;

1213 unsigned cache_end;

1214 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, membin_count);

1215 RandomAccessIter * end_bin = &(bin_cache[cache_offset + max_bin] );

1216

1217 //Calculating the size of each bin; this takes roughly 10% of ru ntime

1218 for (RandomAccessIter current = first; current != last; ++curren t) {

1219 if((*current).size() <= char_offset) {

1220 bin_sizes[bin_count]++;

1221 }

1222 else

1223 bin_sizes[max_bin - static_cast<unsignedchar_typ e>((*current)[char_offset])]++;

1224 }

1225 //Assign the bin positions

1226 bin_cache[cache_offset] = first;

1227 for(unsigned u = 0; u < membin_count - 1; u++)

1228 bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];

1229

1230 //Swap into place

1231 RandomAccessIter nextbinstart = last;

1232 //handling empty bins

1233 RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_co unt]);

1234 RandomAccessIter lastFull = *local_bin;

1235 //Iterating over each element in the bin of empties

1236 for(RandomAccessIter current = *local_bin; current < nextbinstar t; ++current) {

1237 //empties belong in this bin

1238 while((*current).size() > char_offset) {

1239 target_bin = end_bin - static_cast<unsignedchar_ type>((*current)[char_offset]);

1240 iter_swap(current, (*target_bin)++);

1241 }

1242 }

1243 *local_bin = nextbinstart;

1244 nextbinstart = first;

1245 //iterate backwards to find the last bin with elements in it; th is saves iterations in multiple loops

1246 unsigned last_bin = max_bin;

1247 for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }

1248 //This dominates runtime, mostly in the swap and bin lookups

1249 for(unsigned u = 0; u < last_bin; ++u) {

1250 local_bin = bins + u;

1251 nextbinstart += bin_sizes[u];

1252 //Iterating over each element in this bin

1253 for(RandomAccessIter current = *local_bin; current < nex tbinstart; ++current) {

1254 //Swapping elements in current into place until the correct element has been swapped in

1255 for(target_bin = end_bin - static_cast<unsignedc har_type>((*current)[char_offset]); target_bin != local_bin;

1256 target_bin = end_bin - static_cast<unsig nedchar_type>((*current)[char_offset]))

1257 iter_swap(current, (*target_bin)++);

1258 }

1259 *local_bin = nextbinstart;

1260 }

1261 bins[last_bin] = lastFull;

1262 //Recursing

1263 RandomAccessIter lastPos = first;

1264 //Skip this loop for empties

1265 for(unsigned u = cache_offset; u <= cache_offset + last_bin; las tPos = bin_cache[u], ++u) {

1266 size_t count = bin_cache[u] - lastPos;

1267 //don't sort unless there are at least two items to comp are

1268 if(count < 2)

1269 continue;

1270 //using std::sort if its worst-case is better

1271 if(count < max_size)

1272 std::sort(lastPos, bin_cache[u], offset_greatert han<data_type, unsignedchar_type>(char_offset + 1));

1273 else

1274 reverse_string_sort_rec<RandomAccessIter, data_t ype, unsignedchar_type>(lastPos, bin_cache[u], char_offset + 1, bin_cache, cache _end, bin_sizes);

1275 }

1276 }

1277

1278 //String sorting recursive implementation

1279 template <class RandomAccessIter, class data_type, class unsignedchar_ty pe, class get_char, class get_length>

1280 inline void

1281 string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache

1282 , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_cha r getchar, get_length length)

1283 {

1284 //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.

1285 //Iterate to the end of the empties. If all empty, return

1286 while(length(*first) <= char_offset) {

1287 if(++first == last)

1288 return;

1289 }

1290 RandomAccessIter finish = last - 1;

1291 //Getting the last non-empty

1292 for(;length(*finish) <= char_offset; --finish) { }

1293 ++finish;

1294 update_offset(first, finish, char_offset, getchar, length);

1295

1296 const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));

1297 //Equal worst-case between radix and comparison-based is when bi n_count = n*log(n).

1298 const unsigned max_size = bin_count;

1299 const unsigned membin_count = bin_count + 1;

1300 unsigned cache_end;

1301 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, membin_count) + 1;

1302

1303 //Calculating the size of each bin; this takes roughly 10% of ru ntime

1304 for (RandomAccessIter current = first; current != last; ++curren t) {

1305 if(length(*current) <= char_offset) {

1306 bin_sizes[0]++;

1307 }

1308 else

1309 bin_sizes[getchar((*current), char_offset) + 1]+ +;

1310 }

1311 //Assign the bin positions

1312 bin_cache[cache_offset] = first;

1313 for(unsigned u = 0; u < membin_count - 1; u++)

1314 bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];

1315

1316 //Swap into place

1317 RandomAccessIter nextbinstart = first;

1318 //handling empty bins

1319 RandomAccessIter * local_bin = &(bin_cache[cache_offset]);

1320 nextbinstart += bin_sizes[0];

1321 RandomAccessIter * target_bin;

1322 //Iterating over each element in the bin of empties

1323 for(RandomAccessIter current = *local_bin; current < nextbinstar t; ++current) {

1324 //empties belong in this bin

1325 while(length(*current) > char_offset) {

1326 target_bin = bins + getchar((*current), char_off set);

1327 iter_swap(current, (*target_bin)++);

1328 }

1329 }

1330 *local_bin = nextbinstart;

1331 //iterate backwards to find the last bin with elements in it; th is saves iterations in multiple loops

1332 unsigned last_bin = bin_count - 1;

1333 for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }

1334 //This dominates runtime, mostly in the swap and bin lookups

1335 for(unsigned ii = 0; ii < last_bin; ++ii) {

1336 local_bin = bins + ii;

1337 nextbinstart += bin_sizes[ii + 1];

1338 //Iterating over each element in this bin

1339 for(RandomAccessIter current = *local_bin; current < nex tbinstart; ++current) {

1340 //Swapping elements in current into place until the correct element has been swapped in

1341 for(target_bin = bins + getchar((*current), char _offset); target_bin != local_bin;

1342 target_bin = bins + getchar((*current), char_offset))

1343 iter_swap(current, (*target_bin)++);

1344 }

1345 *local_bin = nextbinstart;

1346 }

1347 bins[last_bin] = last;

1348

1349 //Recursing

1350 RandomAccessIter lastPos = bin_cache[cache_offset];

1351 //Skip this loop for empties

1352 for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {

1353 size_t count = bin_cache[u] - lastPos;

1354 //don't sort unless there are at least two items to comp are

1355 if(count < 2)

1356 continue;

1357 //using std::sort if its worst-case is better

1358 if(count < max_size)

1359 std::sort(lastPos, bin_cache[u], offset_char_les sthan<data_type, get_char, get_length>(char_offset + 1));

1360 else

1361 string_sort_rec<RandomAccessIter, data_type, uns ignedchar_type, get_char, get_length>(lastPos, bin_cache[u], char_offset + 1, bi n_cache, cache_end, bin_sizes, getchar, length);

1362 }

1363 }

1364

1365 //String sorting recursive implementation

1366 template <class RandomAccessIter, class data_type, class unsignedchar_ty pe, class get_char, class get_length, class compare>

1367 inline void

1368 string_sort_rec(RandomAccessIter first, RandomAccessIter last, unsigned char_offset, std::vector<RandomAccessIter> &bin_cache

1369 , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_cha r getchar, get_length length, compare comp)

1370 {

1371 //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.

1372 //Iterate to the end of the empties. If all empty, return

1373 while(length(*first) <= char_offset) {

1374 if(++first == last)

1375 return;

1376 }

1377 RandomAccessIter finish = last - 1;

1378 //Getting the last non-empty

1379 for(;length(*finish) <= char_offset; --finish) { }

1380 ++finish;

1381 update_offset(first, finish, char_offset, getchar, length);

1382

1383 const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));

1384 //Equal worst-case between radix and comparison-based is when bi n_count = n*log(n).

1385 const unsigned max_size = bin_count;

1386 const unsigned membin_count = bin_count + 1;

1387 unsigned cache_end;

1388 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, membin_count) + 1;

1389

1390 //Calculating the size of each bin; this takes roughly 10% of ru ntime

1391 for (RandomAccessIter current = first; current != last; ++curren t) {

1392 if(length(*current) <= char_offset) {

1393 bin_sizes[0]++;

1394 }

1395 else

1396 bin_sizes[getchar((*current), char_offset) + 1]+ +;

1397 }

1398 //Assign the bin positions

1399 bin_cache[cache_offset] = first;

1400 for(unsigned u = 0; u < membin_count - 1; u++)

1401 bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];

1402

1403 //Swap into place

1404 RandomAccessIter nextbinstart = first;

1405 //handling empty bins

1406 RandomAccessIter * local_bin = &(bin_cache[cache_offset]);

1407 nextbinstart += bin_sizes[0];

1408 RandomAccessIter * target_bin;

1409 //Iterating over each element in the bin of empties

1410 for(RandomAccessIter current = *local_bin; current < nextbinstar t; ++current) {

1411 //empties belong in this bin

1412 while(length(*current) > char_offset) {

1413 target_bin = bins + getchar((*current), char_off set);

1414 iter_swap(current, (*target_bin)++);

1415 }

1416 }

1417 *local_bin = nextbinstart;

1418 //iterate backwards to find the last bin with elements in it; th is saves iterations in multiple loops

1419 unsigned last_bin = bin_count - 1;

1420 for(; last_bin && !bin_sizes[last_bin + 1]; --last_bin) { }

1421 //This dominates runtime, mostly in the swap and bin lookups

1422 for(unsigned u = 0; u < last_bin; ++u) {

1423 local_bin = bins + u;

1424 nextbinstart += bin_sizes[u + 1];

1425 //Iterating over each element in this bin

1426 for(RandomAccessIter current = *local_bin; current < nex tbinstart; ++current) {

1427 //Swapping elements in current into place until the correct element has been swapped in

1428 for(target_bin = bins + getchar((*current), char _offset); target_bin != local_bin;

1429 target_bin = bins + getchar((*current), char_offset))

1430 iter_swap(current, (*target_bin)++);

1431 }

1432 *local_bin = nextbinstart;

1433 }

1434 bins[last_bin] = last;

1435

1436 //Recursing

1437 RandomAccessIter lastPos = bin_cache[cache_offset];

1438 //Skip this loop for empties

1439 for(unsigned u = cache_offset + 1; u < cache_offset + last_bin + 2; lastPos = bin_cache[u], ++u) {

1440 size_t count = bin_cache[u] - lastPos;

1441 //don't sort unless there are at least two items to comp are

1442 if(count < 2)

1443 continue;

1444 //using std::sort if its worst-case is better

1445 if(count < max_size)

1446 std::sort(lastPos, bin_cache[u], comp);

1447 else

1448 string_sort_rec<RandomAccessIter, data_type, uns ignedchar_type, get_char, get_length, compare>(lastPos

1449 , bin_cache[u], char_offset + 1, bin_cac he, cache_end, bin_sizes, getchar, length, comp);

1450 }

1451 }

1452

1453 //Sorts strings in reverse order, with empties at the end

1454 template <class RandomAccessIter, class data_type, class unsignedchar_ty pe, class get_char, class get_length, class compare>

1455 inline void

1456 reverse_string_sort_rec(RandomAccessIter first, RandomAccessIter last, u nsigned char_offset, std::vector<RandomAccessIter> &bin_cache

1457 , unsigned cache_offset, std::vector<size_t> &bin_sizes, get_cha r getchar, get_length length, compare comp)

1458 {

1459 //This section is not strictly necessary, but makes handling of long identical substrings much faster, with a mild average performance impact.

1460 RandomAccessIter curr = first;

1461 //Iterate to the end of the empties. If all empty, return

1462 while(length(*curr) <= char_offset) {

1463 if(++curr == last)

1464 return;

1465 }

1466 //Getting the last non-empty

1467 while(length(*(--last)) <= char_offset) { }

1468 ++last;

1469 //Offsetting on identical characters. This section works a char acter at a time for optimal worst-case performance.

1470 update_offset(first, last, char_offset, getchar, length);

1471

1472 const unsigned bin_count = (1 << (sizeof(unsignedchar_type)*8));

1473 //Equal worst-case between radix and comparison-based is when bi n_count = n*log(n).

1474 const unsigned max_size = bin_count;

1475 const unsigned membin_count = bin_count + 1;

1476 const unsigned max_bin = bin_count - 1;

1477 unsigned cache_end;

1478 RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_ offset, cache_end, membin_count);

1479 RandomAccessIter *end_bin = &(bin_cache[cache_offset + max_bin]) ;

1480

1481 //Calculating the size of each bin; this takes roughly 10% of ru ntime

1482 for (RandomAccessIter current = first; current != last; ++curren t) {

1483 if(length(*current) <= char_offset) {

1484 bin_sizes[bin_count]++;

1485 }

1486 else

1487 bin_sizes[max_bin - getchar((*current), char_off set)]++;

1488 }

1489 //Assign the bin positions

1490 bin_cache[cache_offset] = first;

1491 for(unsigned u = 0; u < membin_count - 1; u++)

1492 bin_cache[cache_offset + u + 1] = bin_cache[cache_offset + u] + bin_sizes[u];

1493

1494 //Swap into place

1495 RandomAccessIter nextbinstart = last;

1496 //handling empty bins

1497 RandomAccessIter * local_bin = &(bin_cache[cache_offset + bin_co unt]);

1498 RandomAccessIter lastFull = *local_bin;

1499 RandomAccessIter * target_bin;

1500 //Iterating over each element in the bin of empties

1501 for(RandomAccessIter current = *local_bin; current < nextbinstar t; ++current) {

1502 //empties belong in this bin

1503 while(length(*current) > char_offset) {

1504 target_bin = end_bin - getchar((*current), char_ offset);

1505 iter_swap(current, (*target_bin)++);

1506 }

1507 }

1508 *local_bin = nextbinstart;

1509 nextbinstart = first;

1510 //iterate backwards to find the last bin with elements in it; th is saves iterations in multiple loops

1511 unsigned last_bin = max_bin;

1512 for(; last_bin && !bin_sizes[last_bin]; --last_bin) { }

1513 //This dominates runtime, mostly in the swap and bin lookups

1514 for(unsigned u = 0; u < last_bin; ++u) {

1515 local_bin = bins + u;

1516 nextbinstart += bin_sizes[u];

1517 //Iterating over each element in this bin

1518 for(RandomAccessIter current = *local_bin; current < nex tbinstart; ++current) {

1519 //Swapping elements in current into place until the correct element has been swapped in

1520 for(target_bin = end_bin - getchar((*current), c har_offset); target_bin != local_bin;

1521 target_bin = end_bin - getchar((*current ), char_offset))

1522 iter_swap(current, (*target_bin)++);

1523 }

1524 *local_bin = nextbinstart;

1525 }

1526 bins[last_bin] = lastFull;

1527 //Recursing

1528 RandomAccessIter lastPos = first;

1529 //Skip this loop for empties

1530 for(unsigned u = cache_offset; u <= cache_offset + last_bin; las tPos = bin_cache[u], ++u) {

1531 size_t count = bin_cache[u] - lastPos;

1532 //don't sort unless there are at least two items to comp are

1533 if(count < 2)

1534 continue;

1535 //using std::sort if its worst-case is better

1536 if(count < max_size)

1537 std::sort(lastPos, bin_cache[u], comp);

1538 else

1539 reverse_string_sort_rec<RandomAccessIter, data_t ype, unsignedchar_type, get_char, get_length, compare>(lastPos

1540 , bin_cache[u], char_offset + 1, bin_cac he, cache_end, bin_sizes, getchar, length, comp);

1541 }

1542 }

1543

1544 //Holds the bin vector and makes the initial recursive call

1545 template <class RandomAccessIter, class data_type, class unsignedchar_ty pe>

1546 inline void

1547 string_sort(RandomAccessIter first, RandomAccessIter last, data_type, un signedchar_type)

1548 {

1549 std::vector<size_t> bin_sizes;

1550 std::vector<RandomAccessIter> bin_cache;

1551 string_sort_rec<RandomAccessIter, data_type, unsignedchar_type>( first, last, 0, bin_cache, 0, bin_sizes);

1552 }

1553

1554 //Holds the bin vector and makes the initial recursive call

1555 template <class RandomAccessIter, class data_type, class unsignedchar_ty pe>

1556 inline void

1557 reverse_string_sort(RandomAccessIter first, RandomAccessIter last, data_ type, unsignedchar_type)

1558 {

1559 std::vector<size_t> bin_sizes;

1560 std::vector<RandomAccessIter> bin_cache;

1561 reverse_string_sort_rec<RandomAccessIter, data_type, unsignedcha r_type>(first, last, 0, bin_cache, 0, bin_sizes);

1562 }

1563

1564 //Holds the bin vector and makes the initial recursive call

1565 template <class RandomAccessIter, class get_char, class get_length, clas s data_type, class unsignedchar_type>

1566 inline void

1567 string_sort(RandomAccessIter first, RandomAccessIter last, get_char getc har, get_length length, data_type, unsignedchar_type)

1568 {

1569 std::vector<size_t> bin_sizes;

1570 std::vector<RandomAccessIter> bin_cache;

1571 string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length);

1572 }

1573

1574 //Holds the bin vector and makes the initial recursive call

1575 template <class RandomAccessIter, class get_char, class get_length, clas s compare, class data_type, class unsignedchar_type>

1576 inline void

1577 string_sort(RandomAccessIter first, RandomAccessIter last, get_char getc har, get_length length, compare comp, data_type, unsignedchar_type)

1578 {

1579 std::vector<size_t> bin_sizes;

1580 std::vector<RandomAccessIter> bin_cache;

1581 string_sort_rec<RandomAccessIter, data_type, unsignedchar_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);

1582 }

1583

1584 //Holds the bin vector and makes the initial recursive call

1585 template <class RandomAccessIter, class get_char, class get_length, clas s compare, class data_type, class unsignedchar_type>

1586 inline void

1587 reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_c har getchar, get_length length, compare comp, data_type, unsignedchar_type)

1588 {

1589 std::vector<size_t> bin_sizes;

1590 std::vector<RandomAccessIter> bin_cache;

1591 reverse_string_sort_rec<RandomAccessIter, data_type, unsignedcha r_type, get_char, get_length, compare>(first, last, 0, bin_cache, 0, bin_sizes, getchar, length, comp);

1592 }

1593 }

1594

1595 //Allows character-type overloads

1596 template <class RandomAccessIter, class unsignedchar_type>

1597 inline void string_sort(RandomAccessIter first, RandomAccessIter last, unsigne dchar_type unused)

1598 {

1599 //Don't sort if it's too small to optimize

1600 if(last - first < detail::MIN_SORT_SIZE)

1601 std::sort(first, last);

1602 else

1603 detail::string_sort(first, last, *first, unused);

1604 }

1605

1606 //Top-level sorting call; wraps using default of unsigned char

1607 template <class RandomAccessIter>

1608 inline void string_sort(RandomAccessIter first, RandomAccessIter last)

1609 {

1610 unsigned char unused = '\0';

1611 string_sort(first, last, unused);

1612 }

1613

1614 //Allows character-type overloads

1615 template <class RandomAccessIter, class compare, class unsignedchar_type>

1616 inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp, unsignedchar_type unused)

1617 {

1618 //Don't sort if it's too small to optimize

1619 if(last - first < detail::MIN_SORT_SIZE)

1620 std::sort(first, last, comp);

1621 else

1622 detail::reverse_string_sort(first, last, *first, unused);

1623 }

1624

1625 //Top-level sorting call; wraps using default of unsigned char

1626 template <class RandomAccessIter, class compare>

1627 inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, compare comp)

1628 {

1629 unsigned char unused = '\0';

1630 reverse_string_sort(first, last, comp, unused);

1631 }

1632

1633 template <class RandomAccessIter, class get_char, class get_length>

1634 inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_cha r getchar, get_length length)

1635 {

1636 //Don't sort if it's too small to optimize

1637 if(last - first < detail::MIN_SORT_SIZE)

1638 std::sort(first, last);

1639 else {

1640 //skipping past empties at the beginning, which allows us to get the character type

1641 //.empty() is not used so as not to require a user declaration o f it

1642 while(!length(*first)) {

1643 if(++first == last)

1644 return;

1645 }

1646 detail::string_sort(first, last, getchar, length, first, getcha r((first), 0));

1647 }

1648 }

1649

1650 template <class RandomAccessIter, class get_char, class get_length, class comp are>

1651 inline void string_sort(RandomAccessIter first, RandomAccessIter last, get_cha r getchar, get_length length, compare comp)

1652 {

1653 //Don't sort if it's too small to optimize

1654 if(last - first < detail::MIN_SORT_SIZE)

1655 std::sort(first, last, comp);

1656 else {

1657 //skipping past empties at the beginning, which allows us to get the character type

1658 //.empty() is not used so as not to require a user declaration o f it

1659 while(!length(*first)) {

1660 if(++first == last)

1661 return;

1662 }

1663 detail::string_sort(first, last, getchar, length, comp, first, getchar((first), 0));

1664 }

1665 }

1666

1667 template <class RandomAccessIter, class get_char, class get_length, class comp are>

1668 inline void reverse_string_sort(RandomAccessIter first, RandomAccessIter last, get_char getchar, get_length length, compare comp)

1669 {

1670 //Don't sort if it's too small to optimize

1671 if(last - first < detail::MIN_SORT_SIZE)

1672 std::sort(first, last, comp);

1673 else {

1674 //skipping past empties at the beginning, which allows us to get the character type

1675 //.empty() is not used so as not to require a user declaration o f it

1676 while(!length(*(--last))) {

1677 //Note: if there is just one non-empty, and it's at the beginning, then it's already in sorted order

1678 if(first == last)

1679 return;

1680 }

1681 //making last just after the end of the non-empty part of the ar ray

1682 ++last;

1683 detail::reverse_string_sort(first, last, getchar, length, comp, first, getchar((first), 0));

1684 }

1685 }

1686 }

1687

1688 #endif

OLD	NEW

« no previous file with comments | « webrtc/system_wrappers/source/spreadsortlib/constants.hpp ('k') | webrtc/system_wrappers/test/TestSort/TestSort.cc » ('j') | no next file with comments »