Non-container Iterators

[Leslie Sanford]

My area of programming is DSP. I write things like filters, oscillators,
envelopes, etc. I've been looking at STL iterators, and what's struck me is
that if I can find ways to model my code using STL's iterator conventions, I
could possibly make my code more economic while probably losing little to no
efficiency.

As an example, an oscillator will have a "phase accumulator." So typically
in a loop I will have something like this:
phaseAccumulator += phaseIncrement;

if(phaseAccumulator >= 1.0f)
{
phaseAccumulator -= 1.0f;
}

output = waveform(phaseAccumulator);
It occurred to me that I could have a phase accumulator iterator. My code
would turn into this:
phaseAccumulator++;

output = waveform(*phaseAccumulator);
Much more compact. Or even better:
std::transform(phaseFirst, phaseLast, outputBuffer, SineWaveform());
Down to just one line of code. Ok, so far, so good. But there is a gray area
I'm concerned about.

I need to keep track of the phase. The phase is state that needs to persist
across iterations. This means that I need to give the iterator a pointer to
the phase variable when I create it so that as it's iterating, it's also
modifying the phase variable. Something like:

// Inside my Oscillator class somewhere:
it = PhaseIterator it(&phase, increment);

// Inside the PhaseIterator class:
PhaseIterator &operator++()
{
*phase += increment;

if(phase >= 1.0f)
{
phase -= 1.0f;
}

return *this;
}
This works, but it means that I can only use one phase iterator at a time.
That's actually not a problem for me since the iterator is only being used
internally by the Oscillator class, but my question is whether this violates
the spirit of STL iterators. Is there a category of iterators (Input
Iterators, perhaps?) that restrict you to using only one iterator at a time
over a collection?

Advancing an iterator doesn't usually involve changing the collection the
iterator belongs to. However, in this case, the collection is the phase
values belonging to the oscillator; the iterator is actually generating the
phase values that drive oscillation. I like this approach, but was wanting
to get some thoughts on this from others.

[Leslie Sanford]

First, my apologies for the double post. Second, my apologies for replying
to my own post. :-)

After further thought, I don't think iterators are the way to model my phase
accumulator. Rather I think the concept of Generator, a nullary function
that returns a value, is a better model. So I came up with this:
class PhaseAccumulator
{
public:
typedef float result_type;

private:
float *phase;
float increment;

public:
PhaseAccumulator(float *phase, float increment)
{
this->phase = phase;
this->increment = increment;
}

result_type operator()()
{
*phase += increment;

if(*phase >= 1.0f)
{
*phase -= 1.0f;
}

return *phase;
}
};
I use unary functions for my waveforms; they argument is the phase. I need
to fed the output of my PhaseAccumulator into a Waveform object. In looking
at the STL, I haven't found an adapter to do this; I could be missing
something. So I wrote my own:
template<typename Generator, typename UnaryFunction>
class NullaryCompose
{
public:
typedef typename Generator::result_type result_type;

private:
Generator myG;
UnaryFunction myF;

public:
NullaryCompose(Generator g, UnaryFunction f) :
myG(g),
myF(f)
{
}

result_type operator()()
{
return myF(myG());
}
};
Which allows me to do this:
PhaseAccumulator phaseAccumulator(&phase, increment);
NullaryCompose<PhaseAccumulator, WaveShapes::Sinenc(phaseAccumulator,
WaveShapes::Sine());

std::generate(&buffer[0], &buffer[100], nc);
I think modeling these sorts of components as function objects makes more
sense than modeling them as iterators.

[regularguage]

Good grief this is frustrating. Viewing this group through Google
Groups, I have apparently triple posted. The third post was *suppose*
to be 1) an apology for double posting, and 2) further thoughts on how
my phase accumulator would be better modeled using STL's idea of a
Generator instead of an Iterator. But I'm wary of reposting that at
this point.

Sorry folks.

[Daniel T.]

"Leslie Sanford" <ja**********@bitemehotmail.comwrote:

My area of programming is DSP. I write things like filters, oscillators,
envelopes, etc. I've been looking at STL iterators, and what's struck me is
that if I can find ways to model my code using STL's iterator conventions, I
could possibly make my code more economic while probably losing little to no
efficiency.

