atlas  0.6
Public Types | Public Member Functions | Private Attributes | List of all members
atlas::partition::PartitionIterator Class Reference

#include <partition.h>

Public Types

typedef std::vector< unsigned long >::const_iterator SubIterator
typedef std::forward_iterator_tag iterator_category
typedef std::pair< SubIterator, SubIteratorvalue_type
typedef ptrdiff_t difference_type
typedef const value_typepointer
typedef const value_typereference

Public Member Functions

 PartitionIterator (const Partition &)
bool operator== (const PartitionIterator &i) const
bool operator!= (const PartitionIterator &i) const
reference operator* () const
pointer operator-> () const
bool operator() () const
PartitionIteratoroperator++ ()
PartitionIterator operator++ (int)
void rewind ()

Private Attributes

std::vector< unsigned long > d_data
std::vector< SubIteratord_stop
std::pair< SubIterator, SubIteratord_range
std::vector< SubIterator >::const_iterator d_currentEnd

Detailed Description

The idea is that a PartitionIterator gives a convenient way of traversing the classes of a partition. It is intended that PartitionIterators are compared only if they refer to the same partition.

Usage: construct a partition iterator |it| from a partition |pi|, in general in the context of a looping construct

for (PartitionIterator it(pi); it(); ++it) { ... }

Within the body of this loop, |*it| gives a pair of iterators into a vector of integers (in fact into |d_data|) such that iterating from the first to the second traverses a class for |pi|;

for (PartitionIterator::SubIterator jt=it->first; jt!=it->second; ++jt) { ... pi(*jt) is constant during this loop ... }

In fact after the outer loop has advanced |i| times, one has |pi(*jt)==i| throughout the inner loop, provided |pi| as a function is surjective to an initial part of $$. Since the iterator runs through the classes for |pi|, which are non-empty, the inner loop will run at least once in all cases.

The vector d_data contains the integers [0,n[, where n is the size of the set being partitioned, sorted in the order of the partition values. The vector d_stop contains an iterator pointing to the beginning of each class, and a final iterator pointing after the end of d_data. We then only need to return two consecutive elements in d_stop to bound a class.

For convenience a (second-level) iterator |d_currentEnd| into |d_stop| is provided, which always satifies |*d_currentEnd==d_range.second|. In fact instead of |d_range| and |d_currentEnd| one could have maintained a single index |i| such that |d_range| would be given implicitly as |make_pair(stop[i],stop[i+1])|, and |d_currentEnd| as |d_stop.begin()+i+1|.

Since constructing a PartitionIterator requires computing |d_data| which is quite a bit of work (and to a somewhat lesser extent the same holds for copy-constructing or assigning), we provide a |rewind| method that allows restarting a PartitionIterator used in a previous operation.

Member Typedef Documentation

typedef std::forward_iterator_tag atlas::partition::PartitionIterator::iterator_category
typedef std::vector<unsigned long>::const_iterator atlas::partition::PartitionIterator::SubIterator

Constructor & Destructor Documentation

atlas::partition::PartitionIterator::PartitionIterator ( const Partition pi)

Initializes a PartitionIterator ready to run through the classes of pi.

Member Function Documentation

bool atlas::partition::PartitionIterator::operator!= ( const PartitionIterator i) const
void atlas::partition::PartitionIterator::rewind ( )

Member Data Documentation

std::vector<SubIterator>::const_iterator atlas::partition::PartitionIterator::d_currentEnd
std::vector<unsigned long> atlas::partition::PartitionIterator::d_data
std::pair<SubIterator,SubIterator> atlas::partition::PartitionIterator::d_range
std::vector<SubIterator> atlas::partition::PartitionIterator::d_stop

The documentation for this class was generated from the following files: