L1TMuonEndCap/src/helper.h

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::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   // See above
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   // An extended version of the merge sort algorithm to incorporate a 3-way
0191   // comparator. It resorts back to 2-way comparator when one of the three
0192   // lists to be merged is empty.
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       // do nothing
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   // See above
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   // See above. 'Hint' is provided to force the very first division. This is needed to match FW.
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 }  // namespace