Then you might find this interesting:

class fibonacci: public std::iterator< std::forward_iterator_tag, int >
{
int prev_value, value, max;
public:
fibonacci(): prev_value(0), value(0), max(0) { }
explicit fibonacci(int m): prev_value(0), value(1), max(m) { }
const int operator*() const { return value; }
fibonacci& operator++() {
int tmp = value;
value += prev_value;
prev_value = tmp;
return *this;
}
fibonacci operator++(int) {
fibonacci tmp(*this);
++(*this);
return tmp;
}
friend bool operator==(const fibonacci& lhs, const fibonacci& rhs) {
bool result = false;
if ( lhs.value == 0 && rhs.value == 0 ) result = true;
else if ( rhs.value == 0 && !( lhs.value < lhs.max ) )
result = true;
else if ( lhs.value == 0 && !( rhs.value < rhs.max ) )
result = true;
else if ( lhs.prev_value == rhs.prev_value &&
lhs.value == rhs.value &&
lhs.max == rhs.max )
result = true;
return result;
}
};

bool operator!=(const fibonacci& lhs, const fibonacci& rhs) {
return !(lhs == rhs);
}
int main() {
copy( fibonacci( 20 ), fibonacci(),
ostream_iterator<int>( cout, " " ) );
cout << '\n';
}

As an example, an oscillator will have a "phase accumulator." So typically
in a loop I will have something like this:
phaseAccumulator += phaseIncrement;

if(phaseAccumulator >= 1.0f)
{
phaseAccumulator -= 1.0f;
}

output = waveform(phaseAccumulator);
It occurred to me that I could have a phase accumulator iterator. My code
would turn into this:
phaseAccumulator++;

output = waveform(*phaseAccumulator);
Much more compact. Or even better:
std::transform(phaseFirst, phaseLast, outputBuffer, SineWaveform());
Down to just one line of code. Ok, so far, so good. But there is a gray area
I'm concerned about.

I need to keep track of the phase. The phase is state that needs to persist
across iterations. This means that I need to give the iterator a pointer to
the phase variable when I create it so that as it's iterating, it's also
modifying the phase variable. Something like:

// Inside my Oscillator class somewhere:
it = PhaseIterator it(&phase, increment);

// Inside the PhaseIterator class:
PhaseIterator &operator++()
{
*phase += increment;

if(phase >= 1.0f)
{
phase -= 1.0f;
}

return *this;
}
This works, but it means that I can only use one phase iterator at a time.

Not if you put 'phase' inside the iterator. Then you can give two
iterators the same phase and increment and advance each of them a
different amount, and they will each be at a different spot in the
"container".

The key is to provide a sentinel iterator. In your case, the sentinel
can be a PhaseIterator that has an increment of 0.

class PhaseIterator : public std::iterator< std::forward_iterator_tag,
int >
{
float phase;
float increment;
int step;
int max;
public:
PhaseIterator(): phase(0), increment(0), step(0), max(0) { }
explicit PhaseIterator(float i, int m):
phase(0), increment(i), step(0), max(m) { }
const float operator*() const { return phase; }
PhaseIterator& operator++() {
phase += increment;
if ( phase >= 1.0f )
phase -= 1.0f;
++step;
return *this;
}
PhaseIterator operator++(int) {
PhaseIterator tmp(*this);
++(*this);
return tmp;
}
friend bool operator==(const PhaseIterator& lhs,
const PhaseIterator& rhs) {
bool result = false;
if ( lhs.phase == rhs.phase && lhs.increment == rhs.increment )
result = true;
else if ( rhs.increment == 0 && !( lhs.step < lhs.max ) )
result = true;
else if ( lhs.increment == 0 && !( rhs.step < rhs.max ) )
result = true;
return result;
}
};

bool operator!=(const PhaseIterator& lhs, const PhaseIterator& rhs) {
return !(lhs == rhs);
}
int main() {
copy( PhaseIterator( 0.07, 20 ), PhaseIterator(),
ostream_iterator<float>( cout, " " ) );
cout << '\n';
}

[Leslie Sanford]

"Daniel T." wrote:

