Back to home page

Project CMSSW displayed by LXR

 
 

    


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

0001 #ifndef DataFormats_Provenance_IndexIntoFile_h
0002 #define DataFormats_Provenance_IndexIntoFile_h
0003 
0004 /** \class edm::IndexIntoFile
0005 
0006 Used to quickly find the Events, Lumis, and Runs in a single
0007 ROOT format data file and step through them in the desired
0008 order.
0009 
0010 A list of the most important functions that a client would
0011 use directly follows. There are detailed comments below with
0012 the declaration of each function.
0013 
0014 The begin and end functions are used to start and stop
0015 an iteration loop. An argument to the iterator constructor
0016 determines the order of iteration.
0017 
0018 The functions findPosition, findEventPosition, findRunPosition,
0019 and findLumiPosition are used to navigate directly to specific
0020 runs, lumis, and events.
0021 
0022 The functions mentioned above return an object of type
0023 IndexIntoFileItr.  The IndexIntoFileItr class has member
0024 functions which allow one to navigate forward and backward
0025 through the runs, lumis, and events in alternative ways.
0026 See more comments with the declaration of each public member
0027 function in IndexIntoFileItr.
0028 
0029 The iterator  will know what the current item is (as one
0030 would expect).  This could be a run, lumi, or event. It
0031 knows more than that though, it knows all three as is
0032 explained below.
0033 
0034 In the run state, IndexIntoFileItr knows which lumi will
0035 be processed next after the run and also which event will
0036 be processed after the lumi.  These may not be the first
0037 ones in the run if the skip functions were used.
0038 
0039 In the lumi state, the IndexIntoFileItr will always point
0040 at the last associated run and the next event to be processed
0041 after the lumi.  This may not be the first event if the skip
0042 function was used.
0043 
0044 In the event state, the IndexIntoFileItr will always point
0045 at the last corresponding run and also the last corresponding
0046 lumi.
0047 
0048 There can be multiple run entries in a TTree associated
0049 with the same run number and ProcessHistoryID in a file.
0050 There can also be multiple lumi entries associated with
0051 the same lumi number, run number, and ProcessHistoryID.
0052 The sorting orders identified as numericalOrder and
0053 firstAppearanceOrder will make these subgroups contiguous,
0054 but beyond that is up to the client (normally PoolSource,
0055 which passes them up to the EventProcessor)
0056 to deal with merging the multiple run (or lumi) entries
0057 together.
0058 
0059 In entryOrder, the Events are processed in the order they
0060 appear in the Events TTree. The event entries associated
0061 with a run might not be contiguous. The event entries associated
0062 with a lumi might not be contiguous. Even so, the iteration
0063 order will always follow the pattern run followed by contained
0064 lumis followed by contained events (note it's possible
0065 there are no contained events for a lumi or no contained
0066 lumis for a run). Because the events are not contiguous,
0067 this leads to run or lumi entries appearing more than once
0068 in the iteration (once for each contained contiguous sequence
0069 of events plus possibly one additional time near the end
0070 for the run or lumi to be processed and merged, although this
0071 might or might not occur with the last contiguous sequence
0072 of events). The iterator is designed to automatically step to
0073 each event once, even when it points at the same RunOrLumiEntry
0074 with the same events more than once in the iteration. The client
0075 does not need to do anything special related to events. On the
0076 other hand, the client (usually PoolSource, which passes the
0077 value into the Principal) needs to check the iterator functions
0078 named shouldProcessLumi or shouldProcessRun to determine whether
0079 a lumi or run is being encountered more than once. Those functions
0080 will return true only once. At that time, run or lumi products
0081 are read, possibly merged, and written to output. When those
0082 functions return false, transitions still occur but products
0083 are not read, merged or written. If a module attempts to get
0084 run or lumi products in those transitions, there will be a
0085 "ProductNotFound" exception or invalid Handle. In general,
0086 getting run or lumi products from events does not work with
0087 the EntryOrder iterator type.
0088 
0089 One final comment with regards to IndexIntoFileItr.  This
0090 is not an STL iterator and it cannot be used with std::
0091 algorithms.  The data structures are complex and designed
0092 to optimize memory usage. It would be difficult or impossible
0093 implement an iterator that is STL compliant.
0094 
0095 Here is a summary of the data structures in IndexIntoFile.
0096 The persistent data consists of two vectors.
0097 
0098 processHistoryIDs_ is a std::vector<ProcessHistoryID> that
0099 contains the ProcessHistoryIDs with one element in the
0100 vector for each unique ProcessHistoryID. On output they
0101 are ordered as they first written out for each output
0102 file.  On input they are ordered as they are first seen
0103 in each process. Note that each ProcessHistoryID is stored
0104 once in this separate vector. Everywhere else it is needed
0105 it stored as an index into this vector because the
0106 ProcessHistoryID itself is large and it would take more
0107 memory to store them repeatedly in the other vectors.
0108 Note that the ProcessHistoryID's referenced in this
0109 class are always the "reduced" ProcessHistoryID's,
0110 not the ProcessHistoryID of the full ProcessHistory.
0111 You cannot use them to directly access the ProcessHistory
0112 from the ProcessHistoryRegistry.
0113 
0114 runOrLumiEntries_ is a std::vector<RunOrLumiEntry>.
0115 This vector holds one element per entry in the run
0116 TTree and one element per entry in the lumi TTree.
0117 When sorted, everything associated with a given run and
0118 ProcessHistoryID will be contiguous in the vector.
0119 These groups of elements will be sorted by an OutputModule
0120 in the order they first appear when an Event, Lumi or Run
0121 is written to output (close to input order but because of
0122 concurrency it might not be exactly the same). Within each of
0123 these groups the run entries come first in order,
0124 followed by the elements associated with the lumis.
0125 The lumis are also contiguous and sorted by first
0126 appearance by the output module in a way similar to runs.
0127 Within a lumi they are sorted by entry order. And each
0128 luminosity element corresponds to one contiguous sequence
0129 of Events in the Events TTree. Before we implemented
0130 concurrent processing of luminosity blocks that
0131 was the full story. After that it became more complicated
0132 because the sequence of events written to an output
0133 file that were associated with a particular luminosity
0134 block TTree entry might no longer be contiguous. Events
0135 from another concurrent luminosity block could get
0136 mixed in because with multiple events processing simultaneously,
0137 there is no longer any guarantee they will finish in the
0138 same order that they were read. This is handled by writing
0139 additional elements to the runOrLumiEntries_ vector, one for
0140 each contiguous block of events associated with a particular
0141 luminosity block. Only one of these vector elements will
0142 be associated with each entry in the luminosity block TTree
0143 and all the others will contain a TTree entry number that
0144 is invalid (note the one element with a valid entry might
0145 or might not be associated with a contiguous block of
0146 events). In the sort of elements related to a particular
0147 luminosity block, the entries with invalid entry numbers
0148 will come before the valid ones.
0149 
0150 There are a number of transient data members also.
0151 The 3 most important of these are vectors.  To
0152 save memory, these are only filled when needed.
0153 
0154 runOrLumiIndexes_ is a std::vector<RunOrLumiIndexes>.
0155 There is a one to one correspondence between the
0156 elements of this vector and the elements of runOrLumiEntries_.
0157 The elements of this vector are sorted in numerical
0158 order using the ProcessHistoryID index, the run number,
0159 and the lumi number. This ordering allows iteration
0160 in numerical order and also fast lookup based on run
0161 number and lumi number. Each element also has indexes
0162 into the eventNumbers_ and eventEntries_ vectors which
0163 hold the information giving the event numbers and
0164 event entry numbers. Note this vector is initially
0165 formed in the identical order as runOrLumiEntries_
0166 and then sorted with a stable sort. The fact that it
0167 is a stable sort means that within the subrange associated
0168 with a particular luminosity block the elements with
0169 an invalid TTree entry number come first and the later
0170 come the elements with a valid TTree entry number
0171 which are in order of TTree entry number.
0172 
0173 eventNumbers_ is a std::vector containing EventNumber_t's.
0174 eventEntries_ is a std::vector containing EventEntry's.
0175 If filled, both vectors contain the same number of
0176 entries with identical event numbers sorted in the
0177 same order.  The only difference is that one includes
0178 the entry numbers and thus takes more memory.
0179 Each element of runOrLumiIndexes_ associated with a luminosity
0180 block has the indexes necessary to find the range inside
0181 eventNumbers_ or eventEntries_ corresponding to its lumi.
0182 Within that range the elements are sorted by event number,
0183 which is used for the numerical order iteration and to
0184 find an event by the event number.
0185 
0186 The details of the data structure are a little different
0187 when reading files written before release 3_8_0
0188 (backward compatibility, see RootFile::fillIndexIntoFile
0189 for the details).
0190 
0191 This data structure is optimized for low memory usage when
0192 there are large numbers of events.  The optimal case would
0193 occur when there was was one run in a file, one luminosity block
0194 in that run and everything had the same ProcessHistoryID.
0195 If duplicate checking were off and the process simply iterated
0196 through the file in the default order, then only the persistent
0197 vectors would be filled.  One vector would contain 2 elements,
0198 one for the run and the other for the lumi. The other
0199 vector would contain one element, the ProcessHistoryID.
0200 Even if there were a billion events, that would be all that
0201 would exist and take up memory.  The data structure is not the
0202 optimal structure for a very sparse skim, but the overheads
0203 should be tolerable given the number of runs and luminosity
0204 blocks that should occur in CMS data.
0205 
0206 Normally only the persistent parts of the data structure are
0207 filled in the output module. The output module fills them using
0208 two functions designed specifically for that purpose. The
0209 functions are addEntry and sortVector_Run_Or_Lumi_Entries.
0210 
0211 There are some complexities associated with filling the data structure,
0212 mostly revolving around optimizations to minimize the per event memory
0213 usage.  The client needs to know which parts of the data structure to
0214 fill. See the functions below named fixIndexes, setNumberOfEvents,
0215 setEventFinder, fillEventNumbers, fillEventEntries, and inputFileClosed.
0216 
0217 Note that this class is not intended to be used directly by the average
0218 CMS user.  PoolSource and PoolOutputModule are the main clients.  Other
0219 executables that read ROOT format data files, but do not use PoolSource
0220 may also need to use it directly (FWLite, Fireworks, edmFileUtil ...).
0221 The interface is too complex for general use.
0222 
0223 \author W. David Dagenhart, created 19 May, 2010
0224 
0225 */
0226 
0227 #include "DataFormats/Provenance/interface/EventID.h"
0228 #include "DataFormats/Provenance/interface/ProcessHistoryID.h"
0229 #include "DataFormats/Provenance/interface/RunID.h"
0230 #include "DataFormats/Provenance/interface/RunLumiEventNumber.h"
0231 #include "FWCore/Utilities/interface/propagate_const.h"
0232 #include "FWCore/Utilities/interface/value_ptr.h"
0233 #include "FWCore/Utilities/interface/thread_safety_macros.h"
0234 
0235 #include <memory>
0236 
0237 #include <cassert>
0238 #include <iosfwd>
0239 #include <map>
0240 #include <set>
0241 #include <vector>
0242 
0243 class TestIndexIntoFile;
0244 class TestIndexIntoFile1;
0245 class TestIndexIntoFile2;
0246 class TestIndexIntoFile3;
0247 class TestIndexIntoFile4;
0248 class TestIndexIntoFile5;
0249 
0250 namespace edm {
0251 
0252   class ProcessHistoryRegistry;
0253   class RootFile;
0254 
0255   class IndexIntoFile {
0256   public:
0257     class IndexIntoFileItr;
0258     class SortedRunOrLumiItr;
0259     class IndexRunLumiEventKey;
0260 
0261     using EntryNumber_t = long long;
0262     static constexpr int invalidIndex = -1;
0263     static constexpr RunNumber_t invalidRun = 0U;
0264     static constexpr LuminosityBlockNumber_t invalidLumi = 0U;
0265     static constexpr EventNumber_t invalidEvent = 0U;
0266     static constexpr EntryNumber_t invalidEntry = -1LL;
0267 
0268     enum EntryType { kRun, kLumi, kEvent, kEnd };
0269 
0270     IndexIntoFile();
0271     ~IndexIntoFile();
0272 
0273     ProcessHistoryID const& processHistoryID(int i) const;
0274     std::vector<ProcessHistoryID> const& processHistoryIDs() const;
0275 
0276     /// This enum is used to specify the order of iteration.
0277     /// In firstAppearanceOrder there are 3 sort criteria, in order of precedence these are:
0278     ///
0279     ///   1. firstAppearance of the ProcessHistoryID and run number in the Events TTree of
0280     ///   the file (in cases where there are no Events in a run it depends on the order
0281     ///   of the call to writeRun or writeLumi in the preceding step where the IndexIntoFile
0282     ///   was created)
0283     ///
0284     ///   2. firstAppearance of the ProcessHistoryID, run number and lumi number in the Events
0285     ///   TTree of the file (in cases where there are no Events in a lumi it depends on the
0286     ///   order of the call to writeRun or writeLumi in the preceding step where the IndexIntoFile
0287     ///   was created)
0288     ///
0289     ///   3. entry number
0290     ///
0291     /// In numerical order the criteria are in order of precedence are:
0292     ///
0293     ///   1. processHistoryID index (which are normally in order of appearance in the output module)
0294     ///
0295     ///   2. run number
0296     ///
0297     ///   3. lumi number
0298     ///
0299     ///   4. event number
0300     ///
0301     ///   5. entry number
0302     ///
0303     /// In entryOrder the order of iteration is as follows:
0304     ///
0305     ///   1. Events are processed in the exact order they appear in the
0306     ///   input Events TTree. (The main purpose of this order is to allow
0307     ///   fast cloning of the input Events TTree to the output Events TTree.)
0308     ///
0309     ///   2. Runs and Lumis will show up around events so that the pattern
0310     ///   run, then contained lumi(s), then contained event(s) is always followed,
0311     ////  but because events from a run (or lumi) may not be contiguous a particular
0312     ///   run entry or lumi entry may appear multiple times in this ordering. Each
0313     ///   Run entry or lumi entry will appear once with the function shouldProcessRun
0314     ///   or shouldProcessLumi returning true. The client (usually PoolSource) must
0315     ///   notice when these return false and not read or process them multiple times.
0316     ///
0317     ///   3. All runs and lumis associated with a run should be processed
0318     ///   when the last contiguous sequence of events for that run is processed.
0319     ///   If a run has no events, then it is interspersed within that sequence
0320     ///   of runs according to its run TTree entry number.
0321     ///
0322     ///   4. Within a run, lumis should be processed when the last contiguous
0323     ///   subsequence of events from that lumi is processed. If there are
0324     ///   no events from a lumi in the last contiguous sequence of events
0325     ///   from the run, then the lumis are interspersed within the sequence
0326     ///   of lumis from that run in order of lumi TTree entry number.
0327     ///
0328     ///   Note that the ordering above will allow the client (usually PoolSource)
0329     ///   to merge all run entries associated with a single run and merge all lumi
0330     ///   entries associated with a single lumi the first time an input file is
0331     ///   read. This is the same as in the other two orderings.
0332 
0333     enum SortOrder { numericalOrder, firstAppearanceOrder, entryOrder };
0334 
0335     /// Used to start an iteration over the Runs, Lumis, and Events in a file.
0336     /// Note the argument specifies the order
0337     IndexIntoFileItr begin(SortOrder sortOrder) const;
0338 
0339     /// Used to end an iteration over the Runs, Lumis, and Events in a file.
0340     IndexIntoFileItr end(SortOrder sortOrder) const;
0341 
0342     /// Used to determine whether or not to disable fast cloning.
0343     bool iterationWillBeInEntryOrder(SortOrder sortOrder) const;
0344 
0345     /// True if no runs, lumis, or events are in the file.
0346     bool empty() const;
0347 
0348     /// Find a run, lumi, or event.
0349     /// Returns an iterator pointing at it. The iterator will always
0350     /// be in numericalOrder mode.
0351     /// If it is not found the entry type of the iterator will be kEnd.
0352     /// If it is found the entry type of the iterator will always be
0353     /// kRun so the next thing to be processed is the run containing
0354     /// the desired lumi or event or if looking for a run, the run itself.
0355     /// If the lumi and event arguments are 0 (invalid), then it will
0356     /// find a run. If only the event argument is 0 (invalid), then
0357     /// it will find a lumi. If will look for an event if all three
0358     /// arguments are nonzero or if only the lumi argument is 0 (invalid).
0359     /// Note that it will find the first match only so if there is more
0360     /// than one match then the others cannot be found with this method.
0361     /// The order of the search is by processHistoryID index, then run
0362     /// number, then lumi number, then event entry.
0363     /// If searching for a lumi the iterator will advance directly
0364     /// to the desired lumi after the run even if it is not the
0365     /// first lumi in the run.  If searching for an event, the
0366     /// iterator will advance to the lumi containing the run and
0367     /// then the requested event after run even if there are other
0368     /// lumis earlier in that run and other events earlier in that lumi.
0369     IndexIntoFileItr findPosition(RunNumber_t run, LuminosityBlockNumber_t lumi = 0U, EventNumber_t event = 0U) const;
0370 
0371     IndexIntoFileItr findPosition(SortOrder sortOrder,
0372                                   RunNumber_t run,
0373                                   LuminosityBlockNumber_t lumi = 0U,
0374                                   EventNumber_t event = 0U) const;
0375 
0376     /// Same as findPosition,except the entry type of the returned iterator will be kEvent or kEnd and the event argument must be nonzero.
0377     /// This means the next thing to be processed will be the event if it is found.
0378     IndexIntoFileItr findEventPosition(RunNumber_t run, LuminosityBlockNumber_t lumi, EventNumber_t event) const;
0379 
0380     /// Same as findPosition,except the entry type of the returned iterator will be kLumi or kEnd and the lumi argument must be nonzero.
0381     /// This means the next thing to be processed will be the lumi if it is found.
0382     IndexIntoFileItr findLumiPosition(RunNumber_t run, LuminosityBlockNumber_t lumi) const;
0383 
0384     /// Same as findPosition.
0385     IndexIntoFileItr findRunPosition(RunNumber_t run) const;
0386 
0387     bool containsItem(RunNumber_t run, LuminosityBlockNumber_t lumi, EventNumber_t event) const;
0388     bool containsEvent(RunNumber_t run, LuminosityBlockNumber_t lumi, EventNumber_t event) const;
0389     bool containsLumi(RunNumber_t run, LuminosityBlockNumber_t lumi) const;
0390     bool containsRun(RunNumber_t run) const;
0391 
0392     SortedRunOrLumiItr beginRunOrLumi() const;
0393     SortedRunOrLumiItr endRunOrLumi() const;
0394 
0395     /// The intersection argument will be filled with an entry for each event in both IndexIntoFile objects.
0396     /// To be added the event must have the same ProcessHistoryID index, run number, lumi number and event number.
0397     void set_intersection(IndexIntoFile const& indexIntoFile, std::set<IndexRunLumiEventKey>& intersection) const;
0398 
0399     /// Returns true if the IndexIntoFile contains 2 events with the same ProcessHistoryID index, run number, lumi number and event number.
0400     bool containsDuplicateEvents() const;
0401 
0402     //*****************************************************************************
0403     //*****************************************************************************
0404 
0405     class RunOrLumiEntry {
0406     public:
0407       RunOrLumiEntry();
0408 
0409       RunOrLumiEntry(EntryNumber_t orderPHIDRun,
0410                      EntryNumber_t orderPHIDRunLumi,
0411                      EntryNumber_t entry,
0412                      int processHistoryIDIndex,
0413                      RunNumber_t run,
0414                      LuminosityBlockNumber_t lumi,
0415                      EntryNumber_t beginEvents,
0416                      EntryNumber_t Event);
0417 
0418       EntryNumber_t orderPHIDRun() const { return orderPHIDRun_; }
0419       EntryNumber_t orderPHIDRunLumi() const { return orderPHIDRunLumi_; }
0420       EntryNumber_t entry() const { return entry_; }
0421       int processHistoryIDIndex() const { return processHistoryIDIndex_; }
0422       RunNumber_t run() const { return run_; }
0423       LuminosityBlockNumber_t lumi() const { return lumi_; }
0424       EntryNumber_t beginEvents() const { return beginEvents_; }
0425       EntryNumber_t endEvents() const { return endEvents_; }
0426 
0427       bool isRun() const { return lumi() == invalidLumi; }
0428 
0429       void setOrderPHIDRun(EntryNumber_t v) { orderPHIDRun_ = v; }
0430       void setOrderPHIDRunLumi(EntryNumber_t v) { orderPHIDRunLumi_ = v; }
0431       void setProcessHistoryIDIndex(int v) { processHistoryIDIndex_ = v; }
0432 
0433       bool operator<(RunOrLumiEntry const& right) const {
0434         if (orderPHIDRun_ == right.orderPHIDRun()) {
0435           if (orderPHIDRunLumi_ == right.orderPHIDRunLumi()) {
0436             return entry_ < right.entry();
0437           }
0438           return orderPHIDRunLumi_ < right.orderPHIDRunLumi();
0439         }
0440         return orderPHIDRun_ < right.orderPHIDRun();
0441       }
0442 
0443     private:
0444       // All Runs, Lumis, and Events associated with the same
0445       // ProcessHistory and Run in the same input file are processed
0446       // contiguously.  This parameter establishes the default order
0447       // of processing of these contiguous subsets of data.
0448       EntryNumber_t orderPHIDRun_;
0449 
0450       // All Lumis and Events associated with the same
0451       // ProcessHistory, Run, and Lumi in the same input file are
0452       // processed contiguously.  This parameter establishes the
0453       // default order of processing of these contiguous subsets
0454       // of data.
0455       EntryNumber_t orderPHIDRunLumi_;  // -1 if a run
0456 
0457       // TTree entry number of Run or Lumi
0458       // Always will be valid except when the IndexIntoFile was
0459       // created while processing more than 1 luminosity block
0460       // at a time (multiple concurrent lumis). In that case
0461       // there can be multiple contiguous event ranges associated
0462       // with the same lumi TTree entry. Exactly one of those will
0463       // have a valid entry_ number and the rest will be set
0464       // to the invalid value (-1). For a particular lumi, the
0465       // invalid ones sort before the valid ones.
0466       EntryNumber_t entry_;
0467 
0468       int processHistoryIDIndex_;
0469       RunNumber_t run_;
0470       LuminosityBlockNumber_t lumi_;  // 0 indicates this is a run entry
0471 
0472       // These are entry numbers in the Events TTree
0473       // Each RunOrLumiEntry is associated with one contiguous range of events.
0474       // This is disjoint from the ranges associated with all other RunOrLumiEntry's
0475       EntryNumber_t beginEvents_;  // -1 if a run or a lumi with no events
0476       EntryNumber_t endEvents_;    // -1 if a run or a lumi with no events
0477     };
0478 
0479     //*****************************************************************************
0480     //*****************************************************************************
0481 
0482     class RunOrLumiIndexes {
0483     public:
0484       RunOrLumiIndexes(int processHistoryIDIndex, RunNumber_t run, LuminosityBlockNumber_t lumi, int indexToGetEntry);
0485 
0486       int processHistoryIDIndex() const { return processHistoryIDIndex_; }
0487       RunNumber_t run() const { return run_; }
0488       LuminosityBlockNumber_t lumi() const { return lumi_; }
0489       int indexToGetEntry() const { return indexToGetEntry_; }
0490       long long beginEventNumbers() const { return beginEventNumbers_; }
0491       long long endEventNumbers() const { return endEventNumbers_; }
0492 
0493       bool isRun() const { return lumi() == invalidLumi; }
0494 
0495       void setBeginEventNumbers(long long v) { beginEventNumbers_ = v; }
0496       void setEndEventNumbers(long long v) { endEventNumbers_ = v; }
0497 
0498       bool operator<(RunOrLumiIndexes const& right) const {
0499         if (processHistoryIDIndex_ == right.processHistoryIDIndex()) {
0500           if (run_ == right.run()) {
0501             return lumi_ < right.lumi();
0502           }
0503           return run_ < right.run();
0504         }
0505         return processHistoryIDIndex_ < right.processHistoryIDIndex();
0506       }
0507 
0508     private:
0509       int processHistoryIDIndex_;
0510       RunNumber_t run_;
0511       LuminosityBlockNumber_t lumi_;  // 0 indicates this is a run entry
0512       int indexToGetEntry_;
0513 
0514       // The next two data members are indexes into the vectors eventNumbers_ and
0515       // eventEntries_ (which both have the same number of entries in the same order,
0516       // the only difference being that one contains only events numbers and is
0517       // smaller in memory).
0518 
0519       // If there are no events, then the next two are equal (and the value is the
0520       // index where the first event would have gone if there had been one)
0521 
0522       // Note that there can be many RunOrLumiIndexes objects where these two values are
0523       // the same if there are many noncontiguous ranges of events associated with the same
0524       // PHID-Run-Lumi (this one range in eventNumbers_ corresponds to the union of
0525       // all the noncontiguous ranges in the Events TTree).
0526       long long beginEventNumbers_;  // first event this PHID-Run-Lumi (-1 if a run or not set)
0527       long long endEventNumbers_;    // one past last event this PHID-Run-Lumi (-1 if a run or not set)
0528     };
0529 
0530     //*****************************************************************************
0531     //*****************************************************************************
0532 
0533     class EventEntry {
0534     public:
0535       EventEntry() : event_(invalidEvent), entry_(invalidEntry) {}
0536       EventEntry(EventNumber_t event, EntryNumber_t entry) : event_(event), entry_(entry) {}
0537 
0538       EventNumber_t event() const { return event_; }
0539       EntryNumber_t entry() const { return entry_; }
0540 
0541       bool operator<(EventEntry const& right) const { return event() < right.event(); }
0542 
0543       bool operator==(EventEntry const& right) const { return event() == right.event(); }
0544 
0545     private:
0546       EventNumber_t event_;
0547       EntryNumber_t entry_;
0548     };
0549 
0550     //*****************************************************************************
0551     //*****************************************************************************
0552 
0553     class SortedRunOrLumiItr {
0554     public:
0555       SortedRunOrLumiItr(IndexIntoFile const* indexIntoFile, unsigned runOrLumi);
0556 
0557       IndexIntoFile const* indexIntoFile() const { return indexIntoFile_; }
0558       unsigned runOrLumi() const { return runOrLumi_; }
0559 
0560       bool operator==(SortedRunOrLumiItr const& right) const;
0561       bool operator!=(SortedRunOrLumiItr const& right) const;
0562       SortedRunOrLumiItr& operator++();
0563 
0564       bool isRun();
0565 
0566       void getRange(long long& beginEventNumbers,
0567                     long long& endEventNumbers,
0568                     EntryNumber_t& beginEventEntry,
0569                     EntryNumber_t& endEventEntry);
0570 
0571       RunOrLumiIndexes const& runOrLumiIndexes() const;
0572 
0573     private:
0574       IndexIntoFile const* indexIntoFile_;
0575 
0576       // This is an index into runOrLumiIndexes_
0577       // which gives the current position of the iteration
0578       unsigned runOrLumi_;
0579     };
0580 
0581     //*****************************************************************************
0582     //*****************************************************************************
0583 
0584     class IndexIntoFileItrImpl {
0585     public:
0586       IndexIntoFileItrImpl(IndexIntoFile const* indexIntoFile,
0587                            EntryType entryType,
0588                            int indexToRun,
0589                            int indexToLumi,
0590                            int indexToEventRange,
0591                            long long indexToEvent,
0592                            long long nEvents);
0593       virtual ~IndexIntoFileItrImpl();
0594 
0595       virtual IndexIntoFileItrImpl* clone() const = 0;
0596 
0597       EntryType getEntryType() const { return type_; }
0598 
0599       void next();
0600 
0601       void skipEventForward(int& phIndexOfSkippedEvent,
0602                             RunNumber_t& runOfSkippedEvent,
0603                             LuminosityBlockNumber_t& lumiOfSkippedEvent,
0604                             EntryNumber_t& skippedEventEntry);
0605 
0606       void skipEventBackward(int& phIndexOfEvent,
0607                              RunNumber_t& runOfEvent,
0608                              LuminosityBlockNumber_t& lumiOfEvent,
0609                              EntryNumber_t& eventEntry);
0610 
0611       virtual int processHistoryIDIndex() const = 0;
0612       virtual RunNumber_t run() const = 0;
0613       virtual LuminosityBlockNumber_t lumi() const = 0;
0614       virtual EntryNumber_t entry() const = 0;
0615       virtual bool shouldProcessLumi() const = 0;
0616       virtual bool shouldProcessRun() const = 0;
0617       virtual LuminosityBlockNumber_t peekAheadAtLumi() const = 0;
0618       virtual EntryNumber_t peekAheadAtEventEntry() const = 0;
0619       EntryNumber_t firstEventEntryThisRun();
0620       EntryNumber_t firstEventEntryThisLumi();
0621       virtual bool skipLumiInRun() = 0;
0622       virtual bool lumiIterationStartingIndex(int index) const = 0;
0623 
0624       void advanceToNextRun();
0625       void advanceToNextLumiOrRun();
0626       bool skipToNextEventInLumi();
0627       void initializeRun();
0628 
0629       void initializeLumi();
0630 
0631       bool operator==(IndexIntoFileItrImpl const& right) const;
0632 
0633       IndexIntoFile const* indexIntoFile() const { return indexIntoFile_; }
0634 
0635       // runOrLumiEntries_ and runOrLumiIndexes_ have the same size. It
0636       // is returned by the function size(). There are iterator data members
0637       // that are indexes into a container. The iterators also need the size of that
0638       // container and the function indexedSize() returns it. For the NoSort and
0639       // Sorted derived iterator classes, those indexes point directly into
0640       // runOrLumiEntries_ or runOrLumiIndexes_ and therefore return the same
0641       // value as size(). The indexes in the EntryOrder iterator class point into
0642       // a larger container and indexedSize() is overridden to give the size of
0643       // that container.
0644       int size() const { return size_; }
0645       virtual int indexedSize() const;
0646 
0647       EntryType type() const { return type_; }
0648       int indexToRun() const { return indexToRun_; }
0649 
0650       int indexToLumi() const { return indexToLumi_; }
0651       int indexToEventRange() const { return indexToEventRange_; }
0652       long long indexToEvent() const { return indexToEvent_; }
0653       long long nEvents() const { return nEvents_; }
0654 
0655       void copyPosition(IndexIntoFileItrImpl const& position);
0656 
0657       void getLumisInRun(std::vector<LuminosityBlockNumber_t>& lumis) const;
0658 
0659     protected:
0660       void setInvalid();
0661 
0662       void setIndexToLumi(int value) { indexToLumi_ = value; }
0663       void setIndexToEventRange(int value) { indexToEventRange_ = value; }
0664       void setIndexToEvent(long long value) { indexToEvent_ = value; }
0665       void setNEvents(long long value) { nEvents_ = value; }
0666 
0667     private:
0668       virtual void initializeLumi_() = 0;
0669       virtual bool nextEventRange() = 0;
0670       virtual bool previousEventRange() = 0;
0671       bool previousLumiWithEvents();
0672       virtual bool setToLastEventInRange(int index) = 0;
0673       virtual EntryType getRunOrLumiEntryType(int index) const = 0;
0674       virtual bool isSameLumi(int index1, int index2) const = 0;
0675       virtual bool isSameRun(int index1, int index2) const = 0;
0676       virtual LuminosityBlockNumber_t lumi(int index) const = 0;
0677 
0678       IndexIntoFile const* indexIntoFile_;
0679       int size_;
0680 
0681       EntryType type_;
0682       int indexToRun_;
0683       int indexToLumi_;
0684       int indexToEventRange_;
0685       long long indexToEvent_;
0686       long long nEvents_;
0687     };
0688 
0689     //*****************************************************************************
0690     //*****************************************************************************
0691 
0692     class IndexIntoFileItrNoSort : public IndexIntoFileItrImpl {
0693     public:
0694       IndexIntoFileItrNoSort(IndexIntoFile const* indexIntoFile,
0695                              EntryType entryType,
0696                              int indexToRun,
0697                              int indexToLumi,
0698                              int indexToEventRange,
0699                              long long indexToEvent,
0700                              long long nEvents);
0701 
0702       IndexIntoFileItrImpl* clone() const override;
0703 
0704       int processHistoryIDIndex() const override;
0705       RunNumber_t run() const override;
0706       LuminosityBlockNumber_t lumi() const override;
0707       EntryNumber_t entry() const override;
0708       bool shouldProcessLumi() const final { return true; }
0709       bool shouldProcessRun() const final { return true; }
0710       LuminosityBlockNumber_t peekAheadAtLumi() const override;
0711       EntryNumber_t peekAheadAtEventEntry() const override;
0712       bool skipLumiInRun() override;
0713       bool lumiIterationStartingIndex(int index) const override;
0714 
0715     private:
0716       void initializeLumi_() override;
0717       bool nextEventRange() override;
0718       bool previousEventRange() override;
0719       bool setToLastEventInRange(int index) override;
0720       EntryType getRunOrLumiEntryType(int index) const override;
0721       bool isSameLumi(int index1, int index2) const override;
0722       bool isSameRun(int index1, int index2) const override;
0723       LuminosityBlockNumber_t lumi(int index) const override;
0724     };
0725 
0726     //*****************************************************************************
0727     //*****************************************************************************
0728 
0729     class IndexIntoFileItrSorted : public IndexIntoFileItrImpl {
0730     public:
0731       IndexIntoFileItrSorted(IndexIntoFile const* indexIntoFile,
0732                              EntryType entryType,
0733                              int indexToRun,
0734                              int indexToLumi,
0735                              int indexToEventRange,
0736                              long long indexToEvent,
0737                              long long nEvents);
0738 
0739       IndexIntoFileItrImpl* clone() const override;
0740       int processHistoryIDIndex() const override;
0741       RunNumber_t run() const override;
0742       LuminosityBlockNumber_t lumi() const override;
0743       EntryNumber_t entry() const override;
0744       bool shouldProcessLumi() const final { return true; }
0745       bool shouldProcessRun() const final { return true; }
0746       LuminosityBlockNumber_t peekAheadAtLumi() const override;
0747       EntryNumber_t peekAheadAtEventEntry() const override;
0748       bool skipLumiInRun() override;
0749       bool lumiIterationStartingIndex(int index) const override;
0750 
0751     private:
0752       void initializeLumi_() override;
0753       bool nextEventRange() override;
0754       bool previousEventRange() override;
0755       bool setToLastEventInRange(int index) override;
0756       EntryType getRunOrLumiEntryType(int index) const override;
0757       bool isSameLumi(int index1, int index2) const override;
0758       bool isSameRun(int index1, int index2) const override;
0759       LuminosityBlockNumber_t lumi(int index) const override;
0760     };
0761 
0762     //*****************************************************************************
0763     //*****************************************************************************
0764 
0765     class IndexIntoFileItrEntryOrder : public IndexIntoFileItrImpl {
0766     public:
0767       IndexIntoFileItrEntryOrder(IndexIntoFile const* indexIntoFile,
0768                                  EntryType entryType,
0769                                  int indexToRun,
0770                                  int indexToLumi,
0771                                  int indexToEventRange,
0772                                  long long indexToEvent,
0773                                  long long nEvents);
0774 
0775       IndexIntoFileItrImpl* clone() const override;
0776       int processHistoryIDIndex() const override;
0777       RunNumber_t run() const override;
0778       LuminosityBlockNumber_t lumi() const override;
0779       EntryNumber_t entry() const override;
0780       bool shouldProcessLumi() const final;
0781       bool shouldProcessRun() const final;
0782       LuminosityBlockNumber_t peekAheadAtLumi() const override;
0783       EntryNumber_t peekAheadAtEventEntry() const override;
0784       bool skipLumiInRun() override;
0785       bool lumiIterationStartingIndex(int index) const override;
0786       int indexedSize() const override { return indexedSize_; }
0787 
0788     private:
0789       // Note the argument to the function runOrLumisEntry is NOT a
0790       // direct index into the vector in IndexIntoFile! It returns a
0791       // reference to an object from that vector. However, the argument
0792       // to runOrLumisEntry is an index into fileOrderRunOrLumiEntry_
0793       // which reorders the elements so the iteration is in event TTree
0794       // entry order. It also adds in dummy entries to insert
0795       // the extra run and lumi transitions required for that ordering.
0796 
0797       RunOrLumiEntry const& runOrLumisEntry(EntryNumber_t iEntry) const {
0798         return indexIntoFile()->runOrLumiEntries()[fileOrderRunOrLumiEntry_[iEntry]];
0799       }
0800       bool shouldProcessRunOrLumi(EntryNumber_t iEntry) const { return shouldProcessRunOrLumi_[iEntry]; }
0801       bool shouldProcessEvents(EntryNumber_t iEntry) const { return shouldProcessEvents_[iEntry]; }
0802       void initializeLumi_() override;
0803       bool nextEventRange() override;
0804       bool previousEventRange() override;
0805       bool setToLastEventInRange(int index) override;
0806       EntryType getRunOrLumiEntryType(int index) const override;
0807       bool isSameLumi(int index1, int index2) const override;
0808       bool isSameRun(int index1, int index2) const override;
0809       LuminosityBlockNumber_t lumi(int index) const override;
0810 
0811       struct TTreeEntryAndIndex {
0812         IndexIntoFile::EntryNumber_t ttreeEntry_;
0813         int runOrLumiIndex_;
0814       };
0815 
0816       class EntryOrderInitializationInfo {
0817       public:
0818         void resizeVectors(std::vector<RunOrLumiEntry> const&);
0819         void gatherNeededInfo(std::vector<RunOrLumiEntry> const&);
0820         void fillIndexesSortedByEventEntry(std::vector<RunOrLumiEntry> const&);
0821         void fillIndexesToLastContiguousEvents(std::vector<RunOrLumiEntry> const&);
0822 
0823         // Contains information only needed in the constructor of IndexIntoFileItrEntryOrder
0824         std::vector<int> firstIndexOfRun_;
0825         std::vector<int> firstIndexOfLumi_;
0826         std::vector<int> startOfLastContiguousEventsInRun_;
0827         std::vector<int> startOfLastContiguousEventsInLumi_;
0828 
0829         // Will contain indexes of lumi entries with events and will be
0830         // sorted by first Event TTree entry number.
0831         std::vector<TTreeEntryAndIndex> indexesSortedByEventEntry_;
0832         std::vector<TTreeEntryAndIndex>::const_iterator iEventSequence_;
0833         std::vector<TTreeEntryAndIndex>::const_iterator iEventSequenceEnd_;
0834         int eventSequenceIndex_ = 0;
0835         RunOrLumiEntry const* eventSequenceRunOrLumiEntry_ = nullptr;
0836 
0837         void nextEventSequence(std::vector<RunOrLumiEntry> const& runOrLumiEntries) {
0838           ++iEventSequence_;
0839           if (iEventSequence_ < iEventSequenceEnd_) {
0840             eventSequenceIndex_ = iEventSequence_->runOrLumiIndex_;
0841             eventSequenceRunOrLumiEntry_ = &runOrLumiEntries[eventSequenceIndex_];
0842           }
0843         }
0844 
0845         // Holds the index to the first entry associated with each run with no events
0846         // Sorted by the first run TTree entry number
0847         std::vector<TTreeEntryAndIndex> runsWithNoEvents_;
0848         std::vector<TTreeEntryAndIndex>::const_iterator nextRunWithNoEvents_;
0849         std::vector<TTreeEntryAndIndex>::const_iterator endRunsWithNoEvents_;
0850       };
0851 
0852       void addRunsWithNoEvents(EntryOrderInitializationInfo&, EntryNumber_t maxRunTTreeEntry = invalidEntry);
0853       void fillLumisWithNoRemainingEvents(std::vector<TTreeEntryAndIndex>& lumisWithNoRemainingEvents,
0854                                           int startingIndex,
0855                                           EntryNumber_t currentRun,
0856                                           RunOrLumiEntry const* eventSequenceRunOrLumiEntry) const;
0857       void reserveSpaceInVectors(std::vector<EntryNumber_t>::size_type);
0858       void addToFileOrder(int index, bool processRunOrLumi, bool processEvents);
0859       void handleToEndOfContiguousEventsInRun(EntryOrderInitializationInfo& info, EntryNumber_t currentRun);
0860       void handleToEndOfContiguousEventsInLumis(EntryOrderInitializationInfo& info,
0861                                                 EntryNumber_t currentRun,
0862                                                 int endOfRunEntries);
0863       EntryNumber_t lowestInLumi(EntryOrderInitializationInfo& info, int currentLumi) const;
0864       void handleLumisWithNoEvents(std::vector<TTreeEntryAndIndex>::const_iterator& nextLumiWithNoEvents,
0865                                    std::vector<TTreeEntryAndIndex>::const_iterator& endLumisWithNoEvents,
0866                                    EntryNumber_t lumiTTreeEntryNumber,
0867                                    bool completeAll = false);
0868       void handleLumiWithEvents(EntryOrderInitializationInfo& info,
0869                                 int currentLumi,
0870                                 EntryNumber_t firstBeginEventsContiguousLumi);
0871       void handleLumiEntriesNoRemainingEvents(EntryOrderInitializationInfo& info,
0872                                               int& iLumiIndex,
0873                                               int currentLumi,
0874                                               EntryNumber_t firstBeginEventsContiguousLumi,
0875                                               bool completeAll = false);
0876 
0877       int indexedSize_ = 0;
0878       std::vector<EntryNumber_t> fileOrderRunOrLumiEntry_;
0879       std::vector<bool> shouldProcessRunOrLumi_;
0880       std::vector<bool> shouldProcessEvents_;
0881     };
0882 
0883     //*****************************************************************************
0884     //*****************************************************************************
0885 
0886     class IndexIntoFileItr {
0887     public:
0888       /// This itended to be used only internally and by IndexIntoFile.
0889       /// One thing that is needed for the future, is to add some checks
0890       /// to make sure the iterator is in a valid state inside this constructor.
0891       /// It is currently possible to create an iterator with this constructor
0892       /// in an invalid state and the behavior would then be undefined. In the
0893       /// existing internal usages the iterator will always be valid.  (for
0894       /// example IndexIntoFile::begin and IndexIntoFile::findPosition will
0895       /// always return a valid iterator).
0896       IndexIntoFileItr(IndexIntoFile const* indexIntoFile,
0897                        SortOrder sortOrder,
0898                        EntryType entryType,
0899                        int indexToRun,
0900                        int indexToLumi,
0901                        int indexToEventRange,
0902                        long long indexToEvent,
0903                        long long nEvents);
0904 
0905       EntryType getEntryType() const { return impl_->getEntryType(); }
0906       int processHistoryIDIndex() const { return impl_->processHistoryIDIndex(); }
0907       RunNumber_t run() const { return impl_->run(); }
0908       LuminosityBlockNumber_t lumi() const { return impl_->lumi(); }
0909       EntryNumber_t entry() const { return impl_->entry(); }
0910       bool shouldProcessLumi() const { return impl_->shouldProcessLumi(); }
0911       bool shouldProcessRun() const { return impl_->shouldProcessRun(); }
0912       bool lumiIterationStartingIndex(int index) const { return impl_->lumiIterationStartingIndex(index); }
0913 
0914       /// Same as lumi() except when the the current type is kRun.
0915       /// In that case instead of always returning 0 (invalid), it will return the lumi that will be processed next
0916       LuminosityBlockNumber_t peekAheadAtLumi() const { return impl_->peekAheadAtLumi(); }
0917 
0918       /// Same as entry() except when the the current type is kRun or kLumi.
0919       /// In that case instead of always returning -1 (invalid), it will return
0920       /// the event entry that will be processed next and which is in the current
0921       /// run and lumi. If there is none it still returns -1 (invalid).
0922       EntryNumber_t peekAheadAtEventEntry() const { return impl_->peekAheadAtEventEntry(); }
0923 
0924       /// Returns the TTree entry of the first event which would be processed in the
0925       /// current run/lumi if all the events in the run/lumi were processed in the
0926       /// current processing order. If there are none it returns -1 (invalid).
0927       EntryNumber_t firstEventEntryThisRun() { return impl_->firstEventEntryThisRun(); }
0928       EntryNumber_t firstEventEntryThisLumi() { return impl_->firstEventEntryThisLumi(); }
0929 
0930       // This is intentionally not implemented.
0931       // It would be difficult to implement for the no sort mode,
0932       // either slow or using extra memory.
0933       // It would be easy to implement for the sorted iteration,
0934       // but I did not implement it so both cases would offer a
0935       // consistent interface.
0936       // It looks like in all cases where this would be needed
0937       // it would not be difficult to get the event number
0938       // directly from the event auxiliary.
0939       // We may need to revisit this decision in the future.
0940       // EventNumber_t event() const;
0941 
0942       /// Move to next event to be processed
0943       IndexIntoFileItr& operator++() {
0944         impl_->next();
0945         return *this;
0946       }
0947 
0948       /// Move to whatever is immediately after the current event
0949       /// or after the next event if there is not a current event,
0950       /// but do not modify the type or run/lumi
0951       /// indexes unless it is necessary because there
0952       /// are no more events in the current run or lumi.
0953       void skipEventForward(int& phIndexOfSkippedEvent,
0954                             RunNumber_t& runOfSkippedEvent,
0955                             LuminosityBlockNumber_t& lumiOfSkippedEvent,
0956                             EntryNumber_t& skippedEventEntry) {
0957         impl_->skipEventForward(phIndexOfSkippedEvent, runOfSkippedEvent, lumiOfSkippedEvent, skippedEventEntry);
0958       }
0959 
0960       /// Move so that the event immediately preceding the
0961       /// the current position is the next event processed.
0962       /// If the type is kEvent or kLumi, then change the type to kRun
0963       /// if and only if the preceding event is in a different
0964       /// run. If the type is kEvent, change the type to kLumi if
0965       /// the lumi is different but the run is the same.  Otherwise
0966       /// leave the type unchanged.
0967       void skipEventBackward(int& phIndexOfEvent,
0968                              RunNumber_t& runOfEvent,
0969                              LuminosityBlockNumber_t& lumiOfEvent,
0970                              EntryNumber_t& eventEntry) {
0971         impl_->skipEventBackward(phIndexOfEvent, runOfEvent, lumiOfEvent, eventEntry);
0972       }
0973 
0974       /// Move to the next lumi in the current run.
0975       /// Returns false if there is not one.
0976       bool skipLumiInRun() { return impl_->skipLumiInRun(); }
0977 
0978       /// Move to the next event in the current lumi.
0979       /// Returns false if there is not one.
0980       bool skipToNextEventInLumi() { return impl_->skipToNextEventInLumi(); }
0981 
0982       void advanceToNextRun() { impl_->advanceToNextRun(); }
0983       void advanceToNextLumiOrRun() { impl_->advanceToNextLumiOrRun(); }
0984 
0985       void advanceToEvent();
0986       void advanceToLumi();
0987 
0988       bool operator==(IndexIntoFileItr const& right) const { return *impl_ == *right.impl_; }
0989 
0990       bool operator!=(IndexIntoFileItr const& right) const { return !(*this == right); }
0991 
0992       /// Should only be used internally and for tests
0993       void initializeRun() { impl_->initializeRun(); }
0994 
0995       /// Should only be used internally and for tests
0996       void initializeLumi() { impl_->initializeLumi(); }
0997 
0998       /// Copy the position without modifying the pointer to the IndexIntoFile or size
0999       void copyPosition(IndexIntoFileItr const& position);
1000 
1001       void getLumisInRun(std::vector<LuminosityBlockNumber_t>& lumis) const { impl_->getLumisInRun(lumis); }
1002 
1003     private:
1004       //for testing
1005       friend class ::TestIndexIntoFile;
1006       friend class ::TestIndexIntoFile2;
1007       friend class ::TestIndexIntoFile3;
1008       friend class ::TestIndexIntoFile4;
1009       friend class ::TestIndexIntoFile5;
1010 
1011       // The rest of these are intended to be used only by code which tests
1012       // this class.
1013       IndexIntoFile const* indexIntoFile() const { return impl_->indexIntoFile(); }
1014       int size() const { return impl_->size(); }
1015       int indexedSize() const { return impl_->indexedSize(); }
1016       EntryType type() const { return impl_->type(); }
1017       int indexToRun() const { return impl_->indexToRun(); }
1018       int indexToLumi() const { return impl_->indexToLumi(); }
1019       int indexToEventRange() const { return impl_->indexToEventRange(); }
1020       long long indexToEvent() const { return impl_->indexToEvent(); }
1021       long long nEvents() const { return impl_->nEvents(); }
1022 
1023       value_ptr<IndexIntoFileItrImpl> impl_;
1024     };
1025 
1026     //*****************************************************************************
1027     //*****************************************************************************
1028 
1029     class IndexRunKey {
1030     public:
1031       IndexRunKey(int index, RunNumber_t run) : processHistoryIDIndex_(index), run_(run) {}
1032 
1033       int processHistoryIDIndex() const { return processHistoryIDIndex_; }
1034       RunNumber_t run() const { return run_; }
1035 
1036       bool operator<(IndexRunKey const& right) const {
1037         if (processHistoryIDIndex_ == right.processHistoryIDIndex()) {
1038           return run_ < right.run();
1039         }
1040         return processHistoryIDIndex_ < right.processHistoryIDIndex();
1041       }
1042 
1043     private:
1044       int processHistoryIDIndex_;
1045       RunNumber_t run_;
1046     };
1047 
1048     //*****************************************************************************
1049     //*****************************************************************************
1050 
1051     class IndexRunLumiKey {
1052     public:
1053       IndexRunLumiKey(int index, RunNumber_t run, LuminosityBlockNumber_t lumi)
1054           : processHistoryIDIndex_(index), run_(run), lumi_(lumi) {}
1055 
1056       int processHistoryIDIndex() const { return processHistoryIDIndex_; }
1057       RunNumber_t run() const { return run_; }
1058       LuminosityBlockNumber_t lumi() const { return lumi_; }
1059 
1060       bool operator<(IndexRunLumiKey const& right) const {
1061         if (processHistoryIDIndex_ == right.processHistoryIDIndex()) {
1062           if (run_ == right.run()) {
1063             return lumi_ < right.lumi();
1064           }
1065           return run_ < right.run();
1066         }
1067         return processHistoryIDIndex_ < right.processHistoryIDIndex();
1068       }
1069 
1070     private:
1071       int processHistoryIDIndex_;
1072       RunNumber_t run_;
1073       LuminosityBlockNumber_t lumi_;
1074     };
1075 
1076     //*****************************************************************************
1077     //*****************************************************************************
1078 
1079     class IndexRunLumiEventKey {
1080     public:
1081       IndexRunLumiEventKey(int index, RunNumber_t run, LuminosityBlockNumber_t lumi, EventNumber_t event)
1082           : processHistoryIDIndex_(index), run_(run), lumi_(lumi), event_(event) {}
1083 
1084       int processHistoryIDIndex() const { return processHistoryIDIndex_; }
1085       RunNumber_t run() const { return run_; }
1086       LuminosityBlockNumber_t lumi() const { return lumi_; }
1087       EventNumber_t event() const { return event_; }
1088 
1089       bool operator<(IndexRunLumiEventKey const& right) const {
1090         if (processHistoryIDIndex_ == right.processHistoryIDIndex()) {
1091           if (run_ == right.run()) {
1092             if (lumi_ == right.lumi()) {
1093               return event_ < right.event();
1094             }
1095             return lumi_ < right.lumi();
1096           }
1097           return run_ < right.run();
1098         }
1099         return processHistoryIDIndex_ < right.processHistoryIDIndex();
1100       }
1101 
1102     private:
1103       int processHistoryIDIndex_;
1104       RunNumber_t run_;
1105       LuminosityBlockNumber_t lumi_;
1106       EventNumber_t event_;
1107     };
1108 
1109     //*****************************************************************************
1110     //*****************************************************************************
1111 
1112     class EventFinder {
1113     public:
1114       virtual ~EventFinder() {}
1115       virtual EventNumber_t getEventNumberOfEntry(EntryNumber_t entry) const = 0;
1116     };
1117 
1118     //*****************************************************************************
1119     //*****************************************************************************
1120 
1121     // The next two functions are used by the output module to fill the
1122     // persistent data members.
1123 
1124     /// Used by RootOutputModule to fill the persistent data.
1125     /// This will not work properly if entries are not added in the same order as in RootOutputModule
1126     void addEntry(ProcessHistoryID const& processHistoryID,
1127                   RunNumber_t run,
1128                   LuminosityBlockNumber_t lumi,
1129                   EventNumber_t event,
1130                   EntryNumber_t entry);
1131 
1132     /// Used by RootOutputModule after all entries have been added.
1133     /// This only works after the correct sequence of addEntry calls,
1134     /// because it makes some corrections before sorting.  A std::stable_sort
1135     /// works in cases where those corrections are not needed.
1136     void sortVector_Run_Or_Lumi_Entries();
1137 
1138     /// Run this check just after sorting
1139     void checkForMissingRunOrLumiEntry() const;
1140 
1141     //used internally by addEntry
1142     void addLumi(int index, RunNumber_t run, LuminosityBlockNumber_t lumi, EntryNumber_t entry);
1143     //*****************************************************************************
1144     //*****************************************************************************
1145 
1146     // The next group of functions is used by the PoolSource (or other
1147     // input related code) to fill the IndexIntoFile.
1148 
1149     /// Used by PoolSource to force the ProcessHistoryID indexes to be consistent across all input files.
1150     /// Currently this consistency is important when duplicate checking across all input files.
1151     /// It may be important for other reasons in the future.
1152     /// It is important this be called immediately after reading in the object from the input file,
1153     /// before filling the transient data members or using the indexes in any way.
1154     void fixIndexes(std::vector<ProcessHistoryID>& processHistoryIDs);
1155 
1156     /// The number of events needs to be set before filling the transient event vectors.
1157     /// It is used to resize them.
1158     void setNumberOfEvents(EntryNumber_t nevents) { transient_.numberOfEvents_ = nevents; }
1159 
1160     /// Calling this enables the functions that fill the event vectors to get the event numbers.
1161     /// It needs to be called before filling the events vectors
1162     /// This implies the client needs to define a class that inherits from
1163     /// EventFinder and then create one.  This function is used to pass in a
1164     /// pointer to its base class.
1165     void setEventFinder(std::shared_ptr<EventFinder> ptr) { transient_.eventFinder_ = ptr; }
1166 
1167     /// Fills a vector of event numbers.
1168     /// Not filling it reduces the memory used by IndexIntoFile.
1169     /// As long as the event finder is still pointing at an open file
1170     /// this will automatically be called on demand (when the event
1171     /// numbers are are needed). In cases, where the input file may be
1172     /// closed when the need arises, the client code must call this
1173     /// explicitly and fill the vector before the file is closed.
1174     /// In PoolSource, this is necessary when duplicate checking across
1175     /// all files and when doing lookups to see if an event is in a
1176     /// previously opened file.  Either this vector or the one that
1177     /// also contains event entry numbers can be used when looking for
1178     /// duplicate events within the same file or looking up events in
1179     /// in the current file without reading them.
1180     void fillEventNumbers() const;
1181 
1182     /// Fills a vector of objects that contain an event number and
1183     /// the corresponding TTree entry number for the event.
1184     /// Not filling it reduces the memory used by IndexIntoFile.
1185     /// As long as the event finder is still pointing at an open file
1186     /// this will automatically be called on demand (when the event
1187     /// numbers and entries are are needed).  It makes sense for the
1188     /// client to fill this explicitly in advance if it is known that
1189     /// it will be needed, because in some cases this will prevent the
1190     /// event numbers vector from being unnecessarily filled (wasting
1191     /// memory).  This vector will be needed when iterating over events
1192     /// in numerical order or looking up specific events. The entry
1193     /// numbers are needed if the events are actually read from the
1194     /// input file.
1195     void fillEventEntries() const;
1196 
1197     /// If needEventNumbers is true then this function does the same thing
1198     /// as fillEventNumbers.  If NeedEventEntries is true, then this function
1199     /// does the same thing as fillEventEntries.  If both are true, it fills
1200     /// both within the same loop and it uses less CPU than calling those
1201     /// two functions separately.
1202     void fillEventNumbersOrEntries(bool needEventNumbers, bool needEventEntries) const;
1203 
1204     /// If something external to IndexIntoFile is reading through the EventAuxiliary
1205     /// then it could use this to fill in the event numbers so that IndexIntoFile
1206     /// will not read through it again.
1207     std::vector<EventNumber_t>& unsortedEventNumbers() { return transient_.unsortedEventNumbers_; }
1208     std::vector<EventNumber_t> const& unsortedEventNumbers() const { return transient_.unsortedEventNumbers_; }
1209 
1210     /// Clear some vectors and eventFinder when an input file is closed.
1211     /// This reduces the memory used by IndexIntoFile
1212     void inputFileClosed();
1213 
1214     /// Clears the temporary vector of event numbers to reduce memory usage
1215     void doneFileInitialization();
1216 
1217     /// Used for backward compatibility and tests.
1218     /// RootFile::fillIndexIntoFile uses this to deal with input files created
1219     /// with releases before 3_8_0 which do not contain an IndexIntoFile.
1220     std::vector<RunOrLumiEntry>& setRunOrLumiEntries() { return runOrLumiEntries_; }
1221 
1222     /// Used for backward compatibility and tests.
1223     /// RootFile::fillIndexIntoFile uses this to deal with input files created
1224     /// with releases before 3_8_0 which do not contain an IndexIntoFile.
1225     std::vector<ProcessHistoryID>& setProcessHistoryIDs() { return processHistoryIDs_; }
1226 
1227     /// Used for backward compatibility to convert objects created with releases
1228     /// that used the full ProcessHistoryID in IndexIntoFile to use the reduced
1229     /// ProcessHistoryID.
1230     void reduceProcessHistoryIDs(ProcessHistoryRegistry const& processHistoryRegistry);
1231 
1232     //*****************************************************************************
1233     //*****************************************************************************
1234 
1235     /// Used internally and for test purposes.
1236     std::vector<RunOrLumiEntry> const& runOrLumiEntries() const { return runOrLumiEntries_; }
1237 
1238     //*****************************************************************************
1239     //*****************************************************************************
1240 
1241     void initializeTransients() { transient_.reset(); }
1242 
1243     struct Transients {
1244       Transients();
1245       void reset();
1246       int previousAddedIndex_;
1247       std::map<IndexRunKey, EntryNumber_t> runToOrder_;
1248       std::map<IndexRunLumiKey, EntryNumber_t> lumiToOrder_;
1249       EntryNumber_t beginEvents_;
1250       EntryNumber_t endEvents_;
1251       int currentIndex_;
1252       RunNumber_t currentRun_;
1253       LuminosityBlockNumber_t currentLumi_;
1254       EntryNumber_t numberOfEvents_;
1255       edm::propagate_const<std::shared_ptr<EventFinder>> eventFinder_;
1256       std::vector<RunOrLumiIndexes> runOrLumiIndexes_;
1257       std::vector<EventNumber_t> eventNumbers_;
1258       std::vector<EventEntry> eventEntries_;
1259       std::vector<EventNumber_t> unsortedEventNumbers_;
1260     };
1261 
1262   private:
1263     //for testing
1264     friend class ::TestIndexIntoFile;
1265     friend class ::TestIndexIntoFile1;
1266     friend class ::TestIndexIntoFile2;
1267     friend class ::TestIndexIntoFile3;
1268     friend class ::TestIndexIntoFile4;
1269     friend class ::TestIndexIntoFile5;
1270 
1271     /// This function will automatically get called when needed.
1272     /// It depends only on the fact that the persistent data has been filled already.
1273     void fillRunOrLumiIndexes() const;
1274 
1275     std::vector<EventNumber_t>& unsortedEventNumbersMutable() const { return transient_.unsortedEventNumbers_; }
1276     void fillUnsortedEventNumbers() const;
1277     void resetEventFinder() const { transient_.eventFinder_ = nullptr; }  // propagate_const<T> has no reset() function
1278     std::vector<EventEntry>& eventEntries() const { return transient_.eventEntries_; }
1279     std::vector<EventNumber_t>& eventNumbers() const { return transient_.eventNumbers_; }
1280     void sortEvents() const;
1281     void sortEventEntries() const;
1282     int& previousAddedIndex() const { return transient_.previousAddedIndex_; }
1283     std::map<IndexRunKey, EntryNumber_t>& runToOrder() const { return transient_.runToOrder_; }
1284     std::map<IndexRunLumiKey, EntryNumber_t>& lumiToOrder() const { return transient_.lumiToOrder_; }
1285     EntryNumber_t& beginEvents() const { return transient_.beginEvents_; }
1286     EntryNumber_t& endEvents() const { return transient_.endEvents_; }
1287     int& currentIndex() const { return transient_.currentIndex_; }
1288     RunNumber_t& currentRun() const { return transient_.currentRun_; }
1289     LuminosityBlockNumber_t& currentLumi() const { return transient_.currentLumi_; }
1290     std::vector<RunOrLumiIndexes>& runOrLumiIndexes() const { return transient_.runOrLumiIndexes_; }
1291     size_t numberOfEvents() const { return transient_.numberOfEvents_; }
1292     EventNumber_t getEventNumberOfEntry(EntryNumber_t entry) const {
1293       return transient_.eventFinder_->getEventNumberOfEntry(entry);
1294     }
1295 
1296     //This class is used only by one thread at a time within the source serialized code
1297     CMS_SA_ALLOW mutable Transients transient_;
1298 
1299     std::vector<ProcessHistoryID> processHistoryIDs_;  // of reduced process histories
1300     std::vector<RunOrLumiEntry> runOrLumiEntries_;
1301   };
1302 
1303   template <>
1304   struct value_ptr_traits<IndexIntoFile::IndexIntoFileItrImpl> {
1305     static IndexIntoFile::IndexIntoFileItrImpl* clone(IndexIntoFile::IndexIntoFileItrImpl const* p) {
1306       return p->clone();
1307     }
1308     static void destroy(IndexIntoFile::IndexIntoFileItrImpl* p) { delete p; }
1309   };
1310 
1311   class Compare_Index_Run {
1312   public:
1313     bool operator()(IndexIntoFile::RunOrLumiIndexes const& lh, IndexIntoFile::RunOrLumiIndexes const& rh);
1314   };
1315 
1316   class Compare_Index {
1317   public:
1318     bool operator()(IndexIntoFile::RunOrLumiIndexes const& lh, IndexIntoFile::RunOrLumiIndexes const& rh);
1319   };
1320 
1321   // This class exists only to allow forward declarations of IndexIntoFile::IndexIntoFileItr
1322   class IndexIntoFileItrHolder {
1323   public:
1324     IndexIntoFileItrHolder(IndexIntoFile::IndexIntoFileItr const& iIter) : iter_(iIter) {}
1325     void getLumisInRun(std::vector<LuminosityBlockNumber_t>& lumis) const { iter_.getLumisInRun(lumis); }
1326 
1327   private:
1328     IndexIntoFile::IndexIntoFileItr const& iter_;
1329   };
1330 }  // namespace edm
1331 
1332 #endif