File indexing completed on 2024-04-06 12:20:56
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::unique_ptr<value_type[]> p{new value_type[len]};
0152 pointer buf = p.get();
0153 pointer buf_end = buf + len;
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.get();
0175 std::copy(buf, buf_end, first);
0176 }
0177
0178
0179 template <typename RandomAccessIterator, typename Compare = std::less<> >
0180 void merge_sort(RandomAccessIterator first, RandomAccessIterator last, Compare cmp) {
0181 const std::ptrdiff_t len = std::distance(first, last);
0182 if (len > 1) {
0183 RandomAccessIterator middle = std::next(first, len / 2);
0184 merge_sort(first, middle, cmp);
0185 merge_sort(middle, last, cmp);
0186 merge_sort_merge(first, middle, last, cmp);
0187 }
0188 }
0189
0190
0191
0192
0193 template <typename RandomAccessIterator, typename Compare, typename Compare3>
0194 void merge_sort_merge3(RandomAccessIterator first,
0195 RandomAccessIterator one_third,
0196 RandomAccessIterator two_third,
0197 RandomAccessIterator last,
0198 Compare cmp,
0199 Compare3 cmp3) {
0200 const std::ptrdiff_t len = std::distance(first, last);
0201 typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;
0202 typedef typename std::iterator_traits<RandomAccessIterator>::pointer pointer;
0203 std::unique_ptr<value_type[]> p{new value_type[len]};
0204 pointer buf = p.get();
0205 const pointer buf_end = buf + len;
0206
0207 RandomAccessIterator first1 = first;
0208 RandomAccessIterator last1 = one_third;
0209 RandomAccessIterator first2 = one_third;
0210 RandomAccessIterator last2 = two_third;
0211 RandomAccessIterator first3 = two_third;
0212 RandomAccessIterator last3 = last;
0213
0214 while (first1 != last1 && first2 != last2 && first3 != last3) {
0215 int rr = cmp3(*first1, *first2, *first3);
0216 if (rr == 0) {
0217 *buf++ = *first1++;
0218 } else if (rr == 1) {
0219 *buf++ = *first2++;
0220 } else if (rr == 2) {
0221 *buf++ = *first3++;
0222 }
0223 }
0224
0225 if (first3 == last3) {
0226
0227 } else if (first2 == last2) {
0228 first2 = first3;
0229 last2 = last3;
0230 } else if (first1 == last1) {
0231 first1 = first2;
0232 last1 = last2;
0233 first2 = first3;
0234 last2 = last3;
0235 }
0236
0237 while (first1 != last1 && first2 != last2) {
0238 if (cmp(*first2, *first1)) {
0239 *buf++ = *first2++;
0240 } else {
0241 *buf++ = *first1++;
0242 }
0243 }
0244 while (first1 != last1) {
0245 *buf++ = *first1++;
0246 }
0247 while (first2 != last2) {
0248 *buf++ = *first2++;
0249 }
0250
0251 buf = p.get();
0252 std::copy(buf, buf_end, first);
0253 }
0254
0255
0256 template <typename RandomAccessIterator, typename Compare, typename Compare3>
0257 void merge_sort3(RandomAccessIterator first, RandomAccessIterator last, Compare cmp, Compare3 cmp3) {
0258 const std::ptrdiff_t len = std::distance(first, last);
0259 if (len > 1) {
0260 RandomAccessIterator one_third = std::next(first, (len + 2) / 3);
0261 RandomAccessIterator two_third = std::next(first, (len + 2) / 3 * 2);
0262 merge_sort3(first, one_third, cmp, cmp3);
0263 merge_sort3(one_third, two_third, cmp, cmp3);
0264 merge_sort3(two_third, last, cmp, cmp3);
0265 merge_sort_merge3(first, one_third, two_third, last, cmp, cmp3);
0266 }
0267 }
0268
0269
0270 template <typename RandomAccessIterator, typename Compare, typename Compare3>
0271 void merge_sort3_with_hint(
0272 RandomAccessIterator first, RandomAccessIterator last, Compare cmp, Compare3 cmp3, std::ptrdiff_t d) {
0273 const std::ptrdiff_t len = std::distance(first, last);
0274 if (len > 1) {
0275 RandomAccessIterator one_third = std::next(first, d);
0276 RandomAccessIterator two_third = std::next(first, d * 2);
0277 merge_sort3(first, one_third, cmp, cmp3);
0278 merge_sort3(one_third, two_third, cmp, cmp3);
0279 merge_sort3(two_third, last, cmp, cmp3);
0280 merge_sort_merge3(first, one_third, two_third, last, cmp, cmp3);
0281 }
0282 }
0283
0284 }