Pete Becker wrote:

....

>

Yup. Typical developer-written test: I don't understand testing well

enough to do it right, so I'll do something random and hope to hit a

problem. <g>

I have yet to meet a "test" developer that can beat the monte carlo test

for coverage.

OK - I agree, there are cases where a monte-carlo test will never be

able to test adequately, but as a rule, it is better to have a MC test

than not. I have uncovered more legitimate problems from the MC test

than from carefully crafted tests.

>

As I've said several times, developing and testing involve two distinct

sets of skills. Developers think they're good at testing, but any

professional tester will tell you that they aren't.

I challenge you. I don't think of myself as a tester. I believe you

can't do a better job than I in testing my code. Let's use this "range

map" as an example.

I have attached the header file and the test cases.

Your clain that I "don't understand testing well enough" and so I use an

MC test I think is short sighted.

For example, MC tests are the only tests that I have been able to truly

test multithreaded code. It is nigh impossible for me (or any human) to

truly understand all the interactions in a MT scenario. MC tests almost

always will push every edge of the problem space.

Again, it's not to say that there are no systematic errors that can't be

discovered using random tests, but these types of errors are exactly

the kind that a good developer knows exist and tests for or even designs

around.

//

// The Austria library is copyright (c) Gianni Mariani 2004.

//

// Grant Of License. Grants to LICENSEE the non-exclusive right to use the Austria

// library subject to the terms of the LGPL.

//

// A copy of the license is available in this directory or one may be found at this URL:

//

http://www.gnu.org/copyleft/lesser.txt
//

/**

* at_rangemap.h

*

*/

#ifndef x_at_rangemap_h_x

#define x_at_rangemap_h_x 1

#include "at_exports.h"

#include "at_os.h"

#include "at_assert.h"

#include <map>

// Austria namespace

namespace at

