Boost logo

Boost :

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)


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk