next up previous contents index
Next: STL Iterator Wrapper ( Up: Graphs and Iterators Previous: Comparison Predicate ( CompPred   Contents   Index


Observer Node Iterator ( ObserverNodeIt )

Definition

An instance it of class ObserverNodeIt<Obs,Iter> is an observer iterator. Any method call of iterators will be ``observed'' by an internal object of class Obs.

Class ObserverEdgeIt and ObserverAdjIt are defined analogously, i.e. can be used for edge iterators or adjacency iterators, respectively.

Precondition: The template parameter Iter must be a node iterator.

#include < LEDA/graph _iterator.h >

Creation

ObserverNodeIt<Obs,Iter> it introduces a variable it of this class, not bound to an observer or iterator.

ObserverNodeIt<Obs,Iter> it(Obs& obs, Iter base_it)
    introduces a variable it of this class bound to the observer obs and base_it.

Precondition: Obs must have methods observe_constructor(), observe_forward(), observe_update(). These three methods may have arbitrary return types (incl. void).

Operations

void it.init(Obs obs, Iter base_it)
    initializes it, which is bound to obs and base_it afterwards.

Precondition: it is not bound to an observer or iterator.

Obs& it.get_observer() returns a reference to the observer to which it is bound.

Example

First two simple observer classes. The first one is a dummy class, which ignores all notifications. The second one merely counts the number of calls to operator++ for all iterators that share the same observer object through copy construction or assignment (of course, a real implementation should apply some kind of reference counting or other garbage collection).

In this example, the counter variable _count of class SimpleCountObserver will be initialized with the counter variable _count of class DummyObserver, i.e. the variable is created only once.


template <class Iter>
class DummyObserver {
  int* _count;
public:
  DummyObserver() : _count(new int(0)) { }
  void notify_constructor(const Iter& ) { }
  void notify_forward(const Iter& ) { }
  void notify_update(const Iter& ) { }
  int  counter() const { return *_count; }
  int* counter_ptr() const { return _count; }
  bool operator==(const DummyObserver& D) const {
    return _count==D._count; }
};
    
template <class Iter, class Observer>
class SimpleCountObserver {
  int*  _count;
public:
  SimpleCountObserver() : _count(new int(0)) { }
  SimpleCountObserver(Observer& obs) :
    _count(obs.counter_ptr()) { }
  void notify_constructor(const Iter& ) { }
  void notify_forward(const Iter& ) { ++(*_count); }
  void notify_update(const Iter& ) { }
  int  counter() const {  return *_count; }
  int* counter_ptr() const { return _count; }
  bool operator==(const SimpleCountObserver& S) const {
    return _count==S._count; }
};

Next an exemplary application, which counts the number of calls to operator++ of all adjacency iterator objects inside dummy_algorithm. Here the dummy observer class is used only as a ``Trojan horse,'' which carries the pointer to the counter without affecting the code of the algorithm.


template<class Iter>
bool break_condition (const Iter&) { ... }
    
template<class ONodeIt, class OAdjIt>
void  dummy_algorithm(ONodeIt& it, OAdjIt& it2) {
  while (it.valid()) {
    for (it2.update(it); it2.valid() && !break_condition(it2); ++it2)
    ++it;
  }
}
    
int write_count(graph& G) {
  typedef DummyObserver<NodeIt>                  DummyObs;
  typedef SimpleCountObserver<AdjIt,DummyObs>    CountObs;
  typedef ObserverNodeIt<DummyObs,NodeIt>        ONodeIt;
  typedef ObserverAdjIt<CountObs,AdjIt>          OAdjIt;
      
  DummyObs observer;
  ONodeIt   it(observer,NodeIt(G));
  CountObs  observer2(observer);
  OAdjIt    it2(observer2,AdjIt(G));
  dummy_algorithm(it,it2);
  return it2.get_observer().counter();
}


next up previous contents index
Next: STL Iterator Wrapper ( Up: Graphs and Iterators Previous: Comparison Predicate ( CompPred   Contents   Index
LEDA research project
2000-02-09