"Leslie Sanford" wrote:

>My area of programming is DSP. I write things like filters, oscillators,
envelopes, etc. I've been looking at STL iterators, and what's struck me
is that if I can find ways to model my code using STL's iterator
conventions, I could possibly make my code more economic while
probably losing little to no efficiency.

Then you might find this interesting:

class fibonacci: public std::iterator< std::forward_iterator_tag, int >

<snip>

Yes, indeed. That is very interesting.

<snip>

>I need to keep track of the phase. The phase is state that needs to
persist across iterations. This means that I need to give the iterator a
pointer to the phase variable when I create it so that as it's iterating,
it's also modifying the phase variable. Something like:

// Inside my Oscillator class somewhere:
it = PhaseIterator it(&phase, increment);

// Inside the PhaseIterator class:
PhaseIterator &operator++()
{
*phase += increment;

if(phase >= 1.0f)
{
phase -= 1.0f;
}

return *this;
}
This works, but it means that I can only use one phase iterator at a
time.

Not if you put 'phase' inside the iterator. Then you can give two
iterators the same phase and increment and advance each of them a
different amount, and they will each be at a different spot in the
"container".

Understood.

The key is to provide a sentinel iterator. In your case, the sentinel
can be a PhaseIterator that has an increment of 0.

In this case, there is no sentinel iterator as an oscillator, which a phase
accumulator drives, can cycle indefinitely, a kind of circular buffer, I
suppose.

Is it acceptable for an iterator to never reach an "end"? I would have
another way for testing for the end of the loop, specifically the end of the
buffer that I'm filling. I should be able to increment the phase iterator
indefinitely.

while(first != last)
{
*first = *phase;

phase++;
first++;
}

Since (triple) posting, I've been giving this approach some thought, and I
was wondering if a Generator would be a more appropriate model than an
Iterator to represent a phase accumulator.

http://www.sgi.com/tech/stl/Generator.html

class PhaseAccumulator
{
public:
typedef float result_type;

private:
float phase;
float increment;

public:
PhaseAccumulator(float phase, float increment)
{
this->phase = phase;
this->increment = increment;
}

result_type operator()()
{
phase += increment;

if(phase >= 1.0f)
{
phase -= 1.0f;
}

return phase;
}
};

I can have a Square waveform represented as a unary function:

typedef std::unary_function<float, floatWaveShapeBase;

struct Square : public WaveShapeBase
{
result_type operator()(argument_type phase) const
{
assert(phase >= 0.0f && phase < 1.0f);

return phase < 0.5f ? -1.0f : 1.0f;
}
};

And use both in a loop to fill a buffer:

class Oscillator
{
PhaseAccumulator phase;
Square wave;

public:
// Stuff...

void Process(float *first, float *last)
{
while(first != last)
{
*first = wave(phase());

first++;
}
}
}

Maybe this is a more appropriate approach given the concepts involved?

[mlimber]

On Jul 24, 11:18*pm, "Leslie Sanford" <[e-mail]>
wrote:

In this case, there is no sentinel iterator as an oscillator, which a phase
accumulator drives, can cycle indefinitely, a kind of circular buffer, I
suppose.

Is it acceptable for an iterator to never reach an "end"? I would have
another way for testing for the end of the loop, specifically the end of the
buffer that I'm filling. I should be able to increment the phase iterator
indefinitely.

while(first != last)
{
* * *first = *phase;

* * phase++;
* * first++;

}

Since (triple) posting, I've been giving this approach some thought, and I
was wondering if a Generator would be a more appropriate model than an
Iterator to represent a phase accumulator.

http://www.sgi.com/tech/stl/Generator.html

class PhaseAccumulator
{
public:
* * typedef float result_type;

private:
* * float phase;
* * float increment;

public:
* * PhaseAccumulator(float phase, float increment)
* * {
* * * * this->phase = phase;
* * * * this->increment = increment;
* * }

* * result_type operator()()
* * {
* * * * phase += increment;

* * * * if(phase >= 1.0f)
* * * * {
* * * * * * phase -= 1.0f;
* * * * }

* * * * return phase;
* * }

};

I can have a Square waveform represented as a unary function:

