Iterator calculation
What I'm thinking of is to make use of std::for_each() and define my own iterators and my own functor object for the partial results. The iterator will have an operator ++() that will move forwards one or two balls depending on the score of the ball. The Score functor object will have an operator()( const Frame & ) that will add the scores of the next two or three balls to its internal accumulator.
This should get called something like the below:
int calculate_iterator( const std::vector< int > &balls ) {
return std::for_each( Frame( balls.begin(), balls,end() ), Frame( balls.end() ), Score() );
}The first Frame is the one that will get changed as the algorithm moves forwards. It needs to know where the end of the collection is so that when Score looks forwards it knows not to fall off the end of the container. The second Frame only needs to know where the end of the container is.
Now, having written this out I can see that there is a much simpler way of doing this. Only Score needs to worry about falling off the end as it is the only one that is going to look forwards—but only if we assume that the vector is well formed. I.e. that there is no chance of Frame::operator ++() falling off the end. I'm not completely happy about making that assumption so the only change will be that Score will also get given the iterator marking the end of the container.
This leads me to a first cut of something like this:
template< typename const_iterator >
class Frame : private const_iterator {
public:
Frame( const_iterator b, const_iterator e )
: const_iterator( b ), end( e ) {
}
Frame( const_iterator e )
: const_iterator( e ), end( e ) {
}
using const_iterator::operator ++;
using const_iterator::operator !=;
class Score {
public:
Score( const_iterator e )
: score( 0 ), end( e ) {
}
void operator()( const Frame & ) {
}
operator int() const {
return score;
}
private:
int score;
const const_iterator end;
};
private:
const const_iterator end;
};
template< typename const_iterator >
int calculate_score( const_iterator begin, const_iterator end ) {
return std::for_each( Frame< const_iterator >( begin, end ), Frame<const_iterator >( end ), Frame< const_iterator >::Score( end ) );
}I'm not entirely sure whether the Score constructor should be taking a const_iterator or a Frame iterator, but that isn't the most serious problem.
std::for_each takes a functor object which is passed the current value not the current iterator. This isn't going to work as I was going to have the functor object doing the calculation, but it isn't all over. I can write my own operator *() in the Frame iterator which does the looking around and calculates the score for that ball. I wonder if that means I can get rid of Score completely? Maybe there is an accumulator that I can make use of in the STL.
A search through the documentation shows me that there isn't an accumulator object that I can make use of, but there is an algorithm std::accumulate that I can use:
template<class InputIterator, class Type>
Type accumulate(
InputIterator _First,
InputIterator _Last,
Type _Val
);This is going to be very similar to my use of std::for_each, but actually simplifies things a lot. I can throw away that Score object and do this instead:
template< typename const_iterator >
class Frame : private const_iterator {
public:
Frame( const_iterator b, const_iterator e )
: const_iterator( b ), end( e ) {
}
Frame( const_iterator e )
: const_iterator( e ), end( e ) {
}
using const_iterator::operator ++;
using const_iterator::operator !=;
using const_iterator::operator *;
private:
const const_iterator end;
};
template< typename const_iterator >
int calculate_score( const_iterator begin, const_iterator end ) {
return std::accumulate( Frame< const_iterator >( begin, end ), Frame< const_iterator >( end ), const_iterator::value_type() );
}This doesn't quite compile though. I get a wonderfully obtuse compile error.
c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\numeric(16) : error C2243: 'type cast' : conversion from 'Frame<const_iterator> *__w64 ' to 'const std::vector<_Ty>::const_iterator &' exists, but is inaccessible
with
[
const_iterator=std::vector<int>::const_iterator
]
and
[
_Ty=int
]
c:\Dev\Test\VectorBowls\VectorBowling\iterator.cpp(28) : see reference to function template instantiation '_Ty std::accumulate<Frame<const_iterator>,_Ty>(_InIt,_InIt,_Ty)' being compiled
with
[
_Ty=int,
const_iterator=std::vector<int>::const_iterator,
_InIt=Frame<std::vector<int>::const_iterator>
]
c:\Dev\Test\VectorBowls\VectorBowling\iterator.cpp(33) : see reference to function template instantiation 'int calculate_score<std::vector<_Ty>::const_iterator>(const_iterator,const_iterator)' being compiled
with
[
_Ty=int,
const_iterator=std::vector<int>::const_iterator
]It is of course this sort of error message that gives C++ such a bad name. Changing the inheritance from private to public sorts the error (if I put in a typename I'd missed out too). This means that I've probably forgotten a using that the algorithm makes use of or I actually need to write a minimal implementation for the operators.
The only operator that gets passed a Frame is operator != so I think blocking this out will sort it:
bool operator !=( const Frame &f ) const {
return const_iterator::operator !=( f );
}And it now compiles. Running the test harness on it gives me:
Pass Pass Pass Pass Failed: 20/20 not 30: 10,10 Pass Failed: 18/18 not 24: 6,4,6,2 Failed: 18/18 not 24: 6,4,6,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 Failed: 120/120 not 300: 10,10,10,10,10,10,10,10,10,10,10,10 Failed: 120/120 not 200: 10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10,9,1 Failed: 120/120 not 200: 9,1,10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10
This is fine so far. It tells me that so far we are just summing up all of the balls. Exactly what we expected to get.
The next thing we can do is to implement operator ++ so that we iterate jumping from one frame to the next. My first version of this was:
void operator ++() {
if ( const_iterator::operator *() == 10 ) const_iterator::operator ++();
const_iterator::operator ++();
}Which caused the third test to crash. I need to make sure that we don't run off the end of the container:
void operator ++() {
if ( const_iterator::operator *() == 10 ) const_iterator::operator ++();
if ( *this != end ) const_iterator::operator ++();
}This gives me some slightly strange results:
Pass Pass Pass Pass Failed: 10/10 not 30: 10,10 Pass Failed: 18/18 not 24: 6,4,6,2 Failed: 18/18 not 24: 6,4,6,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 Failed: 60/60 not 300: 10,10,10,10,10,10,10,10,10,10,10,10 Failed: 86/86 not 200: 10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10,9,1 Failed: 95/95 not 200: 9,1,10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10
I was expecting the fifth test to return twenty and not ten; test seven should have given me twelve. I've got the test for moving wrong. If the first ball isn't ten we should move two balls forwards. I have the test backwards:
void operator ++() {
if ( const_iterator::operator *() != 10 ) const_iterator::operator ++();
if ( *this != end ) const_iterator::operator ++();
}This is giving me the failures that I was expecting:
Pass Pass Pass Pass Failed: 20/20 not 30: 10,10 Failed: 41/41 not 90: 8,1,7,2,6,3,5,4,4,5,3,6,2,7,1,8,2,7,3,6 Failed: 12/12 not 24: 6,4,6,2 Failed: 12/12 not 24: 6,4,6,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 Failed: 120/120 not 300: 10,10,10,10,10,10,10,10,10,10,10,10 Failed: 94/94 not 200: 10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10,9,1 Failed: 94/94 not 200: 9,1,10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10
We are going to use Frame::operator * in order to return not the score for the current ball, but the score for the current ball as if it was the first in the frame. This is the same concept that the orignal J version used. We need to be careful about running off the end of the array again so we get a first cut of this:
typename const_iterator::value_type operator *() const {
const_iterator pos( *this );
value_type score( *pos );
if ( ++pos != end ) score += *pos;
if ( mark() && ++pos != end ) score += *pos;
return score;
}This implementation introduces a new member, mark(), which will tell us if we need to include the third ball or not. I expect the implementation to be fairly simple:
bool mark() const {
const_iterator pos( *this );
value_type score( *pos );
if ( score == 10 )
return true;
else if ( ++pos != end )
return *pos + score == 10;
else
return false;
}My test run didn't quite give the results I expected:
Pass Pass Failed: 393428/393428 not 10: 10 Pass Pass Pass Pass Pass Failed: -33685689/-33685689 not 300: 10,10,10,10,10,10,10,10,10,10,10,10 Failed: 230/230 not 200: 10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10,9,1 Failed: -33685789/-33685789 not 200: 9,1,10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10
This looks like I'm either reading off the end of the vector or I don't have something initialised properly elsewhere. I'll do what I should have done to start with which is to use a null mark() implementation which just always returns false.
Doing this gives me:
Pass Pass Pass Pass Pass Pass Failed: 18/18 not 24: 6,4,6,2 Failed: 18/18 not 24: 6,4,6,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 Failed: 230/230 not 300: 10,10,10,10,10,10,10,10,10,10,10,10 Failed: 154/154 not 200: 10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10,9,1 Failed: 145/145 not 200: 9,1,10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10
And always returning true gives me:
Pass Failed: 458960/458960 not 0: 0,0,0 Failed: 393428/393428 not 10: 10 Pass Pass Failed: 123/123 not 90: 8,1,7,2,6,3,5,4,4,5,3,6,2,7,1,8,2,7,3,6 Pass Pass Failed: -33685689/-33685689 not 300: 10,10,10,10,10,10,10,10,10,10,10,10 Failed: 230/230 not 200: 10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10,9,1 Failed: -33685789/-33685789 not 200: 9,1,10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10
I think this means my code for adding in the third ball is wrong. Taking a look at it again I've made a classic logic error. As I move to the second ball I do check that I haven't gone past the end of the container before adding the score in, but then I don't act on that fact in those cases where I should be scoring a third ball. The if statement needs an else which returns the score.
typename const_iterator::value_type operator *() const {
const_iterator pos( *this );
value_type score( *pos );
if ( ++pos != end ) score += *pos; else return score;
if ( mark() && ++pos != end ) score += *pos;
return score;
}And this now gives me more likely looking values even if they are still wrong:
Pass Pass Pass Pass Pass Failed: 123/123 not 90: 8,1,7,2,6,3,5,4,4,5,3,6,2,7,1,8,2,7,3,6 Pass Pass Failed: 330/330 not 300: 10,10,10,10,10,10,10,10,10,10,10,10 Failed: 230/230 not 200: 10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10,9,1 Failed: 230/230 not 200: 9,1,10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10
I can now re-instate the mark() I had and see what I get:
Pass Pass Pass Pass Pass Pass Pass Pass Failed: 330/330 not 300: 10,10,10,10,10,10,10,10,10,10,10,10 Failed: 230/230 not 200: 10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10,9,1 Failed: 230/230 not 200: 9,1,10,5,5,10,6,4,10,7,3,10,4,6,10,3,7,10
These last three failures are because I'm not stopping after the tenth frame. This is going to involve keeping track of the frame number and also changing the end test to see that I'm not at the tenth frame. The frame number tracking is quite easy. I'm going to add a int frame to the Frame and then set it to either zero or ten in the two constructors:
Frame( const_iterator b, const_iterator e )
: const_iterator( b ), frame( 0 ), end( e ) {
}
Frame( const_iterator e )
: const_iterator( e ), frame( 10 ), end( e ) {
}I now need to change the operator != to also examine the frame number. This test needs to be right and that means thinking it through properly. I find it easier to think without all of the negatives, so under what conditions are they equal? We need to consider that the Frame iterator instance is equal to the end marker if either the internal iterator parts are equal or if the frame numbers are equal. Turning this around to the not equal gives us that they are not equal if the iterators aren't equal and the frame numbers aren't equal.
bool operator !=( const Frame &f ) const {
return const_iterator::operator !=( f ) && frame != f.frame;
}And now we have success on the tests:
Pass Pass Pass Pass Pass Pass Pass Pass Pass Pass Pass
The final code that we have is this:
template< typename const_iterator >
class Frame : private const_iterator {
public:
Frame( const_iterator b, const_iterator e )
: const_iterator( b ), frame( 0 ), end( e ) {
}
Frame( const_iterator e )
: const_iterator( e ), frame( 10 ), end( e ) {
}
void operator ++() {
++frame;
if ( const_iterator::operator *() != 10 ) const_iterator::operator ++();
if ( *this != end ) const_iterator::operator ++();
}
bool operator !=( const Frame &f ) const {
return const_iterator::operator !=( f ) && frame != f.frame;
}
typename const_iterator::value_type operator *() const {
const_iterator pos( *this );
value_type score( *pos );
if ( ++pos != end ) score += *pos;
else return score;
if ( mark() && ++pos != end ) score += *pos;
return score;
}
bool mark() const {
const_iterator pos( *this );
value_type score( *pos );
if ( score == 10 ) return true;
else if ( ++pos != end ) return *pos + score == 10;
else return false;
}
private:
int frame;
const const_iterator end;
};
template< typename const_iterator >
typename const_iterator::value_type calculate_score( const_iterator begin, const_iterator end ) {
return std::accumulate( Frame< const_iterator >( begin, end ), Frame< const_iterator >( end ), const_iterator::value_type() );
}The one part of the solution that bothers me is the mark() function. I think that this test could be in the operator * where the summing is actually done. For the example we have here the sum is not an expensive operation, but we could merge them at the cost of making the code more complex.
typename const_iterator::value_type operator *() const {
const_iterator pos( *this );
value_type score( *pos );
bool mark( score == 10 );
if ( ++pos != end ) {
score += *pos;
mark = ( mark || score == 10 );
} else return score;
if ( mark && ++pos != end ) score += *pos;
return score;
}I think that the compiler doesn't need the parenthesis around the expression mark || score == 10, but I know it makes it more obvious to me what is going on.
Now that I've removed mark() I'm not even sure that it is more complex, although a couple of small tweaks might make it even better (strike is the right term for all the pins knocked down in the first ball of a frame isn't it?):
typename const_iterator::value_type operator *() const {
const_iterator pos( *this );
value_type score( *pos );
if ( ++pos == end ) return score;
bool strike( score == 10 );
score += *pos;
if ( ( strike || score == 10 ) && ++pos != end ) score += *pos;
return score;
}Now finally I think that calculate_score() can usefully be added to the iterator class which also seems to imply I ought to rename it. The final version is now:
template< typename const_iterator >
class BowlingScore : private const_iterator {
public:
BowlingScore( const_iterator b, const_iterator e )
: const_iterator( b ), frame( 0 ), end( e ) {
}
BowlingScore( const_iterator e )
: const_iterator( e ), frame( 10 ), end( e ) {
}
static typename const_iterator::value_type calculate_score( const_iterator begin, const_iterator end ) {
return std::accumulate( BowlingScore( begin, end ), BowlingScore( end ), const_iterator::value_type() );
}
void operator ++() {
++frame;
if ( const_iterator::operator *() != 10 ) const_iterator::operator ++();
if ( *this != end ) const_iterator::operator ++();
}
bool operator !=( const BowlingScore &f ) const {
return const_iterator::operator !=( f ) && frame != f.frame;
}
typename const_iterator::value_type operator *() const {
const_iterator pos( *this );
value_type score( *pos );
if ( ++pos == end ) return score;
bool strike( score == 10 );
score += *pos;
if ( ( strike || score == 10 ) && ++pos != end ) score += *pos;
return score;
}
private:
int frame;
const const_iterator end;
};
int calculate_iterator( const std::vector< int > &balls ) {
return BowlingScore< std::vector< int >::const_iterator >::calculate_score( balls.begin(), balls.end() );
}
