Re: [boost] Re: A preliminary proposal: AGG project

From: Douglas Gregor (gregod_at_[hidden])
Date: 2002-05-04 17:56:49

On Saturday 04 May 2002 01:55 pm, you wrote:
> Suppose you have a very simple abstract class:
>
> class vertex_source
> {
> public:
>    virtual void reset_iterator() = 0;
>    virtual pathflag next_vertex(double* x, double* y) = 0;
> };
[snip]
> That's it! With this abstract class and the renderer we can create any
> converters. The only thing we have to obey is to inherit our converter
> classes from vertex_source and to override only two methods.

This interface is semantically equivalent to an InputIterator, and it isn't 
hard to write an adaptor that takes the vertex_source interface and makes an 
InputIterator out of it. Here's an off-the-top-of-the-head example:

struct vertex_type {
  pathflag path;
  double x;
  double y;
};

class vertex_iterator {
public:
  typedef std::input_iterator_tag iterator_category;
  typedef vertex_type value_type;
  typedef value_type& reference;
  typedef value_type* pointer;
  typedef std::ptrdiff_t distance_type;

  vertex_iterator() {}
  vertex_iterator(vertex_source* v) : vs(v) 
  { 
    vs->reset_iterator(); 
    value.path = vs->next_vertex(&value.x, &value.y);
  }

  vertex_iterator(const vertex_iterator& other) : 
    vs(other.vs), value(other.value)
  {
  }

  reference operator*() const { return value; }
  pointer operator->() const { return &value; }

  vertex_iterator& operator++() 
  {
    value.path = vs->next_vertex(&value.x, &value.y);
    return *this;
  }

  vertex_iterator operator++(int)
  {
    vertex_iterator result(*this);
    ++this;
    return result;
  }

private:
  vertex_source* vs;
  value_type value;
};

> The simplest one is affine transformer. This class calculates new
> coordinates according to its affine matrix. It's simplest and straight
> because it does not change the semantics of vertices.
>
> class affine_transformer : public vertex_source
> {
> public:
>     affine_transformer(vertex_source* vs) : source(vs) {}
>     virtual void reset_iterator() { source->reset_iterator(); }
>     virtual pathflag next_vertex(double* x, double* y)
>     {
>         pathflag p = source->next_vertex(x, y);
>         register double tx = *x;
>         *x = tx * m0 + *y * m2 + m4;
>         *y = tx * m1 + *y * m3 + m5;
>         return p;
>     }
>     // . . .
> };

A transformer of this type can be formulated as an iterator adaptor. Using 
the Boost Iterator Adaptors library, the policy would look something like 
this:

struct affine_transform_policy : public boost::default_iterator_policies
{
  float m0, m1, m2, m3, m4, m5;

  template <class IteratorAdaptor>
  vertex_type dereference(const IteratorAdaptor& x) const
  { 
    vertex_type vertex = *x.base();
    return vertex_type(vertex.path, 
                       vertex.x*m0 + vertex.y*m2 + m4,
                       vertex.x*m1 + vertex.y*m3 + m5);
  }
};

Then to add an affine transform to a vertex source iterator VertexIterator 
via an iterator adaptor, use the type:

boost::iterator_adaptor<VertexIterator, affine_transform_policy, vertex_type>

> Jens Maurer says:
> > An interface using "reset_iterator" and "next_vertex"
> > is exactly not STL-like, because it does not allow two
> > iterators on the same underlying container-like object.
> > The STL uses separate iterator classes and a begin() / end()
> > interface on the container, and operator++() on the iterator.
> > This allows dealing with subranges."
>
> I agree with it, and to make it more STL-like the idea must be adjusted.
> But how? It's not easy.
> Graphics is a very scpecific area and often general approaches simply don't
> work here. For example. Suppose we have a completely STL-like interface for
> a very complicated class of constructive area geometry. It's supposed to
> have
> iterator, reverse_iterator and the ability to assing iterators to each
> other and
> start from, say, the middle of the sets of vertices. This interface is much
> harder
> to implement than the simplest one that produces a number of vertices
> consecutively. But the real necessity of this complexity is very very
> little.

"STL-like" doesn't need to mean "Container-like". Iteration through different 
vertex sources may fit different iterator categories: a simple vertex 
container would have an iterator modeling RandomAccessIterator, whereas an 
easily reversible operation might have an iterator modeling 
BidirectionalIterator, and for a _really_ complex vertex generator perhaps 
only an InputIterator would be supported.

You might be interested to look at Boost.Tokenizer (or even the Spirit++ 
parser framework). The notion in these libraries is that you can represent 
different levels of parsing as iterator adaptors, in effect creating a 
"parser pipeline", where the original source is a raw stream of bytes coming 
from a file, which is passed through a scanner/lexer/tokenizer to get 
individual tokens, which are passed through a parser to come up with an AST. 
Different domain, exact same idea.

> The major difference between STL containers and AGG converters is that
> STL containers have as much developed interface as possible, but the number
> of them is restricted. They all have a common iterating mechanism and can
> be used in a number of algorithms. AGG has one (or a few) vertex containers
> (that can be STL ones) and potencially endless number of iterators
> (converters) which will work in a pipeline. They cannot have very complex
> interface because it'll be a real pain to implement custom converters.

STL containers have a complex interface; iterators do not.

> So, now it's time to ask for suggestions how to adjust the idea in order
> make
> it more corresponding with STL and BOOST. For now I cannot invent anything
> appropriate without affecting the efficiency or without increasing the
> complexity
> and the amount of code twice of more.

My vote should be obvious from the above :)

        Doug