Back to home page

Project CMSSW displayed by LXR

 
 

    


File indexing completed on 2022-05-06 00:35:16

0001 #include "DataFormats/Provenance/interface/IndexIntoFile.h"
0002 #include "DataFormats/Provenance/interface/ProcessHistoryRegistry.h"
0003 #include "FWCore/Utilities/interface/Algorithms.h"
0004 #include "FWCore/Utilities/interface/EDMException.h"
0005 
0006 #include <algorithm>
0007 #include <iomanip>
0008 #include <ostream>
0009 
0010 namespace edm {
0011 
0012   int const IndexIntoFile::invalidIndex;
0013   RunNumber_t const IndexIntoFile::invalidRun;
0014   LuminosityBlockNumber_t const IndexIntoFile::invalidLumi;
0015   EventNumber_t const IndexIntoFile::invalidEvent;
0016   IndexIntoFile::EntryNumber_t const IndexIntoFile::invalidEntry;
0017 
0018   IndexIntoFile::Transients::Transients()
0019       : previousAddedIndex_(invalidIndex),
0020         runToOrder_(),
0021         lumiToOrder_(),
0022         beginEvents_(invalidEntry),
0023         endEvents_(invalidEntry),
0024         currentIndex_(invalidIndex),
0025         currentRun_(invalidRun),
0026         currentLumi_(invalidLumi),
0027         numberOfEvents_(0),
0028         eventFinder_(),
0029         runOrLumiIndexes_(),
0030         eventNumbers_(),
0031         eventEntries_(),
0032         unsortedEventNumbers_() {}
0033 
0034   void IndexIntoFile::Transients::reset() {
0035     previousAddedIndex_ = invalidIndex;
0036     runToOrder_.clear();
0037     lumiToOrder_.clear();
0038     beginEvents_ = invalidEntry;
0039     endEvents_ = invalidEntry;
0040     currentIndex_ = invalidIndex;
0041     currentRun_ = invalidRun;
0042     currentLumi_ = invalidLumi;
0043     numberOfEvents_ = 0;
0044     eventFinder_ = nullptr;  // propagate_const<T> has no reset() function
0045     runOrLumiIndexes_.clear();
0046     eventNumbers_.clear();
0047     eventEntries_.clear();
0048     unsortedEventNumbers_.clear();
0049   }
0050 
0051   IndexIntoFile::IndexIntoFile() : transient_(), processHistoryIDs_(), runOrLumiEntries_() {}
0052 
0053   IndexIntoFile::~IndexIntoFile() {}
0054 
0055   ProcessHistoryID const& IndexIntoFile::processHistoryID(int i) const { return processHistoryIDs_.at(i); }
0056 
0057   std::vector<ProcessHistoryID> const& IndexIntoFile::processHistoryIDs() const { return processHistoryIDs_; }
0058 
0059   void IndexIntoFile::addLumi(int index, RunNumber_t run, LuminosityBlockNumber_t lumi, EntryNumber_t entry) {
0060     // assign each lumi an order value sequentially when first seen
0061     std::pair<IndexRunLumiKey, EntryNumber_t> keyAndOrder{IndexRunLumiKey{index, run, lumi}, lumiToOrder().size()};
0062     lumiToOrder().insert(keyAndOrder);  // does nothing if this key already was inserted
0063     runOrLumiEntries_.emplace_back(invalidEntry,
0064                                    lumiToOrder()[IndexRunLumiKey{index, run, lumi}],
0065                                    entry,
0066                                    index,
0067                                    run,
0068                                    lumi,
0069                                    beginEvents(),
0070                                    endEvents());
0071     beginEvents() = invalidEntry;
0072     endEvents() = invalidEntry;
0073   }
0074 
0075   void IndexIntoFile::addEntry(ProcessHistoryID const& processHistoryID,
0076                                RunNumber_t run,
0077                                LuminosityBlockNumber_t lumi,
0078                                EventNumber_t event,
0079                                EntryNumber_t entry) {
0080     int index = 0;
0081     // First see if the ProcessHistoryID is the same as the previous one.
0082     // This is just a performance optimization.  We expect to usually get
0083     // many in a row that are the same.
0084     if (previousAddedIndex() != invalidIndex && processHistoryID == processHistoryIDs_[previousAddedIndex()]) {
0085       index = previousAddedIndex();
0086     } else {
0087       // If it was not the same as the previous one then search through the
0088       // entire vector.  If it is not there, it needs to be added at the
0089       // end.
0090       index = 0;
0091       while (index < static_cast<int>(processHistoryIDs_.size()) && processHistoryIDs_[index] != processHistoryID) {
0092         ++index;
0093       }
0094       if (index == static_cast<int>(processHistoryIDs_.size())) {
0095         processHistoryIDs_.push_back(processHistoryID);
0096       }
0097     }
0098     previousAddedIndex() = index;
0099 
0100     if (lumi == invalidLumi) {  // adding a run entry
0101       std::pair<IndexRunKey, EntryNumber_t> keyAndOrder{IndexRunKey{index, run}, runToOrder().size()};
0102       runToOrder().insert(keyAndOrder);  // does nothing if this key already was inserted
0103       runOrLumiEntries_.emplace_back(
0104           runToOrder()[IndexRunKey{index, run}], invalidEntry, entry, index, run, lumi, invalidEntry, invalidEntry);
0105     } else {
0106       if (event == invalidEvent) {  // adding a lumi entry
0107         if ((currentIndex() != index or currentRun() != run or currentLumi() != lumi) and
0108             currentLumi() != invalidLumi) {
0109           //we have overlapping lumis so must inject a placeholder
0110           addLumi(currentIndex(), currentRun(), currentLumi(), invalidEntry);
0111         }
0112         addLumi(index, run, lumi, entry);
0113         currentIndex() = invalidIndex;
0114         currentRun() = invalidRun;
0115         currentLumi() = invalidLumi;
0116         std::pair<IndexRunKey, EntryNumber_t> keyAndOrder{IndexRunKey{index, run}, runToOrder().size()};
0117         runToOrder().insert(keyAndOrder);  // does nothing if this key already was inserted
0118       } else {                             // adding an event entry
0119         if ((currentIndex() != index or currentRun() != run or currentLumi() != lumi) and
0120             currentLumi() != invalidLumi) {
0121           //We have overlapping lumis so need to inject a placeholder
0122           addLumi(currentIndex(), currentRun(), currentLumi(), invalidEntry);
0123         }
0124         setNumberOfEvents(numberOfEvents() + 1);
0125         if (beginEvents() == invalidEntry) {
0126           currentRun() = run;
0127           currentIndex() = index;
0128           currentLumi() = lumi;
0129           beginEvents() = entry;
0130           endEvents() = beginEvents() + 1;
0131           std::pair<IndexRunKey, EntryNumber_t> keyAndOrder{IndexRunKey{index, run}, runToOrder().size()};
0132           runToOrder().insert(keyAndOrder);  // does nothing if this key already was inserted
0133         } else {
0134           assert(currentIndex() == index);
0135           assert(currentRun() == run);
0136           assert(currentLumi() == lumi);
0137           assert(entry == endEvents());
0138           ++endEvents();
0139         }
0140       }
0141     }
0142   }
0143 
0144   void IndexIntoFile::fillRunOrLumiIndexes() const {
0145     if (runOrLumiEntries_.empty() || !runOrLumiIndexes().empty()) {
0146       return;
0147     }
0148     runOrLumiIndexes().reserve(runOrLumiEntries_.size());
0149 
0150     int index = 0;
0151     for (RunOrLumiEntry const& item : runOrLumiEntries_) {
0152       runOrLumiIndexes().emplace_back(item.processHistoryIDIndex(), item.run(), item.lumi(), index);
0153       ++index;
0154     }
0155     stable_sort_all(runOrLumiIndexes());
0156 
0157     long long beginEventNumbers = 0;
0158 
0159     std::vector<RunOrLumiIndexes>::iterator beginOfLumi = runOrLumiIndexes().begin();
0160     std::vector<RunOrLumiIndexes>::iterator endOfLumi = beginOfLumi;
0161     std::vector<RunOrLumiIndexes>::iterator iEnd = runOrLumiIndexes().end();
0162     while (true) {
0163       while (beginOfLumi != iEnd && beginOfLumi->isRun()) {
0164         ++beginOfLumi;
0165       }
0166       if (beginOfLumi == iEnd)
0167         break;
0168 
0169       endOfLumi = beginOfLumi + 1;
0170       while (endOfLumi != iEnd && beginOfLumi->processHistoryIDIndex() == endOfLumi->processHistoryIDIndex() &&
0171              beginOfLumi->run() == endOfLumi->run() && beginOfLumi->lumi() == endOfLumi->lumi()) {
0172         ++endOfLumi;
0173       }
0174       int nEvents = 0;
0175       for (std::vector<RunOrLumiIndexes>::iterator iter = beginOfLumi; iter != endOfLumi; ++iter) {
0176         if (runOrLumiEntries_[iter->indexToGetEntry()].beginEvents() != invalidEntry) {
0177           nEvents += runOrLumiEntries_[iter->indexToGetEntry()].endEvents() -
0178                      runOrLumiEntries_[iter->indexToGetEntry()].beginEvents();
0179         }
0180       }
0181       for (std::vector<RunOrLumiIndexes>::iterator iter = beginOfLumi; iter != endOfLumi; ++iter) {
0182         iter->setBeginEventNumbers(beginEventNumbers);
0183         iter->setEndEventNumbers(beginEventNumbers + nEvents);
0184       }
0185       beginEventNumbers += nEvents;
0186       beginOfLumi = endOfLumi;
0187     }
0188     assert(runOrLumiIndexes().size() == runOrLumiEntries_.size());
0189   }
0190 
0191   void IndexIntoFile::fillEventNumbers() const { fillEventNumbersOrEntries(true, false); }
0192 
0193   void IndexIntoFile::fillEventEntries() const { fillEventNumbersOrEntries(false, true); }
0194 
0195   void IndexIntoFile::fillEventNumbersOrEntries(bool needEventNumbers, bool needEventEntries) const {
0196     if (numberOfEvents() == 0) {
0197       return;
0198     }
0199 
0200     if (needEventNumbers && !eventNumbers().empty()) {
0201       needEventNumbers = false;
0202     }
0203 
0204     if (needEventEntries && !eventEntries().empty()) {
0205       needEventEntries = false;
0206     }
0207 
0208     if (needEventNumbers && !eventEntries().empty()) {
0209       assert(numberOfEvents() == eventEntries().size());
0210       eventNumbers().reserve(eventEntries().size());
0211       for (std::vector<EventNumber_t>::size_type entry = 0U; entry < numberOfEvents(); ++entry) {
0212         eventNumbers().push_back(eventEntries()[entry].event());
0213       }
0214       return;
0215     }
0216 
0217     if (!needEventNumbers && !needEventEntries) {
0218       return;
0219     }
0220 
0221     fillUnsortedEventNumbers();
0222 
0223     if (needEventNumbers) {
0224       eventNumbers().resize(numberOfEvents(), IndexIntoFile::invalidEvent);
0225     }
0226     if (needEventEntries) {
0227       eventEntries().resize(numberOfEvents());
0228     }
0229 
0230     long long offset = 0;
0231     long long previousBeginEventNumbers = -1LL;
0232 
0233     for (SortedRunOrLumiItr runOrLumi = beginRunOrLumi(), runOrLumiEnd = endRunOrLumi(); runOrLumi != runOrLumiEnd;
0234          ++runOrLumi) {
0235       if (runOrLumi.isRun())
0236         continue;
0237 
0238       long long beginEventNumbers = 0;
0239       long long endEventNumbers = 0;
0240       EntryNumber_t beginEventEntry = invalidEntry;
0241       EntryNumber_t endEventEntry = invalidEntry;
0242       runOrLumi.getRange(beginEventNumbers, endEventNumbers, beginEventEntry, endEventEntry);
0243 
0244       // This is true each time one hits a new lumi section (except if the previous lumi had
0245       // no events, in which case the offset is still 0 anyway)
0246       if (beginEventNumbers != previousBeginEventNumbers)
0247         offset = 0;
0248 
0249       for (EntryNumber_t entry = beginEventEntry; entry != endEventEntry; ++entry) {
0250         if (needEventNumbers) {
0251           eventNumbers().at((entry - beginEventEntry) + offset + beginEventNumbers) = unsortedEventNumbers().at(entry);
0252         }
0253         if (needEventEntries) {
0254           eventEntries().at((entry - beginEventEntry) + offset + beginEventNumbers) =
0255               EventEntry(unsortedEventNumbers().at(entry), entry);
0256         }
0257       }
0258 
0259       previousBeginEventNumbers = beginEventNumbers;
0260       offset += endEventEntry - beginEventEntry;
0261     }
0262     if (needEventNumbers) {
0263       sortEvents();
0264       assert(numberOfEvents() == eventNumbers().size());
0265     }
0266     if (needEventEntries) {
0267       sortEventEntries();
0268       assert(numberOfEvents() == eventEntries().size());
0269     }
0270   }
0271 
0272   void IndexIntoFile::fillUnsortedEventNumbers() const {
0273     if (numberOfEvents() == 0 || !unsortedEventNumbers().empty()) {
0274       return;
0275     }
0276     unsortedEventNumbersMutable().reserve(numberOfEvents());
0277 
0278     // The main purpose for the existence of the unsortedEventNumbers
0279     // vector is that it can easily be filled by reading through
0280     // the EventAuxiliary branch in the same order as the TTree
0281     // entries. fillEventNumbersOrEntries can then use this information
0282     // instead of using getEventNumberOfEntry directly and reading
0283     // the branch in a different order.
0284     for (std::vector<EventNumber_t>::size_type entry = 0U; entry < numberOfEvents(); ++entry) {
0285       unsortedEventNumbersMutable().push_back(getEventNumberOfEntry(entry));
0286     }
0287   }
0288 
0289   // We are closing the input file, but we need to keep event numbers.
0290   // We can delete the other transient collections by using the swap trick.
0291 
0292   void IndexIntoFile::inputFileClosed() {
0293     std::vector<EventEntry>().swap(eventEntries());
0294     std::vector<RunOrLumiIndexes>().swap(runOrLumiIndexes());
0295     std::vector<EventNumber_t>().swap(unsortedEventNumbers());
0296     resetEventFinder();
0297   }
0298 
0299   void IndexIntoFile::doneFileInitialization() { std::vector<EventNumber_t>().swap(unsortedEventNumbers()); }
0300 
0301   void IndexIntoFile::reduceProcessHistoryIDs(ProcessHistoryRegistry const& processHistoryRegistry) {
0302     std::vector<ProcessHistoryID> reducedPHIDs;
0303 
0304     std::map<ProcessHistoryID, int> reducedPHIDToIndex;
0305     std::pair<ProcessHistoryID, int> mapEntry(ProcessHistoryID(), 0);
0306     std::pair<std::map<ProcessHistoryID, int>::iterator, bool> insertResult;
0307 
0308     std::vector<int> phidIndexConverter;
0309     for (auto const& phid : processHistoryIDs_) {
0310       ProcessHistoryID const& reducedPHID = processHistoryRegistry.reducedProcessHistoryID(phid);
0311       mapEntry.first = reducedPHID;
0312       insertResult = reducedPHIDToIndex.insert(mapEntry);
0313 
0314       if (insertResult.second) {
0315         insertResult.first->second = reducedPHIDs.size();
0316         reducedPHIDs.push_back(reducedPHID);
0317       }
0318       phidIndexConverter.push_back(insertResult.first->second);
0319     }
0320     processHistoryIDs_.swap(reducedPHIDs);
0321 
0322     // If the size of the vector of IDs does not change
0323     // then their indexes and the ordering of the Runs and
0324     // and Lumis does not change, so we are done.
0325     if (processHistoryIDs_.size() == reducedPHIDs.size()) {
0326       return;
0327     }
0328 
0329     std::map<IndexIntoFile::IndexRunKey, int> runOrderMap;
0330     std::pair<std::map<IndexIntoFile::IndexRunKey, int>::iterator, bool> runInsertResult;
0331 
0332     std::map<IndexIntoFile::IndexRunLumiKey, int> lumiOrderMap;
0333     std::pair<std::map<IndexIntoFile::IndexRunLumiKey, int>::iterator, bool> lumiInsertResult;
0334 
0335     // loop over all the RunOrLumiEntry's
0336     for (auto& item : runOrLumiEntries_) {
0337       // Convert the process history index so it points into the new vector of reduced IDs
0338       item.setProcessHistoryIDIndex(phidIndexConverter.at(item.processHistoryIDIndex()));
0339 
0340       // Convert the phid-run order
0341       IndexIntoFile::IndexRunKey runKey(item.processHistoryIDIndex(), item.run());
0342       runInsertResult = runOrderMap.insert(std::pair<IndexIntoFile::IndexRunKey, int>(runKey, 0));
0343       if (runInsertResult.second) {
0344         runInsertResult.first->second = item.orderPHIDRun();
0345       } else {
0346         item.setOrderPHIDRun(runInsertResult.first->second);
0347       }
0348 
0349       // Convert the phid-run-lumi order for the lumi entries
0350       if (item.lumi() != 0) {
0351         IndexIntoFile::IndexRunLumiKey lumiKey(item.processHistoryIDIndex(), item.run(), item.lumi());
0352         lumiInsertResult = lumiOrderMap.insert(std::pair<IndexIntoFile::IndexRunLumiKey, int>(lumiKey, 0));
0353         if (lumiInsertResult.second) {
0354           lumiInsertResult.first->second = item.orderPHIDRunLumi();
0355         } else {
0356           item.setOrderPHIDRunLumi(lumiInsertResult.first->second);
0357         }
0358       }
0359     }
0360     std::stable_sort(runOrLumiEntries_.begin(), runOrLumiEntries_.end());
0361   }
0362 
0363   void IndexIntoFile::fixIndexes(std::vector<ProcessHistoryID>& processHistoryIDs) {
0364     std::map<int, int> oldToNewIndex;
0365     for (std::vector<ProcessHistoryID>::const_iterator iter = processHistoryIDs_.begin(),
0366                                                        iEnd = processHistoryIDs_.end();
0367          iter != iEnd;
0368          ++iter) {
0369       std::vector<ProcessHistoryID>::const_iterator iterExisting =
0370           std::find(processHistoryIDs.begin(), processHistoryIDs.end(), *iter);
0371       if (iterExisting == processHistoryIDs.end()) {
0372         oldToNewIndex[iter - processHistoryIDs_.begin()] = processHistoryIDs.size();
0373         processHistoryIDs.push_back(*iter);
0374       } else {
0375         oldToNewIndex[iter - processHistoryIDs_.begin()] = iterExisting - processHistoryIDs.begin();
0376       }
0377     }
0378     processHistoryIDs_ = processHistoryIDs;
0379 
0380     for (RunOrLumiEntry& item : runOrLumiEntries_) {
0381       item.setProcessHistoryIDIndex(oldToNewIndex[item.processHistoryIDIndex()]);
0382     }
0383   }
0384 
0385   void IndexIntoFile::sortVector_Run_Or_Lumi_Entries() {
0386     for (RunOrLumiEntry& item : runOrLumiEntries_) {
0387       std::map<IndexRunKey, EntryNumber_t>::const_iterator keyAndOrder =
0388           runToOrder().find(IndexRunKey(item.processHistoryIDIndex(), item.run()));
0389       if (keyAndOrder == runToOrder().end()) {
0390         throw Exception(errors::LogicError)
0391             << "In IndexIntoFile::sortVector_Run_Or_Lumi_Entries. A run entry is missing.\n"
0392             << "This means the IndexIntoFile product in the output file will be corrupted.\n"
0393             << "The output file will be unusable for most purposes.\n"
0394             << "If this occurs after an unrelated exception was thrown in\n"
0395             << "endLuminosityBlock or endRun then ignore this exception and fix\n"
0396             << "the primary exception. This is an expected side effect.\n"
0397             << "Otherwise please report this to the core framework developers\n";
0398       }
0399       item.setOrderPHIDRun(keyAndOrder->second);
0400     }
0401     stable_sort_all(runOrLumiEntries_);
0402     checkForMissingRunOrLumiEntry();
0403   }
0404 
0405   void IndexIntoFile::checkForMissingRunOrLumiEntry() const {
0406     bool shouldThrow = false;
0407     bool foundValidLumiEntry = true;
0408     EntryNumber_t currentRun = invalidEntry;
0409     EntryNumber_t currentLumi = invalidEntry;
0410     EntryNumber_t previousLumi = invalidEntry;
0411 
0412     RunOrLumiEntry const* lastEntry = nullptr;
0413     for (RunOrLumiEntry const& item : runOrLumiEntries_) {
0414       if (item.isRun()) {
0415         currentRun = item.orderPHIDRun();
0416       } else {  // Lumi
0417         if (item.orderPHIDRun() != currentRun) {
0418           throw Exception(errors::LogicError)
0419               << "In IndexIntoFile::sortVector_Run_Or_Lumi_Entries. Missing Run entry.\n"
0420               << "If this occurs after an unrelated exception occurs, please ignore this\n"
0421               << "exception and fix the primary exception. This is a possible and expected\n"
0422               << "side effect. Otherwise, please report to Framework developers.\n"
0423               << "This could indicate a bug in the source or Framework\n"
0424               << "Run: " << item.run() << " Lumi: " << item.lumi() << " Entry: " << item.entry() << "\n";
0425         }
0426         currentLumi = item.orderPHIDRunLumi();
0427         if (currentLumi != previousLumi) {
0428           if (!foundValidLumiEntry) {
0429             shouldThrow = true;
0430             break;
0431           }
0432           foundValidLumiEntry = false;
0433           previousLumi = currentLumi;
0434         }
0435         if (item.entry() != invalidEntry) {
0436           foundValidLumiEntry = true;
0437         }
0438       }
0439       lastEntry = &item;
0440     }
0441     if (!foundValidLumiEntry) {
0442       shouldThrow = true;
0443     }
0444 
0445     if (shouldThrow) {
0446       throw Exception(errors::LogicError)
0447           << "In IndexIntoFile::sortVector_Run_Or_Lumi_Entries. Missing valid Lumi entry.\n"
0448           << "If this occurs after an unrelated exception occurs, please ignore this\n"
0449           << "exception and fix the primary exception. This is a possible and expected\n"
0450           << "side effect. Otherwise, please report to Framework developers.\n"
0451           << "This could indicate a bug in the source or Framework\n"
0452           << "Run: " << lastEntry->run() << " Lumi: " << lastEntry->lumi() << " Entry: " << lastEntry->entry() << "\n";
0453     }
0454   }
0455 
0456   void IndexIntoFile::sortEvents() const {
0457     fillRunOrLumiIndexes();
0458     std::vector<RunOrLumiIndexes>::iterator beginOfLumi = runOrLumiIndexes().begin();
0459     std::vector<RunOrLumiIndexes>::iterator endOfLumi = beginOfLumi;
0460     std::vector<RunOrLumiIndexes>::iterator iEnd = runOrLumiIndexes().end();
0461     while (true) {
0462       while (beginOfLumi != iEnd && beginOfLumi->isRun()) {
0463         ++beginOfLumi;
0464       }
0465       if (beginOfLumi == iEnd)
0466         break;
0467 
0468       endOfLumi = beginOfLumi + 1;
0469       while (endOfLumi != iEnd && beginOfLumi->processHistoryIDIndex() == endOfLumi->processHistoryIDIndex() &&
0470              beginOfLumi->run() == endOfLumi->run() && beginOfLumi->lumi() == endOfLumi->lumi()) {
0471         ++endOfLumi;
0472       }
0473       assert(beginOfLumi->endEventNumbers() >= 0);
0474       assert(beginOfLumi->endEventNumbers() <= static_cast<long long>(eventNumbers().size()));
0475       std::sort(eventNumbers().begin() + beginOfLumi->beginEventNumbers(),
0476                 eventNumbers().begin() + beginOfLumi->endEventNumbers());
0477       beginOfLumi = endOfLumi;
0478     }
0479   }
0480 
0481   void IndexIntoFile::sortEventEntries() const {
0482     fillRunOrLumiIndexes();
0483     std::vector<RunOrLumiIndexes>::iterator beginOfLumi = runOrLumiIndexes().begin();
0484     std::vector<RunOrLumiIndexes>::iterator endOfLumi = beginOfLumi;
0485     std::vector<RunOrLumiIndexes>::iterator iEnd = runOrLumiIndexes().end();
0486     while (true) {
0487       while (beginOfLumi != iEnd && beginOfLumi->isRun()) {
0488         ++beginOfLumi;
0489       }
0490       if (beginOfLumi == iEnd)
0491         break;
0492 
0493       endOfLumi = beginOfLumi + 1;
0494       while (endOfLumi != iEnd && beginOfLumi->processHistoryIDIndex() == endOfLumi->processHistoryIDIndex() &&
0495              beginOfLumi->run() == endOfLumi->run() && beginOfLumi->lumi() == endOfLumi->lumi()) {
0496         ++endOfLumi;
0497       }
0498       assert(beginOfLumi->endEventNumbers() >= 0);
0499       assert(beginOfLumi->endEventNumbers() <= static_cast<long long>(eventEntries().size()));
0500       std::sort(eventEntries().begin() + beginOfLumi->beginEventNumbers(),
0501                 eventEntries().begin() + beginOfLumi->endEventNumbers());
0502       beginOfLumi = endOfLumi;
0503     }
0504   }
0505 
0506   IndexIntoFile::IndexIntoFileItr IndexIntoFile::begin(SortOrder sortOrder) const {
0507     if (empty()) {
0508       return end(sortOrder);
0509     }
0510     IndexIntoFileItr iter(this, sortOrder, kRun, 0, invalidIndex, invalidIndex, 0, 0);
0511     iter.initializeRun();
0512     return iter;
0513   }
0514 
0515   IndexIntoFile::IndexIntoFileItr IndexIntoFile::end(SortOrder sortOrder) const {
0516     return IndexIntoFileItr(this, sortOrder, kEnd, invalidIndex, invalidIndex, invalidIndex, 0, 0);
0517   }
0518 
0519   bool IndexIntoFile::iterationWillBeInEntryOrder(SortOrder sortOrder) const {
0520     EntryNumber_t maxEntry = invalidEntry;
0521     for (IndexIntoFileItr it = begin(sortOrder), itEnd = end(sortOrder); it != itEnd; ++it) {
0522       if (it.getEntryType() == kEvent) {
0523         if (it.entry() < maxEntry) {
0524           return false;
0525         }
0526         maxEntry = it.entry();
0527       }
0528     }
0529     return true;
0530   }
0531 
0532   bool IndexIntoFile::empty() const { return runOrLumiEntries().empty(); }
0533 
0534   IndexIntoFile::IndexIntoFileItr IndexIntoFile::findPosition(RunNumber_t run,
0535                                                               LuminosityBlockNumber_t lumi,
0536                                                               EventNumber_t event) const {
0537     fillRunOrLumiIndexes();
0538 
0539     bool lumiMissing = (lumi == 0 && event != 0);
0540 
0541     std::vector<RunOrLumiIndexes>::const_iterator iEnd = runOrLumiIndexes().end();
0542     std::vector<RunOrLumiIndexes>::const_iterator phEnd;
0543 
0544     // Loop over ranges of entries with the same ProcessHistoryID
0545     for (std::vector<RunOrLumiIndexes>::const_iterator phBegin = runOrLumiIndexes().begin(); phBegin != iEnd;
0546          phBegin = phEnd) {
0547       RunOrLumiIndexes el(phBegin->processHistoryIDIndex(), run, lumi, 0);
0548       phEnd = std::upper_bound(phBegin, iEnd, el, Compare_Index());
0549 
0550       std::vector<RunOrLumiIndexes>::const_iterator iRun = std::lower_bound(phBegin, phEnd, el, Compare_Index_Run());
0551 
0552       if (iRun == phEnd || iRun->run() != run)
0553         continue;
0554 
0555       if (lumi == invalidLumi && event == invalidEvent) {
0556         IndexIntoFileItr indexItr(
0557             this, numericalOrder, kRun, iRun - runOrLumiIndexes().begin(), invalidIndex, invalidIndex, 0, 0);
0558         indexItr.initializeRun();
0559         return indexItr;
0560       }
0561 
0562       std::vector<RunOrLumiIndexes>::const_iterator iRunEnd = std::upper_bound(iRun, phEnd, el, Compare_Index_Run());
0563       if (!lumiMissing) {
0564         std::vector<RunOrLumiIndexes>::const_iterator iLumi = std::lower_bound(iRun, iRunEnd, el);
0565         if (iLumi == iRunEnd || iLumi->lumi() != lumi)
0566           continue;
0567 
0568         if (event == invalidEvent) {
0569           IndexIntoFileItr indexItr(this,
0570                                     numericalOrder,
0571                                     kRun,
0572                                     iRun - runOrLumiIndexes().begin(),
0573                                     iLumi - runOrLumiIndexes().begin(),
0574                                     invalidIndex,
0575                                     0,
0576                                     0);
0577           indexItr.initializeLumi();
0578           return indexItr;
0579         }
0580 
0581         long long beginEventNumbers = iLumi->beginEventNumbers();
0582         long long endEventNumbers = iLumi->endEventNumbers();
0583         if (beginEventNumbers >= endEventNumbers)
0584           continue;
0585 
0586         long long indexToEvent = 0;
0587         if (!eventEntries().empty()) {
0588           std::vector<EventEntry>::const_iterator eventIter =
0589               std::lower_bound(eventEntries().begin() + beginEventNumbers,
0590                                eventEntries().begin() + endEventNumbers,
0591                                EventEntry(event, invalidEntry));
0592           if (eventIter == (eventEntries().begin() + endEventNumbers) || eventIter->event() != event)
0593             continue;
0594 
0595           indexToEvent = eventIter - eventEntries().begin() - beginEventNumbers;
0596         } else {
0597           fillEventNumbers();
0598           std::vector<EventNumber_t>::const_iterator eventIter = std::lower_bound(
0599               eventNumbers().begin() + beginEventNumbers, eventNumbers().begin() + endEventNumbers, event);
0600           if (eventIter == (eventNumbers().begin() + endEventNumbers) || *eventIter != event)
0601             continue;
0602 
0603           indexToEvent = eventIter - eventNumbers().begin() - beginEventNumbers;
0604         }
0605 
0606         int newIndexToLumi = iLumi - runOrLumiIndexes().begin();
0607         while (runOrLumiEntries_[runOrLumiIndexes()[newIndexToLumi].indexToGetEntry()].entry() == invalidEntry) {
0608           ++newIndexToLumi;
0609           assert(static_cast<unsigned>(newIndexToLumi) < runOrLumiEntries_.size());
0610           assert(runOrLumiIndexes()[newIndexToLumi].lumi() == lumi);
0611         }
0612 
0613         return IndexIntoFileItr(this,
0614                                 numericalOrder,
0615                                 kRun,
0616                                 iRun - runOrLumiIndexes().begin(),
0617                                 newIndexToLumi,
0618                                 iLumi - runOrLumiIndexes().begin(),
0619                                 indexToEvent,
0620                                 endEventNumbers - beginEventNumbers);
0621       }
0622       if (lumiMissing) {
0623         std::vector<RunOrLumiIndexes>::const_iterator iLumi = iRun;
0624         while (iLumi != iRunEnd && iLumi->lumi() == invalidLumi) {
0625           ++iLumi;
0626         }
0627         if (iLumi == iRunEnd)
0628           continue;
0629 
0630         std::vector<RunOrLumiIndexes>::const_iterator lumiEnd;
0631         for (; iLumi != iRunEnd; iLumi = lumiEnd) {
0632           RunOrLumiIndexes elWithLumi(phBegin->processHistoryIDIndex(), run, iLumi->lumi(), 0);
0633           lumiEnd = std::upper_bound(iLumi, iRunEnd, elWithLumi);
0634 
0635           long long beginEventNumbers = iLumi->beginEventNumbers();
0636           long long endEventNumbers = iLumi->endEventNumbers();
0637           if (beginEventNumbers >= endEventNumbers)
0638             continue;
0639 
0640           long long indexToEvent = 0;
0641           if (!eventEntries().empty()) {
0642             std::vector<EventEntry>::const_iterator eventIter =
0643                 std::lower_bound(eventEntries().begin() + beginEventNumbers,
0644                                  eventEntries().begin() + endEventNumbers,
0645                                  EventEntry(event, invalidEntry));
0646             if (eventIter == (eventEntries().begin() + endEventNumbers) || eventIter->event() != event)
0647               continue;
0648             indexToEvent = eventIter - eventEntries().begin() - beginEventNumbers;
0649           } else {
0650             fillEventNumbers();
0651             std::vector<EventNumber_t>::const_iterator eventIter = std::lower_bound(
0652                 eventNumbers().begin() + beginEventNumbers, eventNumbers().begin() + endEventNumbers, event);
0653             if (eventIter == (eventNumbers().begin() + endEventNumbers) || *eventIter != event)
0654               continue;
0655             indexToEvent = eventIter - eventNumbers().begin() - beginEventNumbers;
0656           }
0657 
0658           int newIndexToLumi = iLumi - runOrLumiIndexes().begin();
0659           while (runOrLumiEntries_[runOrLumiIndexes()[newIndexToLumi].indexToGetEntry()].entry() == invalidEntry) {
0660             ++newIndexToLumi;
0661             assert(static_cast<unsigned>(newIndexToLumi) < runOrLumiEntries_.size());
0662             assert(runOrLumiIndexes()[newIndexToLumi].lumi() == iLumi->lumi());
0663           }
0664 
0665           return IndexIntoFileItr(this,
0666                                   numericalOrder,
0667                                   kRun,
0668                                   iRun - runOrLumiIndexes().begin(),
0669                                   newIndexToLumi,
0670                                   iLumi - runOrLumiIndexes().begin(),
0671                                   indexToEvent,
0672                                   endEventNumbers - beginEventNumbers);
0673         }
0674       }
0675     }  // Loop over ProcessHistoryIDs
0676 
0677     return IndexIntoFileItr(this, numericalOrder, kEnd, invalidIndex, invalidIndex, invalidIndex, 0, 0);
0678   }
0679 
0680   IndexIntoFile::IndexIntoFileItr IndexIntoFile::findPosition(SortOrder sortOrder,
0681                                                               RunNumber_t run,
0682                                                               LuminosityBlockNumber_t lumi,
0683                                                               EventNumber_t event) const {
0684     if (sortOrder == IndexIntoFile::numericalOrder) {
0685       return findPosition(run, lumi, event);  // a faster algorithm
0686     }
0687     IndexIntoFileItr itr = begin(sortOrder);
0688     IndexIntoFileItr itrEnd = end(sortOrder);
0689 
0690     while (itr != itrEnd) {
0691       if (itr.run() != run) {
0692         itr.advanceToNextRun();
0693       } else {
0694         if (lumi == invalidLumi && event == invalidEvent) {
0695           return itr;
0696         } else if (lumi != invalidLumi && itr.peekAheadAtLumi() != lumi) {
0697           if (!itr.skipLumiInRun()) {
0698             itr.advanceToNextRun();
0699           }
0700         } else {
0701           if (event == invalidEvent) {
0702             return itr;
0703           } else {
0704             EventNumber_t eventNumber = getEventNumberOfEntry(itr.peekAheadAtEventEntry());
0705             if (eventNumber == event) {
0706               return itr;
0707             } else {
0708               if (!itr.skipToNextEventInLumi()) {
0709                 if (!itr.skipLumiInRun()) {
0710                   itr.advanceToNextRun();
0711                 }
0712               }
0713             }
0714           }
0715         }
0716       }
0717     }
0718     return itrEnd;
0719   }
0720 
0721   IndexIntoFile::IndexIntoFileItr IndexIntoFile::findEventPosition(RunNumber_t run,
0722                                                                    LuminosityBlockNumber_t lumi,
0723                                                                    EventNumber_t event) const {
0724     assert(event != invalidEvent);
0725     IndexIntoFileItr iter = findPosition(run, lumi, event);
0726     iter.advanceToEvent();
0727     return iter;
0728   }
0729 
0730   IndexIntoFile::IndexIntoFileItr IndexIntoFile::findLumiPosition(RunNumber_t run, LuminosityBlockNumber_t lumi) const {
0731     assert(lumi != invalidLumi);
0732     IndexIntoFileItr iter = findPosition(run, lumi, 0U);
0733     iter.advanceToLumi();
0734     return iter;
0735   }
0736 
0737   IndexIntoFile::IndexIntoFileItr IndexIntoFile::findRunPosition(RunNumber_t run) const {
0738     return findPosition(run, 0U, 0U);
0739   }
0740 
0741   bool IndexIntoFile::containsItem(RunNumber_t run, LuminosityBlockNumber_t lumi, EventNumber_t event) const {
0742     return (event != 0) ? containsEvent(run, lumi, event) : (lumi ? containsLumi(run, lumi) : containsRun(run));
0743   }
0744 
0745   bool IndexIntoFile::containsEvent(RunNumber_t run, LuminosityBlockNumber_t lumi, EventNumber_t event) const {
0746     return findEventPosition(run, lumi, event).getEntryType() != kEnd;
0747   }
0748 
0749   bool IndexIntoFile::containsLumi(RunNumber_t run, LuminosityBlockNumber_t lumi) const {
0750     return findLumiPosition(run, lumi).getEntryType() != kEnd;
0751   }
0752 
0753   bool IndexIntoFile::containsRun(RunNumber_t run) const { return findRunPosition(run).getEntryType() != kEnd; }
0754 
0755   IndexIntoFile::SortedRunOrLumiItr IndexIntoFile::beginRunOrLumi() const { return SortedRunOrLumiItr(this, 0); }
0756 
0757   IndexIntoFile::SortedRunOrLumiItr IndexIntoFile::endRunOrLumi() const {
0758     return SortedRunOrLumiItr(this, runOrLumiEntries().size());
0759   }
0760 
0761   void IndexIntoFile::set_intersection(IndexIntoFile const& indexIntoFile,
0762                                        std::set<IndexRunLumiEventKey>& intersection) const {
0763     if (empty() || indexIntoFile.empty())
0764       return;
0765     fillRunOrLumiIndexes();
0766     indexIntoFile.fillRunOrLumiIndexes();
0767     RunOrLumiIndexes const& back1 = runOrLumiIndexes().back();
0768     RunOrLumiIndexes const& back2 = indexIntoFile.runOrLumiIndexes().back();
0769 
0770     // Very quick decision if the run ranges in the two files do not overlap
0771     if (back2 < runOrLumiIndexes().front())
0772       return;
0773     if (back1 < indexIntoFile.runOrLumiIndexes().front())
0774       return;
0775 
0776     SortedRunOrLumiItr iter1 = beginRunOrLumi();
0777     SortedRunOrLumiItr iEnd1 = endRunOrLumi();
0778 
0779     SortedRunOrLumiItr iter2 = indexIntoFile.beginRunOrLumi();
0780     SortedRunOrLumiItr iEnd2 = indexIntoFile.endRunOrLumi();
0781 
0782     // Quick decision if the lumi ranges in the two files do not overlap
0783     while (iter1 != iEnd1 && iter1.isRun())
0784       ++iter1;
0785     if (iter1 == iEnd1)
0786       return;
0787     if (back2 < iter1.runOrLumiIndexes())
0788       return;
0789 
0790     while (iter2 != iEnd2 && iter2.isRun())
0791       ++iter2;
0792     if (iter2 == iEnd2)
0793       return;
0794     if (back1 < iter2.runOrLumiIndexes())
0795       return;
0796 
0797     RunOrLumiIndexes const* previousIndexes = nullptr;
0798 
0799     // Loop through the both IndexIntoFile objects and look for matching lumis
0800     while (iter1 != iEnd1 && iter2 != iEnd2) {
0801       RunOrLumiIndexes const& indexes1 = iter1.runOrLumiIndexes();
0802       RunOrLumiIndexes const& indexes2 = iter2.runOrLumiIndexes();
0803       if (indexes1 < indexes2) {
0804         ++iter1;
0805       } else if (indexes2 < indexes1) {
0806         ++iter2;
0807       } else {  // they are equal
0808 
0809         // Skip them if it is a run or the same lumi
0810         if (indexes1.isRun() || (previousIndexes && !(*previousIndexes < indexes1))) {
0811           ++iter1;
0812           ++iter2;
0813         } else {
0814           previousIndexes = &indexes1;
0815 
0816           // Found a matching lumi, now look for matching events
0817 
0818           long long beginEventNumbers1 = indexes1.beginEventNumbers();
0819           long long endEventNumbers1 = indexes1.endEventNumbers();
0820 
0821           long long beginEventNumbers2 = indexes2.beginEventNumbers();
0822           long long endEventNumbers2 = indexes2.endEventNumbers();
0823 
0824           // there must be at least 1 event in each lumi for there to be any matches
0825           if ((beginEventNumbers1 >= endEventNumbers1) || (beginEventNumbers2 >= endEventNumbers2)) {
0826             ++iter1;
0827             ++iter2;
0828             continue;
0829           }
0830 
0831           if (!eventEntries().empty() && !indexIntoFile.eventEntries().empty()) {
0832             std::vector<EventEntry> matchingEvents;
0833             std::insert_iterator<std::vector<EventEntry> > insertIter(matchingEvents, matchingEvents.begin());
0834             std::set_intersection(eventEntries().begin() + beginEventNumbers1,
0835                                   eventEntries().begin() + endEventNumbers1,
0836                                   indexIntoFile.eventEntries().begin() + beginEventNumbers2,
0837                                   indexIntoFile.eventEntries().begin() + endEventNumbers2,
0838                                   insertIter);
0839             for (EventEntry const& entry : matchingEvents) {
0840               intersection.insert(IndexRunLumiEventKey(
0841                   indexes1.processHistoryIDIndex(), indexes1.run(), indexes1.lumi(), entry.event()));
0842             }
0843           } else {
0844             fillEventNumbers();
0845             indexIntoFile.fillEventNumbers();
0846             std::vector<EventNumber_t> matchingEvents;
0847             std::insert_iterator<std::vector<EventNumber_t> > insertIter(matchingEvents, matchingEvents.begin());
0848             std::set_intersection(eventNumbers().begin() + beginEventNumbers1,
0849                                   eventNumbers().begin() + endEventNumbers1,
0850                                   indexIntoFile.eventNumbers().begin() + beginEventNumbers2,
0851                                   indexIntoFile.eventNumbers().begin() + endEventNumbers2,
0852                                   insertIter);
0853             for (EventNumber_t const& eventNumber : matchingEvents) {
0854               intersection.insert(
0855                   IndexRunLumiEventKey(indexes1.processHistoryIDIndex(), indexes1.run(), indexes1.lumi(), eventNumber));
0856             }
0857           }
0858         }
0859       }
0860     }
0861   }
0862 
0863   bool IndexIntoFile::containsDuplicateEvents() const {
0864     RunOrLumiIndexes const* previousIndexes = nullptr;
0865 
0866     for (SortedRunOrLumiItr iter = beginRunOrLumi(), iEnd = endRunOrLumi(); iter != iEnd; ++iter) {
0867       RunOrLumiIndexes const& indexes = iter.runOrLumiIndexes();
0868 
0869       // Skip it if it is a run or the same lumi
0870       if (indexes.isRun() || (previousIndexes && !(*previousIndexes < indexes))) {
0871         continue;
0872       }
0873       previousIndexes = &indexes;
0874 
0875       long long beginEventNumbers = indexes.beginEventNumbers();
0876       long long endEventNumbers = indexes.endEventNumbers();
0877 
0878       // there must be more than 1 event in the lumi for there to be any duplicates
0879       if (beginEventNumbers + 1 >= endEventNumbers)
0880         continue;
0881 
0882       if (!eventEntries().empty()) {
0883         std::vector<EventEntry>::iterator last = eventEntries().begin() + endEventNumbers;
0884         if (std::adjacent_find(eventEntries().begin() + beginEventNumbers, last) != last) {
0885           return true;
0886         }
0887       } else {
0888         fillEventNumbers();
0889         std::vector<EventNumber_t>::iterator last = eventNumbers().begin() + endEventNumbers;
0890         if (std::adjacent_find(eventNumbers().begin() + beginEventNumbers, last) != last) {
0891           return true;
0892         }
0893       }
0894     }
0895     return false;
0896   }
0897 
0898   IndexIntoFile::RunOrLumiEntry::RunOrLumiEntry()
0899       : orderPHIDRun_(invalidEntry),
0900         orderPHIDRunLumi_(invalidEntry),
0901         entry_(invalidEntry),
0902         processHistoryIDIndex_(invalidIndex),
0903         run_(invalidRun),
0904         lumi_(invalidLumi),
0905         beginEvents_(invalidEntry),
0906         endEvents_(invalidEntry) {}
0907 
0908   IndexIntoFile::RunOrLumiEntry::RunOrLumiEntry(EntryNumber_t orderPHIDRun,
0909                                                 EntryNumber_t orderPHIDRunLumi,
0910                                                 EntryNumber_t entry,
0911                                                 int processHistoryIDIndex,
0912                                                 RunNumber_t run,
0913                                                 LuminosityBlockNumber_t lumi,
0914                                                 EntryNumber_t beginEvents,
0915                                                 EntryNumber_t endEvents)
0916       : orderPHIDRun_(orderPHIDRun),
0917         orderPHIDRunLumi_(orderPHIDRunLumi),
0918         entry_(entry),
0919         processHistoryIDIndex_(processHistoryIDIndex),
0920         run_(run),
0921         lumi_(lumi),
0922         beginEvents_(beginEvents),
0923         endEvents_(endEvents) {}
0924 
0925   IndexIntoFile::RunOrLumiIndexes::RunOrLumiIndexes(int processHistoryIDIndex,
0926                                                     RunNumber_t run,
0927                                                     LuminosityBlockNumber_t lumi,
0928                                                     int indexToGetEntry)
0929       : processHistoryIDIndex_(processHistoryIDIndex),
0930         run_(run),
0931         lumi_(lumi),
0932         indexToGetEntry_(indexToGetEntry),
0933         beginEventNumbers_(-1),
0934         endEventNumbers_(-1) {}
0935 
0936   IndexIntoFile::SortedRunOrLumiItr::SortedRunOrLumiItr(IndexIntoFile const* indexIntoFile, unsigned runOrLumi)
0937       : indexIntoFile_(indexIntoFile), runOrLumi_(runOrLumi) {
0938     assert(runOrLumi_ <= indexIntoFile_->runOrLumiEntries().size());
0939     indexIntoFile_->fillRunOrLumiIndexes();
0940   }
0941 
0942   bool IndexIntoFile::SortedRunOrLumiItr::operator==(SortedRunOrLumiItr const& right) const {
0943     return indexIntoFile_ == right.indexIntoFile() && runOrLumi_ == right.runOrLumi();
0944   }
0945 
0946   bool IndexIntoFile::SortedRunOrLumiItr::operator!=(SortedRunOrLumiItr const& right) const {
0947     return indexIntoFile_ != right.indexIntoFile() || runOrLumi_ != right.runOrLumi();
0948   }
0949 
0950   IndexIntoFile::SortedRunOrLumiItr& IndexIntoFile::SortedRunOrLumiItr::operator++() {
0951     if (runOrLumi_ != indexIntoFile_->runOrLumiEntries().size()) {
0952       ++runOrLumi_;
0953     }
0954     return *this;
0955   }
0956 
0957   bool IndexIntoFile::SortedRunOrLumiItr::isRun() {
0958     return indexIntoFile_->runOrLumiIndexes().at(runOrLumi_).lumi() == invalidLumi;
0959   }
0960 
0961   void IndexIntoFile::SortedRunOrLumiItr::getRange(long long& beginEventNumbers,
0962                                                    long long& endEventNumbers,
0963                                                    EntryNumber_t& beginEventEntry,
0964                                                    EntryNumber_t& endEventEntry) {
0965     beginEventNumbers = indexIntoFile_->runOrLumiIndexes().at(runOrLumi_).beginEventNumbers();
0966     endEventNumbers = indexIntoFile_->runOrLumiIndexes().at(runOrLumi_).endEventNumbers();
0967 
0968     int indexToGetEntry = indexIntoFile_->runOrLumiIndexes().at(runOrLumi_).indexToGetEntry();
0969     beginEventEntry = indexIntoFile_->runOrLumiEntries_.at(indexToGetEntry).beginEvents();
0970     endEventEntry = indexIntoFile_->runOrLumiEntries_.at(indexToGetEntry).endEvents();
0971   }
0972 
0973   IndexIntoFile::RunOrLumiIndexes const& IndexIntoFile::SortedRunOrLumiItr::runOrLumiIndexes() const {
0974     return indexIntoFile_->runOrLumiIndexes().at(runOrLumi_);
0975   }
0976 
0977   IndexIntoFile::IndexIntoFileItrImpl::IndexIntoFileItrImpl(IndexIntoFile const* indexIntoFile,
0978                                                             EntryType entryType,
0979                                                             int indexToRun,
0980                                                             int indexToLumi,
0981                                                             int indexToEventRange,
0982                                                             long long indexToEvent,
0983                                                             long long nEvents)
0984       : indexIntoFile_(indexIntoFile),
0985         size_(static_cast<int>(indexIntoFile_->runOrLumiEntries_.size())),
0986         type_(entryType),
0987         indexToRun_(indexToRun),
0988         indexToLumi_(indexToLumi),
0989         indexToEventRange_(indexToEventRange),
0990         indexToEvent_(indexToEvent),
0991         nEvents_(nEvents) {}
0992 
0993   IndexIntoFile::IndexIntoFileItrImpl::~IndexIntoFileItrImpl() {}
0994 
0995   void IndexIntoFile::IndexIntoFileItrImpl::next() {
0996     if (type_ == kEvent) {
0997       if ((indexToEvent_ + 1) < nEvents_) {
0998         ++indexToEvent_;
0999       } else {
1000         bool found = nextEventRange();
1001 
1002         if (!found) {
1003           type_ = getRunOrLumiEntryType(indexToLumi_ + 1);
1004 
1005           if (type_ == kLumi) {
1006             ++indexToLumi_;
1007             initializeLumi();
1008           } else if (type_ == kRun) {
1009             indexToRun_ = indexToLumi_ + 1;
1010             initializeRun();
1011           } else {
1012             setInvalid();  // type_ is kEnd
1013           }
1014         }
1015       }
1016     } else if (type_ == kLumi) {
1017       if (indexToLumi_ + 1 == indexedSize()) {
1018         if (indexToEvent_ < nEvents_) {
1019           type_ = kEvent;
1020         } else {
1021           setInvalid();
1022         }
1023       } else {
1024         EntryType nextType = getRunOrLumiEntryType(indexToLumi_ + 1);
1025 
1026         if (nextType == kLumi && isSameLumi(indexToLumi_, indexToLumi_ + 1)) {
1027           ++indexToLumi_;
1028         } else if (indexToEvent_ < nEvents_) {
1029           type_ = kEvent;
1030         } else if (nextType == kRun) {
1031           type_ = kRun;
1032           indexToRun_ = indexToLumi_ + 1;
1033           initializeRun();
1034         } else {
1035           ++indexToLumi_;
1036           initializeLumi();
1037         }
1038       }
1039     } else if (type_ == kRun) {
1040       EntryType nextType = getRunOrLumiEntryType(indexToRun_ + 1);
1041       bool sameRun = isSameRun(indexToRun_, indexToRun_ + 1);
1042       if (nextType == kRun && sameRun) {
1043         ++indexToRun_;
1044       } else if (nextType == kRun && !sameRun) {
1045         ++indexToRun_;
1046         initializeRun();
1047       } else if (nextType == kLumi) {
1048         type_ = kLumi;
1049       } else {
1050         setInvalid();
1051       }
1052     }
1053   }
1054 
1055   void IndexIntoFile::IndexIntoFileItrImpl::skipEventForward(int& phIndexOfSkippedEvent,
1056                                                              RunNumber_t& runOfSkippedEvent,
1057                                                              LuminosityBlockNumber_t& lumiOfSkippedEvent,
1058                                                              EntryNumber_t& skippedEventEntry) {
1059     if (indexToEvent_ < nEvents_) {
1060       phIndexOfSkippedEvent = processHistoryIDIndex();
1061       runOfSkippedEvent = run();
1062       lumiOfSkippedEvent = peekAheadAtLumi();
1063       skippedEventEntry = peekAheadAtEventEntry();
1064 
1065       if ((indexToEvent_ + 1) < nEvents_) {
1066         ++indexToEvent_;
1067         return;
1068       } else if (nextEventRange()) {
1069         return;
1070       } else if (type_ == kRun || type_ == kLumi) {
1071         if (skipLumiInRun()) {
1072           return;
1073         }
1074       } else if (type_ == kEvent) {
1075         next();
1076         return;
1077       }
1078       advanceToNextRun();
1079       return;
1080     }
1081 
1082     if (type_ == kRun) {
1083       while (skipLumiInRun()) {
1084         if (indexToEvent_ < nEvents_) {
1085           skipEventForward(phIndexOfSkippedEvent, runOfSkippedEvent, lumiOfSkippedEvent, skippedEventEntry);
1086           return;
1087         }
1088       }
1089     }
1090 
1091     while (indexToEvent_ >= nEvents_ && type_ != kEnd) {
1092       while (skipLumiInRun()) {
1093         if (indexToEvent_ < nEvents_) {
1094           skipEventForward(phIndexOfSkippedEvent, runOfSkippedEvent, lumiOfSkippedEvent, skippedEventEntry);
1095           return;
1096         }
1097       }
1098       advanceToNextRun();
1099     }
1100     if (type_ == kEnd) {
1101       phIndexOfSkippedEvent = invalidIndex;
1102       runOfSkippedEvent = invalidRun;
1103       lumiOfSkippedEvent = invalidLumi;
1104       skippedEventEntry = invalidEntry;
1105       return;
1106     }
1107     skipEventForward(phIndexOfSkippedEvent, runOfSkippedEvent, lumiOfSkippedEvent, skippedEventEntry);
1108     return;
1109   }
1110 
1111   void IndexIntoFile::IndexIntoFileItrImpl::skipEventBackward(int& phIndexOfEvent,
1112                                                               RunNumber_t& runOfEvent,
1113                                                               LuminosityBlockNumber_t& lumiOfEvent,
1114                                                               EntryNumber_t& eventEntry) {
1115     // Look for previous events in the current lumi
1116     if (indexToEvent_ > 0) {
1117       --indexToEvent_;
1118     } else if (!previousEventRange()) {
1119       // Look for previous events in previous lumis
1120       if (!previousLumiWithEvents()) {
1121         // If we get here there are no previous events in the file
1122 
1123         if (!indexIntoFile_->empty()) {
1124           // Set the iterator to the beginning of the file
1125           type_ = kRun;
1126           indexToRun_ = 0;
1127           initializeRun();
1128         }
1129         phIndexOfEvent = invalidIndex;
1130         runOfEvent = invalidRun;
1131         lumiOfEvent = invalidLumi;
1132         eventEntry = invalidEntry;
1133         return;
1134       }
1135     }
1136     // Found a previous event and we have set the iterator so that this event
1137     // will be the next event process. (There may or may not be a run and/or
1138     // a lumi processed first).
1139     // Return information about this event
1140     phIndexOfEvent = processHistoryIDIndex();
1141     runOfEvent = run();
1142     lumiOfEvent = peekAheadAtLumi();
1143     eventEntry = peekAheadAtEventEntry();
1144   }
1145 
1146   bool IndexIntoFile::IndexIntoFileItrImpl::previousLumiWithEvents() {
1147     // Find the correct place to start the search
1148     int newLumi = indexToLumi();
1149     if (newLumi == invalidIndex) {
1150       newLumi = indexToRun() == invalidIndex ? indexedSize() - 1 : indexToRun();
1151     } else {
1152       while (getRunOrLumiEntryType(newLumi - 1) == kLumi && isSameLumi(newLumi, newLumi - 1)) {
1153         --newLumi;
1154       }
1155       --newLumi;
1156     }
1157     if (newLumi <= 0)
1158       return false;
1159 
1160     // Look backwards for a lumi with events
1161     for (; newLumi > 0; --newLumi) {
1162       if (getRunOrLumiEntryType(newLumi) == kRun) {
1163         continue;
1164       }
1165       if (setToLastEventInRange(newLumi)) {
1166         break;  // found it
1167       }
1168     }
1169     if (newLumi == 0)
1170       return false;
1171 
1172     // Finish initializing the iterator
1173     // Go back to the first lumi entry for this lumi
1174     while (getRunOrLumiEntryType(newLumi - 1) == kLumi && isSameLumi(newLumi, newLumi - 1)) {
1175       --newLumi;
1176     }
1177     // Then go forward to the first valid one (or if there are not any valid ones
1178     // to the last one, only possible in the entryOrder case)
1179     while (not lumiIterationStartingIndex(newLumi)) {
1180       ++newLumi;
1181     }
1182 
1183     setIndexToLumi(newLumi);
1184 
1185     if (type() != kEnd && isSameRun(newLumi, indexToRun())) {
1186       if (type() == kEvent)
1187         type_ = kLumi;
1188       return true;
1189     }
1190     int newRun = newLumi;
1191     while (newRun > 0 && getRunOrLumiEntryType(newRun - 1) == kLumi) {
1192       --newRun;
1193     }
1194     --newRun;
1195     assert(getRunOrLumiEntryType(newRun) == kRun);
1196     while (getRunOrLumiEntryType(newRun - 1) == kRun && isSameRun(newRun - 1, newLumi)) {
1197       --newRun;
1198     }
1199     indexToRun_ = newRun;
1200     type_ = kRun;
1201     return true;
1202   }
1203 
1204   IndexIntoFile::EntryNumber_t IndexIntoFile::IndexIntoFileItrImpl::firstEventEntryThisRun() {
1205     if (indexToLumi() == invalidIndex)
1206       return invalidEntry;
1207 
1208     int saveIndexToLumi = indexToLumi();
1209     int saveIndexToEventRange = indexToEventRange();
1210     long long saveIndexToEvent = indexToEvent();
1211     long long saveNEvents = nEvents();
1212 
1213     initializeRun();
1214 
1215     IndexIntoFile::EntryNumber_t returnValue = invalidEntry;
1216 
1217     do {
1218       if (indexToEvent() < nEvents()) {
1219         returnValue = peekAheadAtEventEntry();
1220         break;
1221       }
1222     } while (skipLumiInRun());
1223 
1224     setIndexToLumi(saveIndexToLumi);
1225     setIndexToEventRange(saveIndexToEventRange);
1226     setIndexToEvent(saveIndexToEvent);
1227     setNEvents(saveNEvents);
1228 
1229     return returnValue;
1230   }
1231 
1232   IndexIntoFile::EntryNumber_t IndexIntoFile::IndexIntoFileItrImpl::firstEventEntryThisLumi() {
1233     if (indexToLumi() == invalidIndex)
1234       return invalidEntry;
1235 
1236     int saveIndexToLumi = indexToLumi();
1237     int saveIndexToEventRange = indexToEventRange();
1238     long long saveIndexToEvent = indexToEvent();
1239     long long saveNEvents = nEvents();
1240 
1241     while (indexToLumi() - 1 > 0) {
1242       if (getRunOrLumiEntryType(indexToLumi() - 1) == kRun)
1243         break;
1244       if (!isSameLumi(indexToLumi(), indexToLumi() - 1))
1245         break;
1246       --indexToLumi_;
1247     }
1248     initializeLumi();
1249 
1250     IndexIntoFile::EntryNumber_t returnValue = invalidEntry;
1251 
1252     if (indexToEvent() < nEvents()) {
1253       returnValue = peekAheadAtEventEntry();
1254     }
1255 
1256     setIndexToLumi(saveIndexToLumi);
1257     setIndexToEventRange(saveIndexToEventRange);
1258     setIndexToEvent(saveIndexToEvent);
1259     setNEvents(saveNEvents);
1260 
1261     return returnValue;
1262   }
1263 
1264   void IndexIntoFile::IndexIntoFileItrImpl::advanceToNextRun() {
1265     if (type_ == kEnd)
1266       return;
1267     for (int i = 1; indexToRun_ + i < indexedSize(); ++i) {
1268       if (getRunOrLumiEntryType(indexToRun_ + i) == kRun) {
1269         if (!isSameRun(indexToRun_, indexToRun_ + i)) {
1270           type_ = kRun;
1271           indexToRun_ += i;
1272           initializeRun();
1273           return;
1274         }
1275       }
1276     }
1277     setInvalid();
1278   }
1279 
1280   void IndexIntoFile::IndexIntoFileItrImpl::advanceToNextLumiOrRun() {
1281     if (type_ == kEnd)
1282       return;
1283     assert(indexToRun_ != invalidIndex);
1284 
1285     // A preliminary step is to advance to the last run entry for
1286     // this run (actually this step is not needed in the
1287     // context I expect this to be called in, just being careful)
1288     int startSearch = indexToRun_;
1289     for (int i = 1; startSearch + i < indexedSize(); ++i) {
1290       if (getRunOrLumiEntryType(startSearch + i) == kRun && isSameRun(indexToRun_, startSearch + i)) {
1291         indexToRun_ = startSearch + i;
1292       } else {
1293         break;
1294       }
1295     }
1296 
1297     if (type_ == kRun && indexToLumi_ != invalidIndex) {
1298       type_ = kLumi;
1299       return;
1300     }
1301 
1302     startSearch = indexToLumi_;
1303     if (startSearch == invalidIndex)
1304       startSearch = indexToRun_;
1305     for (int i = 1; startSearch + i < indexedSize(); ++i) {
1306       if (getRunOrLumiEntryType(startSearch + i) == kRun) {
1307         if (!isSameRun(indexToRun_, startSearch + i)) {
1308           type_ = kRun;
1309           indexToRun_ = startSearch + i;
1310           initializeRun();
1311           return;
1312         }
1313       } else if (indexToLumi_ != invalidIndex) {
1314         if (!isSameLumi(indexToLumi_, startSearch + i)) {
1315           type_ = kLumi;
1316           indexToLumi_ = startSearch + i;
1317           initializeLumi();
1318           return;
1319         }
1320       }
1321     }
1322     setInvalid();
1323   }
1324 
1325   bool IndexIntoFile::IndexIntoFileItrImpl::skipToNextEventInLumi() {
1326     if (indexToEvent_ >= nEvents_)
1327       return false;
1328     if ((indexToEvent_ + 1) < nEvents_) {
1329       ++indexToEvent_;
1330       return true;
1331     }
1332     return nextEventRange();
1333   }
1334 
1335   void IndexIntoFile::IndexIntoFileItrImpl::initializeRun() {
1336     indexToLumi_ = invalidIndex;
1337     indexToEventRange_ = invalidIndex;
1338     indexToEvent_ = 0;
1339     nEvents_ = 0;
1340 
1341     for (int i = indexToRun_ + 1, iEnd = indexedSize(); i < iEnd; ++i) {
1342       EntryType entryType = getRunOrLumiEntryType(i);
1343       bool sameRun = isSameRun(indexToRun_, i);
1344 
1345       if (entryType == kRun) {
1346         if (sameRun) {
1347           continue;
1348         } else {
1349           break;
1350         }
1351       } else {
1352         indexToLumi_ = i;
1353         initializeLumi();
1354         return;
1355       }
1356     }
1357   }
1358 
1359   void IndexIntoFile::IndexIntoFileItrImpl::initializeLumi() {
1360     initializeLumi_();
1361     auto oldLumi = lumi();
1362     // Then go forward to the first valid one (or if there are not any valid ones
1363     // to the last one, only possible in the entryOrder case)
1364     while (not lumiIterationStartingIndex(indexToLumi_)) {
1365       ++indexToLumi_;
1366     }
1367     assert(oldLumi == lumi());
1368   }
1369 
1370   bool IndexIntoFile::IndexIntoFileItrImpl::operator==(IndexIntoFileItrImpl const& right) const {
1371     return (indexIntoFile_ == right.indexIntoFile_ && size_ == right.size_ && type_ == right.type_ &&
1372             indexToRun_ == right.indexToRun_ && indexToLumi_ == right.indexToLumi_ &&
1373             indexToEventRange_ == right.indexToEventRange_ && indexToEvent_ == right.indexToEvent_ &&
1374             nEvents_ == right.nEvents_);
1375   }
1376 
1377   int IndexIntoFile::IndexIntoFileItrImpl::indexedSize() const { return size(); }
1378 
1379   void IndexIntoFile::IndexIntoFileItrImpl::copyPosition(IndexIntoFileItrImpl const& position) {
1380     type_ = position.type_;
1381     indexToRun_ = position.indexToRun_;
1382     indexToLumi_ = position.indexToLumi_;
1383     indexToEventRange_ = position.indexToEventRange_;
1384     indexToEvent_ = position.indexToEvent_;
1385     nEvents_ = position.nEvents_;
1386   }
1387 
1388   void IndexIntoFile::IndexIntoFileItrImpl::getLumisInRun(std::vector<LuminosityBlockNumber_t>& lumis) const {
1389     assert(shouldProcessRun());
1390     lumis.clear();
1391 
1392     if (type_ == kEnd)
1393       return;
1394 
1395     LuminosityBlockNumber_t previousLumi = invalidLumi;
1396 
1397     for (int i = 1; (i + indexToRun_) < indexedSize(); ++i) {
1398       int index = i + indexToRun_;
1399       EntryType entryType = getRunOrLumiEntryType(index);
1400 
1401       if (entryType == kRun) {
1402         if (isSameRun(indexToRun_, index)) {
1403           continue;
1404         } else {
1405           break;
1406         }
1407       } else {
1408         LuminosityBlockNumber_t luminosityBlock = lumi(index);
1409         if (luminosityBlock != invalidLumi && luminosityBlock != previousLumi) {
1410           lumis.push_back(luminosityBlock);
1411           previousLumi = luminosityBlock;
1412         }
1413       }
1414     }
1415     std::sort(lumis.begin(), lumis.end());
1416     lumis.erase(std::unique(lumis.begin(), lumis.end()), lumis.end());
1417   }
1418 
1419   void IndexIntoFile::IndexIntoFileItrImpl::setInvalid() {
1420     type_ = kEnd;
1421     indexToRun_ = invalidIndex;
1422     indexToLumi_ = invalidIndex;
1423     indexToEventRange_ = invalidIndex;
1424     indexToEvent_ = 0;
1425     nEvents_ = 0;
1426   }
1427 
1428   IndexIntoFile::IndexIntoFileItrNoSort::IndexIntoFileItrNoSort(IndexIntoFile const* indexIntoFile,
1429                                                                 EntryType entryType,
1430                                                                 int indexToRun,
1431                                                                 int indexToLumi,
1432                                                                 int indexToEventRange,
1433                                                                 long long indexToEvent,
1434                                                                 long long nEvents)
1435       : IndexIntoFileItrImpl(
1436             indexIntoFile, entryType, indexToRun, indexToLumi, indexToEventRange, indexToEvent, nEvents) {}
1437 
1438   IndexIntoFile::IndexIntoFileItrImpl* IndexIntoFile::IndexIntoFileItrNoSort::clone() const {
1439     return new IndexIntoFileItrNoSort(*this);
1440   }
1441 
1442   int IndexIntoFile::IndexIntoFileItrNoSort::processHistoryIDIndex() const {
1443     if (type() == kEnd)
1444       return invalidIndex;
1445     return indexIntoFile()->runOrLumiEntries()[indexToRun()].processHistoryIDIndex();
1446   }
1447 
1448   RunNumber_t IndexIntoFile::IndexIntoFileItrNoSort::run() const {
1449     if (type() == kEnd)
1450       return invalidRun;
1451     return indexIntoFile()->runOrLumiEntries()[indexToRun()].run();
1452   }
1453 
1454   LuminosityBlockNumber_t IndexIntoFile::IndexIntoFileItrNoSort::lumi() const {
1455     if (type() == kEnd || type() == kRun)
1456       return invalidLumi;
1457     return indexIntoFile()->runOrLumiEntries()[indexToLumi()].lumi();
1458   }
1459 
1460   IndexIntoFile::EntryNumber_t IndexIntoFile::IndexIntoFileItrNoSort::entry() const {
1461     if (type() == kEnd)
1462       return invalidEntry;
1463     if (type() == kRun)
1464       return indexIntoFile()->runOrLumiEntries()[indexToRun()].entry();
1465     if (type() == kLumi)
1466       return indexIntoFile()->runOrLumiEntries()[indexToLumi()].entry();
1467     return indexIntoFile()->runOrLumiEntries()[indexToEventRange()].beginEvents() + indexToEvent();
1468   }
1469 
1470   LuminosityBlockNumber_t IndexIntoFile::IndexIntoFileItrNoSort::peekAheadAtLumi() const {
1471     if (indexToLumi() == invalidIndex)
1472       return invalidLumi;
1473     return indexIntoFile()->runOrLumiEntries()[indexToLumi()].lumi();
1474   }
1475 
1476   IndexIntoFile::EntryNumber_t IndexIntoFile::IndexIntoFileItrNoSort::peekAheadAtEventEntry() const {
1477     if (indexToLumi() == invalidIndex)
1478       return invalidEntry;
1479     if (indexToEvent() >= nEvents())
1480       return invalidEntry;
1481     return indexIntoFile()->runOrLumiEntries()[indexToEventRange()].beginEvents() + indexToEvent();
1482   }
1483 
1484   void IndexIntoFile::IndexIntoFileItrNoSort::initializeLumi_() {
1485     assert(indexToLumi() != invalidIndex);
1486 
1487     setIndexToEventRange(invalidIndex);
1488     setIndexToEvent(0);
1489     setNEvents(0);
1490 
1491     for (int i = 0; indexToLumi() + i < size(); ++i) {
1492       if (indexIntoFile()->runOrLumiEntries()[indexToLumi() + i].isRun()) {
1493         break;
1494       } else if (indexIntoFile()->runOrLumiEntries()[indexToLumi() + i].lumi() ==
1495                  indexIntoFile()->runOrLumiEntries()[indexToLumi()].lumi()) {
1496         if (indexIntoFile()->runOrLumiEntries()[indexToLumi() + i].beginEvents() == invalidEntry) {
1497           continue;
1498         }
1499         setIndexToEventRange(indexToLumi() + i);
1500         setIndexToEvent(0);
1501         setNEvents(indexIntoFile()->runOrLumiEntries()[indexToEventRange()].endEvents() -
1502                    indexIntoFile()->runOrLumiEntries()[indexToEventRange()].beginEvents());
1503         break;
1504       } else {
1505         break;
1506       }
1507     }
1508   }
1509 
1510   bool IndexIntoFile::IndexIntoFileItrNoSort::nextEventRange() {
1511     if (indexToEventRange() == invalidIndex)
1512       return false;
1513 
1514     // Look for the next event range, same lumi but different entry
1515     for (int i = 1; indexToEventRange() + i < size(); ++i) {
1516       if (indexIntoFile()->runOrLumiEntries()[indexToEventRange() + i].isRun()) {
1517         return false;  // hit next run
1518       } else if (indexIntoFile()->runOrLumiEntries()[indexToEventRange() + i].lumi() ==
1519                  indexIntoFile()->runOrLumiEntries()[indexToEventRange()].lumi()) {
1520         if (indexIntoFile()->runOrLumiEntries()[indexToEventRange() + i].beginEvents() == invalidEntry) {
1521           continue;  // same lumi but has no events, keep looking
1522         }
1523         setIndexToEventRange(indexToEventRange() + i);
1524         setIndexToEvent(0);
1525         setNEvents(indexIntoFile()->runOrLumiEntries()[indexToEventRange()].endEvents() -
1526                    indexIntoFile()->runOrLumiEntries()[indexToEventRange()].beginEvents());
1527         return true;  // found more events in this lumi
1528       }
1529       return false;  // hit next lumi
1530     }
1531     return false;  // hit the end of the IndexIntoFile
1532   }
1533 
1534   bool IndexIntoFile::IndexIntoFileItrNoSort::previousEventRange() {
1535     if (indexToEventRange() == invalidIndex)
1536       return false;
1537     assert(indexToEventRange() < size());
1538 
1539     // Look backward for a previous event range with events, same lumi but different entry
1540     for (int i = 1; indexToEventRange() - i > 0; ++i) {
1541       int newRange = indexToEventRange() - i;
1542       if (indexIntoFile()->runOrLumiEntries()[newRange].isRun()) {
1543         return false;  // hit run
1544       } else if (isSameLumi(newRange, indexToEventRange())) {
1545         if (indexIntoFile()->runOrLumiEntries()[newRange].beginEvents() == invalidEntry) {
1546           continue;  // same lumi but has no events, keep looking
1547         }
1548         setIndexToEventRange(newRange);
1549         setNEvents(indexIntoFile()->runOrLumiEntries()[indexToEventRange()].endEvents() -
1550                    indexIntoFile()->runOrLumiEntries()[indexToEventRange()].beginEvents());
1551         setIndexToEvent(nEvents() - 1);
1552         return true;  // found previous event in this lumi
1553       }
1554       return false;  // hit previous lumi
1555     }
1556     return false;  // hit the beginning of the IndexIntoFile, 0th entry has to be a run
1557   }
1558 
1559   bool IndexIntoFile::IndexIntoFileItrNoSort::setToLastEventInRange(int index) {
1560     if (indexIntoFile()->runOrLumiEntries()[index].beginEvents() == invalidEntry) {
1561       return false;
1562     }
1563     setIndexToEventRange(index);
1564     setNEvents(indexIntoFile()->runOrLumiEntries()[indexToEventRange()].endEvents() -
1565                indexIntoFile()->runOrLumiEntries()[indexToEventRange()].beginEvents());
1566     assert(nEvents() > 0);
1567     setIndexToEvent(nEvents() - 1);
1568     return true;
1569   }
1570 
1571   bool IndexIntoFile::IndexIntoFileItrNoSort::skipLumiInRun() {
1572     if (indexToLumi() == invalidIndex)
1573       return false;
1574     for (int i = 1; indexToLumi() + i < size(); ++i) {
1575       int newLumi = indexToLumi() + i;
1576       if (indexIntoFile()->runOrLumiEntries()[newLumi].isRun()) {
1577         return false;  // hit next run
1578       } else if (indexIntoFile()->runOrLumiEntries()[newLumi].lumi() ==
1579                  indexIntoFile()->runOrLumiEntries()[indexToLumi()].lumi()) {
1580         continue;
1581       }
1582       setIndexToLumi(newLumi);
1583       initializeLumi();
1584       return true;  // hit next lumi
1585     }
1586     return false;  // hit the end of the IndexIntoFile
1587   }
1588 
1589   bool IndexIntoFile::IndexIntoFileItrNoSort::lumiIterationStartingIndex(int index) const {
1590     return indexIntoFile()->runOrLumiEntries()[index].entry() != invalidEntry;
1591   }
1592 
1593   IndexIntoFile::EntryType IndexIntoFile::IndexIntoFileItrNoSort::getRunOrLumiEntryType(int index) const {
1594     if (index < 0 || index >= size()) {
1595       return kEnd;
1596     } else if (indexIntoFile()->runOrLumiEntries()[index].isRun()) {
1597       return kRun;
1598     }
1599     return kLumi;
1600   }
1601 
1602   bool IndexIntoFile::IndexIntoFileItrNoSort::isSameLumi(int index1, int index2) const {
1603     if (index1 < 0 || index1 >= size() || index2 < 0 || index2 >= size()) {
1604       return false;
1605     }
1606     return indexIntoFile()->runOrLumiEntries()[index1].lumi() == indexIntoFile()->runOrLumiEntries()[index2].lumi();
1607   }
1608 
1609   bool IndexIntoFile::IndexIntoFileItrNoSort::isSameRun(int index1, int index2) const {
1610     if (index1 < 0 || index1 >= size() || index2 < 0 || index2 >= size()) {
1611       return false;
1612     }
1613     return indexIntoFile()->runOrLumiEntries()[index1].run() == indexIntoFile()->runOrLumiEntries()[index2].run() &&
1614            indexIntoFile()->runOrLumiEntries()[index1].processHistoryIDIndex() ==
1615                indexIntoFile()->runOrLumiEntries()[index2].processHistoryIDIndex();
1616   }
1617 
1618   LuminosityBlockNumber_t IndexIntoFile::IndexIntoFileItrNoSort::lumi(int index) const {
1619     if (index < 0 || index >= size()) {
1620       return invalidLumi;
1621     }
1622     return indexIntoFile()->runOrLumiEntries()[index].lumi();
1623   }
1624 
1625   IndexIntoFile::IndexIntoFileItrSorted::IndexIntoFileItrSorted(IndexIntoFile const* indexIntoFile,
1626                                                                 EntryType entryType,
1627                                                                 int indexToRun,
1628                                                                 int indexToLumi,
1629                                                                 int indexToEventRange,
1630                                                                 long long indexToEvent,
1631                                                                 long long nEvents)
1632       : IndexIntoFileItrImpl(
1633             indexIntoFile, entryType, indexToRun, indexToLumi, indexToEventRange, indexToEvent, nEvents) {
1634     indexIntoFile->fillRunOrLumiIndexes();
1635   }
1636 
1637   IndexIntoFile::IndexIntoFileItrImpl* IndexIntoFile::IndexIntoFileItrSorted::clone() const {
1638     return new IndexIntoFileItrSorted(*this);
1639   }
1640 
1641   int IndexIntoFile::IndexIntoFileItrSorted::processHistoryIDIndex() const {
1642     if (type() == kEnd)
1643       return invalidIndex;
1644     return indexIntoFile()->runOrLumiIndexes()[indexToRun()].processHistoryIDIndex();
1645   }
1646 
1647   RunNumber_t IndexIntoFile::IndexIntoFileItrSorted::run() const {
1648     if (type() == kEnd)
1649       return invalidRun;
1650     return indexIntoFile()->runOrLumiIndexes()[indexToRun()].run();
1651   }
1652 
1653   LuminosityBlockNumber_t IndexIntoFile::IndexIntoFileItrSorted::lumi() const {
1654     if (type() == kEnd || type() == kRun)
1655       return invalidLumi;
1656     return indexIntoFile()->runOrLumiIndexes()[indexToLumi()].lumi();
1657   }
1658 
1659   IndexIntoFile::EntryNumber_t IndexIntoFile::IndexIntoFileItrSorted::entry() const {
1660     if (type() == kEnd)
1661       return invalidEntry;
1662     if (type() == kRun) {
1663       int i = indexIntoFile()->runOrLumiIndexes()[indexToRun()].indexToGetEntry();
1664       return indexIntoFile()->runOrLumiEntries()[i].entry();
1665     }
1666     if (type() == kLumi) {
1667       int i = indexIntoFile()->runOrLumiIndexes()[indexToLumi()].indexToGetEntry();
1668       return indexIntoFile()->runOrLumiEntries()[i].entry();
1669     }
1670     long long eventNumberIndex =
1671         indexIntoFile()->runOrLumiIndexes()[indexToEventRange()].beginEventNumbers() + indexToEvent();
1672     indexIntoFile()->fillEventEntries();
1673     return indexIntoFile()->eventEntries().at(eventNumberIndex).entry();
1674   }
1675 
1676   LuminosityBlockNumber_t IndexIntoFile::IndexIntoFileItrSorted::peekAheadAtLumi() const {
1677     if (indexToLumi() == invalidIndex)
1678       return invalidLumi;
1679     return indexIntoFile()->runOrLumiIndexes()[indexToLumi()].lumi();
1680   }
1681 
1682   IndexIntoFile::EntryNumber_t IndexIntoFile::IndexIntoFileItrSorted::peekAheadAtEventEntry() const {
1683     if (indexToLumi() == invalidIndex)
1684       return invalidEntry;
1685     if (indexToEvent() >= nEvents())
1686       return invalidEntry;
1687     long long eventNumberIndex =
1688         indexIntoFile()->runOrLumiIndexes()[indexToEventRange()].beginEventNumbers() + indexToEvent();
1689     indexIntoFile()->fillEventEntries();
1690     return indexIntoFile()->eventEntries().at(eventNumberIndex).entry();
1691   }
1692 
1693   void IndexIntoFile::IndexIntoFileItrSorted::initializeLumi_() {
1694     assert(indexToLumi() != invalidIndex);
1695     setIndexToEventRange(indexToLumi());
1696     setIndexToEvent(0);
1697     setNEvents(indexIntoFile()->runOrLumiIndexes()[indexToLumi()].endEventNumbers() -
1698                indexIntoFile()->runOrLumiIndexes()[indexToLumi()].beginEventNumbers());
1699     if (nEvents() == 0) {
1700       setIndexToEventRange(invalidIndex);
1701     }
1702   }
1703 
1704   bool IndexIntoFile::IndexIntoFileItrSorted::nextEventRange() { return false; }
1705 
1706   bool IndexIntoFile::IndexIntoFileItrSorted::previousEventRange() { return false; }
1707 
1708   bool IndexIntoFile::IndexIntoFileItrSorted::setToLastEventInRange(int index) {
1709     long long nEventsInRange = indexIntoFile()->runOrLumiIndexes()[index].endEventNumbers() -
1710                                indexIntoFile()->runOrLumiIndexes()[index].beginEventNumbers();
1711     if (nEventsInRange == 0) {
1712       return false;
1713     }
1714     while (index > 0 && !indexIntoFile()->runOrLumiIndexes()[index - 1].isRun() && isSameLumi(index, index - 1)) {
1715       --index;
1716     }
1717     assert(nEventsInRange == indexIntoFile()->runOrLumiIndexes()[index].endEventNumbers() -
1718                                  indexIntoFile()->runOrLumiIndexes()[index].beginEventNumbers());
1719 
1720     setIndexToEventRange(index);
1721     setNEvents(nEventsInRange);
1722     assert(nEvents() > 0);
1723     setIndexToEvent(nEventsInRange - 1);
1724     return true;
1725   }
1726 
1727   bool IndexIntoFile::IndexIntoFileItrSorted::skipLumiInRun() {
1728     if (indexToLumi() == invalidIndex)
1729       return false;
1730     for (int i = 1; indexToLumi() + i < size(); ++i) {
1731       int newLumi = indexToLumi() + i;
1732       if (indexIntoFile()->runOrLumiIndexes()[newLumi].isRun()) {
1733         return false;  // hit next run
1734       } else if (indexIntoFile()->runOrLumiIndexes()[newLumi].lumi() ==
1735                  indexIntoFile()->runOrLumiIndexes()[indexToLumi()].lumi()) {
1736         continue;
1737       }
1738       setIndexToLumi(newLumi);
1739       initializeLumi();
1740       return true;  // hit next lumi
1741     }
1742     return false;  // hit the end of the IndexIntoFile
1743   }
1744 
1745   bool IndexIntoFile::IndexIntoFileItrSorted::lumiIterationStartingIndex(int index) const {
1746     return indexIntoFile()->runOrLumiEntries()[indexIntoFile()->runOrLumiIndexes()[index].indexToGetEntry()].entry() !=
1747            invalidEntry;
1748   }
1749 
1750   IndexIntoFile::EntryType IndexIntoFile::IndexIntoFileItrSorted::getRunOrLumiEntryType(int index) const {
1751     if (index < 0 || index >= size()) {
1752       return kEnd;
1753     } else if (indexIntoFile()->runOrLumiIndexes()[index].isRun()) {
1754       return kRun;
1755     }
1756     return kLumi;
1757   }
1758 
1759   bool IndexIntoFile::IndexIntoFileItrSorted::isSameLumi(int index1, int index2) const {
1760     if (index1 < 0 || index1 >= size() || index2 < 0 || index2 >= size()) {
1761       return false;
1762     }
1763     return indexIntoFile()->runOrLumiIndexes()[index1].lumi() == indexIntoFile()->runOrLumiIndexes()[index2].lumi();
1764   }
1765 
1766   bool IndexIntoFile::IndexIntoFileItrSorted::isSameRun(int index1, int index2) const {
1767     if (index1 < 0 || index1 >= size() || index2 < 0 || index2 >= size()) {
1768       return false;
1769     }
1770     return indexIntoFile()->runOrLumiIndexes()[index1].run() == indexIntoFile()->runOrLumiIndexes()[index2].run() &&
1771            indexIntoFile()->runOrLumiIndexes()[index1].processHistoryIDIndex() ==
1772                indexIntoFile()->runOrLumiIndexes()[index2].processHistoryIDIndex();
1773   }
1774 
1775   LuminosityBlockNumber_t IndexIntoFile::IndexIntoFileItrSorted::lumi(int index) const {
1776     if (index < 0 || index >= size()) {
1777       return invalidLumi;
1778     }
1779     return indexIntoFile()->runOrLumiIndexes()[index].lumi();
1780   }
1781 
1782   // *************************************
1783 
1784   IndexIntoFile::IndexIntoFileItrEntryOrder::IndexIntoFileItrEntryOrder(IndexIntoFile const* iIndexIntoFile,
1785                                                                         EntryType entryType,
1786                                                                         int indexToRun,
1787                                                                         int indexToLumi,
1788                                                                         int indexToEventRange,
1789                                                                         long long indexToEvent,
1790                                                                         long long nEvents)
1791       : IndexIntoFileItrImpl(
1792             iIndexIntoFile, entryType, indexToRun, indexToLumi, indexToEventRange, indexToEvent, nEvents) {
1793     EntryOrderInitializationInfo info;
1794     info.resizeVectors(indexIntoFile()->runOrLumiEntries());
1795     reserveSpaceInVectors(indexIntoFile()->runOrLumiEntries().size());
1796 
1797     // fill firstIndexOfLumi, firstIndexOfRun, runsWithNoEvents
1798     info.gatherNeededInfo(indexIntoFile()->runOrLumiEntries());
1799 
1800     info.fillIndexesSortedByEventEntry(indexIntoFile()->runOrLumiEntries());
1801     info.fillIndexesToLastContiguousEvents(indexIntoFile()->runOrLumiEntries());
1802 
1803     EntryNumber_t currentRun = invalidEntry;
1804 
1805     // The main iterator created here (iEventSequence) is incremented
1806     // in the function handleToEndOfContiguousEventsInRun and
1807     // the functions it calls. The iterator is stored in "info",
1808     // which also holds other information related to the iteration.
1809     // The information is passed to these functions inside the "info"
1810     // object.
1811     for (info.iEventSequence_ = info.indexesSortedByEventEntry_.cbegin(),
1812         info.iEventSequenceEnd_ = info.indexesSortedByEventEntry_.cend();
1813          info.iEventSequence_ < info.iEventSequenceEnd_;) {
1814       info.eventSequenceIndex_ = info.iEventSequence_->runOrLumiIndex_;
1815       info.eventSequenceRunOrLumiEntry_ = &indexIntoFile()->runOrLumiEntries()[info.eventSequenceIndex_];
1816 
1817       assert(info.eventSequenceRunOrLumiEntry_->orderPHIDRun() != currentRun);
1818       currentRun = info.eventSequenceRunOrLumiEntry_->orderPHIDRun();
1819 
1820       // Handles the set of events contiguous in the Events TTree from
1821       // a single run and all the entries (Run or Lumi) associated with
1822       // those events and possibly some runs with no events that precede
1823       // the run in the runs TTree.
1824       handleToEndOfContiguousEventsInRun(info, currentRun);
1825     }
1826     // This takes care of only Runs with no Events at the end of
1827     // the Runs TTree that were not already added.
1828     addRunsWithNoEvents(info);
1829     indexedSize_ = fileOrderRunOrLumiEntry_.size();
1830   }
1831 
1832   IndexIntoFile::IndexIntoFileItrImpl* IndexIntoFile::IndexIntoFileItrEntryOrder::clone() const {
1833     return new IndexIntoFileItrEntryOrder(*this);
1834   }
1835 
1836   int IndexIntoFile::IndexIntoFileItrEntryOrder::processHistoryIDIndex() const {
1837     if (type() == kEnd)
1838       return invalidIndex;
1839     return runOrLumisEntry(indexToRun()).processHistoryIDIndex();
1840   }
1841 
1842   RunNumber_t IndexIntoFile::IndexIntoFileItrEntryOrder::run() const {
1843     if (type() == kEnd)
1844       return invalidRun;
1845     return runOrLumisEntry(indexToRun()).run();
1846   }
1847 
1848   LuminosityBlockNumber_t IndexIntoFile::IndexIntoFileItrEntryOrder::lumi() const {
1849     if (type() == kEnd || type() == kRun)
1850       return invalidLumi;
1851     return runOrLumisEntry(indexToLumi()).lumi();
1852   }
1853 
1854   IndexIntoFile::EntryNumber_t IndexIntoFile::IndexIntoFileItrEntryOrder::entry() const {
1855     if (type() == kEnd)
1856       return invalidEntry;
1857     if (type() == kRun)
1858       return runOrLumisEntry(indexToRun()).entry();
1859     if (type() == kLumi) {
1860       auto entry = runOrLumisEntry(indexToLumi()).entry();
1861       if (entry == invalidEntry) {
1862         auto const& runLumiEntry = runOrLumisEntry(indexToLumi());
1863         for (int index = indexToLumi() + 1; index < indexedSize(); ++index) {
1864           auto const& laterRunOrLumiEntry = runOrLumisEntry(index);
1865           if (runLumiEntry.lumi() == laterRunOrLumiEntry.lumi() and runLumiEntry.run() == laterRunOrLumiEntry.run() and
1866               runLumiEntry.processHistoryIDIndex() == laterRunOrLumiEntry.processHistoryIDIndex() &&
1867               laterRunOrLumiEntry.entry() != invalidEntry) {
1868             return laterRunOrLumiEntry.entry();
1869           }
1870         }
1871         // We should always find one and never get here!
1872         throw Exception(errors::LogicError) << "In IndexIntoFile::IndexIntoFileItrEntryOrder::entry. Could not\n"
1873                                             << "find valid TTree entry number for lumi. This means the IndexIntoFile\n"
1874                                             << "product in the output file will be corrupted.\n"
1875                                             << "The output file will be unusable for most purposes.\n"
1876                                             << "If this occurs after an unrelated exception was thrown,\n"
1877                                             << "then ignore this exception and fix the primary exception.\n"
1878                                             << "This is an expected side effect.\n"
1879                                             << "Otherwise, please report this to the core framework developers\n";
1880       }
1881       return entry;
1882     }
1883     return runOrLumisEntry(indexToEventRange()).beginEvents() + indexToEvent();
1884   }
1885 
1886   bool IndexIntoFile::IndexIntoFileItrEntryOrder::shouldProcessLumi() const {
1887     assert(type() == kLumi);
1888     assert(indexToLumi() != invalidIndex);
1889     return shouldProcessRunOrLumi_[indexToLumi()];
1890   }
1891 
1892   bool IndexIntoFile::IndexIntoFileItrEntryOrder::shouldProcessRun() const {
1893     assert(type() == kRun);
1894     assert(indexToRun() != invalidIndex);
1895     return shouldProcessRunOrLumi_[indexToRun()];
1896   }
1897 
1898   LuminosityBlockNumber_t IndexIntoFile::IndexIntoFileItrEntryOrder::peekAheadAtLumi() const {
1899     if (indexToLumi() == invalidIndex)
1900       return invalidLumi;
1901     return runOrLumisEntry(indexToLumi()).lumi();
1902   }
1903 
1904   IndexIntoFile::EntryNumber_t IndexIntoFile::IndexIntoFileItrEntryOrder::peekAheadAtEventEntry() const {
1905     if (indexToLumi() == invalidIndex)
1906       return invalidEntry;
1907     if (indexToEvent() >= nEvents())
1908       return invalidEntry;
1909     return runOrLumisEntry(indexToEventRange()).beginEvents() + indexToEvent();
1910   }
1911 
1912   void IndexIntoFile::IndexIntoFileItrEntryOrder::initializeLumi_() {
1913     assert(indexToLumi() != invalidIndex);
1914 
1915     setIndexToEventRange(invalidIndex);
1916     setIndexToEvent(0);
1917     setNEvents(0);
1918 
1919     for (int index = indexToLumi(); index < indexedSize(); ++index) {
1920       if (runOrLumisEntry(index).isRun()) {
1921         break;
1922       } else if (runOrLumisEntry(index).lumi() == runOrLumisEntry(indexToLumi()).lumi()) {
1923         if (runOrLumisEntry(index).beginEvents() == invalidEntry || !shouldProcessEvents(index)) {
1924           continue;
1925         }
1926         setIndexToEventRange(index);
1927         setIndexToEvent(0);
1928         setNEvents(runOrLumisEntry(indexToEventRange()).endEvents() -
1929                    runOrLumisEntry(indexToEventRange()).beginEvents());
1930         break;
1931       } else {
1932         break;
1933       }
1934     }
1935   }
1936 
1937   bool IndexIntoFile::IndexIntoFileItrEntryOrder::nextEventRange() {
1938     if (indexToEventRange() == invalidIndex)
1939       return false;
1940 
1941     // Look for the next event range, same lumi but different entry
1942     for (int index = indexToEventRange() + 1; index < indexedSize(); ++index) {
1943       if (runOrLumisEntry(index).isRun()) {
1944         return false;  // hit next run
1945       } else if (runOrLumisEntry(index).lumi() == runOrLumisEntry(indexToEventRange()).lumi()) {
1946         if (runOrLumisEntry(index).beginEvents() == invalidEntry || !shouldProcessEvents(index)) {
1947           continue;  // same lumi but has no events, keep looking
1948         }
1949         setIndexToEventRange(index);
1950         setIndexToEvent(0);
1951         setNEvents(runOrLumisEntry(indexToEventRange()).endEvents() -
1952                    runOrLumisEntry(indexToEventRange()).beginEvents());
1953         return true;  // found more events in this lumi
1954       }
1955       return false;  // hit next lumi
1956     }
1957     return false;  // hit the end of the IndexIntoFile
1958   }
1959 
1960   bool IndexIntoFile::IndexIntoFileItrEntryOrder::previousEventRange() {
1961     if (indexToEventRange() == invalidIndex)
1962       return false;
1963     assert(indexToEventRange() < indexedSize());
1964 
1965     // Look backward for a previous event range with events, same lumi but different entry
1966     for (int newRange = indexToEventRange() - 1; newRange > 0; --newRange) {
1967       if (runOrLumisEntry(newRange).isRun()) {
1968         return false;  // hit run
1969       } else if (isSameLumi(newRange, indexToEventRange())) {
1970         if (runOrLumisEntry(newRange).beginEvents() == invalidEntry || !shouldProcessEvents(newRange)) {
1971           continue;  // same lumi but has no events, keep looking
1972         }
1973         setIndexToEventRange(newRange);
1974         setNEvents(runOrLumisEntry(indexToEventRange()).endEvents() -
1975                    runOrLumisEntry(indexToEventRange()).beginEvents());
1976         setIndexToEvent(nEvents() - 1);
1977         return true;  // found previous event in this lumi
1978       }
1979       return false;  // hit previous lumi
1980     }
1981     return false;  // hit the beginning of the IndexIntoFile, 0th entry has to be a run
1982   }
1983 
1984   bool IndexIntoFile::IndexIntoFileItrEntryOrder::setToLastEventInRange(int index) {
1985     if (runOrLumisEntry(index).beginEvents() == invalidEntry || !shouldProcessEvents(index)) {
1986       return false;
1987     }
1988     setIndexToEventRange(index);
1989     setNEvents(runOrLumisEntry(indexToEventRange()).endEvents() - runOrLumisEntry(indexToEventRange()).beginEvents());
1990     assert(nEvents() > 0);
1991     setIndexToEvent(nEvents() - 1);
1992     return true;
1993   }
1994 
1995   bool IndexIntoFile::IndexIntoFileItrEntryOrder::skipLumiInRun() {
1996     if (indexToLumi() == invalidIndex)
1997       return false;
1998     for (int i = 1; indexToLumi() + i < indexedSize(); ++i) {
1999       int newLumi = indexToLumi() + i;
2000       if (runOrLumisEntry(newLumi).isRun()) {
2001         return false;  // hit next run
2002       } else if (runOrLumisEntry(newLumi).lumi() == runOrLumisEntry(indexToLumi()).lumi()) {
2003         continue;
2004       }
2005       setIndexToLumi(newLumi);
2006       initializeLumi();
2007       return true;  // hit next lumi
2008     }
2009     return false;  // hit the end of the IndexIntoFile
2010   }
2011 
2012   bool IndexIntoFile::IndexIntoFileItrEntryOrder::lumiIterationStartingIndex(int index) const {
2013     assert(index >= 0 && index < indexedSize());
2014     auto entry = runOrLumisEntry(index).entry();
2015     if (entry == invalidEntry) {
2016       // Usually the starting index is just the first one with a valid lumi TTree entry
2017       // number. If there aren't any that are valid, then use the last one.
2018       if (index + 1 < indexedSize()) {
2019         if (runOrLumisEntry(index).lumi() != runOrLumisEntry(index + 1).lumi()) {
2020           return true;
2021         }
2022       } else if (index + 1 == indexedSize()) {
2023         return true;
2024       }
2025     }
2026     return entry != invalidEntry;
2027   }
2028 
2029   IndexIntoFile::EntryType IndexIntoFile::IndexIntoFileItrEntryOrder::getRunOrLumiEntryType(int index) const {
2030     if (index < 0 || index >= indexedSize()) {
2031       return kEnd;
2032     } else if (runOrLumisEntry(index).isRun()) {
2033       return kRun;
2034     }
2035     return kLumi;
2036   }
2037 
2038   bool IndexIntoFile::IndexIntoFileItrEntryOrder::isSameLumi(int index1, int index2) const {
2039     if (index1 < 0 || index1 >= indexedSize() || index2 < 0 || index2 >= indexedSize()) {
2040       return false;
2041     }
2042     return runOrLumisEntry(index1).lumi() == runOrLumisEntry(index2).lumi();
2043   }
2044 
2045   bool IndexIntoFile::IndexIntoFileItrEntryOrder::isSameRun(int index1, int index2) const {
2046     if (index1 < 0 || index1 >= indexedSize() || index2 < 0 || index2 >= indexedSize()) {
2047       return false;
2048     }
2049     return runOrLumisEntry(index1).run() == runOrLumisEntry(index2).run() &&
2050            runOrLumisEntry(index1).processHistoryIDIndex() == runOrLumisEntry(index2).processHistoryIDIndex();
2051   }
2052 
2053   LuminosityBlockNumber_t IndexIntoFile::IndexIntoFileItrEntryOrder::lumi(int index) const {
2054     if (index < 0 || index >= indexedSize()) {
2055       return invalidLumi;
2056     }
2057     return runOrLumisEntry(index).lumi();
2058   }
2059 
2060   void IndexIntoFile::IndexIntoFileItrEntryOrder::EntryOrderInitializationInfo::resizeVectors(
2061       std::vector<RunOrLumiEntry> const& runOrLumiEntries) {
2062     // The value in orderPHIDRun_ is unique to each run and corresponds
2063     // to a unique pair of values of run number and ProcessHistoryID.
2064     // It's incremented by one each time a new run is added to the
2065     // IndexIntoFile so that makes it convenient and efficient for
2066     // indexing elements in a vector with an element per run.
2067     // It is also convenient to use when comparing two runs
2068     // to see if they are the same run.
2069     // Analogous things are true for orderPHIDRunLumi_ except
2070     // that the lumi number is also used and it identifies lumis
2071     // instead of runs in IndexIntoFile.
2072 
2073     EntryNumber_t maxOrderPHIDRun = invalidEntry;
2074     EntryNumber_t maxOrderPHIDRunLumi = invalidEntry;
2075     unsigned int nSize = 0;
2076 
2077     for (auto const& runOrLumiEntry : runOrLumiEntries) {
2078       assert(runOrLumiEntry.orderPHIDRun() >= 0);
2079       if (runOrLumiEntry.orderPHIDRun() > maxOrderPHIDRun) {
2080         maxOrderPHIDRun = runOrLumiEntry.orderPHIDRun();
2081       }
2082       if (!runOrLumiEntry.isRun()) {
2083         assert(runOrLumiEntry.orderPHIDRunLumi() >= 0);
2084         if (runOrLumiEntry.orderPHIDRunLumi() > maxOrderPHIDRunLumi) {
2085           maxOrderPHIDRunLumi = runOrLumiEntry.orderPHIDRunLumi();
2086         }
2087       }
2088       if (runOrLumiEntry.beginEvents() != invalidEntry) {
2089         // Count entries with events
2090         ++nSize;
2091       }
2092     }
2093     firstIndexOfRun_.resize(maxOrderPHIDRun + 1, invalidIndex);
2094     firstIndexOfLumi_.resize(maxOrderPHIDRunLumi + 1, invalidIndex);
2095     startOfLastContiguousEventsInRun_.resize(maxOrderPHIDRun + 1, invalidIndex);
2096     startOfLastContiguousEventsInLumi_.resize(maxOrderPHIDRunLumi + 1, invalidIndex);
2097     indexesSortedByEventEntry_.reserve(nSize);
2098   }
2099 
2100   void IndexIntoFile::IndexIntoFileItrEntryOrder::EntryOrderInitializationInfo::gatherNeededInfo(
2101       std::vector<RunOrLumiEntry> const& runOrLumiEntries) {
2102     int iEnd = static_cast<int>(runOrLumiEntries.size());
2103 
2104     EntryNumber_t previousLumi = invalidEntry;
2105     EntryNumber_t previousRun = invalidEntry;
2106     int index = 0;
2107 
2108     for (auto const& runOrLumiEntry : runOrLumiEntries) {
2109       // If first entry for a lumi
2110       if (!runOrLumiEntry.isRun() && runOrLumiEntry.orderPHIDRunLumi() != previousLumi) {
2111         previousLumi = runOrLumiEntry.orderPHIDRunLumi();
2112 
2113         // Fill map holding the first index into runOrLumiEntries for each lum
2114         firstIndexOfLumi_[runOrLumiEntry.orderPHIDRunLumi()] = index;
2115       }
2116 
2117       // If first entry for a run
2118       if (runOrLumiEntry.orderPHIDRun() != previousRun) {
2119         previousRun = runOrLumiEntry.orderPHIDRun();
2120 
2121         // Fill map holding the first index into runOrLumiEntries for each run
2122         firstIndexOfRun_[runOrLumiEntry.orderPHIDRun()] = index;
2123 
2124         // Look ahead to see if the run has events or not
2125         bool runHasEvents = false;
2126         for (int indexWithinRun = index + 1;
2127              indexWithinRun < iEnd && runOrLumiEntries[indexWithinRun].orderPHIDRun() == runOrLumiEntry.orderPHIDRun();
2128              ++indexWithinRun) {
2129           if (runOrLumiEntries[indexWithinRun].beginEvents() != invalidEntry) {
2130             runHasEvents = true;
2131             break;
2132           }
2133         }
2134         if (!runHasEvents) {
2135           runsWithNoEvents_.push_back({runOrLumiEntry.entry(), index});
2136         }
2137       }
2138       ++index;
2139     }
2140 
2141     std::sort(runsWithNoEvents_.begin(),
2142               runsWithNoEvents_.end(),
2143               [](TTreeEntryAndIndex const& left, TTreeEntryAndIndex const& right) -> bool {
2144                 return left.ttreeEntry_ < right.ttreeEntry_;
2145               });
2146 
2147     nextRunWithNoEvents_ = runsWithNoEvents_.cbegin();
2148     endRunsWithNoEvents_ = runsWithNoEvents_.cend();
2149   }
2150 
2151   void IndexIntoFile::IndexIntoFileItrEntryOrder::EntryOrderInitializationInfo::fillIndexesSortedByEventEntry(
2152       std::vector<RunOrLumiEntry> const& runOrLumiEntries) {
2153     int index = 0;
2154     for (auto const& runOrLumiEntry : runOrLumiEntries) {
2155       if (runOrLumiEntry.beginEvents() != invalidEntry) {
2156         indexesSortedByEventEntry_.push_back({runOrLumiEntry.beginEvents(), index});
2157       }
2158       ++index;
2159     }
2160 
2161     std::sort(indexesSortedByEventEntry_.begin(),
2162               indexesSortedByEventEntry_.end(),
2163               [](TTreeEntryAndIndex const& left, TTreeEntryAndIndex const& right) -> bool {
2164                 return left.ttreeEntry_ < right.ttreeEntry_;
2165               });
2166 
2167     // The next "for loop" is just a sanity check, it should always pass.
2168     int previousIndex = invalidIndex;
2169     for (auto const& eventSequence : indexesSortedByEventEntry_) {
2170       int currentIndex = eventSequence.runOrLumiIndex_;
2171       if (previousIndex != invalidIndex) {
2172         assert(runOrLumiEntries[previousIndex].endEvents() == runOrLumiEntries[currentIndex].beginEvents());
2173       }
2174       previousIndex = currentIndex;
2175     }
2176   }
2177 
2178   void IndexIntoFile::IndexIntoFileItrEntryOrder::EntryOrderInitializationInfo::fillIndexesToLastContiguousEvents(
2179       std::vector<RunOrLumiEntry> const& runOrLumiEntries) {
2180     EntryNumber_t previousRun = invalidEntry;
2181     EntryNumber_t previousLumi = invalidEntry;
2182     for (auto const& iter : indexesSortedByEventEntry_) {
2183       auto currentRun = runOrLumiEntries[iter.runOrLumiIndex_].orderPHIDRun();
2184       if (currentRun != previousRun) {
2185         startOfLastContiguousEventsInRun_[currentRun] = iter.runOrLumiIndex_;
2186         previousRun = currentRun;
2187       }
2188       auto currentLumi = runOrLumiEntries[iter.runOrLumiIndex_].orderPHIDRunLumi();
2189       if (currentLumi != previousLumi) {
2190         startOfLastContiguousEventsInLumi_[currentLumi] = iter.runOrLumiIndex_;
2191         previousLumi = currentLumi;
2192       }
2193     }
2194   }
2195 
2196   void IndexIntoFile::IndexIntoFileItrEntryOrder::addRunsWithNoEvents(EntryOrderInitializationInfo& info,
2197                                                                       EntryNumber_t maxRunTTreeEntry) {
2198     auto const& runOrLumiEntries = indexIntoFile()->runOrLumiEntries();
2199 
2200     for (auto& nextRunWithNoEvents = info.nextRunWithNoEvents_;
2201          nextRunWithNoEvents != info.endRunsWithNoEvents_ &&
2202          (maxRunTTreeEntry == invalidEntry || nextRunWithNoEvents->ttreeEntry_ < maxRunTTreeEntry);
2203          ++nextRunWithNoEvents) {
2204       int index = nextRunWithNoEvents->runOrLumiIndex_;
2205       EntryNumber_t runToAdd = runOrLumiEntries[index].orderPHIDRun();
2206       for (int iEnd = static_cast<int>(runOrLumiEntries.size());
2207            index < iEnd && runOrLumiEntries[index].orderPHIDRun() == runToAdd;
2208            ++index) {
2209         // This will add in Run entries and the entries of Lumis in those Runs
2210         addToFileOrder(index, true, false);
2211       }
2212     }
2213   }
2214 
2215   void IndexIntoFile::IndexIntoFileItrEntryOrder::fillLumisWithNoRemainingEvents(
2216       std::vector<TTreeEntryAndIndex>& lumisWithNoRemainingEvents,
2217       int startingIndex,
2218       EntryNumber_t currentRun,
2219       RunOrLumiEntry const* eventSequenceRunOrLumiEntry) const {
2220     auto const& runOrLumiEntries = indexIntoFile()->runOrLumiEntries();
2221     int iEnd = static_cast<int>(runOrLumiEntries.size());
2222 
2223     // start at the first entry after the Run entries
2224     // iterate over all the lumi entries in this Run
2225     // The outer loop iterates over lumis and inner loop iterates over entries in each lumi
2226     for (int indexOfLumiEntry = startingIndex;
2227          indexOfLumiEntry < iEnd && runOrLumiEntries[indexOfLumiEntry].orderPHIDRun() == currentRun;) {
2228       auto currentLumiIndex = indexOfLumiEntry;
2229       auto const& currentLumiEntry = runOrLumiEntries[currentLumiIndex];
2230       assert(!currentLumiEntry.isRun());
2231       auto currentLumi = currentLumiEntry.orderPHIDRunLumi();
2232 
2233       bool foundUnprocessedEvents = false;
2234       EntryNumber_t minLumiTTreeEntry = invalidEntry;
2235       // iterate over the lumi entries associated with a single lumi
2236       for (; indexOfLumiEntry < iEnd && runOrLumiEntries[indexOfLumiEntry].orderPHIDRunLumi() == currentLumi;
2237            ++indexOfLumiEntry) {
2238         if (runOrLumiEntries[indexOfLumiEntry].beginEvents() >= eventSequenceRunOrLumiEntry->beginEvents()) {
2239           foundUnprocessedEvents = true;
2240         }
2241         // Find the smallest valid Lumi TTree entry for this lumi
2242         auto lumiTTreeEntry = runOrLumiEntries[indexOfLumiEntry].entry();
2243         if (lumiTTreeEntry != invalidEntry &&
2244             (minLumiTTreeEntry == invalidEntry || lumiTTreeEntry < minLumiTTreeEntry)) {
2245           minLumiTTreeEntry = lumiTTreeEntry;
2246         }
2247       }
2248       // No event sequences left to process and at least one valid lumi TTree entry.
2249       if (!foundUnprocessedEvents && minLumiTTreeEntry != invalidEntry) {
2250         lumisWithNoRemainingEvents.push_back({minLumiTTreeEntry, currentLumiIndex});
2251       }
2252     }
2253 
2254     std::sort(lumisWithNoRemainingEvents.begin(),
2255               lumisWithNoRemainingEvents.end(),
2256               [](TTreeEntryAndIndex const& left, TTreeEntryAndIndex const& right) -> bool {
2257                 return left.ttreeEntry_ < right.ttreeEntry_;
2258               });
2259   }
2260 
2261   void IndexIntoFile::IndexIntoFileItrEntryOrder::reserveSpaceInVectors(
2262       std::vector<EntryNumber_t>::size_type sizeToReserve) {
2263     // Reserve some space. Most likely this is not big enough, but better than reserving nothing.
2264     fileOrderRunOrLumiEntry_.reserve(sizeToReserve);
2265     shouldProcessRunOrLumi_.reserve(sizeToReserve);
2266     shouldProcessEvents_.reserve(sizeToReserve);
2267   }
2268 
2269   void IndexIntoFile::IndexIntoFileItrEntryOrder::addToFileOrder(int index, bool processRunOrLumi, bool processEvents) {
2270     fileOrderRunOrLumiEntry_.push_back(index);
2271     shouldProcessRunOrLumi_.push_back(processRunOrLumi);
2272     shouldProcessEvents_.push_back(processEvents);
2273   }
2274 
2275   void IndexIntoFile::IndexIntoFileItrEntryOrder::handleToEndOfContiguousEventsInRun(EntryOrderInitializationInfo& info,
2276                                                                                      EntryNumber_t currentRun) {
2277     auto const& runOrLumiEntries = indexIntoFile()->runOrLumiEntries();
2278     int iEnd = static_cast<int>(runOrLumiEntries.size());
2279 
2280     int indexOfRunEntry = info.firstIndexOfRun_[currentRun];
2281 
2282     // Event entries are put in the exact same order as in the Events TTree.
2283     // We make some effort to make the Runs and Lumis come out in Run TTree
2284     // order and Lumi TTree order, but that is often not possible.
2285 
2286     // If it is the last contiguous sequence of events for the Run, also
2287     // add ALL entries corresponding to valid Run or Lumi TTree entries for
2288     // this Run. This is the place where the Run and Lumi products will get
2289     // processed and merged, ALL of them for this run whether or not they have
2290     // events in this particular subsequence of events. This forces all the Run
2291     // and Lumi product merging to occur the first time a file is read.
2292     if (info.startOfLastContiguousEventsInRun_[currentRun] == info.eventSequenceIndex_) {
2293       // Add runs with no events that have an earlier Run TTree entry number
2294       addRunsWithNoEvents(info, runOrLumiEntries[indexOfRunEntry].entry());
2295 
2296       // Add all valid run entries associated with the event sequence
2297       for (; indexOfRunEntry < iEnd && runOrLumiEntries[indexOfRunEntry].isRun(); ++indexOfRunEntry) {
2298         assert(runOrLumiEntries[indexOfRunEntry].orderPHIDRun() == currentRun);
2299         addToFileOrder(indexOfRunEntry, true, false);
2300       }
2301 
2302       // Add all lumi entries associated with this run
2303       handleToEndOfContiguousEventsInLumis(info, currentRun, indexOfRunEntry);
2304 
2305     } else {
2306       // Add only the first run entry and flag it to be not processed yet.
2307       addToFileOrder(indexOfRunEntry, false, false);
2308 
2309       // Add the minimum number of lumi entries so that the events they reference
2310       // will be processed in the correct order, lumis are not to be processed.
2311       // The lumis will be added again later to be processed.
2312       while (info.iEventSequence_ != info.iEventSequenceEnd_ &&
2313              info.eventSequenceRunOrLumiEntry_->orderPHIDRun() == currentRun) {
2314         addToFileOrder(info.eventSequenceIndex_, false, true);
2315         info.nextEventSequence(runOrLumiEntries);
2316       }
2317     }
2318   }
2319 
2320   void IndexIntoFile::IndexIntoFileItrEntryOrder::handleToEndOfContiguousEventsInLumis(
2321       EntryOrderInitializationInfo& info, EntryNumber_t currentRun, int endOfRunEntries) {
2322     // Form a list of lumis that have no more events left to be processed and are in the current
2323     // run and have at least one valid Lumi TTree entry. Contains the index to the first
2324     // lumi entry and its TTree entry number, sorted by earliest lumi TTree entry number.
2325     std::vector<TTreeEntryAndIndex> lumisWithNoRemainingEvents;
2326     fillLumisWithNoRemainingEvents(
2327         lumisWithNoRemainingEvents, endOfRunEntries, currentRun, info.eventSequenceRunOrLumiEntry_);
2328     auto nextLumiWithNoEvents = lumisWithNoRemainingEvents.cbegin();
2329     auto endLumisWithNoEvents = lumisWithNoRemainingEvents.cend();
2330 
2331     // On each step of this iteration we process all the events in a contiguous sequence of events
2332     // from a single lumi (these are events that haven't already been processed and are contained
2333     // within the last contiguous sequence of events from the containing run).
2334     while (info.iEventSequence_ < info.iEventSequenceEnd_ &&
2335            info.eventSequenceRunOrLumiEntry_->orderPHIDRun() == currentRun) {
2336       auto currentLumi = info.eventSequenceRunOrLumiEntry_->orderPHIDRunLumi();
2337 
2338       // Last contiguous sequence of events in lumi
2339       if (info.startOfLastContiguousEventsInLumi_[currentLumi] == info.eventSequenceIndex_) {
2340         auto firstBeginEventsContiguousLumi = info.eventSequenceRunOrLumiEntry_->beginEvents();
2341         // Find the first Lumi TTree entry number for this Lumi
2342         EntryNumber_t lumiTTreeEntryNumber = lowestInLumi(info, currentLumi);
2343 
2344         // In addition, we want lumis before this in the lumi tree if they have no events
2345         // left to be processed
2346         handleLumisWithNoEvents(nextLumiWithNoEvents, endLumisWithNoEvents, lumiTTreeEntryNumber);
2347 
2348         // Handle the lumi with the next sequence of events to process
2349         handleLumiWithEvents(info, currentLumi, firstBeginEventsContiguousLumi);
2350 
2351       } else {
2352         // not last contiguous event sequence for lumi
2353         while (info.iEventSequence_ < info.iEventSequenceEnd_ &&
2354                info.eventSequenceRunOrLumiEntry_->orderPHIDRunLumi() == currentLumi) {
2355           addToFileOrder(info.eventSequenceIndex_, false, true);
2356           info.nextEventSequence(indexIntoFile()->runOrLumiEntries());
2357         }
2358       }
2359     }
2360     handleLumisWithNoEvents(nextLumiWithNoEvents, endLumisWithNoEvents, invalidEntry, true);
2361   }
2362 
2363   IndexIntoFile::EntryNumber_t IndexIntoFile::IndexIntoFileItrEntryOrder::lowestInLumi(
2364       EntryOrderInitializationInfo& info, int currentLumi) const {
2365     auto const& runOrLumiEntries = indexIntoFile()->runOrLumiEntries();
2366     int iEnd = static_cast<int>(runOrLumiEntries.size());
2367 
2368     for (int iLumiIndex = info.firstIndexOfLumi_[currentLumi];
2369          iLumiIndex < iEnd && runOrLumiEntries[iLumiIndex].orderPHIDRunLumi() == currentLumi;
2370          ++iLumiIndex) {
2371       EntryNumber_t lumiTTreeEntryNumber = runOrLumiEntries[iLumiIndex].entry();
2372       if (lumiTTreeEntryNumber != invalidEntry) {
2373         // First valid one is the lowest because of the sort order of the container
2374         return lumiTTreeEntryNumber;
2375       }
2376     }
2377     return invalidEntry;
2378   }
2379 
2380   void IndexIntoFile::IndexIntoFileItrEntryOrder::handleLumisWithNoEvents(
2381       std::vector<TTreeEntryAndIndex>::const_iterator& nextLumiWithNoEvents,
2382       std::vector<TTreeEntryAndIndex>::const_iterator& endLumisWithNoEvents,
2383       EntryNumber_t lumiTTreeEntryNumber,
2384       bool completeAll) {
2385     auto const& runOrLumiEntries = indexIntoFile()->runOrLumiEntries();
2386     int iEnd = static_cast<int>(runOrLumiEntries.size());
2387 
2388     for (; nextLumiWithNoEvents < endLumisWithNoEvents &&
2389            (completeAll || nextLumiWithNoEvents->ttreeEntry_ < lumiTTreeEntryNumber);
2390          ++nextLumiWithNoEvents) {
2391       int iLumiIndex = nextLumiWithNoEvents->runOrLumiIndex_;
2392       auto orderPHIDRunLumi = runOrLumiEntries[iLumiIndex].orderPHIDRunLumi();
2393       for (; iLumiIndex < iEnd && runOrLumiEntries[iLumiIndex].orderPHIDRunLumi() == orderPHIDRunLumi; ++iLumiIndex) {
2394         if (runOrLumiEntries[iLumiIndex].entry() != invalidEntry) {
2395           addToFileOrder(iLumiIndex, true, false);
2396         }
2397       }
2398     }
2399   }
2400 
2401   void IndexIntoFile::IndexIntoFileItrEntryOrder::handleLumiWithEvents(EntryOrderInitializationInfo& info,
2402                                                                        int currentLumi,
2403                                                                        EntryNumber_t firstBeginEventsContiguousLumi) {
2404     auto const& runOrLumiEntries = indexIntoFile()->runOrLumiEntries();
2405     int iLumiIndex = info.firstIndexOfLumi_[currentLumi];
2406     while (info.iEventSequence_ < info.iEventSequenceEnd_ &&
2407            info.eventSequenceRunOrLumiEntry_->orderPHIDRunLumi() == currentLumi) {
2408       // lumi entries for the currentLumi with no remaining Events to process and
2409       // with Lumi TTree entry numbers less than the Lumi TTree entry for the next
2410       // sequence of Events.
2411       handleLumiEntriesNoRemainingEvents(info, iLumiIndex, currentLumi, firstBeginEventsContiguousLumi);
2412 
2413       // Add entry with the next event sequence
2414       bool shouldProcessLumi = runOrLumiEntries[info.eventSequenceIndex_].entry() != invalidEntry;
2415       addToFileOrder(info.eventSequenceIndex_, shouldProcessLumi, true);
2416       info.nextEventSequence(runOrLumiEntries);
2417     }
2418     handleLumiEntriesNoRemainingEvents(info, iLumiIndex, currentLumi, firstBeginEventsContiguousLumi, true);
2419   }
2420 
2421   void IndexIntoFile::IndexIntoFileItrEntryOrder::handleLumiEntriesNoRemainingEvents(
2422       EntryOrderInitializationInfo& info,
2423       int& iLumiIndex,
2424       int currentLumi,
2425       EntryNumber_t firstBeginEventsContiguousLumi,
2426       bool completeAll) {
2427     auto const& runOrLumiEntries = indexIntoFile()->runOrLumiEntries();
2428     int iEnd = static_cast<int>(runOrLumiEntries.size());
2429 
2430     for (; iLumiIndex < iEnd && runOrLumiEntries[iLumiIndex].orderPHIDRunLumi() == currentLumi &&
2431            (completeAll || runOrLumiEntries[iLumiIndex].entry() < info.eventSequenceRunOrLumiEntry_->entry());
2432          ++iLumiIndex) {
2433       if (runOrLumiEntries[iLumiIndex].entry() == invalidEntry ||
2434           runOrLumiEntries[iLumiIndex].beginEvents() >= firstBeginEventsContiguousLumi) {
2435         continue;
2436       }
2437       addToFileOrder(iLumiIndex, true, false);
2438     }
2439   }
2440 
2441   //*************************************
2442 
2443   IndexIntoFile::IndexIntoFileItr::IndexIntoFileItr(IndexIntoFile const* indexIntoFile,
2444                                                     SortOrder sortOrder,
2445                                                     EntryType entryType,
2446                                                     int indexToRun,
2447                                                     int indexToLumi,
2448                                                     int indexToEventRange,
2449                                                     long long indexToEvent,
2450                                                     long long nEvents)
2451       : impl_() {
2452     if (sortOrder == numericalOrder) {
2453       value_ptr<IndexIntoFileItrImpl> temp(new IndexIntoFileItrSorted(
2454           indexIntoFile, entryType, indexToRun, indexToLumi, indexToEventRange, indexToEvent, nEvents));
2455       swap(temp, impl_);
2456     } else if (sortOrder == firstAppearanceOrder) {
2457       value_ptr<IndexIntoFileItrImpl> temp(new IndexIntoFileItrNoSort(
2458           indexIntoFile, entryType, indexToRun, indexToLumi, indexToEventRange, indexToEvent, nEvents));
2459       swap(temp, impl_);
2460     } else {
2461       value_ptr<IndexIntoFileItrImpl> temp(new IndexIntoFileItrEntryOrder(
2462           indexIntoFile, entryType, indexToRun, indexToLumi, indexToEventRange, indexToEvent, nEvents));
2463       swap(temp, impl_);
2464     }
2465   }
2466 
2467   void IndexIntoFile::IndexIntoFileItr::advanceToEvent() {
2468     for (EntryType entryType = getEntryType(); entryType != kEnd && entryType != kEvent; entryType = getEntryType()) {
2469       impl_->next();
2470     }
2471   }
2472 
2473   void IndexIntoFile::IndexIntoFileItr::advanceToLumi() {
2474     for (EntryType entryType = getEntryType(); entryType != kEnd && entryType != kLumi; entryType = getEntryType()) {
2475       impl_->next();
2476     }
2477   }
2478 
2479   void IndexIntoFile::IndexIntoFileItr::copyPosition(IndexIntoFileItr const& position) {
2480     impl_->copyPosition(*position.impl_);
2481   }
2482 
2483   bool Compare_Index_Run::operator()(IndexIntoFile::RunOrLumiIndexes const& lh,
2484                                      IndexIntoFile::RunOrLumiIndexes const& rh) {
2485     if (lh.processHistoryIDIndex() == rh.processHistoryIDIndex()) {
2486       return lh.run() < rh.run();
2487     }
2488     return lh.processHistoryIDIndex() < rh.processHistoryIDIndex();
2489   }
2490 
2491   bool Compare_Index::operator()(IndexIntoFile::RunOrLumiIndexes const& lh, IndexIntoFile::RunOrLumiIndexes const& rh) {
2492     return lh.processHistoryIDIndex() < rh.processHistoryIDIndex();
2493   }
2494 }  // namespace edm