src/Algo/RoadSortingLayer.cc

0001 #include "FWCore/MessageLogger/interface/MessageLogger.h"
0002
0003 #include "L1Trigger/L1TMuonEndCapPhase2/interface/EMTFContext.h"
0004 #include "L1Trigger/L1TMuonEndCapPhase2/interface/Utils/DataUtils.h"
0005 #include "L1Trigger/L1TMuonEndCapPhase2/interface/Utils/DebugUtils.h"
0006
0007 #include "L1Trigger/L1TMuonEndCapPhase2/interface/Algo/RoadSortingLayer.h"
0008
0009 using namespace emtf::phase2::algo;
0010
0011 RoadSortingLayer::RoadSortingLayer(const EMTFContext& context) : context_(context) {}
0012
0013 void RoadSortingLayer::apply(const unsigned int& first_n,
0014                              const std::vector<road_collection_t>& zone_roads,
0015                              std::vector<road_t>& best_roads) const {
0016   // Find the best roads from each zone
0017   std::vector<road_t> top_roads;
0018
0019   for (unsigned int i_zone = 0; i_zone < zone_roads.size(); ++i_zone) {  // Loop Zones
0020
0021     auto& roads = zone_roads[i_zone];
0022
0023     // Suppress qualities of non local maximum
0024     road_collection_t suppressed_roads;
0025
0026     {
0027       const int last_col = v3::kHitmapNCols - 1;
0028
0029       for (unsigned int i_col = 0; i_col < v3::kHitmapNCols; ++i_col) {
0030         bool is_local_max = true;
0031         bool is_last_col = i_col == last_col;
0032         bool is_first_col = i_col == 0;
0033
0034         // If this is not the last column, compare it with the next column's road
0035         // If this column has better or equal quality than the next, this is still the local max
0036         if (is_local_max && !is_last_col) {
0037           is_local_max &= (roads[i_col].quality >= roads[i_col + 1].quality);
0038         }
0039
0040         // If this is not the first column, compare it with the previous column's road
0041         // If this column has better quality than the previous, this is still the local max
0042         if (is_local_max && !is_first_col) {
0043           is_local_max &= (roads[i_col].quality > roads[i_col - 1].quality);
0044         }
0045
0046         // Suppress qualities
0047         if (is_local_max) {
0048           suppressed_roads[i_col].zone = i_zone;
0049           suppressed_roads[i_col].col = i_col;
0050           suppressed_roads[i_col].pattern = roads[i_col].pattern;
0051           suppressed_roads[i_col].quality = roads[i_col].quality;
0052         } else {
0053           // Debug Info
0054           if (this->context_.config_.verbosity_ > 2 && roads[i_col].quality > 0) {
0055             edm::LogInfo("L1TEMTFpp") << "Road Suppressed"
0056                                       << " zone " << i_zone << " col " << i_col << " pat " << roads[i_col].pattern
0057                                       << " qual " << roads[i_col].quality << std::endl;
0058           }
0059
0060           // Suppress
0061           suppressed_roads[i_col].zone = i_zone;
0062           suppressed_roads[i_col].col = i_col;
0063           suppressed_roads[i_col].pattern = roads[i_col].pattern;
0064           suppressed_roads[i_col].quality = 0;
0065         }
0066       }
0067     }
0068
0069     // Keep best of every pair
0070     const int keep_n_roads = v3::kHitmapNCols / 2;
0071
0072     road_t roads_kept[keep_n_roads];
0073
0074     {
0075       for (unsigned int i_col = 0; i_col < keep_n_roads; ++i_col) {
0076         bool is_single = (i_col * 2 + 1) >= v3::kHitmapNCols;
0077
0078         if (is_single || suppressed_roads[i_col * 2].quality > 0) {
0079           roads_kept[i_col] = suppressed_roads[i_col * 2];
0080         } else {
0081           roads_kept[i_col] = suppressed_roads[i_col * 2 + 1];
0082         }
0083
0084         if (this->context_.config_.verbosity_ > 2 && roads_kept[i_col].quality > 0) {
0085           edm::LogInfo("L1TEMTFpp") << "Road Kept"
0086                                     << " zone " << roads_kept[i_col].zone << " col " << roads_kept[i_col].col << " pat "
0087                                     << roads_kept[i_col].pattern << " qual " << roads_kept[i_col].quality << std::endl;
0088         }
0089       }
0090     }
0091
0092     // Mergesort-reduce to n best roads
0093     // This will sort descending order (higher-value means lower-index) and keep the first n roads
0094
0095     // Sort the first 32 cols since there are 144 columns and we wish to sort powers of 2, therefore 128 to keep priorities.
0096     data::mergesort(
0097         roads_kept, 32, 16, [](const road_t& lhs, const road_t& rhs) -> int { return lhs.quality < rhs.quality; });
0098
0099     // Shift everything 16 cols to the left
0100     for (unsigned int i = 16; i < (keep_n_roads - 16); ++i) {
0101       roads_kept[i] = roads_kept[i + 16];
0102     }
0103
0104     // Merge-sort the remaining 128 cols
0105     data::mergesort(roads_kept, 128, first_n, [](const road_t& lhs, const road_t& rhs) -> int {
0106       return lhs.quality < rhs.quality;
0107     });
0108
0109     // Collect best roads
0110     for (unsigned int i_col = 0; i_col < first_n; ++i_col) {
0111       top_roads.push_back(roads_kept[i_col]);
0112     }
0113   }  // End Loop Zones
0114
0115   // Debug Info
0116   if (this->context_.config_.verbosity_ > 2) {
0117     for (const auto& road : top_roads) {
0118       // Short-Circuit: Skip quality-0 roads
0119       if (road.quality == 0) {
0120         continue;
0121       }
0122
0123       edm::LogInfo("L1TEMTFpp") << "Top Road"
0124                                 << " zone " << road.zone << " col " << road.col << " pat " << road.pattern << " qual "
0125                                 << road.quality << std::endl;
0126     }
0127   }
0128
0129   // Mergesort-reduce to n best roads
0130   // This will sort descending order (higher-value means lower-index) and keep the first n roads
0131
0132   // Sort the first 8 cols since there are 12 cols and we wish to sort powers of 2, therefore 8 to keep priorities
0133   data::mergesort(
0134       &top_roads[0], 8, 4, [](const road_t& lhs, const road_t& rhs) -> int { return lhs.quality < rhs.quality; });
0135
0136   // Shift everything 4 cols to the left
0137   for (unsigned int i = 4; i < top_roads.size(); ++i) {
0138     top_roads[i] = top_roads[i + 4];
0139   }
0140
0141   // Merge-sort remaining 8 cols
0142   data::mergesort(
0143       &top_roads[0], 8, first_n, [](const road_t& lhs, const road_t& rhs) -> int { return lhs.quality < rhs.quality; });
0144
0145   // Collect best roads
0146   for (unsigned int i_road = 0; i_road < first_n; ++i_road) {
0147     const auto& road = top_roads[i_road];
0148
0149     best_roads.push_back(road);
0150
0151     // Debug Info
0152     if (this->context_.config_.verbosity_ > 1 && road.quality > 0) {
0153       edm::LogInfo("L1TEMTFpp") << "Best Road " << i_road << " zone " << road.zone << " col " << road.col << " pat "
0154                                 << road.pattern << " qual " << road.quality << std::endl;
0155     }
0156   }
0157 }