-
Notifications
You must be signed in to change notification settings - Fork 0
/
checks.h
47 lines (43 loc) · 1.82 KB
/
checks.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include "inplaceMerge.h"
#include "merges.h"
template <class Iter, class Compare>
void checkIfLast(int &pos, int &n, MonotonyType &monotony, int &curLen, Iter &begin, Compare &cmp, vector<pair<Iter, int> > &runs, const ITimSortParams ¶ms){
if (monotony == decreasing) {
Reverse(begin + (pos + 1 - curLen), begin + pos + 1);
}
runs.push_back({begin + (pos + 1 - curLen), curLen});
mergeRuns(runs, cmp, params);
}
template <class Iter, class Compare>
void checkIfUndefined(int &pos, int &n, MonotonyType &monotony, int &curLen, Iter &begin, Compare &cmp, vector<pair<Iter, int> > &runs, const ITimSortParams ¶ms){
if (greaterEqual(begin + pos + 1, begin + pos, cmp)) {
monotony = nonDecreasing;
} else {
monotony = decreasing;
}
++curLen;
}
template <class Iter, class Compare>
void checkIfDecreasing(int &pos, int &n, MonotonyType &monotony, int &curLen, int &length, Iter &begin, Compare &cmp, vector<pair<Iter, int> > &runs, const ITimSortParams ¶ms){
if (lessEqual(begin + pos + 1, begin + pos, cmp)) {
++curLen;
} else {
if (curLen < length) {
movePos(curLen, length, n, pos, begin, cmp);
} else {
Reverse(begin + (pos + 1 - curLen), begin + pos + 1);
}
updateRuns(runs, pos, begin, curLen, cmp, monotony, params);
}
}
template <class Iter, class Compare>
void checkIfNonDecreasing(int &pos, int &n, MonotonyType &monotony, int &curLen, int &length, Iter &begin, Compare &cmp, vector<pair<Iter, int> > &runs, const ITimSortParams ¶ms){
if (greaterEqual(begin + pos + 1, begin + pos, cmp)) {
++curLen;
} else {
if (curLen < length) {
movePos(curLen, length, n, pos, begin, cmp);
}
updateRuns(runs, pos, begin, curLen, cmp, monotony, params);
}
}