interface/Utils/DataUtils.h

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   // Merge-Sort
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     // Loop pairs
0040     while (wire_2 < block_end) {
0041       // Trim results
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       // Swap Wires
0051       swapWires(arr, wire_1, wire_2, comparator);
0052
0053       // Calculate next wire_1
0054       if (step == 1) {
0055         wire_1 = wire_2 + 1;
0056       } else {
0057         wire_1 = wire_1 + 1;
0058       }
0059
0060       // Calculate next wire_2
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     // Sort
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     // Merge
0075     auto offset = 0u;
0076     auto step = 2u;
0077     auto block_size = step * 2;
0078
0079     // Loop block sizes
0080     while (true) {
0081       // Loop step sizes
0082       // If the offset is greater than the amount of wires to keep
0083       // there's no need to continue, since (offset)-wires are known
0084       // to not contribute to the end result
0085       while (true) {
0086         // Loop blocks
0087         auto block_begin = 0u;
0088         auto block_end = block_size;
0089
0090         while (block_begin < arr_size) {
0091           // Constrain block_end
0092           if (block_end > arr_size)
0093             block_end = arr_size;
0094
0095           // Merge block
0096           mergesortBlock(arr, offset, step, block_begin, block_end, first_n, comparator);
0097
0098           // Move to next block
0099           block_begin = block_end;
0100           block_end = block_end + block_size;
0101         }
0102
0103         // Decrease step
0104         if (step > 2) {
0105           // For each pass we are certain of the local min and max
0106           // so skip 2 wires and reduce the step
0107           offset = offset + 2;
0108           step = step - 2;
0109         } else if (step == 2) {
0110           // For final pass we are certain of the global min and max
0111           // so skip 1 wire and compare wires 1 to 1, the last value
0112           // will be left without a partner; naturally since
0113           // it's the global min
0114           offset = 1;
0115           step = 1;
0116         } else {
0117           // Short-Circuit: Done
0118           break;
0119         }
0120       }
0121
0122       // Short-Circuit: No more wires
0123       if (block_size >= arr_size)
0124         break;
0125
0126       // Double the block size
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   // Median Calculation
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;  // Mid = (Top + Bot) / 2
0147     } else {
0148       mid = arr[(arr_size - 1) / 2];
0149     }
0150
0151     return mid;
0152   }
0153 }  // namespace emtf::phase2::data
0154
0155 #endif  // L1Trigger_L1TMuonEndCapPhase2_DataUtils_h not defined