Proposal for enhanced iterators

Foreword

In the context of the PhysicsAnalysis package (but not only), there seems a need for a SymLink capability arised. What is SymLink ? This is the ability StoreGate provides to fake inheritance between collections of instances of objects (which does have an inheritance relationship). For example, if Electron derives from ParticleBase, SymLink provides a way to make the compiler thinks ElectronContainer derives from ParticleBaseContainer. Remember that according to the C++ FAQ, this is not plain C++ compliant stuff. Even if it sounds weird, a collection of Daughter instances is not the same thing than a collection of Mother. Take a look at this C++FAQ-Lite.

So if it happens a method needs a collection of ParticleBase as input and that you have a handle on Electrons, SymLink is your solution. However, as all the tricks, it has some drawbacks. Namely, it seems it is not the most portable thing in C++ code hence one might run into problems when/if one tries to run a piece of code containing this feature on another platform or compiled with something else than gcc.

From this assertion might also arise the need of a portable, non-intrusive and non-disruptive solution (and maybe the less confusive from users' point of view as possible). Here come iterators. They might not be the solution neither they'll make coffee for you nor write your code for you, but they surely deserve some attention.

Introduction

Iterators, together with algorithms and containers, are the corner stone of the Sandard Template Library. The iterators of the STL provide a way to walk through any STL container (map,vector,deque,...) and let the algorithm they are passed to do its work. This allows wide code reusability from the STL. Of course on of the reason of this reusability comes from the template nature of this library. We don't want our libraries to be heavily templated because we kind of rely more on Objected-Oriented programming (as opposed to metaprogramming, which is just another word for templatization).

So the whole point of the need of introducing SymLink into every corner of our code is that we want both some inheritance relationship and the ability to have some way to walk through a collection of objects. At the element level (ie: the objects contained into a container) we have the inheritance relationship. But we loose the collection feature.

Iterators might be thought as an intermediate level :

• by just dereferencing them we access to the underlying object (and thus the inheritance pops up)
• they provide a way to traverse a collection of objects.

But instead having the inheritance feature coming from the underlying object, one could make the iterators inherit from each other (and thus reproducing the same inheritance hierarchy tree than their underlying objects) and honouring some base interface to access to some top level class. This is a cumbersome way to define polymorphic iterators.

Polymorphic iterators

So, polymorphic iterators could be used to solve the SymLink problem. Let see how one could implement this for the PhysicsAnalysis use case.

NB: Let me point out that an always almost up-to-date version of this proposal can be found under my CVS repository.

First we need a base interface to access to IParticle instances.

Interface of IIParticleIterator

class IIParticleIterator
{
  public:
   virtual ~IIParticleIterator() {}
   virtual IIParticleIterator* clone() const = 0;

   // This method determines the top level of the inheritance tree
   // one is working with.
   virtual const IParticle* operator*() const = 0;

   // Now this is just some iterator interface methods to
   // provides means of walking through a collection of objects
   // Note that it could be factorized using some boost iterator traits.
   virtual IIParticleIterator& operator++() = 0;
   virtual IIParticleIterator& operator--() = 0;
   virtual IIParticleIterator& operator++(int) = 0;
   virtual IIParticleIterator& operator--(int) = 0;

   virtual bool operator==(const IIParticleIterator& rhs) const = 0;
   virtual bool operator!=(const IIParticleIterator& rhs) const {
     return !operator==(rhs);
   }
   virtual bool operator< (const IIParticleIterator& rhs) const = 0;
 };

So now we have written in the stone how we want our iterators will behave let implement it. In the following we will exercise the inheritance tree down to the Electron class. Hence the next class to have a look at is the ParticleBase, just after implementing a templated IParticleIterator :

template<typename T=IParticle>
class IParticleIterator : public IIParticleIterator
{
  typedef typename std::vector<T*>::const_iterator const_iter_t;
  public:
    // Implementation details of IIParticleIterator interface
    // It just delegates the work to the iterator of the
    // underlying container this polymorphic iterator has been
    // made from

  private:
    const_iter_t m_iter;
};

Then we implement the next layer down the road toward the Electron class :

class ParticleBaseIterator : public IParticleIterator<IParticle>
{
  typedef std::vector<ParticleBase*>::const_iterator const_iter_t;
  public:
    // Other implementation details of IIParticleInterator
    // interface, overloading the one previously done by
    // the templated IParticleIterator

  // ParticleBaseIterator specific interface : we retrieve
  // an pointer to a ParticleBase instance
  const const_iter_t::value_type getObject() const { return *m_iter; }

  private:
    const_iter_t m_iter;
};

And finally we arrived at the implementation of iterator for Electron :

class ElectronIterator : public ParticleBaseIterator
{
  typedef std::vector<Electron*>::const_iterator const_iter_t;
  public:
    // Other implementation details of IIParticleInterator
    // interface, overloading the one previously done by
    // the templated ParticleBaseIterator

    // ElectronIterator specific interface : we retrieve
    // an pointer to an Electron instance
    const const_iter_t::value_type getObject() const { return *m_iter; }

  private:
    const_iter_t m_iter;
};

At this point we have mapped the complete inheritance tree from IParticle down to Electron. Let us see how does this fit in the whole Athena/Gaudi framework. Actually there are two options.

Modifications to DataVector < T >

First of all, one can plug these new iterators, directly into the DataVector class, at the cost of (still to be done and worked out) some memory management. I created a new container class which derives from the vanilla DataVector in order to not pollute the existing scheme.

template<typename T>
class MyDV : public DataVector<T>
{
  public:
    // Overload the typedef for const_iterator so client code will
    // transparently uses the polymorphic iterators instead of the bare
    // STL ones
   typedef IIParticleIterator& const_iterator;
   typedef IParticleIterator<T> const_iter;

   // New retrieval of begin and end iterators:
   // Obviously we have to do some memory management (through smart and/or auto
   // pointers to prevent memory leaks)
   const_iter& myBeg() const { return *(new const_iter(DataVector<T>::begin())); }
   const_iter& myEnd() const { return *(new const_iter(DataVector<T>::end())); }
};

And the same stuff for a new ElectronContainer class :

class MyEles : public DataVector<Electron> 
{
  public:
   typedef ElectronIterator const_iter;

   const_iter& myBeg() const { return *(new const_iter(DataVector<Electron>::begin())); }
   const_iter& myEnd() const { return *(new const_iter(DataVector<Electron>::end())); }
};

However this memory management could be just unacceptable. So another way could be to decouple the polymorphic iterators from the container class (ie: unnest the iterator). Thus this would allow us to write something along these lines :

IParticleIterator<Electron> itr = electrons->begin();
ElectronIterator eleItr = electrons->begin();

where electrons is an instance of a genuine ElectronContainer. In fact, both ways (plug iterators into DataVector or decouple them) can live together alongside.

At this point we are all set.

Application to some analysis code

Suppose I have some analysis method which only requires the IParticle interface. This means I only need to know the 4-momentum of a particle and e.g. its pdgId. So I write this little function like this :

namespace Ana {
  void recoII( IIParticleIterator& i, IIParticleIterator& end ) {
    std::cout << "------- Using pure interface: " << std::endl;
    for ( ; i != end; ++i ) {
      std::cout << "\t\t==> Id= " << (*i)->charge()
      << "\te= " << (*i)->e() / GeV
      << std::endl;
    }
    std::cout << "------- Done -------" << std::endl;
  }
}

But then if I want a more sophisticated method which makes use of the egamma object of the underlying Electron, I have to declare it and require it in the signature of the function :

namespace Ana {
  void recoFromEle( ElectronIterator& i, 
          ElectronIterator& end )
  {
    std::cout << "------- Using Electron interface: " << std::endl;
    for ( ; i != end; ++i ) {

    std::string eg = "has_egamma";
    if ( i.getObject()->eg() == 0 ) {
       eg = "NO_egamma";
    }

    std::cout << "\t\t==> Id= " << (*i)->charge()
              << "\te= " << (*i)->e()
              << "\teg= " << eg
              << std::endl;
    }
    std::cout << "------- Done -------" << std::endl;
  }
}

As you can see I check that the Electron has indeed a pointer to an egamma object. Ok, so far so good. Let us investigate how I can use these functions into my analysis code :

 // retrieve a customised container of electrons : MyEles
 // and an ElectronContainer
 const ElectronContainer * electrons = ...;
 const MyEles * myEles = ...;

 // I can loop over them like this
 std::cout << "Loop over MyEles::const_iter: (" 
          << eles->size() << ")"
          << std::endl;
 for ( MyEles::const_iterator i = eles->myBeg();
       i != eles->myEnd();
       ++i ) {
    std::cout << "\t==> Id= " << (*i)->charge() 
             << "\te= " << (*i)->e()
             << "\teta= " << (*i)->eta()
             << std::endl;
 }
  
 // Or loop over them at the ParticleBase level like this:
 std::cout << "Loop over MyPBs::const_iter: (" 
           << eles->size() << ")"
           << std::endl;
 for ( MyPBs::const_iterator i = eles->myBeg();
       i != eles->myEnd();
       ++i ) {
    std::cout << "\t==> Id= " << (*i)->charge() 
              << "\te= " << (*i)->e()
              << "\teta= " << (*i)->eta()
              << std::endl;
 }

 // Now lets exercise our analysis functions:

 // 1) for the customised container
 std::cout << "Use the recoFromII fct:" << std::endl;
 Ana::recoFromII( eles->myBeg(), eles->myEnd() );

 std::cout << "Use the recoFromEle fct:" << std::endl;
 Ana::recoFromEle( eles->myBeg(), eles->myEnd() );

 // 2) for the vanilla one
 ElectronIterator eItr  = electrons->begin();
 ElectronIterator endItr= electrons->end();

 std::cout << "Use the recoFromII fct:" << std::endl;
 Ana::recoFromII( eItr, endItr ); // there, the ElectronIterators are taken as IIParticleIterators
                                  // Normally we should have rely on SymLink to create an IParticleContainer
 // reinitialize iterators
 std::cout << "Use the recoFromEle fct:" << std::endl;
 Ana::recoFromEle( eItr, endItr );

It just works !!

Application to SymLink and StoreGate

Smart iterators / View of Container

Smart iterators (and/or view iterators) can model different views of a container. They can ease the way we are handling the filtering process of containers' content and could nicely fit with the IFilter tools (predicates in STL wording).

transform_view

decorator_view

Ever wanted to get a seamless way to attach some additional information to your bare class ? And this for each element of some container ? Like for example attach (or associate) some Mc Truth object to your ParticleJet or JetTag object ?

This decorator_view could just fill the bill. By combining the content of 2 containers (reco/Mc) linked together with some predicate (an IParticleAssocFilter class for example) you would get this association done for each of your elements.

filter_view

union_view

(or DataBucket in StoreGate wording ?)

Application to the EventView EDM

Bibliography

• views.ps: View containers and smart iterators
• flll-tr-0204.pdf: View containers : filter iterators - 1
• flll-tr-0209.pdf: View containers : filter iterators - 2
• smart_iterators.pdf: Smart iterators
• http://www.zeta.org.au/~jon/STL/views/doc/views.html
• View Template Library
• STL and OO mixing : polymorphic iterators
• Beta code for a View library for Boost CVS

-- SebastienBinet - 03 May 2005