Re: [boost] [test] testing for strict weak ordering

From: Gennadiy Rozental (gennadiy.rozental_at_[hidden])
Date: 2007-02-05 11:56:09

"Thorsten Ottosen" <thorsten.ottosen_at_[hidden]> wrote in message 
news:45C75E5A.7030309_at_dezide.com...
> I see this as bunch of garbage chars. I don't know why. Could you
> include the file in the message itself?

Strange, I do not have any problems reading my post. Here it is:

#ifndef RUNTIME_CONCEPT_CHECK_HPP
#define RUNTIME_CONCEPT_CHECK_HPP

//  (C) Copyright John Panzer, Gennadiy Rozental 2002.
//  Permission to copy, use, modify, sell and distribute this software
//  is granted provided this copyright notice appears in all copies.
//  This software is provided "as is" without express or implied warranty,
//  and with no claim as to its suitability for any purpose.
//
//  See http://www.boost.org for most recent version including 
documentation.

// BOOST
#include <boost/config.hpp>

// BTL
#include <boost/test/test_tools.hpp>

// STL
#include <vector>

// 
************************************************************************** 
//
// **************           test_strict_weak_ordering 
************** //
// 
************************************************************************** 
//

// Tests whether a predicate functor cmp is a (model of) a
// Strict Weak Ordering, suitable for use with ordering
// algorithms and associative containers.
//
// Requires:
//
// Cmp cmp : A binary functor satisfying the interface
//   requirements for a Strict Weak Ordering.
//
// InputIterator begin, end : An iterator range defining
//   a test data set.  The value_type must be copy
//   constructible, be compatible with the two input
//   arguments to cmp, and have an appropriate operator<<
//   defined for reporting purposes.
//
// Details:
//
// This algorithm runs a series of tests using the supplied
// test data against the functor cmp.  This checks whether
// cmp is a (model of a) Strict Weak Ordering, as defined by:
//
// Stability:
//   cmp(a,b) must return the same answer for the same
//   values a,b regardless of number of times it is
//   queried (basic Predicate requirement).
// Irreflexivity:
//   cmp(a,a) is false for any value a.
// Antisymmetry:
//   cmp(a,b) -> !cmp(b,a)
// Transitivity:
//   cmp(a,b) and cmp(b,c) implies cmp(a,c) for all
//   a,b,c.
// Transitivity of Equivalence:
//   a~=b and b~=c implies a~=c for all a,b,c, where
//   x~=y is defined by !cmp(x,y).
//
// Note: If the value_type does not already have a reasonable
// operator<<, adding the following to unit test code will
// allow this function to link:
//
// ostream &operator << (ostream &os,T const &) {
//     return os << '*';
// }
//
// See also:
// http://www.sgi.com/tech/stl/StrictWeakOrdering.html
//

template <class Predicate, typename InputIterator>
void
test_strict_weak_ordering( std::string predicate, Predicate cmp, 
InputIterator begin, InputIterator end )
{
    // Type of elements dealt with (must be copyable):
    typedef typename std::iterator_traits<InputIterator>::value_type 
value_type;

    // Array of values to test against, copied
    // from user-supplied input values:
    std::vector<value_type> values(begin,end);

    // A matrix recording functor comparison answers:
    std::vector<std::vector<bool> > lt_answer;
    int data_set_size=values.size();
    int i, j;

    // Fill out lt_answer matrix using cmp:
    lt_answer.resize(data_set_size);

    for( i=0; i < data_set_size; ++i ) {
        lt_answer[i].resize( data_set_size );

        for (j=0; j < data_set_size; ++j) {
            // Record result of comparison:
            lt_answer[i][j] = cmp(values[i], values[j]);

            // Test for stability:
            BOOST_CHECK_MESSAGE( lt_answer[i][j] == cmp(values[i], 
values[j]),
                "Predicate P(a,b)=" << predicate
                << " fails stability test; returns both true and false when 
called multiple times for: a= "
                << values[i] << " and b= " << values[j] );
        }

        // Test for irreflexivity:
        BOOST_CHECK_MESSAGE( !cmp(values[i],values[i]),
            "Predicate P(a,b)=" << predicate
            << " fails irreflexivity test; P(a,a) returns true for a= " << 
values[i] );
    }

    for(i=0;i<data_set_size;++i) {
        for(j=0;j<data_set_size;++j) {
            // Check for antisymmetry: cmp(a,b) -> !cmp(b,a)
            BOOST_CHECK_MESSAGE( !(lt_answer[i][j] && lt_answer[j][i]),
                "Predicate P(a,b)=" << predicate
                << " fails antisymmetry test; both P(a,b) and P(b,a) return 
true for a= " << values[i] << " and b= " << values[j] );

            for(int k=0;k<data_set_size;++k) {
                // Check for transitivity:
                // cmp(a,b) & cmp(b,c) -> cmp(a,c)
                BOOST_CHECK_MESSAGE( !lt_answer[i][j] || !lt_answer[j][k] || 
lt_answer[i][k],
                    "Predicate P(a,b)=" << predicate
                    << " fails transitivity test; both P(a,b) and P(b,c) 
return true but P(a,c) returns false for a= "
                    << values[i] << ", b= " << values[j] << " and c= " << 
values[k] );

                // Check for transitivity of equivalence:
                // !cmp(a,b) & !cmp(b,c) -> !cmp(a,c)
                BOOST_CHECK_MESSAGE( lt_answer[i][j] || lt_answer[j][k] || 
!lt_answer[i][k],
                    "Predicate P(a,b)=" << predicate <<
                    " fails transitivity of equiualence test; both P(a,b) 
and P(b,c) return false but P(a,c) returns true for a= "
                    << values[i] << ", b= " << values[j] << " and c= " << 
values[k] );
            }
        }
    }
}

#define BOOST_CHECK_STRICT_WEAK_ORDERING( Predicate, begin, end ) \
    test_strict_weak_ordering( #Predicate, Predicate, begin, end )

#endif // RUNTIME_CONCEPT_CHECK_HPP

//  Revision History
//   29 Jan 02  Initial version (John Panzer)
//   29 Jan 02  Modified to be used with Boost Test Library (Gennadiy 
Rozental)