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
