-
Notifications
You must be signed in to change notification settings - Fork 0
/
sorting.cpp
95 lines (76 loc) · 2.86 KB
/
sorting.cpp
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include "lib.h"
struct obj_idx_less {
OBJ *objs;
obj_idx_less(OBJ *objs) : objs(objs) {}
bool operator () (uint32 idx1, uint32 idx2) {
return comp_objs(objs[idx1], objs[idx2]) > 0;
}
};
struct obj_idx_less_no_eq {
OBJ *values;
obj_idx_less_no_eq(OBJ *values) : values(values) {}
bool operator () (uint32 idx1, uint32 idx2) {
int cr = comp_objs(values[idx1], values[idx2]);
return cr != 0 ? cr > 0 : idx1 < idx2;
}
};
////////////////////////////////////////////////////////////////////////////////
struct obj_pair_idx_less {
OBJ *major_sort, *minor_sort;
obj_pair_idx_less(OBJ *major_sort, OBJ *minor_sort) : major_sort(major_sort), minor_sort(minor_sort) {}
bool operator () (uint32 idx1, uint32 idx2) {
int cr = comp_objs(major_sort[idx1], major_sort[idx2]);
if (cr != 0)
return cr > 0;
cr = comp_objs(minor_sort[idx1], minor_sort[idx2]);
if (cr != 0)
return cr > 0;
return idx1 < idx2;
}
};
////////////////////////////////////////////////////////////////////////////////
struct obj_triple_idx_less {
OBJ *col1, *col2, *col3;
obj_triple_idx_less(OBJ *col1, OBJ *col2, OBJ *col3) : col1(col1), col2(col2), col3(col3) {}
bool operator () (uint32 idx1, uint32 idx2) {
int cr = comp_objs(col1[idx1], col1[idx2]);
if (cr != 0)
return cr > 0;
cr = comp_objs(col2[idx1], col2[idx2]);
if (cr != 0)
return cr > 0;
cr = comp_objs(col3[idx1], col3[idx2]);
if (cr != 0)
return cr > 0;
return idx1 < idx2;
}
};
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
void stable_index_sort(uint32 *index, OBJ *values, uint32 count) {
for (uint32 i=0 ; i < count ; i++)
index[i] = i;
std::sort(index, index+count, obj_idx_less_no_eq(values));
}
void stable_index_sort(uint32 *index, OBJ *major_sort, OBJ *minor_sort, uint32 count) {
for (uint32 i=0 ; i < count ; i++)
index[i] = i;
std::sort(index, index+count, obj_pair_idx_less(major_sort, minor_sort));
}
void stable_index_sort(uint32 *index, OBJ *major_sort, OBJ *middle_sort, OBJ *minor_sort, uint32 count) {
for (uint32 i=0 ; i < count ; i++)
index[i] = i;
std::sort(index, index+count, obj_triple_idx_less(major_sort, middle_sort, minor_sort));
}
////////////////////////////////////////////////////////////////////////////////
void index_sort(uint32 *index, OBJ *values, uint32 count) {
for (uint32 i=0 ; i < count ; i++)
index[i] = i;
std::sort(index, index+count, obj_idx_less(values));
}
void index_sort(uint32 *index, OBJ *major_sort, OBJ *minor_sort, uint32 count) {
stable_index_sort(index, major_sort, minor_sort, count);
}
void index_sort(uint32 *index, OBJ *major_sort, OBJ *middle_sort, OBJ *minor_sort, uint32 count) {
stable_index_sort(index, major_sort, middle_sort, minor_sort, count);
}