File indexing completed on 2024-04-06 12:21:00
0001 #ifndef L1Trigger_L1TMuonEndCapPhase2_DataUtils_h
0002 #define L1Trigger_L1TMuonEndCapPhase2_DataUtils_h
0003
0004 #include <array>
0005 #include <vector>
0006 #include <type_traits>
0007
0008 #include "L1Trigger/L1TMuonEndCapPhase2/interface/EMTFfwd.h"
0009 #include "L1Trigger/L1TMuonEndCapPhase2/interface/EMTFTypes.h"
0010 #include "L1Trigger/L1TMuonEndCapPhase2/interface/EMTFConstants.h"
0011
0012 namespace emtf::phase2::data {
0013
0014
0015 template <typename T, typename C>
0016 void swapWires(T arr[], const unsigned int& wire_1, const unsigned int& wire_2, const C& comparator) {
0017 int result = comparator(arr[wire_1], arr[wire_2]);
0018
0019 if (result == 1) {
0020 auto temp = arr[wire_1];
0021 arr[wire_1] = arr[wire_2];
0022 arr[wire_2] = temp;
0023 }
0024 }
0025
0026 template <typename T, typename C>
0027 void mergesortBlock(T arr[],
0028 const unsigned int& offset,
0029 const unsigned int& step,
0030 const unsigned int& block_begin,
0031 const unsigned int& block_end,
0032 const unsigned int& first_n,
0033 const C& comparator) {
0034 auto wire_offset = offset + block_begin;
0035 auto wire_cutoff = first_n + block_begin;
0036 auto wire_1 = wire_offset;
0037 auto wire_2 = wire_1 + step;
0038
0039
0040 while (wire_2 < block_end) {
0041
0042 if (first_n > 0 && wire_cutoff < block_end) {
0043 bool wire_needed = (wire_offset <= wire_1) && (wire_1 <= wire_cutoff);
0044
0045 if (!wire_needed) {
0046 break;
0047 }
0048 }
0049
0050
0051 swapWires(arr, wire_1, wire_2, comparator);
0052
0053
0054 if (step == 1) {
0055 wire_1 = wire_2 + 1;
0056 } else {
0057 wire_1 = wire_1 + 1;
0058 }
0059
0060
0061 wire_2 = wire_1 + step;
0062 }
0063 }
0064
0065 template <typename T, typename C>
0066 void mergesort(T arr[], const unsigned int& arr_size, const unsigned int& first_n, const C& comparator) {
0067
0068 auto n_pairs = static_cast<unsigned int>(arr_size / 2);
0069
0070 for (unsigned int i = 0; i < n_pairs; ++i) {
0071 swapWires(arr, 2 * i, 2 * i + 1, comparator);
0072 }
0073
0074
0075 auto offset = 0u;
0076 auto step = 2u;
0077 auto block_size = step * 2;
0078
0079
0080 while (true) {
0081
0082
0083
0084
0085 while (true) {
0086
0087 auto block_begin = 0u;
0088 auto block_end = block_size;
0089
0090 while (block_begin < arr_size) {
0091
0092 if (block_end > arr_size)
0093 block_end = arr_size;
0094
0095
0096 mergesortBlock(arr, offset, step, block_begin, block_end, first_n, comparator);
0097
0098
0099 block_begin = block_end;
0100 block_end = block_end + block_size;
0101 }
0102
0103
0104 if (step > 2) {
0105
0106
0107 offset = offset + 2;
0108 step = step - 2;
0109 } else if (step == 2) {
0110
0111
0112
0113
0114 offset = 1;
0115 step = 1;
0116 } else {
0117
0118 break;
0119 }
0120 }
0121
0122
0123 if (block_size >= arr_size)
0124 break;
0125
0126
0127 offset = 0;
0128 step = block_size;
0129 block_size = step * 2;
0130 }
0131 }
0132
0133 template <typename T, typename C>
0134 void mergesort(T arr[], const unsigned int& arr_size, const C& comparator) {
0135 mergesort(arr, arr_size, 0, comparator);
0136 }
0137
0138
0139 template <typename T>
0140 T getMedianOfSorted(T arr[], const unsigned int& arr_size) {
0141 T mid;
0142
0143 if ((arr_size % 2) == 0) {
0144 const auto& top = arr[arr_size / 2];
0145 const auto& bot = arr[arr_size / 2 - 1];
0146 mid = (top + bot) >> 1;
0147 } else {
0148 mid = arr[(arr_size - 1) / 2];
0149 }
0150
0151 return mid;
0152 }
0153 }
0154
0155 #endif