Circulator Concept Reference

Definition

A Circulator is similar to an Iterator, with the difference that it is designed for circular data structures.

Circulators

Iterators in the STL were tailored for linear sequences. The specialization for circular data structures leads to slightly different requirements which we will summarize in the circulators concept. The main difference is that a circular data structure has no natural past-the-end value. As a consequence, a container supporting circulators will not have an end()-member function. The semantic of a circulator range differs from the semantic of an iterator range. For a circulator c the range [c, c) denotes the sequence of all elements in the data structure. For iterators, this range defines the empty sequence. A separate test for an empty sequence has been added to the circulator requirements: A comparison c == NULL for a circulator c is true for an empty sequence. As for C++, we recommend the use of 0 instead of NULL.

Circulators

Similar to STL iterators, we distinguish between forward, bidirectional, and random access circulatorsInput circulators are a contradiction, since any circulator is supposed to return once to itself. Output circulators are not supported since they would be indistinguishable from output iterators.. Most requirements for circulators are equal to those for iterators. We present the changes, please refer to [[2], chapter 18 or [1]] for the iterator requirements.

Past-the-end value: There is no past-the-end value for circulators.

Singular values: There are no singular values for circulatorsSince circulators must be implemented as classes anyway, there is no need to allow singular values for them. An un-initalized circulator does not have a singular value, but is supposed to refer to an empty sequence.

Empty sequence: The comparison c == NULL (or c == 0) for a circulator c is true if c denotes an empty sequence, and false otherwise.

Dereferenceable values: A circulator that does not denote an empty sequence is dereferenceable.

Reachability: Each dereferenceable circulator can reach itself with a finite and non-empty sequence of applications of operator++.

Ranges: For any circulator c the range [c, c) is a valid range. If the circulator refers to an empty sequence, the range [c, c) denotes the empty range. Otherwise the circulator is dereferenceable and the range [c, c) denotes the sequence of all elements in the data structure. Remark: When a circulator is used in a place of an iterator, as, for example, with an STL algorithm, it will work as expected with the only exception that, in STL algorithms, the range [c, c) denotes always the empty range. This is not a requirement, but a consequence of the requirements stated here and the fact that the STL requirements for iterator ranges are based on the operator++ and the operator==, which we use for circulators as well. In principle, we face here the difference between a while loop and a do-while loop.

Types: For a circulator of type c the following local types are required:

C::value_type	value type the circulator refers to.
C::reference	reference type used for the return type of C::operator*().
C::pointer	pointer type used for the return type of C::operator->().
C::size_type	unsigned integral type that can hold the size of a sequence
C::difference_type	signed integral type that can hold the distance between two circulators.
C::iterator_category	circulator category.

Forward Circulators

In the following, we assume that a and b are circulators of type C, r is of type C& (is assignable), and T denotes the value type of C. Let D be the distance type of C. As for C++, we recommend the use of 0 instead of NULL.

C()	a circulator equal to NULL denoting an empty sequence.
a == NULL	Returns true if a denotes an empty sequence, false otherwise.
	For simplicity, NULL == a is not required. The
	behavior for comparisons with pointer-like values different than NULL
	is undefined. A runtime assertion is recommended.
a != NULL	Returns !(a == NULL).
++r	Like for forward iterators, but a dereferenceable circulator r will always
	be dereferenceable after ++r (no past-the-end value). Precondition: r
	does not denote an empty sequence.
r++	Same as for ++r.
C::iterator_category	circulator category Forward_circulator_tag.

Bidirectional Circulators

The same requirements as for the forward circulators hold for bidirectional iterators with the following change of the iterator category:

C::iterator_category

circulator category Bidirectional_circulator_tag.

Random Access Circulators

The same requirements as for the bidirectional circulators hold for random access iterators with the following changes and extensions.

The idea of random access extends naturally to circulators using equivalence classes modulus the length of the sequence. With this in mind, the additional requirements for random access iterators hold also for random access circulators. The only exception is that the random access iterator is required to provide a total order on the sequence, which a circulator cannot provideOne might define an order by splitting the circle at a fixed point, e.g. the start circulator provided from the data structure. This is what the adaptor to iterators will do. Nonetheless, we do not require this for circulators..

The difference of two circulators is not unique as for iterators. A reasonable requirement demands that the result is in a certain range [1-size, size-1], where size is the size of the sequence, and that whenever a circulator a is fixed that the differences with all other circulators of the sequence form a consistent ordering.

For the adaptor to iterators a minimal circulator d_min is required for which the difference c - d_min to all other circulators c is non negative.

b - a	limited range and consistent ordering as explained above.
a.min_circulator()	returns the minimal circulator from the range [a,a).
C::iterator_category	circulator category Random_access_circulator_tag.

Const Circulators

As with iterators, we distinguish between circulators and const circulators. The expression *a = t with t of type T is valid for mutable circulators. It is invalid for const circulators.

Circulators in Container Classes

For a container x of type X that supports circulators c the following naming convention is recommended:

X::Circulator	the type of the mutable circulator.
X::Const_circulator	the type of the const circulator.
c = x.begin()	the start circulator of the sequence. It is of type X::Circulator for a
	mutable container or X::Const_circulator for a const container.

If a container will support iterators and circulators, the member function circulator_begin() is proposed. However, the support of iterators and circulators simultaneously is not recommended, since it would lead to fat interfaces. The natural choice should be supported, the other concept will be available through adaptors.

Example

A generic contains function accepts a range of circulators and a value. It returns true if the value is contained in the sequence of items denoted by the range of circulators. As usual for circular structures, a do-while loop is preferable, such that for the specific input, c == d, all elements in the sequence are reached. Note that the example simplifies if the sequence is known to be non-empty, which is for example the common case in polyhedral surfaces where vertices and facets have at least one incident edge.

template <class Circulator, class T> 
bool contains( Circulator c, Circulator d, const T& value) { 
  if (c != 0) { 
    do { 
      if (*c == value) 
        return true; 
    } while (++c != d); 
  } 
  return false; 
} 

Examples:

Circulator/circulator_prog1.cpp, and Circulator/circulator_prog2.cpp.