{

// ======== TypeRange =================================================

/**

* TypeRange describes the range of a particular type

*

*/

template <typename w_RangeType>

class TypeRange

{

public:

// range type

typedef w_RangeType t_RangeType;

// ======== Adjacent ==============================================

/**

* Adjacent returns true if the two parameters are "one apart"

*

* @param i_lesser is the lesser of the two values

* @param i_greater is the greater of the two

* @return true is no other elements exist between i_lesser and i_greater

*/

static bool Adjacent(

const t_RangeType & i_lesser,

const t_RangeType & i_greater

) {

t_RangeType l_greater_less( i_greater );

-- l_greater_less; // go to the earlier element

// deal with wrapping

if ( i_greater < l_greater_less )

{

return false;

}

return !( i_lesser < l_greater_less );

}

};

// ======== RangeMap ==================================================

/**

* RangeMap is a template that defines ranges.

*

*/

template <typename w_RangeType, typename w_RangeTraits=TypeRange<w_RangeType

class RangeMap

{

public:

// range type

typedef w_RangeType t_RangeType;

typedef w_RangeTraits t_RangeTraits;

// index on the end of the range

typedef std::map< t_RangeType, t_RangeType t_Map;

typedef typename t_Map::iterator t_Iterator;

// ======== AddRange ==============================================

/**

* Add a segment to the range.

*

* @param i_begin The beginning of the range (inclusive)

* @param i_end The end of the range (inclusive)

* @return nothing

*/

void AddRange( const t_RangeType & i_begin, const t_RangeType & i_end )

{

const bool l_less_than( i_end < i_begin );

const t_RangeType & l_begin = ! l_less_than ? i_begin : i_end;

const t_RangeType & l_end = l_less_than ? i_begin : i_end;

// deal with an empty map here

if ( m_map.empty() )

{

// shorthand adding the first element into the map

m_map[ l_end ] = l_begin;

return;

}

// see if there is a segment to merge - find the element that preceeds

// l_begin

t_Iterator l_begin_bound = m_map.lower_bound( l_begin );

if ( l_begin_bound == m_map.end() )

{

// l_begin is after the last element

-- l_begin_bound;

if ( t_RangeTraits::Adjacent( l_begin_bound->first, l_begin ) )

{

// yes, they are mergable

t_RangeType l_temp = l_begin_bound->second;

m_map.erase( l_begin_bound );

m_map[ l_end ] = l_temp;

return;

}

// not mergable - add the segment at the end

m_map[ l_end ] = l_begin;

return;

}

// if the end of the segment being inserted is not beyond this one

if ( ( l_end < l_begin_bound->second ) && ! t_RangeTraits::Adjacent( l_end, l_begin_bound->second ) )

{

// NOT mergable with subsequent segments

if ( l_begin_bound == m_map.begin() )

{

// There is no previous segment

m_map[ l_end ] = l_begin;

return;

}

// The segment being inserted can't be merged at the end

// see if it can be merged with the previous one

t_Iterator l_previous = l_begin_bound;

-- l_previous;

AT_Assert( l_previous->first < l_begin );

if ( ! t_RangeTraits::Adjacent( l_previous->first, l_begin ) )

{

// not overlapping with previous and not mergable

m_map[ l_end ] = l_begin;

return;

}

else

{

// we are mergable with the previous element

// yes, they are mergable

t_RangeType l_temp = l_previous->second;

m_map.erase( l_previous );

m_map[ l_end ] = l_temp;

return;

}

}

if ( l_begin_bound == m_map.begin() )

{

if ( l_end < l_begin_bound->first )

{

if ( l_end < l_begin_bound->second )

{

if ( t_RangeTraits::Adjacent( l_end, l_begin_bound->second ) )

{

l_begin_bound->second = l_begin;

return;

}

else

{

m_map[ l_end ] = l_begin;

return;

}

}

else

{

if ( l_begin < l_begin_bound->second )

{

l_begin_bound->second = l_begin;

}

return;

}

}

else

{

t_RangeType l_new_begin = l_begin;

if ( l_begin_bound->second < l_begin )

{

l_new_begin = l_begin_bound->second;

}

// Check to see what segment is close to the end

t_Iterator l_end_bound = m_map.lower_bound( l_end );

if ( l_end_bound == m_map.end() )

{

// erase all the segments from l_previous to the end and

// replace with one

m_map.erase( l_begin_bound, l_end_bound );

m_map[ l_end ] = l_new_begin;

return;

}

if ( l_end < l_end_bound->second && ! t_RangeTraits::Adjacent( l_end, l_end_bound->second ) )

{

m_map.erase( l_begin_bound, l_end_bound );

m_map[ l_end ] = l_new_begin;

return;

}

// merge with the current end

m_map.erase( l_begin_bound, l_end_bound ); // erase segments in between

l_end_bound->second = l_new_begin;

return;

}

}

if ( l_begin_bound == m_map.begin() )

{

// no previous ranges

// see if we can merge with the current range

}

// find the previous iterator

t_Iterator l_previous = l_begin_bound;

-- l_previous;

t_RangeType l_new_begin = l_begin;

if ( t_RangeTraits::Adjacent( l_previous->first, l_begin ) )

{

l_new_begin = l_previous->second;

}

else

{

++ l_previous;

if ( l_previous->second < l_new_begin )

{

l_new_begin = l_previous->second;

}

}

t_RangeType l_new_end = l_end;

// Check to see what segment is close to the end

t_Iterator l_end_bound = m_map.lower_bound( l_end );

if ( l_end_bound == m_map.end() )

{

// erase all the segments from l_previous to the end and

// replace with one

m_map.erase( l_previous, l_end_bound );

m_map[ l_end ] = l_new_begin;

return;

}

if ( l_end < l_end_bound->second && ! t_RangeTraits::Adjacent( l_end, l_end_bound->second ) )

{

m_map.erase( l_previous, l_end_bound );

m_map[ l_end ] = l_new_begin;

return;

}

// merge with the current end

m_map.erase( l_previous, l_end_bound ); // erase segments in between

l_end_bound->second = l_new_begin;

return;

}

// ======== SubtractRange =========================================

/**

* SubtractRange removes the range. (opposite of Add)

*

*

* @param i_begin Beginning of range to subtract

* @param i_end End of range to subtract

* @return nothing

*/

void SubtractRange( const t_RangeType & i_begin, const t_RangeType & i_end )

{

const bool l_less_than( i_end < i_begin );

const t_RangeType & l_begin = ! l_less_than ? i_begin : i_end;

const t_RangeType & l_end = l_less_than ? i_begin : i_end;

// deal with an empty map here

if ( m_map.empty() )

{

// Nothing to remove

return;

}

// See if we find a segment

// l_begin

t_Iterator l_begin_bound = m_map.lower_bound( l_begin );

if ( l_begin_bound == m_map.end() )

{

// this does not cover any segments

return;

}

if ( l_begin_bound->second < l_begin )

{

// this segment is broken up

t_RangeType l_newend = l_begin;

-- l_newend;

m_map[ l_newend ] = l_begin_bound->second;

l_begin_bound->second = l_begin;

}

t_Iterator l_end_bound = m_map.lower_bound( l_end );

if ( l_end_bound == m_map.end() )

{

// erase all the segments from the beginning to end

m_map.erase( l_begin_bound, l_end_bound );

return;

}

if ( !( l_end < l_end_bound->first ) )

{

// the segment end must be equal the segment given

++ l_end_bound;

m_map.erase( l_begin_bound, l_end_bound );

return;

}

// need to break up the final segment

m_map.erase( l_begin_bound, l_end_bound );

if ( !( l_end < l_end_bound->second ) )

{

t_RangeType l_newbegin = l_end;

++ l_newbegin;

l_end_bound->second = l_newbegin;

}

return;

}

// ======== IsSet =================================================

/**

* Checks to see if the position is set

*

* @param i_pos

* @return True if the position is set

*/

bool IsSet( const t_RangeType & i_pos )

{

t_Iterator l_bound = m_map.lower_bound( i_pos );

if ( l_bound == m_map.end() )

{

// this does not cover any segments

return false;

}

return !( i_pos < l_bound->second );

}

t_Map m_map;

};

}; // namespace

