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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
#pragma once
#include <util/generic/algorithm.h>
#include <util/generic/array_ref.h>
#include <util/generic/strbuf.h>
#include <array>
#include <functional>
namespace NEnumSerializationRuntime {
enum class ESortOrder: int {
Unordered = 0, // беспорядок
Ascending = 1, // можно искать бинарным поиском, но есть эквивалентные ключи. Гланый ключ находится через lower_bound
StrictlyAscending = 2, // + все ключи уникальны
DirectMapping = 3, // последовательность целых чисел без пропусков, индекс элемента можно вычислить из его значения не делая поиск
};
template <typename TEnumRepresentationType>
struct TEnumStringPair {
TEnumRepresentationType Key;
TStringBuf Name;
};
template <typename TEnumRepresentationType>
constexpr ESortOrder GetKeyFieldSortOrder(const TArrayRef<const TEnumStringPair<TEnumRepresentationType>> initializer) {
if (initializer.empty()) {
return ESortOrder::DirectMapping;
}
bool direct = true;
bool strict = true;
bool sorted = true;
const auto* data = initializer.data();
const size_t size = initializer.size();
TEnumRepresentationType expected = data[0].Key;
for (size_t i = 1; i < size; ++i) {
const auto& prev = data[i - 1].Key;
const auto& next = data[i - 0].Key;
if (++expected != next) {
direct = false;
}
if (prev >= next) {
strict = false;
}
if (prev > next) {
sorted = false;
break;
}
}
return direct ? ESortOrder::DirectMapping
: strict ? ESortOrder::StrictlyAscending
: sorted ? ESortOrder::Ascending
: ESortOrder::Unordered;
}
template <typename TEnumRepresentationType>
constexpr ESortOrder GetNameFieldSortOrder(const TArrayRef<const TEnumStringPair<TEnumRepresentationType>> initializer) {
if (initializer.empty()) {
return ESortOrder::DirectMapping;
}
bool strict = true;
bool sorted = true;
const auto* data = initializer.data();
const size_t size = initializer.size();
for (size_t i = 1; i < size; ++i) {
const std::string_view& prev = data[i - 1].Name;
const std::string_view& next = data[i - 0].Name;
const int cmp = prev.compare(next);
if (cmp >= 0) {
strict = false;
}
if (cmp > 0) {
sorted = false;
break;
}
}
return strict ? ESortOrder::StrictlyAscending
: sorted ? ESortOrder::Ascending
: ESortOrder::Unordered;
}
#if defined(__cpp_lib_array_constexpr) && defined(__cpp_lib_constexpr_algorithms) && defined(__cpp_lib_constexpr_functional)
// Функция должна состоять из единственного вызова
// std::stable_sort(v.begin(), v.end(), [](const T& a, const T& b) { return a.Key < b.Key; });
// и возврата отсортированного массива.
// Но в C++20 stable_sort ещё не имеет спецификатора constexpr и не может использоваться тут.
// Поэтому в текущей реализации вместо этого делается обычная нестабильная сортировка пар {ключ элемента, положение элемента}.
template <class T, size_t N>
constexpr std::array<T, N> TryStableSortKeys(std::array<T, N> v) {
// Компилятор обычно ограничивает число шагов, которые можно сделать при вычислении constexpr-функции (см. опции `-fconstexpr-steps=N` или `/constexpr:stepsN`).
// Число же шагов, необходимых для сортировки, зависит не только от длины массива,
// но и от используемого алгоритма, от числа вложенных функций в его реализации, и от наличия assert'ов в ней.
// Что также означает, что число шагов может меняться в несколько раз при смене реализации STL или при сборке с NDEBUG и без.
//
// Исчерпание бюджета на действия приведёт к ошибки компиляции без возможности восстановления.
// То есть без возможности обнаружить эту ситуацию и переключится на другой алгоритм.
//
// Поэтому максимальный размер сортируемого массива заранее ограничивается безопасной константой.
// А все массивы большего размера досортировываются уже во время исполнения программы.
constexpr size_t MAX_COMPILE_TIME_SORT_ARRAY_SIZE = 2'000;
if (v.size() > MAX_COMPILE_TIME_SORT_ARRAY_SIZE) {
return v;
}
// Многие перечисления уже отсортированы. Но текущая реализация constexpr std::sort в libcxx не проверяет этот случай и всегда работает за время Θ(NlogN)
if (IsSortedBy(v.begin(), v.end(), std::mem_fn(&T::Key))) {
return v;
}
std::array<const T*, N> ptrs;
Iota(ptrs.begin(), ptrs.end(), &v[0]);
auto cmpKeyPointersFn = [](const T* a, const T* b) {
if (a->Key != b->Key) {
return a->Key < b->Key;
}
return a < b; // ensure stable sort order
};
Sort(ptrs.begin(), ptrs.end(), cmpKeyPointersFn);
std::array<T, N> r;
for (size_t i = 0; i < N; ++i) {
r[i] = *ptrs[i];
}
return r;
}
#else
template <class T, size_t N>
constexpr std::array<T, N> TryStableSortKeys(std::array<T, N> v) {
return v; // skip sort in case of old language version
}
#endif
}
|
