RetroSearch Browse

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from http://www.ncbi.nlm.nih.gov/IEB/ToolBox/CPP_DOC/doxyhtml/timsort_8hpp_source.html below:

NCBI C++ ToolKit: include/util/timsort.hpp Source File

29 #ifndef GFX_TIMSORT_HPP 30 #define GFX_TIMSORT_HPP 38 #ifdef ENABLE_TIMSORT_LOG 40 #define GFX_TIMSORT_LOG(expr) (std::clog << "# "

<< __func__ << ": " << expr << std::endl)

42 #define GFX_TIMSORT_LOG(expr) ((void)0) 45 #if __cplusplus >= 201103L && !DISABLE_STD_MOVE 46 #define ENABLE_STD_MOVE 1 50 #define GFX_TIMSORT_MOVE(x) std::move(x) 51 #define GFX_TIMSORT_MOVE_RANGE(in1, in2, out) std::move((in1), (in2), (out)) 52 #define GFX_TIMSORT_MOVE_BACKWARD(in1, in2, out) std::move_backward((in1), (in2), (out)) 54 #define GFX_TIMSORT_MOVE(x) (x) 55 #define GFX_TIMSORT_MOVE_RANGE(in1, in2, out) std::copy((in1), (in2), (out)) 56 #define GFX_TIMSORT_MOVE_BACKWARD(in1, in2, out) std::copy_backward((in1), (in2), (out)) 68 template

typename

RandomAccessIterator>

69 inline void timsort

(RandomAccessIterator

const first

, RandomAccessIterator

const last

);

74 template

typename

RandomAccessIterator,

typename

LessFunction>

75 inline void timsort

(RandomAccessIterator

const first

, RandomAccessIterator

const last

, LessFunction compare);

81 template

typename

Value,

typename

LessFunction>

class Compare