#endif // x_at_rangemap_h_x

#include "at_rangemap.h"

#include "at_unit_test.h"

#include <iostream>

#include <vector>

#include <cstdlib>

using namespace at;

namespace RangemapTest {

//

// ======== TestBitMap ================================================

/**

* TestBitMap is like a range map but the logic is far easier.

*

*/

template <typename w_RangeType, typename w_RangeTraits=TypeRange<w_RangeType

class TestBitMap

{

public:

// range type

typedef w_RangeType t_RangeType;

typedef w_RangeTraits t_RangeTraits;

// ======== AddRange ==============================================

/**

* Add a segment to the range.

*

* @param i_begin The beginning of the range (inclusive)

* @param i_end The end of the range (inclusive)

* @return nothing

*/

void AddRange( const t_RangeType & i_begin, const t_RangeType & i_end )

{

const bool l_less_than( i_end < i_begin );

const t_RangeType & l_begin = ! l_less_than ? i_begin : i_end;

const t_RangeType & l_end = l_less_than ? i_begin : i_end;

CheckSize( l_end );

for ( unsigned i = l_begin; i <= l_end; ++i )

{

m_bitmap[ i ] = true;

}

}

// ======== SubtractRange =========================================

/**

* SubtractRange removes the range. (opposite of Add)

*

*

* @param i_begin Beginning of range to subtract

* @param i_end End of range to subtract

* @return nothing

*/

void SubtractRange( const t_RangeType & i_begin, const t_RangeType & i_end )

{

const bool l_less_than( i_end < i_begin );

const t_RangeType & l_begin = ! l_less_than ? i_begin : i_end;

const t_RangeType & l_end = l_less_than ? i_begin : i_end;

CheckSize( l_end );

for ( unsigned i = l_begin; i <= l_end; ++i )

{

m_bitmap[ i ] = false;

}

}

// ======== IsSet =================================================

/**

* Checks to see if the position is set

*

* @param i_pos

* @return True if the position is set

*/

bool IsSet( const t_RangeType & i_pos )

{

if ( m_bitmap.size() < std::size_t( i_pos ) )

{

return false;

}

return m_bitmap[ i_pos ];

}

void CheckSize( const t_RangeType & i_end )

{

if ( m_bitmap.size() < std::size_t(i_end + 1) )

{

m_bitmap.resize( i_end + 1 );

}

}

std::vector<bool m_bitmap;

};

// ======== TestBoth ==================================================

/**

*

*

*/

template <typename w_RangeType, typename w_RangeTraits=TypeRange<w_RangeType

class TestBoth

{

public:

// range type

typedef w_RangeType t_RangeType;

typedef w_RangeTraits t_RangeTraits;

// ======== AddRange ==============================================

/**

* Add a segment to the range.

*

* @param i_begin The beginning of the range (inclusive)

* @param i_end The end of the range (inclusive)

* @return nothing

*/

void AddRange( const t_RangeType & i_begin, const t_RangeType & i_end )

{

m_rangemap_pre = m_rangemap;

m_rangemap.AddRange( i_begin, i_end );

m_bitmap.AddRange( i_begin, i_end );

Verify( "Add", i_begin, i_end );

}

// ======== SubtractRange =========================================

/**

* SubtractRange removes the range. (opposite of Add)

*

*

* @param i_begin Beginning of range to subtract

* @param i_end End of range to subtract

* @return nothing

*/

void SubtractRange( const t_RangeType & i_begin, const t_RangeType & i_end )

{

m_rangemap_pre = m_rangemap;

m_rangemap.SubtractRange( i_begin, i_end );

m_bitmap.SubtractRange( i_begin, i_end );

Verify( "Sub", i_begin, i_end );

}

void Verify( const char * i_op, const t_RangeType & i_begin, const t_RangeType & i_end )

{

unsigned l_elems = m_bitmap.m_bitmap.size();

typename at::RangeMap< w_RangeType, w_RangeTraits >::t_Iterator l_bound;

typename at::RangeMap< w_RangeType, w_RangeTraits >::t_Iterator l_previous;

bool l_previous_set = false;

for ( unsigned i = 0; i < (l_elems); ++ i )

{

l_bound = m_rangemap.m_map.lower_bound( i );

bool l_rangemap_val = l_bound == m_rangemap.m_map.end() ? false : !( i < l_bound->second );

bool l_bitmap_val = m_bitmap.IsSet(i);

bool l_segment_fail = false;

if ( l_previous_set )

{

if ( l_rangemap_val )

{

l_segment_fail = l_previous != l_bound;

}

}

else

{

}

l_previous_set = l_rangemap_val;

if ( l_rangemap_val && ! l_segment_fail )

{

l_previous = l_bound;

}

if ( ( l_rangemap_val != l_bitmap_val ) || l_segment_fail )

{

if ( l_segment_fail )

{

std::cout << "Segments ( " << l_bound->second << ", " << l_bound->first << " ) and \n";

std::cout << " ( " << l_previous->second << ", " << l_previous->first << " ) and \n";

}

std::cout << "Operation = " << i_op << " i_begin = " << i_begin << " i_end = " << i_end << "\n";

std::cout << "Pre operation ";

DumpRanges( m_rangemap_pre.m_map );

std::cout << "Post operation ";

DumpRanges( m_rangemap.m_map );

std::cout << "rangemap " << w_RangeType(i) << " - l_rangemap_val = " << l_rangemap_val << ", l_bitmap_val = " << l_bitmap_val << "\n";

}

AT_TCAssert( m_rangemap.IsSet(i) == m_bitmap.IsSet(i), "Bitmap differs" );

}

}

void DumpRanges()

{

DumpRanges( m_rangemap.m_map );

}

void DumpRanges( typename at::RangeMap< w_RangeType, w_RangeTraits >::t_Map & l_map )

{

typename at::RangeMap< w_RangeType, w_RangeTraits >::t_Iterator l_iterator;

for ( l_iterator = l_map.begin(); l_iterator != l_map.end(); ++ l_iterator )

{

std::cout << "( " << l_iterator->second << ", " << l_iterator->first << " )";

}

std::cout << "\n";

}

at::RangeMap< w_RangeType, w_RangeTraits m_rangemap;

at::RangeMap< w_RangeType, w_RangeTraits m_rangemap_pre;

TestBitMap< w_RangeType, w_RangeTraits m_bitmap;

};

AT_TestArea( RangeMap, "Rangemap object tests" );

AT_DefineTest( RangeMap, RangeMap, "Basic RangeMap test" )

{

void Run()

{

{

TestBoth<unsigned charl_rm;

l_rm.AddRange( 'a','x' );

l_rm.AddRange( 'A','X' );

l_rm.AddRange( 'z','z' );

l_rm.AddRange( 'Y','Z' );

l_rm.DumpRanges();

}

{

TestBoth<unsigned charl_rm;

l_rm.AddRange( '0','0' );

l_rm.AddRange( 'a','a' );

l_rm.AddRange( 'c','c' );

l_rm.AddRange( 'h','h' );

l_rm.AddRange( 'b','g' );

l_rm.DumpRanges();

}

{

TestBoth<unsigned charl_rm;

l_rm.AddRange( '0','0' );

l_rm.AddRange( 'a','a' );

l_rm.AddRange( 'c','c' );

l_rm.AddRange( 'h','h' );

l_rm.AddRange( 'b','i' );

l_rm.DumpRanges();

l_rm.AddRange( 'c','c' );

l_rm.DumpRanges();

l_rm.SubtractRange( 'b','b' );

l_rm.SubtractRange( 'c','c' );

l_rm.SubtractRange( 'd','d' );

l_rm.SubtractRange( 'c','c' );

l_rm.DumpRanges();

}

{

TestBoth<unsigned charl_rm;

l_rm.AddRange( 'a','a' );

l_rm.AddRange( 'c','c' );

l_rm.AddRange( 'h','h' );

l_rm.AddRange( 'b','i' );

l_rm.AddRange( '0','0' );

l_rm.SubtractRange( '0','0' );

l_rm.AddRange( '0', 'i' );

l_rm.SubtractRange( '0','i' );

l_rm.AddRange( 'A','Z' );

l_rm.SubtractRange( 'M','M' );

l_rm.DumpRanges();

}

}

};

AT_RegisterTest( RangeMap, RangeMap );

AT_DefineTest( MonteRangeMap, RangeMap, "Basic RangeMap test" )

{

void Run()

{

TestBoth<unsignedl_rm;

std::srand( 39000 );

int range = 60;

for ( int i = 0; i < 10000; ++i )

{

unsigned l_begin = std::rand() % range;

unsigned l_end = std::rand() % range;

bool operation = ( 2 & std::rand() ) == 0;

if ( operation )

{

l_rm.SubtractRange( l_begin, l_end );

}

else

{

l_rm.AddRange( l_begin, l_end );

}

}

}

};

AT_RegisterTest( MonteRangeMap, RangeMap );

} // RangeMap Test namespace