typedef std::unary_function<float, floatWaveShapeBase;

struct Square : public WaveShapeBase
{
* * result_type operator()(argument_type phase) const
* * {
* * * * assert(phase >= 0.0f && phase < 1.0f);

* * * * return phase < 0.5f ? -1.0f : 1.0f;
* * }

};

And use both in a loop to fill a buffer:

class Oscillator
{
* * PhaseAccumulator phase;
* * Square wave;

* * public:
* * * * // Stuff...

* * void Process(float *first, float *last)
* * {
* * * * while(first != last)
* * * * {
* * * * * * *first = wave(phase());

* * * * * * first++;
* * * * }
* * }

}

Maybe this is a more appropriate approach given the concepts involved?

Since the phase can't "end" in any meaningful sense, a generator may
be a more appropriate design pattern. Pseudo-random number generators
(eventually) loop, too, and they're commonly used as generator
functors. That being said, there certainly are generator-style
iterators out there, e.g. boost::counting_iterator:

http://www.boost.org/doc/libs/1_35_0..._iterator.html

Using something like that approach, your oscillator class might look
like:

void Oscillator::Process(float *begin, float *end)
{
// Generate
std::transform(
phase.begin(),
phase.end( std::distance(begin,end) ),
begin,
Square );
}

I assume the phase has been given counting_iterator-like support,
where the end() function takes a parameter telling it how many times
to increment. Note also that you could convert your square wave
functor to an ordinary function with the signature float Square(float)
since it doesn't take any constructor parameters or maintain mutable
state. The member variable for that functor is overkill.