{

101 return

less_

(x, y);

112 template

typename

RandomAccessIterator,

typename

LessFunction>

class TimSort

{

115 typedef typename

std::iterator_traits<iter_t>::reference

ref_t

;

116 typedef typename

std::iterator_traits<iter_t>::difference_type

diff_t

;

142 diff_t

nRemaining = (hi - lo);

143 if

(nRemaining < 2) {

160 if

(runLen < minRun) {

162 binarySort

(cur, cur + force, cur + runLen, c);

170

nRemaining -= runLen;

171

}

while

(nRemaining != 0);

178

" pending_.size(): "

<< ts.

pending_

.size());

182 assert

(lo <= start && start <= hi);

186 for

(; start < hi; ++start) {

191 for

(

iter_t

p = start; p > pos; --p) {

206 if

(compare.

(*(runHi++), *lo)) {

207 while

(runHi < hi && compare.

(*runHi, *(runHi - 1))) {

210

std::reverse(lo, runHi);

212 while

(runHi < hi && compare.

(*runHi, *(runHi - 1))) {

271 assert

(

== stackSize - 2 ||

== stackSize - 3);

278 assert

(len1 > 0 && len2 > 0);

279 assert

(base1 + len1 == base2);

283 if

(

== stackSize - 3) {

299

len2 =

gallopLeft

(*(base1 + (len1 - 1)), base2, len2, len2 - 1);

306 mergeLo

(base1, len1, base2, len2);

308 mergeHi

(base1, len1, base2, len2);

320 while

(ofs < maxOfs &&

comp_

(

key

, *(base + (hint + ofs)))) {

322

ofs = (ofs << 1) + 1;

335 diff_t const

maxOfs = hint + 1;

336 while

(ofs < maxOfs &&

comp_

(

key

, *(base + (hint - ofs)))) {

338

ofs = (ofs << 1) + 1;

349

lastOfs = hint - ofs;

352 assert

(-1 <= lastOfs && lastOfs < ofs && ofs <=

len

);

364 diff_t const

maxOfs = hint + 1;

365 while

(ofs < maxOfs &&

comp_

(

key

, *(base + (hint - ofs)))) {

367

ofs = (ofs << 1) + 1;

378

lastOfs = hint - ofs;

382 while

(ofs < maxOfs &&

comp_

(

key

, *(base + (hint + ofs)))) {

384

ofs = (ofs << 1) + 1;

397 assert

(-1 <= lastOfs && lastOfs < ofs && ofs <=

len

);

403 assert

(len1 > 0 && len2 > 0 && base1 + len1 == base2);

429 bool

break_outer =

false

;

431 assert

(len1 > 1 && len2 > 0);

433 if

(

comp_

(*cursor2, *cursor1)) {

450

}

while

((count1 | count2) < minGallop);

456 assert

(len1 > 1 && len2 > 0);

476

count2 =

gallopLeft

(*cursor1, cursor2, len2, 0);

512 assert

(len1 != 0 &&

"Comparison function violates its general contract"

);

520 assert

(len1 > 0 && len2 > 0 && base1 + len1 == base2);

524 iter_t

cursor1 = base1 + len1;

526 iter_t

dest = base2 + len2;

548 bool

break_outer =

false

;

550 assert

(len1 > 0 && len2 > 1);

552 if

(

comp_

(*(cursor2-1), *(cursor1-1))) {

569

}

while

((count1 | count2) < minGallop);

575 assert

(len1 > 0 && len2 > 1);

577

count1 = len1 -

gallopRight

(*(cursor2-1), base1, len1, len1 - 1);

595

count2 = len2 -

gallopLeft

(*(cursor1-1),

tmp_

.begin(), len2, len2 - 1);

632 assert

(len2 != 0 &&

"Comparison function violates its general contract"

);

646 template

typename

IterT,

typename

LessT>

friend void timsort

(IterT

first

, IterT

last

, LessT c);

649 template

typename

RandomAccessIterator>

650 inline void timsort

(RandomAccessIterator

const first

, RandomAccessIterator

const last

) {

655 template

typename

RandomAccessIterator,

typename

LessFunction>

656 inline void timsort

(RandomAccessIterator

const first

, RandomAccessIterator

const last

, LessFunction compare) {

662 #undef GFX_TIMSORT_LOG 663 #undef GFX_TIMSORT_MOVE 664 #undef GFX_TIMSORT_MOVE_RANGE 665 #undef GFX_TIMSORT_MOVE_BACKWARD

bool le(value_type x, value_type y)

bool lt(value_type x, value_type y)

bool ge(value_type x, value_type y)

func_type & less_function()

Compare(const Compare< value_type, func_type > &other)

bool gt(value_type x, value_type y)

void mergeLo(iter_t const base1, diff_t len1, iter_t const base2, diff_t len2)

diff_t gallopRight(ref_t key, Iter const base, diff_t const len, diff_t const hint)

std::iterator_traits< iter_t >::difference_type diff_t

static diff_t minRunLength(diff_t n)

std::iterator_traits< iter_t >::value_type value_t

void pushRun(iter_t const runBase, diff_t const runLen)

RandomAccessIterator iter_t

diff_t gallopLeft(ref_t key, Iter const base, diff_t const len, diff_t const hint)

std::iterator_traits< iter_t >::reference ref_t

static diff_t countRunAndMakeAscending(iter_t const lo, iter_t const hi, compare_t compare)

void mergeHi(iter_t const base1, diff_t len1, iter_t const base2, diff_t len2)

Compare< const value_t &, LessFunction > compare_t

std::vector< value_t >::iterator tmp_iter_t

std::vector< value_t > tmp_

void mergeForceCollapse()

static const int MIN_MERGE

static void sort(iter_t const lo, iter_t const hi, compare_t c)

void copy_to_tmp(iter_t const begin, diff_t const len)

friend void timsort(IterT first, IterT last, LessT c)

static void binarySort(iter_t const lo, iter_t const hi, iter_t start, compare_t compare)

void mergeAt(diff_t const i)

static const int MIN_GALLOP

std::vector< run > pending_

static DLIST_TYPE *DLIST_NAME() first(DLIST_LIST_TYPE *list)

static DLIST_TYPE *DLIST_NAME() last(DLIST_LIST_TYPE *list)

void timsort(RandomAccessIterator const first, RandomAccessIterator const last)

Same as std::stable_sort(first, last).

double value_type

The numeric datatype used by the parser.

const struct ncbi::grid::netcache::search::fields::KEY key

GenericValue< UTF8<> > Value

GenericValue with UTF8 encoding.

double r(size_t dimension_, const Int4 *score_, const double *prob_, double theta_)

static SLJIT_INLINE sljit_ins l(sljit_gpr r, sljit_s32 d, sljit_gpr x, sljit_gpr b)

run(iter_t const b, diff_t const l)

#define GFX_TIMSORT_MOVE(x)

#define GFX_TIMSORT_MOVE_BACKWARD(in1, in2, out)

#define GFX_TIMSORT_MOVE_RANGE(in1, in2, out)

#define GFX_TIMSORT_LOG(expr)

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4