File indexing completed on 2023-03-17 11:12:42
0001 #include <bitset>
0002 #include <string>
0003 #include <sstream>
0004 #include <vector>
0005 #include <map>
0006 #include <memory>
0007
0008 namespace {
0009
0010
0011 template <typename INT>
0012 std::string to_hex(INT i) {
0013 std::stringstream s;
0014 s << "0x" << std::hex << i;
0015 return s.str();
0016 }
0017
0018
0019 template <typename INT>
0020 std::string to_binary(INT i, int n) {
0021 std::stringstream s;
0022 if (sizeof(i) <= 4) {
0023 std::bitset<32> b(i);
0024 s << "0b" << b.to_string().substr(32 - n, 32);
0025 } else if (sizeof(i) <= 8) {
0026 std::bitset<64> b(i);
0027 s << "0b" << b.to_string().substr(64 - n, 64);
0028 }
0029 return s.str();
0030 }
0031
0032
0033 template <typename T, size_t N>
0034 constexpr size_t array_size(T (&)[N]) {
0035 return N;
0036 }
0037
0038
0039 template <typename T, size_t N>
0040 std::string array_as_string(const T (&arr)[N]) {
0041 std::stringstream s;
0042 const char* sep = "";
0043 for (size_t i = 0; i < N; ++i) {
0044 s << sep << arr[i];
0045 sep = " ";
0046 }
0047 return s.str();
0048 }
0049
0050
0051
0052
0053
0054
0055
0056 namespace details {
0057 template <class T>
0058 struct _reversed {
0059 T& t;
0060 _reversed(T& _t) : t(_t) {}
0061 decltype(t.rbegin()) begin() { return t.rbegin(); }
0062 decltype(t.rend()) end() { return t.rend(); }
0063 };
0064 }
0065 template <class T>
0066 details::_reversed<T> reversed(T& t) {
0067 return details::_reversed<T>(t);
0068 }
0069
0070
0071
0072 template <class STR = std::string>
0073 std::vector<STR> split_string(const std::string& s, char c = ' ', char d = ' ') {
0074 std::vector<STR> result;
0075 const char* str = s.c_str();
0076 do {
0077 const char* begin = str;
0078 while (*str != c && *str != d && *str)
0079 str++;
0080 result.emplace_back(begin, str);
0081 } while (0 != *str++);
0082 return result;
0083 }
0084
0085
0086
0087 template <class T1, class T2>
0088 void flatten_container(const T1& input, T2& output) {
0089 typename T1::const_iterator it;
0090 for (it = input.begin(); it != input.end(); ++it) {
0091 output.insert(output.end(), it->begin(), it->end());
0092 }
0093 }
0094
0095
0096 template <typename>
0097 struct is_map_of_vectors : public std::false_type {};
0098
0099 template <typename T1, typename T2>
0100 struct is_map_of_vectors<std::map<T1, std::vector<T2> > > : public std::true_type {};
0101
0102
0103 template <typename Map>
0104 void merge_map_into_map(const Map& map1, Map& map2) {
0105
0106 typedef typename Map::iterator Iterator;
0107 typedef typename Map::mapped_type Container;
0108
0109 for (auto& kv1 : map1) {
0110 std::pair<Iterator, bool> ins = map2.insert(kv1);
0111 if (!ins.second) {
0112 if (is_map_of_vectors<Map>::value) {
0113 const Container* container1 = &(kv1.second);
0114 Container* container2 = &(ins.first->second);
0115 container2->insert(container2->end(), container1->begin(), container1->end());
0116 }
0117 }
0118 }
0119 }
0120
0121
0122
0123
0124
0125 template <class ForwardIt, class BinaryPredicate, class BinaryOp>
0126 ForwardIt adjacent_cluster(ForwardIt first, ForwardIt last, BinaryPredicate adjacent, BinaryOp cluster) {
0127 if (first == last)
0128 return last;
0129
0130 ForwardIt result = first;
0131 while (++first != last) {
0132 if (!adjacent(*result, *first)) {
0133 *++result = std::move(*first);
0134 } else {
0135 cluster(*result, *first);
0136 }
0137 }
0138 return ++result;
0139 }
0140
0141
0142
0143 template <typename RandomAccessIterator, typename Compare = std::less<> >
0144 void merge_sort_merge(RandomAccessIterator first,
0145 RandomAccessIterator middle,
0146 RandomAccessIterator last,
0147 Compare cmp) {
0148 const std::ptrdiff_t len = std::distance(first, last);
0149 typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
0150 typedef typename std::iterator_traits<RandomAccessIterator>::pointer pointer;
0151 std::pair<pointer, std::ptrdiff_t> p = std::get_temporary_buffer<value_type>(len);
0152 pointer buf = p.first;
0153 pointer buf_end = std::next(p.first, p.second);
0154
0155 RandomAccessIterator first1 = first;
0156 RandomAccessIterator last1 = middle;
0157 RandomAccessIterator first2 = middle;
0158 RandomAccessIterator last2 = last;
0159
0160 while (first1 != last1 && first2 != last2) {
0161 if (cmp(*first2, *first1)) {
0162 *buf++ = *first2++;
0163 } else {
0164 *buf++ = *first1++;
0165 }
0166 }
0167 while (first1 != last1) {
0168 *buf++ = *first1++;
0169 }
0170 while (first2 != last2) {
0171 *buf++ = *first2++;
0172 }
0173
0174 buf = p.first;
0175 std::copy(buf, buf_end, first);
0176 std::return_temporary_buffer(p.first);
0177 }
0178
0179
0180 template <typename RandomAccessIterator, typename Compare = std::less<> >
0181 void merge_sort(RandomAccessIterator first, RandomAccessIterator last, Compare cmp) {
0182 const std::ptrdiff_t len = std::distance(first, last);
0183 if (len > 1) {
0184 RandomAccessIterator middle = std::next(first, len / 2);
0185 merge_sort(first, middle, cmp);
0186 merge_sort(middle, last, cmp);
0187 merge_sort_merge(first, middle, last, cmp);
0188 }
0189 }
0190
0191
0192
0193
0194 template <typename RandomAccessIterator, typename Compare, typename Compare3>
0195 void merge_sort_merge3(RandomAccessIterator first,
0196 RandomAccessIterator one_third,
0197 RandomAccessIterator two_third,
0198 RandomAccessIterator last,
0199 Compare cmp,
0200 Compare3 cmp3) {
0201 const std::ptrdiff_t len = std::distance(first, last);
0202 typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
0203 typedef typename std::iterator_traits<RandomAccessIterator>::pointer pointer;
0204 std::pair<pointer, std::ptrdiff_t> p = std::get_temporary_buffer<value_type>(len);
0205 pointer buf = p.first;
0206 pointer buf_end = std::next(p.first, p.second);
0207
0208 RandomAccessIterator first1 = first;
0209 RandomAccessIterator last1 = one_third;
0210 RandomAccessIterator first2 = one_third;
0211 RandomAccessIterator last2 = two_third;
0212 RandomAccessIterator first3 = two_third;
0213 RandomAccessIterator last3 = last;
0214
0215 while (first1 != last1 && first2 != last2 && first3 != last3) {
0216 int rr = cmp3(*first1, *first2, *first3);
0217 if (rr == 0) {
0218 *buf++ = *first1++;
0219 } else if (rr == 1) {
0220 *buf++ = *first2++;
0221 } else if (rr == 2) {
0222 *buf++ = *first3++;
0223 }
0224 }
0225
0226 if (first3 == last3) {
0227
0228 } else if (first2 == last2) {
0229 first2 = first3;
0230 last2 = last3;
0231 } else if (first1 == last1) {
0232 first1 = first2;
0233 last1 = last2;
0234 first2 = first3;
0235 last2 = last3;
0236 }
0237
0238 while (first1 != last1 && first2 != last2) {
0239 if (cmp(*first2, *first1)) {
0240 *buf++ = *first2++;
0241 } else {
0242 *buf++ = *first1++;
0243 }
0244 }
0245 while (first1 != last1) {
0246 *buf++ = *first1++;
0247 }
0248 while (first2 != last2) {
0249 *buf++ = *first2++;
0250 }
0251
0252 buf = p.first;
0253 std::copy(buf, buf_end, first);
0254 std::return_temporary_buffer(p.first);
0255 }
0256
0257
0258 template <typename RandomAccessIterator, typename Compare, typename Compare3>
0259 void merge_sort3(RandomAccessIterator first, RandomAccessIterator last, Compare cmp, Compare3 cmp3) {
0260 const std::ptrdiff_t len = std::distance(first, last);
0261 if (len > 1) {
0262 RandomAccessIterator one_third = std::next(first, (len + 2) / 3);
0263 RandomAccessIterator two_third = std::next(first, (len + 2) / 3 * 2);
0264 merge_sort3(first, one_third, cmp, cmp3);
0265 merge_sort3(one_third, two_third, cmp, cmp3);
0266 merge_sort3(two_third, last, cmp, cmp3);
0267 merge_sort_merge3(first, one_third, two_third, last, cmp, cmp3);
0268 }
0269 }
0270
0271
0272 template <typename RandomAccessIterator, typename Compare, typename Compare3>
0273 void merge_sort3_with_hint(
0274 RandomAccessIterator first, RandomAccessIterator last, Compare cmp, Compare3 cmp3, std::ptrdiff_t d) {
0275 const std::ptrdiff_t len = std::distance(first, last);
0276 if (len > 1) {
0277 RandomAccessIterator one_third = std::next(first, d);
0278 RandomAccessIterator two_third = std::next(first, d * 2);
0279 merge_sort3(first, one_third, cmp, cmp3);
0280 merge_sort3(one_third, two_third, cmp, cmp3);
0281 merge_sort3(two_third, last, cmp, cmp3);
0282 merge_sort_merge3(first, one_third, two_third, last, cmp, cmp3);
0283 }
0284 }
0285
0286 }