The down-side to this approach is that the use of std::transform()
with a generator-style iterator to generate is takes some thinking,
and one of our goals for code is (or, should be) to make it readable.
The names of the standard functions are intended to communicate your
meaning rather than obscure it (cf. http://www.ddj.com/cpp/184401446),
but generator-style iterators cut against the grain in a circumstance
like this.

A generator approach: Using functional composition [let's call ours
my_compose(f,g) = f(g())], whose implementation is relatively
straightforward and similar to the common extension to the STL (e.g.,
http://www.sgi.com/tech/stl/unary_compose.html), one can make this
clearer on first reading:

std::generate( begin, end, my_compose( Square, phase ) );

Now fewer tricks are being played, and its meaning should be clearer
to someone reading your code down the line (which could be you).

Cheers! --M

[Daniel T.]

On Jul 24, 11:18*pm, "Leslie Sanford" <[e-mail]>
wrote:

"Daniel T." wrote:

"Leslie Sanford" wrote:

My area of programming is DSP. I write things like filters, oscillators,
envelopes, etc. I've been looking at STL iterators, and what's struck me
is that if I can find ways to model my code using STL's iterator
conventions, I could possibly make my code more economic while
probably losing little to no efficiency.

Then you might find this interesting:

class fibonacci: public std::iterator< std::forward_iterator_tag, int >

<snip>

Yes, indeed. That is very interesting.

<snip>

I need to keep track of the phase. The phase is state that needs to
persist across iterations. This means that I need to give the iteratora
pointer to the phase variable when I create it so that as it's iterating,
it's also modifying the phase variable. Something like:

// Inside my Oscillator class somewhere:
it = PhaseIterator it(&phase, increment);

// Inside the PhaseIterator class:
PhaseIterator &operator++()
{
* * *phase += increment;

* * *if(phase >= 1.0f)
* * {
* * * * phase -= 1.0f;
* * }

* * return *this;
}

This works, but it means that I can only use one phase iterator at a
time.

Not if you put 'phase' inside the iterator. Then you can give two
iterators the same phase and increment and advance each of them a
different amount, and they will each be at a different spot in the
"container".

Understood.

The key is to provide a sentinel iterator. In your case, the sentinel
can be a PhaseIterator that has an increment of 0.

In this case, there is no sentinel iterator as an oscillator, which a phase
accumulator drives, can cycle indefinitely, a kind of circular buffer, I
suppose.

Is it acceptable for an iterator to never reach an "end"? I would have
another way for testing for the end of the loop, specifically the end of the
buffer that I'm filling. I should be able to increment the phase iterator
indefinitely.

while(first != last)
{
* * *first = *phase;

* * phase++;
* * first++;

}

Since (triple) posting, I've been giving this approach some thought, and I
was wondering if a Generator would be a more appropriate model than an
Iterator to represent a phase accumulator.

http://www.sgi.com/tech/stl/Generator.html

class PhaseAccumulator
{
public:
* * typedef float result_type;

private:
* * float phase;
* * float increment;

public:
* * PhaseAccumulator(float phase, float increment)
* * {
* * * * this->phase = phase;
* * * * this->increment = increment;
* * }

* * result_type operator()()
* * {
* * * * phase += increment;

* * * * if(phase >= 1.0f)
* * * * {
* * * * * * phase -= 1.0f;
* * * * }

* * * * return phase;
* * }

};

I can have a Square waveform represented as a unary function:

typedef std::unary_function<float, floatWaveShapeBase;

struct Square : public WaveShapeBase
{
* * result_type operator()(argument_type phase) const
* * {
* * * * assert(phase >= 0.0f && phase < 1.0f);

* * * * return phase < 0.5f ? -1.0f : 1.0f;
* * }

};

And use both in a loop to fill a buffer:

class Oscillator
{
* * PhaseAccumulator phase;
* * Square wave;

* * public:
* * * * // Stuff...

* * void Process(float *first, float *last)
* * {
* * * * while(first != last)
* * * * {
* * * * * * *first = wave(phase());

* * * * * * first++;
* * * * }
* * }

}

Maybe this is a more appropriate approach given the concepts involved?

That sounds like it would work. Then your process function can be
replaced by the generate algorithm.

float arr[20];
generate( arr, arr + 20, PhaseAccumulator(0, 0.3) );

or better:

vector< float arr;
generate_n( back_inserter( arr ), 20, PhaseAccumulator(0, 0.3) );

But if you make a powerful enough PhaseAccumulator iterator, you won't
*need* to fill the array with values, you can use the iterator
directly over the calculated container.

[Leslie Sanford]

"mlimber" wrote:

>
A generator approach: Using functional composition [let's call ours
my_compose(f,g) = f(g())], whose implementation is relatively
straightforward and similar to the common extension to the STL (e.g.,
http://www.sgi.com/tech/stl/unary_compose.html), one can make this
clearer on first reading:

std::generate( begin, end, my_compose( Square, phase ) );

I like this approach; the idea of function composition is appealing. The
problem is handling state. The waveform function object is stateless, a true
function. However, the phase accumulator has state, specifically the value
of its phase. Say I have the following:

void Oscillator::Process(float *begin, float *end)
{
// Assumes a phase member variable.
std::generate(begin, end, my_compose(Square(), phase);
}

Each time Process is called the phase needs to pick up from where it left
off with the previous call. However, 'phase' is passed in by value, so the
phase accumulator that's actually getting advanced by generate is a copy of
the original. The end result is that each time Process is called, phase
starts at the same place.

I see a couple of ways around this. Design the phase accumulator so that it
takes a pointer to the actual phase variable:

// Inside the Oscillator class..

// Member variable.
float phase;

//...

void Oscillator::Process(float *begin, float *end)
{
std::generate(begin, end, my_compose(Square(),
PhaseAccumulator(&phase));
}

This ensures that the phase value that's getting incremented persists
between calls since the PhaseAccumulator is incrementing the pointer
variable.

I suppose this solution is ok.

Another approach is to somehow update the phase accumulator after generate
has done its job:

void Oscillator::Process(float *begin, float *end)
{
MyCompose<Square, PhaseAccumulatormc(Square(), phase);

std::generate(begin, end, mc);

// Assumes our custom compose template exposes the generator function
object.
phase = mc.generator;
}

This works as well. Another way is to explicitely tell the generate function
to treat the phase accumulator object as a reference, but then I'm pretty
sure I'd lose inlining in that case. Things would start to look ugly at that
point anyway.

Also, we can forego the convenience of using generate and simply write the
loop ourselves using the same member variables:

void Oscillator::Process(float *first, float *last)
{
while(first != last)
{
// Assumes phase and wave are member variables.
*first = wave(phase());

first++;
}
}