Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2021-02-14 14:23:21

0001 #include <bitset>
0002 #include <string>
0003 #include <sstream>
0004 #include <vector>
0005 #include <map>
0006 #include <memory>
0007 
0008 namespace {
0009 
0010   // Return an integer as a hex string
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   // Return an integer as a binary string
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   // Return the size of a 1D plain array
0033   template <typename T, size_t N>
0034   constexpr size_t array_size(T (&)[N]) {
0035     return N;
0036   }
0037 
0038   // Return the elements of a 1D plain array as a string (elements are separated by ' ')
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   // This function allows one to loop over a container in reversed order using C++11 for(auto ...) loop
0051   // e.g.
0052   //   for (auto x: reversed(v)) {
0053   //     // do something
0054   //   }
0055   // See http://stackoverflow.com/a/21510185
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   }  // namespace details
0065   template <class T>
0066   details::_reversed<T> reversed(T& t) {
0067     return details::_reversed<T>(t);
0068   }
0069 
0070   // Split a string by delimiters (default: ' ') into a vector of string
0071   // See http://stackoverflow.com/a/53878
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   // Flatten a vector<vector<T> > into a vector<T>
0086   // The input type T can be different from the output type T
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   // Check type for map of vector
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   // Merge a map of vectors (map1) into another map of vectors (map2)
0103   template <typename Map>
0104   void merge_map_into_map(const Map& map1, Map& map2) {
0105     // This is customized for maps of containers.
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) {                      // if insertion into map2 was not successful
0112         if (is_map_of_vectors<Map>::value) {  // special case for map of vectors
0113           const Container* container1 = &(kv1.second);
0114           Container* container2 = &(ins.first->second);
0115           container2->insert(container2->end(), container1->begin(), container1->end());
0116         }  // else do nothing
0117       }
0118     }
0119   }
0120 
0121   // A simple nearest-neighbor clustering algorithm
0122   // It iterates through a sorted container once, whenever the 'adjacent'
0123   // comparison between two elements evaluates to true, the 'cluster'
0124   // operator is called to merge them.
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   // Textbook merge sort algorithm with the same interface as std::sort()
0142   // An internal buffer of the same size as the container is used internally.
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   // See above
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   // An extended version of the merge sort algorithm to incorporate a 3-way
0192   // comparator. It resorts back to 2-way comparator when one of the three
0193   // lists to be merged is empty.
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       // do nothing
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   // See above
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   // See above. 'Hint' is provided to force the very first division. This is needed to match FW.
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 }  // namespace