Last significant change: 2005/02/07
Moving between related objects of an object structure is called Navigation. This chapter describes a set of tools that have been developed to help navigate MINOS object structures. It is divided into the following sections:-
Each section has been designed to be read in isolation; so if you are only interested in using the tools without the whys and the wherefores, you can just concentrate on section 9.2 and ignore the others.
Throughout this chapter the character strings Xxx and Yyy are placeholders which should be replaced with the appropriate class name. There is just one exception: the header file XxxItr.h really is typed like that i.e. Xxx is not a placeholder but is to be typed literally.
So, if you see an example like this:-
#include "Xxx.h" XxxItr myItr;
and you want to apply it to a class called MyClass, then it should be written like this:-
#include "Xxx.h" MyClassItr myItr;
This section has been designed to be read without looking at the other sections of this chapter so some level of repetition is unavoidable. However it concentrates exclusively on explaining how to use the tools without discussing design issues.
The purpose of the tools is to aid navigation of the event and detector object structures. The navigation objects are transient, that is to say they are created as necessary and are not stored permanently. The idea is that designers of the event and detector object structures provide code to create the navigation objects on demand. The end user seems a uniform interface via these navigation objects.
The heart of navigation is the iterator. Its objective is to give access to a set of objects. In the Fortran days you might store a set of items in an array and then process them sequentially using an index. In the OO world the index is replaced by an iterator which can be asked repeatedly to return the next object until there is none left. The advantage is that the you no longer care where or how the objects are stored, all you need is a method to retrieve them.
The navigation tools have two types of iterators:-
The sets are homogeneous i.e. all the members of the set are of the same class. or at least are derived from a common class. In both cases the iterator accesses objects from a single set and provides sequential and random access, sorting and selection services. The only difference between the two types is that the second type has an additional selection facility: to select the sub-set of objects associated with a single object from the other set of the relationship.
Most of the navigation code is generic, that is to say it can support operations on any sets of objects. It does this by accessing all objects via void pointers. Such pointers are very powerful, they can point at any byte in memory, and so are very dangerous as well! So you never deal directly with these pointers but always use objects that pass the right type of pointer. This means that for any set of objects you wish to navigate there has to be an associated iterator class that returns this type of object. The class is named XxxItr where Xxx denotes the particular class name. So if you have a class called MyClass the tools require the creation of a class called MyClassItr. This code can be created using a C++ macro. Assuming that your class code has the normal .h header and .cxx implementation files, then all you need do is:-
#include "Navigation/XxxItr.h" XXXITRDEF(MyClass)
XXXITRIMP(MyClass)
#pragma link C++ class MyClassItr; #pragma link C++ class MyClassKeyFunc; #pragma link C++ class MyClassKeyFunctor;
The purpose of MyClassKeyFunc will be explained when we deal with sorting in section 9.2.6 and MyClassKeyFunctor when we deal with functors in section 9.2.9.
Note: Remember: the header file XxxItr.h really is typed like that i.e. Xxx is not a placeholder but is to be typed literally.
Sequential access is the mostly commonly used functionality of an OO iterator. Indeed it is all that some types of iterator can do. Iterators are very popular and several different programming styles have developed. As far as possible the navigation tools support the main ones to help you become familiar with the different styles that you will undoubtedly encounter looking at external code.
The first programming style is the most natural for anyone just starting with OO: no iterator operations involve operating overloading.
Suppose you have an XxxItr called myItr and the class Xxx has a Print() member function, then this will print out every one:-
while ( myItr.IsValid() ) {
Xxx* myObj = myItr.Ptr();
myObj->Print();
myItr.Next();
}
The loop operates while the iterator's member function IsValid() returns true i.e. until there is no Xxx objects to return. The member function Ptr() returns a pointer to the current Xxx which can then be asked to Print() before the iterator is moved forward by asking it to perform its Next() function.
The iterator will return a zero if asked to return a pointer when IsValid() returns false and as 0 is the value of false you can, if you like to cut down lines of code, rewrite the above as:-
while ( Xxx* myObj = myItr.Ptr() ) {
myObj->Print();
myItr.Next();
}
For people who like to be minimalist (which may not be conducive to code transparency), this also works:-
myItr.Prev(); while ( Xxx* myObj = myItr.NextPtr() ) myObj->Print();
Prev() moves the iterator back (even if it was at the first object) and NextPtr() moves forward and returns the pointer to the object. At any time you can move back to the first object in the set with:-
myItr.ResetFirst();
As has already been hinted at, you can iterate over the set in reverse order if you want to:-
myItr.ResetLast()
while ( myItr.IsValid() ) {
Xxx* myObj = myItr.Ptr();
myObj->Print();
myItr.Prev();
}
There is also a PrevPtr() if you need it.
Functors are objects that have the function operator () overloaded. This means that the object can be called rather like a function. This style is favoured by ROOT for its iterators. The Functor style is also popular for small ``single-minded'' objects. The member functions of the XxxItr class have been chosen to ensure that any segment of code using ROOT iterators would continue to work if replaced by these navigation iterators. To loop over all objects in the above example with this style you would code:-
while ( Xxx* myObj = myItr() ) myObj->Print();
myItr() isn't a function call but a call to myItr operator() member function. This does two things:-
You can flip the sign on the current direction at any time with:-
myItr.SetDirection(+1); //Move forward myItr.SetDirection(-1); //Move backward
To be helpful, if you ask the iterator to ResetFirst() it will set the default direction is set forward and if you ResetLast() it will set the default direction is backwards. There is also:-
myItr.Reset();
which moves it back to the beginning relative to the current direction i.e. it is equivalent to ResetFirst() if the default direction is forwards otherwise it is equivalent to ResetLast()
STL is the Standard Template Library which comes complete with a set of
containers (objects that hold other objects) and iterators that operate on
these containers. STL is part if the standard C++ so the STL style effectively
becomes the standard for iterators. STL views iterators as if they were
pointers to an array of objects, consequently the operators ++ and --
move the pointer forwards and backwards and the dereference operator
* returns the object itself.
The tools only partially support this style. In particular:-
-- operators are supported
(++myItr is O.K. but not myItr++).
This is how you would iterate:-
while ( myItr.IsValid() } {
(*myItr).Print();
++myItr;
}
As before ResetFirst() and ResetLast() moves to the start and end of the set.
Its is possible, but probably not advisable, to mix all of the above 3 styles in a single loop!
It is often useful to be able to process all the objects in a set in some predefined order. The tools support this and, because of the way they work allow you to sort the set without disturbing the underlying object structure. This is possible because they have their own private copy of the set stored in a NavSet object, and your XxxItr object connects to, and iterates over, this set. This also means you can create multiple iterators simultaneously and have each ordered in its own way.
The way ordering works is that you have to tell the tools how to assign a value to every member of the set and then they sort the set into ascending order based on the value. If you want to processes in descending order you can just process the set backwards of course. The type of value you assign must be a simple type: an integer, floating point, or character string and its value must be derived from public member functions of the objects in the set. To support the notion of a sortable value, the tools have a type of object called a NavKey with the following properties:-
Your first job is to write a little function which takes a pointer to your Xxx object and returns a NavKey. As NavKeys can be created directly from simple types, writing this function is simple. Suppose Xxx has the member function Time() that returns a Float_t, then you could create a function, say KeyFromTime:-
#include "Navigation/NavKey.h"
static NavKey KeyFromTime( Xxx* obj) { return obj->Time(); }
The expression obj->Time() is of type Float_t but the compiler wants a
NavKey,
however it knows how to create a NavKey from a Float_t so creates one.
Remember in C and C++ all functions have to be defined at the file level,
they cannot be embedded within other functions to hide them. The `static'
keyword at least keeps the name local to the file so the name KeyFromTime
won't conflict with the same name defined in other files.
In a similar way, if Xxx has the member function Name() that returns a pointer to Char_t and PlaneNo() that returns Int_t you could write:-
static NavKey KeyFromName( Xxx* obj) { return obj->Name(); }
static NavKey KeyFromPlaneNo( Xxx* obj) { return obj->PlaneNo(); }
The function names are arbitrary, but it makes sense to be consistent and choose something logical.
Having written the function, you next job is to get it applied. It might seem reasonable for XxxItr to have a member function that could take your function as an argument and apply it. Now originally, for reasons we will go into shortly, this was not allowed. However this rule has been relaxed and code to sort on the KeyFromTime function looks like this:-
#include "Navigation/NavKey.h" #include "Navigation/NavSet.h" ... myItr.SetSortFun(KeyFromTime);
Important: When a NavSet is given a sort function it resets all its iterators by sending them their ResetFirst() message.
You can change the sort function at any time and as often as you like, but bear in mind that the iterator gets reset each time you do. NavSet applies the ordering at once and all iterators will process in this order. However if subsequently anyone changes the state of any objects in the underlying set that NavSet set mirrors this will not be reflected in the order processed. For example, suppose you have a set of digitizations and your NavSet of it is ordered by time. Further suppose you then recalibrate the digitizations and it changes the times to such an extent that the original time ordering is wrong, the NavSet isn't aware of the change, so its order won't change. If you know this may have happened you can refresh (see 9.2.15).
We now have to introduce a little history to understand why there is a second, more complicated way, to do the same thing! There may be times when you have to use this second method.
The reason why originally there was a rule that forbade an iterator requesting a NavSet sort itself, was considered flawed for several reasons:-
This is what the code looks like to sort Xxx by Time:-
#include "Navigation/NavKey.h" #include "Navigation/NavSet.h" ... // Create an XxxKeyFunc. Any member function that has // the word "Create" means that you, as the caller are going // to be the owner of a new object and will need to look after it! XxxKeyFunc* myKf = myItr.CreateKeyFunc(); // Program it with the sort function. mkKf->SetFun(KeyFromTime); // Ask the iterator for its NavSet and then pass the // XxxKeyFunC to it. The name "Adopt" means that the NavSet // now owns the XxxKeyFunc and can delete it anytime it // pleases e.g. when asked to adopt another. myItr.GetSet()->AdoptSortKeyFunc(myKf); // As you no longer own the XxxKeyFunc the safest thing is // to clear the pointer so that you are not tempted to // use it again! myKf = 0;
You will need this more complex method if passing in programmable objects - see section 9.2.9.
You can cancel sorting by passing a null pointer to either SetSortFun or AdoptSortKeyFunc:-
myItr.SetSortFun(0);
or
myItr.GetSet()->AdoptSortKeyFunc(0);
This won't unsort the set of course but will mean that the NavSet will not attempt to maintain order after operations such as mapping (see 9.2.8)
In the previous section we have seen examples sorting by time or by plane number, but what if you wanted to sort first by plane and then, within each plane, by time? This can be done by using by passing in two sort functions. In the short form:-
#include "Navigation/NavKey.h" #include "Navigation/NavSet.h" ... myItr.SetSortFun(KeyFromPlaneNo,kFALSE); myItr.SetSortFun(KeyFromTime);
and the long form:-
#include "Navigation/NavKey.h" #include "Navigation/NavSet.h" ... XxxKeyFunc* myKf = myItr.CreateKeyFunc(); mkKf->SetFun(KeyFromPlaneNo); myItr.GetSet()->AdoptSortKeyFunc(myKf); myKf = myItr.CreateKeyFunc(); mkKf->SetFun(KeyFromTime); myItr.GetSet()->AdoptSortKeyFunc(myKf,kFALSE); myKf = 0;
The second argument to SetSortFun and AdoptSortKeyFunc, which defaults to kTRUE, controls the deletion any existing key functions. The first call above removes any existing sort function before adding KeyFromPlaneNo but the second call just adds the key function KeyFromTime to the end of the list.
In the case of 2 sort functions there is an even shorter form:-
#include "Navigation/NavKey.h" #include "Navigation/NavSet.h" ... myItr.SetSort2Fun(KeyFromPlaneNo,KeyFromTime);
which ensures sorting is suppressed until both functions have been set.
In this way you can combine two or more key functions to fully specify the sort order. Each time you append a new key function, the set is resorted and the ordering further refined. Of course it is a little wasteful sorting before all the required functions are given to the NavSet so you can suppress sorting by passing a third argument, that defaults to kTRUE, to either SetSortFun or AdoptSortKeyFunc:-
... // Suppress sorting until second function has been supplied myItr.SetSortFun(myKf,kTRUE,kFALSE); ... // Pass second function and sort. myItr.SetSortFun(myKf,kTRUE,kFALSE);
You can apply several different forms of selection and the result is that you only see the reduced set until the selection is cancelled. The Reset* messages move the iterator to the first or last selected object and the sequential access only returns selected objects. However the Size() member function continues to return the full size of the set; use the SizeSelect() member function to see how many are currently selected. With no selection in force, SizeSelect() is equivalent to Size().
Important: When a selection is applied or cancelled on a NavSet the NavSet resets all its iterators by sending them their ResetFirst() message.
If more than one form of selection is in force, they form an AND - objects are selected only if all criteria are satisfied. See also Masks (section 9.2.10) for an alternative way to select set members.
Slicing means selecting only those objects whose key value lies within a specified range of values. Suppose you had sorted your Xxx objects by time and now only wanted to process those that lie within the time window 10. to 50. To do this you need to send NavSet its Slice message:-
myItr.GetSet()->Slice(10.,50.);
cout << "There are " << myItr.SizeSelect()
<< " selected objects."" << endl;
after which myItr will be reset to the start of the slice ready for you to process all the Xxx objects in the time range. If the lower and upper limits coincide you can supply a single argument. For example:-
myItr.GetSet()->Slice(30.);
selects objects whose time is exactly 30. Of course for floating point values, requiring an exact match like this may fail if rounding errors are involved.
Slicing will fail unless:-
As with sorting, the slice will not reflect subsequent changes to the objects in the set. Use the Refresh message (9.2.15) if necessary.
To cancel slice selection call ClearSlice:-
myItr.GetSet()->ClearSlice();
As this is a change in selection, all iterators get reset.
To change the slice, first reset it and then apply the new slice e.g.:-
myItr.GetSet()->ClearSlice(); myItr.GetSet()->Slice(50.,100.);
Important: Don't apply a second slice without resetting; that will attempt to slice in the second dimension - see below.
Just as with sorting, you can apply multiple slices. Suppose you have applied multiple sorts first by plane number and then by time. In which case the statements:-
myItr.GetSet()->Slice(1,100.); myItr.GetSet()->Slice(10.,50.);
would reject any Xxx objects whose plane number was not within the range 1..100 or whose time as not in the range 10.0..50.0.
The system generalises to any (reasonable!) number of dimensions: the nth sort function is used by the nth slice. As with sorting you can suppress the operation of selection until all slices have been defined by using an optional second argument that defaults to kTRUE:-
myItr.GetSet()->Slice(1,100.,kFALSE); myItr.GetSet()->Slice(10.,50.);
The first slice over plane number remains dormant until the second slice over time is applied.
Selection by user is very similar to sorting (9.2.6). As with sorting there are two ways to do it. Either way the user defines a function that returns a NavKey with the values true or false (non-zero or zero). In the short form this function is directly passed to the iterator. In the long form it is wrapped in an XxxKeyFunc, and passed it to the NavSet via its AdoptSelectKeyFunc message.
Suppose you want to select Xxxs that have either a time less than 50. or a plane number greater that 100, then you could code a selection function like this:-
NavKey SelectPlaneNoTime( Xxx* obj) { return obj->PlaneNo() >
100. || obj->Time() < 50.; }
Having written the function, you apply it like this.
Short form:-
myItr.SetSelectFun(KeyFromTime);
long form:-
// Create an XxxKeyFunc. Any member function that has // the word "Create" means that you, as the caller are going // to be the owner of a new object and will need to look after it! XxxKeyFunc* myKf = myItr.CreateKeyFunc(); // Program it with the sort function. mkKf->SetFun(KeyFromTime); // Ask the iterator for its NavSet and then pass the // XxxKeyFunC to it. The name "Adopt" means that the NavSet // now owns the XxxKeyFunc and can delete it anytime it // pleases e.g. when asked to adopt another. myItr.GetSet()->AdoptSelectKeyFunc(myKf); // As you no longer own the XxxKeyFunc the safest thing is // to clear the pointer so that you are not tempted to // use it again! myKf = 0;
In the normal course of events the object set is not expected to change while navigation is in progress, but if it does while looping over them with an iterator, you may miss some or may retrieve some that subsequently should have been ignored. Navigation of a set that is changing is always a potential problem, see Refreshing Iterators (9.2.15) for a discussion.
To cancel selection by using a null function pointer:-
myItr.SetSelectFun(0);
or
myItr.GetSet()->AdoptSelectKeyFunc(0);
As with SetSortFun and AdoptSortKeyFunc, SetSelectFun and AdoptSelectKeyFunc can take a trailing argument that if set to kFALSE suppresses the application of the selection:-
myItr.GetSet()->AdoptSelectKeyFunc(myKf,kFALSE);
However, unlikeSetSortFun and AdoptSortKeyFunc, applying another SetSortFun and AdoptSelectKeyFunc will replace the existing function, it nevers appends a second one. This might lead you to wonder why you would want to suppress selection. This will become clear in section 9.2.11 which discusses simple optimisation techniques.
You can invert the meaning of your selection function by using:-
myItr.GetSet()->InvertSelection();
which reapplies it but only selects those members that fail the selection cut. To switch back to the normal selection and reapply it:-
myItr.GetSet()->InvertSelection(kFALSE);
Whenever a new selection function is adopted, normal selection applies. As with SetSelectFun and AdoptSelectKeyFunc, InvertSelection can take a trailing argument that if set to kFALSE suppresses the application of the selection.
Mapping is the process by which a relationship is navigated. Suppose you have two sets A and B that have a relationship, that is to say that each member in one set is associated with zero or more members in the other set. You can select on this association. For example, if you have an iterator over the A set, you can select those that are associated with an individual B set member by passing the NavSet a pointer to the B set member. If that member has no association, or if you pass a pointer to a B that isn't a member of the B set then, as you might expect, you get an empty A sub-set. This is also true unless your iterator was created for a set that is participating in a relationship.
To illustrate the idea suppose your Xxx set is in 1:n relationship with a second set of Yyy objects, that is to say for every Xxx there is 1 or more Yyy but each Yyy has only one Xxx. Further suppose both Xxx and Yyy have a Name() member function. This is how you could loop over all Xxx objects and list the Yyys it is associated with:-
// Include the class headers (which should both use the XXXITRDEF to
// declare the XxxItr and YyyItr classes).
#include "Xxx.h"
#include "Yyy.h"
#include "Navigation/NavSet.h"
// Create iterators over both sets in the relationship.
// This code will only work if this relationship is built in;
// you will have to see other documentation for other relationships.
XxxItr itrXxx("Yyy");
YyyItr itrYyy("Xxx");
cout << "The Xxx set has " << itrXxx.Size() << " members" << endl;
cout << "The Yyy set has " << itrYyy.Size() << " members" << endl;
// Outer loop over all the Xxx set.
while ( itrXxx.IsValid() {
Xxx* myXxx = itrXxx.Ptr();
// Subselect Yyy to the association with this Xxx.
itrYyy.GetSet()->Map(myXxx);
cout << "Xxx " << myXxx->Name() << " is associated "
<< itrYyy.SizeSelect() << " Yyy objects:-" << end;
// Inner loop over all Yyy associated with this Xxx.
while ( itrYyy.IsValid() (
Yyy* myYyy = itrYyy.Ptr();
cout << " Yyy " << myYyy->Name() << endl;
itrYyy.Next();
}
itrXxx.Next();
}
If you know the result of the mapping is a single member subset, it is a bit tedious to perform the map and then pick up the first (and only) set member so, to allow a shortcut, you can pass the Map request directly to your iterator and have it return a pointer to the first set member.
Important: Sending a Map message to an XxxItr still results it its NavSet being sent its Map message and, as with other forms of selection, results in all the NavSet's iterators being sent their ResetFirst() message.
In our example each Yyy is associated with exactly one Xxx so you could write a loop over all Yyy set members and list their association like this:-
// Undo any selection by mapping in force on Yyy iterator.
// This will also reset the iterator to the start of its range.
itrYyy.Map(0);
while ( itrYyy.IsValid() ) {
Yyy* myYyy = itrYyy.Ptr();
Xxx* myXxx = itrXxx.Map(myYyy);
cout << "Yyy " << myYyy->Name() << " is associated with "
<< myXxx->Name() << end;
itrYyy.Next();
}
Note that supplying a null pointer to NavSet's Map function:-
itrYyy.Map(0);
cancels the mapping selection and, like other changes in selection, resets the iterators.
NavKey SelectPlaneNoTime( Xxx* obj)
{ return obj->PlaneNo() > 100. || obj->Time() < 50.; }
Such a function is not much good if you don't know until execution time what plane number and time limits to impose. You might like to be able to create an object that can hold the limits you want and then use that to select. Actually this isn't too hard to do just using the power of inheritance. Along with the XxxKeyFunc class, the Navigation package also defines the abstract XxxKeyFunctor class that you can inherit from. To pursue the example we could write a functor class MyXxxKeyFunctor:-
class MyXxxKeyFunctor : public XxxKeyFunctor {
public:
MyXxxKeyFunctor(Int_t pLim = 100, Float_t tLim = 50.) :
fPlaneNoLim(pLim),
fTimeLim(tLim)
{ };
~MyXxxKeyFunctor(){ }
virtual NavKey operator()(const Xxx* obj) const;
virtual XxxKeyFunctor* Clone() const {
return new MyXxxKeyFunctor(*this); }
private:
Int_t fPlaneNoLim;
Float_t fTimeLim;
};
It inherits from XxxKeyFunctor and has two state variables fPlaneNoLim and fTimeLim that will hold the limits. These are initialised using the constructor arguments pLim and tLim, and take defaults that correspond to the key function it will replace. It has the function operator overloaded (that's what makes it a functor). Here is its implementation:-
NavKey XxxKeyFunctor::operator()(const Xxx* obj) const {
return obj->PlaneNo() > fPlaneNoLim || obj->Time() < fTimeLim; }
}
It also has a Clone() method that can be used to make copies of itself. In our simple example:-
virtual XxxKeyFunctor* Clone() const {
return new MyXxxKeyFunctor(*this); }
works because the compiler can provide a default copy constructor. If
your function does clever things and allocates memory on the heap then
you had better override this. Note that, although it creates a new
functor of yours (MyXxxKeyFunctor) Clone actually returns a
pointer to the abstract XxxKeyFunctor base class. The reason
that the Clone method is there is that this allows you to safely
create your functors on the stack without worrying about memory leaks
for the Navigation package makes its own copy to be used for as long
as it needs to.
The object is used in place of a function. For example to place a selection plane limit of 20 and a time limit of 10:-
XxxKeyFunc* myKf = myItr.CreateKeyFunc(); // Create a stack based functor and store a clone // in the XxxKeyFunc MyXxxKeyFunc functor(20,10.); mkKf->SetFun(functor); // Now store the XxxKeyFunc myItr.GetSet()->AdoptSelectKeyFunc(myKf); myKf = 0;
Create your functors on the stack to avoid possible memory leaks.
Although functors are probably most useful for selection they can also be used for sorting. As they are programmable they can be as complicated as you like. You could even have a functor single class with multiple modes that could be handle all selection and ordering for the Xxx class and select the required mode at construction time.
The Navigation tools provide a non-invasive way of associating a mask with each member of the set. Masks are of type NavMask::Mask_t which is defined to be UShort_t so you can have up to 16 flags to mark set members in any way you like. Currently the interface is rather crude but can be refined if required. The masks are held in a separate NavMask class that you can access via its owing NavSet:-
NavMask& GetMasks() { return fMasks; }
Once you have a NavMask you can get and set masks using:-
Mask_t GetMask(void* obj) const; void SetMask(Mask_t mask, void* obj);
or set all masks using:-
void SetAllMasks(Mask_t mask);
In all cases obj is the address of the object you want to set. Although this class is meant to be used in conjunction with a NavSet, you can cheat and pass any address which will then be associated with a mask.
As an example the following statements test bit 2 of the mask associated with object currently pointed to by the iterator itr
NavMask& mask = itr.GetSet()->GetMasks();
if ( mask.GetMask(itr.Ptr()) & 1<<2 ) {
cout << "Bit 2 is set 2" << endl;
}
As we have seen, its is possible to apply multiple sort functions and slices as well as applying a selection function. Each of these operations involve changes to the underlying NavSet and might be quite expensive. For example, suppose you first applied a slice (which would do nothing as there is no corresponding sort) and the apply a sort. This activates the slice to reject unwanted entries of the NavSet and then sorts the rest. If you are going to apply multiple operations before you start to access the data you can tell the NavSet not keep up to date, but just to record the operations. The NavSet methods ClearSlice, Slice(NavKey, NavKey), AdoptSelectKeyFunc and AdoptSortKeyFunc and the XxxItr methods SetSortFun and SetSelectFun all have a final optional argument:-
Bool_t update=kTRUE
By setting this to kFALSE, the NavSet is not updated. When you are finished you now have to use the Update method to get things back into sync. For example:-
// Program with the 2 sort functions.
myItr.GetSet()->AdoptSortKeyFunc(myKf1,kTRUE, kFALSE);
myItr.GetSet()->AdoptSortKeyFunc(myKf2,kFALSE,kFALSE);
...
// Apply a couple of slices.
myItr.GetSet()->Slice(1,100., kFALSE);
myItr.GetSet()->Slice(10.,50.,kFALSE);
...
// Add in a selection function.
myItr.GetSet()->AdoptSelectKeyFunc(myKf3, kFALSE);
// Now bring NavSet up to date.
myItr.GetSet()->Update();
As currently implemented, slicing is considered to be part of selection, and as such is more global than sorting. A consequence of this is that each time you:-
myItr.GetSet()->ClearSlice();
you are removing slice selection and this forces a re-sort of the full set.
If, having sorted a set, you want to just loop over a subset which corresponds to a single NavKey value (say myValue), code the loop as follows:-
for ( myItr.Reset();
myItr.IsValid();
myItr.Next() ) {
Int_t comp = myItr.GetNavKey().CompareValue(myValue);
// Quit if we have passed the value and skip if we haven't reached it yet.
if ( comp > 0 ) break;
if ( comp < 0 ) continue;
...
}
This saves time by quiting from the loop once the required value has been passed.
A rewrite of Navigation is planned and the way slicing and sorting interact will be reviewed at that time.
One final word on optimising. If performance is really essential and all you are doing is iterating sequentially then you might consider forgoing any sort and selection features and simply use whatever iteration techniques are available from the underlying set on which NavSet is built. The Navigation package was written to give a full function access but this does come at the price of creating a NavSet which does take time to create and maintain.
Code to do the above is as follows:-
#include "Navigation/NavKey.h"
#include "Navigation/NavSet.h"
...
XxxItr myPlaneItr; // Set up by some code!
// Set up the sort functions.
myPlaneItr.SetSortFun(KeyFromPlaneNo);
myPlaneItr.SetSortFun(KeyFromTime,kFALSE);
myKf = 0;
// Outer loop over plane number
for ( myPlaneItr.Reset();
myPlaneItr.IsValid();
myPlaneItr.NextKey() ) {
// Code to access object at myPlaneItr;
// Inner loop over times
for ( XxxItr myTimeItr(myPlaneItr,kTRUE);
myTimeItr.IsValid();
myTimeItr.Next() }
// Code to access object at myTimeItr;
}
}
You have seen all of the above functions before except the following:-
myPlaneItr.NextKey()
XxxItr myTimeItr(myPlaneItr,kTRUE)
The scheme can be extended 3 or more dimensions by adding a further sort functions, using NextKey for all but the innermost iterator and creating all but the outermost iterator using the special copy constructor with the iterator from the level above.
Although their primary function is to give sequential access to a set, iterators can also give random access using the:-
Bool_t Jump(Int_t index)member function. If the index is valid i.e. is within range and the corresponding object is selected then the iterator moves to the new position and the function returns kTRUE. Otherwise the iterator remains unchanged (which might also be invalid) and kFALSE is returned. E.g.:-
if ( itr.Jump(6) ) cout << "Iterator moved to position 6" << endl; else cout << "Position 6 is invalid" << endl;
You can also save the current index using GetIndex and restore it later:-
Int_t savePos = itr.GetIndex(); ... // Restore position itr.Jump(savePos);In case you were wondering, there is a SetIndex(Int_t index) and it is equivalent to Jump(Int_t index)
Some points to note about jumping:-
For all of the points given above, jumping should be used with caution. It is probably best used without any form of selection and after any required sorting has been applied.
If you are confident that you know the jump will suceed you can use JumpPtr, which both jumps are retrieves the pointer (cf NextPtr):-
cout << "Object at position 6:" << itr.JumpPtr(6)->Print() << endl;
XxxItr myItr2(myItr);
This copies the exact state, including the current position and direction of myItr into the new iterator myItr2. After this they can be operated on independently. Further iterators can be manufactured in the same way. To bring any two back into step just assign one to the other:-
// Move myItr to the current position and direction of myItr2. myItr = myItr2;
You can also tie one iterator to a sub-slice of another. In section 9.2.12 we saw how:-
XxxItr myTimeItr(myPlaneItr,kTRUE)created myTimeItr sliced to the current plane number value associated with myPlaneItr. An alternative way to do after creation of myTimeItr is:-
myTimeItr.SubSlice(myPlaneItr)
Important: Cloned iterators all operate on the same set; changes in sorting and selection will affect them all in the same way. In particular, changes to sort order and selection will cause all iterators to be reset.
If you want your iterators to be truly independent; each with its own sort and select then create iterators from scratch rather than by cloning them.
The navigation tools are primarily designed to navigate stable object structures. The idea is that some Monte Carlo or reconstruction process creates the object structure and also provides a method to create an iterator to allow you to explore the results of the process. Attempting to navigate an object structure that is still being changed is a risky business! To require that an iterator do a complete revalidation of its view of a set (as held in the NavSet), each time you used it, would incur an unreasonable overhead. Instead it assumes that nothing has changed and, if it has, this could result in:-
Some operations will reflect changes, due to the way that the system is implemented. In particular:-
but it would be unwise to rely on these ``accidental'' features.
If you really need to navigate a changing object structure because you are building it and want to use the tools, then you can, at any time, issue a refresh request to the NavSet:-
myItr.GetSet()->Refresh();
This is an expensive operation as it has to rebuild the set, resort, reselect and finally reset all iterators. In case you were wondering about the difference between Refresh and Update (see 9.2.11), after Refresh NavSet will reflect the current state of the underlying object structure while Update will only ensure that the NavSet is consistant with its internal sorting, slicing and selections.
The navigation tools have two types of iterators:-
#include "TCollection.h" TCollection* mySet; // A ROOT container of Xxx objects. // Create a iterator over the set. XxxItr myItr(mySet); // The iterator can also be created from a ROOT iterator // using either a pointer to a TIter:- TIter* myRootItr2 = new TIter(mySet); XxxItr myItr2(myRootItr2); // or the TIter itself:- TIter myRootItr3(mySet); XxxItr myItr3(myRootItr3); // or use a default constructor ... XxxItr myItr; // ... and then attach it to a ROOT container myItr.Attach(mySet);
Note that the last of the examples means that an iterator can be a data member of some class and be built with the default constructor. Of course it just behaves as if its connected to an empty set until the Attach method is used to attach it to a TCollection of the right type of objects. Alternatively it can be initialised by copying another, possibly temporary, iterator to it, e.g.:-
// Create a tempoary iterator just to initialise the data member.
{
XxxItr myItr3(myRootItr3);
myIter = myItr3;
}
#include "Lattice/Lattice.h"
Lattice* myXxxWithYyy; // A Lattice holding a relationship:-
// o A set of Xxx objects on the left
// o A set of Yyy objects on the right
// Create an iterator over the Xxx set.
XxxItr itrXxx(myXxxWithYyy, Lattice::kLeft));
/ Create an iterator over the Yyy set.
YyyItr itrYyy(myXxxWithYyy, Lattice::kRight);
For information on the creation of Lattice object, see 9.2.16.
The concept, and much of the code for the Lattice package, was written by Jon Thaler for the CLEO experiment. A Lattice is an object that can hold relationships between two sets of objects:-
Class Xxx objects <-- Lattice --> Class Yyy objects
The relationship between them can be:-
All lattices are bi-directional; you can navigate in either direction. You update a lattice by giving a relationship in one direction and the lattice automatically builds its inverse.
Although it is possible to create Lattices directly, a helper class, called a LatticeMaker can simplify things for you. For example:-
#include "Lattice/LatticeMaker.h"
LatticeMaker maker;
Lattice* myLat = maker.CreateLattice("Xxx","Yyy", "n:m");
creates a Lattice on the heap between objects of Xxx and Yyy in an n:m relationship. n:m is the default if the last argument is omitted or invalid, other legal values are 1:n and n:1.
Important: LatticeMaker always creates Lattices on the heap and gives them to you; it is your responsibility to delete the Lattice when no longer needed.
Given the Lattice myLat created above, and assuming the declarations:-
Xxx* myObjXxx; Yyy* myObjYyy;
then the statement:-
myLat->ConnectLR(myObjXxx,myObjYyy);
makes a left to right connection between them.
Putting this all together, suppose:-
Bool_t IsAssociated(const Xxx* objXxx, const Yyy* objYyy);
that returns true if the two objects are associated and false otherwise.
then the following code builds a general n:m Lattice between them:-
#include "Lattice/LatticeMaker.h"
LatticeMaker maker;
Lattice* myLat = maker.CreateLattice("Xxx","Yyy", "n:m");
TIter itrXxx(&mySetXxx);
TIter itrYyy(&mySetYyy);
// Get each member of mySetXxx, converting from TObject* to const Xxx*
itrXxx.Reset();
while (
( const Xxx* objXxx = dynamic_cast<const Xxx*>( itrXxx() ) )
){
// Get each member of mySetYyy, converting from TObject* to const Yyy*
itrYyy.Reset();
while (
( const Yyy* objYyy = dynamic_cast<const Yyy*>( itrYyy() ) )
) {
// Form connection if required.
if ( IsAssociated(objXxx,objYyy) ) lat->ConnectLR(objXxx,objYyy);
}
}
This method is so generic that it is built into LatticeMaker itself. However, it does not know about your Xxx and Yyy classes so expects an association function of the form:-
Bool_t AssociateFunc(const TObject* objXxx, const TObject* objYyy);
such a function would be easily built from our IsAssociated function:-
Bool_t AssociateFunc(const TObject* objXxx, const TObject* objYyy) {
const Xxx* myXxx = dynamic_cast<const Xxx*>(objXxx);
const Yyy* myYyy = dynamic_cast<const Yyy*>(objYyy);
// Make sure that the dynamic casts did not return 0!
return myXxx & myYyy & IsAssociated(myXxx,myYyy);
}
then you can build your Lattice like this:-
LatticeMaker maker;
Lattice* myLat = maker.CreateLattice(&mySetXxx,
&mySetYyy,
AssociateFunc ,
"n:m");
as before, the last argument can also be "1:n" and "n:1".
Important: Any member of mySetXxx or mySetYyy that has no association will not appear in the lattice.
For 1:n and n:1 relationships, the build is not very efficient; LatticeMaker has to loop over entries on the side that has single
multiplicity and for each will, on average, have to loop half of the
other side making a total of 
association tests. If n and m
are large, there is a more efficient method that reduces this to 
but requires that each entry in the set that has multiple
associations has a unique
Long_t key and each entry in the set that has single
associations can tell you the key it is associated with. Typical
functions to get these keys might look like this:-
Long_t GetUniqueKey(const TObject* objXxx) {
const Xxx* myXxx = dynamic_cast<const Xxx*>(objXxx);
// If dynamic casts returns 0 return illegal key.
return ( myXxx ) ? myXxx->GetUniqueKey() : -1;
}
Long_t GetAssociateKey(const TObject* objYyy) {
const Yyy* myYyy = dynamic_cast<const Yyy*>(objYyy);
// If dynamic casts returns 0 return a different illegal key.
return ( myYyy ) ? myYyy->GetAssociateKey() : -2;
}
then you can build your Lattice like this-
LatticeMaker maker;
Lattice* myLat = maker.Create1:NLattice(&mySetXxx,
&mySetYyy,
GetUniqueKey ,
GetAssociateKey);
in this case the Lattice has to be 1:n.
Over the years HEP developed a very successful and simple architecture for Monte Carlo and Reconstruction programs. It consisted of dynamic public data structures describing the events and detector that were operated upon by a set of independent processors. As Fortran 77 does not support dynamic data structures, the HEP community developed memory managers for the purpose, the last of these being ZEBRA. These managers came complete with navigational tools to traverse links of the data structure. Powerful those these managers were they had two serious drawbacks:-
Consequently the design and use of banks were very strongly coupled which serious hampered program development. One of the driving forces behind OO methodology was the need to break this coupling between implementation and use. In an OO design the components (objects now instead of banks) control all access and coupling is limited to the public interface the object's support. However this responsibility includes navigation to related objects and this can be unsatisfactory for several reasons:-
The purpose of the MINOS navigational tools is to address all of the above. The tools do not permanently record relationships; the objects retain that responsibility. Indeed they, or some other software element, has to take on new responsibility: the creation of transient (i.e. created as required during execution) navigation objects. However, once that is done the end users see uniform fully functional navigational interface which is independent of the actual implementation.
Much of the foundation, not to mention significant portions of code, come from the Lattice classes which implement arbitrary n:m relationships by Jon Thaler for the CLEO experiment.
This section outlines the functionality of the tools.
Navigation involves two types of activity.
The tools support 1:n navigation, and may eventually support full n:m navigation between pairs of sets.
The tools place no restrictions on the type of object set being navigated and are non-invasive i.e. no changes need to be made to the object's class. This confers an additional advantage as it implies multiple navigational objects operating concurrently. For example, this would mean that the same set could be simultaneously sorted with several different sort criteria.
Finally the tools are type safe, that is to say, although they work for any type of object the user always deals with objects of the correct type and does not have to perform a potentially dangerous cast of a pointer to the right type.
See List of Classes of the Navigation PACKRAT For a description of the classes that implement the tools with the aid of a few simple UML (Unified Modelling Language) diagrams.