October 2009 - Boost - lists.preview.boost.org

[string]
by remi.chateauneu＠gmx.de 26 Oct '09

26 Oct '09

Hi, Is there any interest for a class for computing Levenshtein and Damerau distances ? It is inspired from http://en.wikipedia.org/wiki/Levenshtein_distance with some enhancements: - The buffer can be reused thanks to a class, avoiding reallocations. - Only one buffer of twice the size of the longest string is necessary (Instead of the product of the size of the two input sequences). (Three times the size for Damerau distance). - It works with any input iterator category for one string, any iterator except input_iterator for the second string. - The distance type is templatized (Allowing to use short ints to save buffer space). - Any type of element can be used (Not only chars). - More efficient than the other implementations I could find on the web, completely inlined (Specific care to maximize memory locality). - The cost function can be specified with a functor (Insertion, deletion, replacement, transposition). - Tested with GCC 3.2.3 and 4.2.3, Visual C++ 2005. There was a proposal for such a function two years ago (edit_distance), but maybe this one, being faster, might be of interest for the string algorithms library ? The code is not very big so please let me attach it here. Thanks /* boost levenshtein.hpp header file * * Copyright Remi Chateauneu 2009 * Distributed under the Boost Software License, Version 1.0. (See * accompanying file LICENSE_1_0.txt or copy at * http://www.boost.org/LICENSE_1_0.txt) * * $Id: $ * * Idea by x */ #ifndef BOOST_LEVENSHTEIN_HPP #define BOOST_LEVENSHTEIN_HPP #include <string.h> #include <vector> namespace boost { /// Given a distance formula, levenshtein or damerau, does some processing of the input parameters. template< class Distance, class Formula > class distance_base { /// This uses Curiously recurring template pattern template < class Iter1, class Iter2 > inline Distance distance_noswap( Iter1 begS1, Iter1 endS1, Iter2 ptrS2, size_t len2 ) { return static_cast< Formula * >(this)->distance_noswap( begS1, endS1, ptrS2, len2 ); }; public: /// If both lengths are available, we can swap to increase speed. template < class Iter1, class Iter2 > Distance distance_swap( Iter1 begS1, Iter1 endS1, size_t len1, Iter2 begS2, Iter2 endS2, size_t len2 ) { /// The longer string should go to the inner loop return ( len1 < len2 ) ? distance_noswap( begS1, endS1, begS2, len2 ) : distance_noswap( begS2, endS2, begS1, len1 ); }; /// For plain containers. We assume that 'size()' has a constant cost. template < class Container1, class Container2 > Distance operator()( const Container1 & s1, const Container2 & s2 ) { return distance_swap( s1.begin(), s1.end(), s1.size(), s2.begin(), s2.end(), s2.size() ); }; /// For plain C-style strings. No need to create a temporary string. Distance operator()( const char * ptrS1, const char * ptrS2 ) { size_t len1 = strlen(ptrS1); size_t len2 = strlen(ptrS2); return distance_swap( ptrS1, ptrS1 + len1, len1, ptrS2, ptrS2 + len2, len2 ); }; /// If no iterator is an input_iterator, we may be able to swap them for performance. template< class Iter1, class Iter2 > Distance distance_iterator( Iter1 beg1, Iter1 end1, std::forward_iterator_tag, Iter2 beg2, Iter2 end2, std::forward_iterator_tag ) { return distance_swap( beg1, end1, std::distance( beg1, end1 ), beg2, end2, std::distance( beg2, end2 ) ); }; /// If the first iterator only is an input_iterator, then process it. template< class Iter1, class Iter2 > Distance distance_iterator( Iter1 beg1, Iter1 end1, std::input_iterator_tag, Iter2 beg2, Iter2 end2, std::forward_iterator_tag ) { return distance_noswap( beg1, end1, beg2, std::distance( beg2, end2 ) ); }; /// If the first iterator only is an input_iterator, then swap them first. template< class Iter1, class Iter2 > Distance distance_iterator( Iter1 beg1, Iter1 end1, std::forward_iterator_tag, Iter2 beg2, Iter2 end2, std::input_iterator_tag ) { return distance_noswap( beg2, end2, beg1, std::distance( beg1, end1 ) ); }; /// According to the type of iterator, not all operations are possible. template< class Iter1, class Iter2 > Distance operator()( Iter1 beg1, Iter1 end1, Iter2 beg2, Iter2 end2 ) { return distance_iterator( beg1, end1, typename std::iterator_traits< Iter1 >::iterator_category(), beg2, end2, typename std::iterator_traits< Iter2 >::iterator_category() ); }; }; // distance_base /// A user functor must have this interface. /// NOTE: The distance must always be positive. template< class Distance, class Char > struct dummy_functor { /// Char subsitution. Distance operator()( Char, Char ) const ; /// Char insertion or deletion. The cost /// is the same for both cases otherwise the distance /// would not be commutative. Distance operator()( Char ) const ; /// Char transposition (Option, for Damerau only). /// This does not depends on the character. Distance operator()(void) const ; }; /// Default functor for the most common case. It is never instantiated. /// Equivalent to a cost of '1' for character insertion, deletion or substitution. struct distance_null_functor {}; /// Specialization for the default case, for performance. /// This wraps a user functor, and compute the core test of Levenshtein distance. template < class Distance, class Functor > class cell_min { /// A user can specify the cost of char insertion, deletion and substitution. /// It must match the interface of dummy_functor. Functor _ftor ; public: cell_min() {}; cell_min( const Functor & refFtor ) : _ftor( refFtor ) {}; /// The cost of character insertion and deletion are the same otherwise /// it would not be commutative, and would not be a distance. template< class Char > Distance min_levenshtein( const Distance & distIJ, const Distance & distI1J, const Distance & distIJ1, const Char & chrLeft, const Char & chrRight ) { return std::min( distIJ + _ftor( chrLeft, chrRight ), std::min( distI1J + _ftor( chrLeft ), distIJ1 + _ftor( chrRight ) ) ); }; /// The operator without argument computes the cost of a transposition /// and does not depend on the transposed characters. /// Damerau is tested on top of Levenshtein comparison. Distance min_damerau( const Distance & prevDiag, const Distance & currDiag ) { return std::min( Distance( prevDiag + _ftor() ), currDiag ); }; }; // cell_min /// Does the core comparison of Levenshtein distance when no /// user functor is provided. This is the most common case /// and must be the fastest. template < class Distance > class cell_min< Distance, distance_null_functor > { public: cell_min() {}; cell_min( const distance_null_functor & ) {}; /// Here we save two additions, than if the general class were used. template< class Char > Distance min_levenshtein( const Distance & distIJ, const Distance & distI1J, const Distance & distIJ1, const Char & , const Char & ) const { return 1 + std::min( distIJ, std::min( distI1J, distIJ1 ) ); }; /// The usual cost of a transposition can be set to 1. /// Damerau is tested on top of Levenshtein comparison. Distance min_damerau( const Distance & prevDiag, const Distance & currDiag ) const { return std::min( prevDiag, currDiag + 1 ); }; }; // cell_min (Specialization) /// Most of times, Distance is 'unsigned int'. template< class Distance > class distance_buffer { /// TODO: Use temporary buffer. std::vector< Distance > _buffer ; size_t _sz ; public: distance_buffer() : _sz(0) {}; void resize( size_t sz ) { if( sz <= _sz ) return ; _buffer.resize( sz ); _sz = _buffer.size(); }; Distance * start(void) { return &_buffer[0]; } }; // distance_buffer /// This wraps a buffer which can be reused, because buffer allocations are costly. /// The distance may be char, short, int: This can reduce the buffer size. /// TODO: Do not resize the buffer but use the stack if less than X elements. /// TODO: Use a specific buffer allocation. template < class Distance = unsigned int, class Functor = distance_null_functor > class levenshtein : public distance_base< Distance, levenshtein< Distance, Functor > > { /// This wraps a user-provided optional functor. cell_min< Distance, Functor > _minFtor ; /// Max size: Twice the longest string + 2. distance_buffer< Distance > _buffer ; public: levenshtein() {}; levenshtein( const Functor & refFtor ) : _minFtor( refFtor ) {}; /// The size of the first range is not needed, any iterator type will do. template < class Iter1, class Iter2 > Distance distance_noswap( Iter1 begS1, Iter1 endS1, Iter2 ptrS2, size_t len2 ) { typedef typename std::iterator_traits< Iter1 >::value_type Char ; /// The buffer contains two lines of distance. _buffer.resize( 2 * ( len2 + 1 ) ); Distance * localPtr = _buffer.start() ; for(unsigned j = 0; j <= len2; ++j) { localPtr[ 2 * j ] = (Distance)j; } const Distance * endPtr = localPtr + 2 * len2 ; /// One cell out of two is associated to one line, the other to the next line. /// The two lines are swapped at each loop. for( unsigned i = 1; ; ) { localPtr = _buffer.start() ; localPtr[1] = Distance(i++) /* i,j+1 */ ; Char chr1 = *begS1++ ; // Restart from the beginning of the second string. for( Iter2 currS2 = ptrS2 ; localPtr != endPtr ; localPtr += 2 ) { const Char chr2 = *currS2++ ; Distance costDiag = localPtr[ 0 ]; /// Optimisation: The distance cannot increase if the chars are identical. if( chr1 != chr2 ) { /// Good data locality in four contiguous cells of the buffer. costDiag = _minFtor.min_levenshtein( costDiag, /* i,j */ localPtr[ 2 ] /* i+1,j */, localPtr[ 1 ] /* i,j+1 */, chr1, chr2 ); } localPtr[ 3 ] = costDiag ; } /// The loop is unrolled two steps by two. if( begS1 == endS1 ) { /// After an even number of half-loops (and lines). return localPtr[ 1 ] /* i+1,j+1 */ ; } /// This starts an odd line. localPtr = _buffer.start() ; localPtr[0] = Distance(i++) /* i,j+1 */ ; chr1 = *begS1++; // Restart from the beginning of the second string. for( Iter2 currS2 = ptrS2 ; localPtr != endPtr ; localPtr += 2 ) { const Char chr2 = *currS2++ ; Distance costDiag = localPtr[ 1 ]; /// Optimisation: The distance cannot increase if the chars are identical. if( chr1 != chr2 ) { /// Good data locality in four contiguous cells of the buffer. costDiag = _minFtor.min_levenshtein( costDiag, /* i,j */ localPtr[ 3 ] /* i+1,j */, localPtr[ 0 ] /* i,j+1 */, chr1, chr2 ); } localPtr[ 2 ] = costDiag ; }; if( begS1 == endS1 ) { /// After an odd number of lines. return localPtr[ 0 ] /* i+1,j+1 */ ; } } /// Should never happen. return Distance(0); }; // distance_noswap }; // levenshtein /// This wraps a buffer which can be reused, because buffer allocations are costly. /// The distance may be char, short, int: This can reduce the buffer size. template < class Distance = unsigned int, class Functor = distance_null_functor > class damerau : public distance_base< Distance, damerau< Distance, Functor > > { /// This wraps a user-provided optional functor. cell_min< Distance, Functor > _minFtor ; /// Max size: Twice the longest string + 2. distance_buffer< Distance > _buffer ; public: damerau() {}; damerau( const Functor & refFtor ) : _minFtor( refFtor ) {}; /// The size of the first range is not needed, any iterator will do. template < class Iter1, class Iter2 > Distance distance_noswap( Iter1 begS1, Iter1 endS1, Iter2 ptrS2, size_t len2 ) { typedef typename std::iterator_traits< Iter1 >::value_type Char ; /// The buffer contains two lines of distance. _buffer.resize( 3 * ( len2 + 3 ) ); Distance * localPtr = _buffer.start() ; for(unsigned j = 0; j <= len2; ++j) { localPtr[ 3 * j] = (Distance)j; } /// One cell out of two is associated to one line, the other to the next line. int offPrev = 2, offCurr = 0, offNext = 1 ; Char chr1, chr1_prev ; /// The three lines are shifted at each loop. for( unsigned i = 1; begS1 != endS1 ; chr1_prev = chr1, ++begS1, ++i, offCurr = offNext, offNext = offPrev, offPrev = offPrev == 2 ? 0 : offPrev + 1 ) { Distance * localPtr = _buffer.start() ; localPtr[offNext] = Distance(i) /* i+1,j */ ; chr1 = *begS1 ; Char chr2, chr2_prev ; Iter2 currS2 = ptrS2 ; for(unsigned j = 0; j < len2; chr2_prev = chr2, ++currS2, ++j, localPtr += 3 ) { chr2 = *currS2 ; Distance costDiag = localPtr[ offCurr ] /* i,j */ ; /// Optimisation: The distance cannot increase if the chars are identical. /// NOTE: Without this test, a valid transposition could not be checked. if( chr1 != chr2 ) { /// Good data locality in four contiguous cells of the buffer. costDiag = _minFtor.min_levenshtein( costDiag, localPtr[ 3 + offCurr ], localPtr[ offNext ], chr1, chr2 ); /// If beyond the first column and line, check for a transposition. /// This makes sense only if the current chars are different. if( ( i > 1 ) && ( j > 0 ) && ( chr1 == chr2_prev ) && ( chr1_prev == chr2 ) ) { costDiag= _minFtor.min_damerau( costDiag, localPtr[ offPrev - 3 ] /* i-1,j-1 */ ); } } localPtr[ 3 + offNext ] = costDiag /* i+1,j+1 */ ; } } return _buffer.start()[ 3 * len2 + offCurr ]; }; // distance_noswap }; // damerau } // namespace boost #endif /* BOOST_LEVENSHTEIN_HPP */ #include <iostream> #include <string> #include <list> #include <vector> #include <iterator> #include "levenshtein.hpp" using namespace std ; /// This can be later used for creating combinations of tests. static void tst_perf(size_t nbLoops) { static const char * tst[] = { "a", "c", "bc", "abc", "bcdef", "abcdegh", "acdeghi", "acedghi", "abcdfgi", "abcfgi", "abcfig" }; const size_t nbTst = sizeof(tst)/sizeof(tst[0]); boost::levenshtein<int> tmpLev ; boost::damerau<int> tmpDam ; while( nbLoops-- ) { for( size_t i = 0 ; i < nbTst ; ++i ) { for( size_t j = i + 1 ; j < nbTst ; ++j ) { int distLev = tmpLev( tst[i], tst[j] ); int distDam = tmpDam( tst[i], tst[j] ); }; }; } } // http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_d… template <class T> size_t edit_distance(const T& s1, const T& s2) { const size_t len1 = s1.size(), len2 = s2.size(); vector<vector<unsigned int> > d(len1 + 1, vector<unsigned int>(len2 + 1)); d[0][0] = 0; for(unsigned int i = 1; i <= len1; ++i) d[i][0] = i; for(unsigned int i = 1; i <= len2; ++i) d[0][i] = i; for(unsigned int i = 1; i <= len1; ++i) for(unsigned int j = 1; j <= len2; ++j) d[i][j] = std::min( std::min(d[i - 1][j] + 1, d[i][j - 1] + 1), d[i - 1][j - 1] + (s1[i - 1] == s2[j - 1] ? 0 : 1) ); return d[len1][len2]; } /// Classical implementation. For comparing results. size_t levenshtein_dist(const std::string & source, const std::string & target) { const size_t n = source.length(); const size_t m = target.length(); if (n == 0) return m; if (m == 0) return n; vector<vector<size_t> > matrix(n + 1, vector<size_t>(m + 1,0)); for (size_t i = 0; i <= n; i++) { matrix[i][0]=i; } for (size_t j = 0; j <= m; j++) { matrix[0][j]=j; } for (size_t i = 1; i <= n; i++) { char s_i = source[i-1]; for (size_t j = 1; j <= m; j++) { char t_j = target[j-1]; int cost; if (s_i == t_j) { cost = 0; } else { cost = 1; } size_t above = matrix[i-1][j]; size_t left = matrix[i][j-1]; size_t diag = matrix[i-1][j-1]; size_t cell = std::min( above + 1, std::min(left + 1, diag + cost)); matrix[i][j]=cell; } } return matrix[n][m]; } /// Classical implementation. For comparing results. size_t damerau_dist(const std::string & source, const std::string & target) { const size_t n = source.length(); const size_t m = target.length(); if (n == 0) return m; if (m == 0) return n; vector<vector<size_t> > matrix(n + 1, vector<size_t>(m + 1,0)); for (size_t i = 0; i <= n; i++) { matrix[i][0]=i; } for (size_t j = 0; j <= m; j++) { matrix[0][j]=j; } for (size_t i = 1; i <= n; i++) { char s_i = source[i-1]; for (size_t j = 1; j <= m; j++) { char t_j = target[j-1]; int cost; if (s_i == t_j) { cost = 0; } else { cost = 1; } size_t above = matrix[i-1][j]; size_t left = matrix[i][j-1]; size_t diag = matrix[i-1][j-1]; size_t cell = std::min( above + 1, std::min(left + 1, diag + cost)); // Step 6A: Cover transposition, in addition to deletion, // insertion and substitution. This step is taken from: // Berghel, Hal ; Roach, David : "An Extension of Ukkonen's // Enhanced Dynamic Programming ASM Algorithm" // (http://www.acm.org/~hlb/publications/asm/asm.html) if( (i > 1) && (j > 1) && (source[i-2] == t_j) && (s_i == target[j-2]) ) { cell = std::min( cell, matrix[i-2][j-2] + 1 ); } matrix[i][j]=cell; } } return matrix[n][m]; } struct TstData { const char * _left ; const char * _right ; unsigned int _lev ; unsigned int _dam ; }; /// We can check whether the result is OK. static const TstData tst_array[] = { { "a","c", 1, 1 }, { "a","bc", 2, 2 }, { "ab","ba", 2, 1 }, { "a","abc", 2, 2 }, { "a","bcdef", 5, 5 }, { "a","abcdegh", 6, 6 }, { "a","acdeghi", 6, 6 }, { "a","acedghi", 6, 6 }, { "a","abcdfgi", 6, 6 }, { "a","abcfgi", 5, 5 }, { "a","abcfig", 5, 5 }, { "c","bc", 1, 1 }, { "c","abc", 2, 2 }, { "c","bcdef", 4, 4 }, { "c","abcdegh", 6, 6 }, { "c","acdeghi", 6, 6 }, { "c","acedghi", 6, 6 }, { "c","abcdfgi", 6, 6 }, { "c","abcfgi", 5, 5 }, { "c","abcfig", 5, 5 }, { "bc","abc", 1, 1 }, { "abcd","badc", 3, 2 }, { "bc","bcdef", 3, 3 }, { "bc","abcdegh", 5, 5 }, { "bc","acdeghi", 6, 6 }, { "bc","acedghi", 6, 6 }, { "bc","abcdfgi", 5, 5 }, { "bc","abcfgi", 4, 4 }, { "bc","abcfig", 4, 4 }, { "abc","bcdef", 4, 4 }, { "abc","abcdegh", 4, 4 }, { "abc","acdeghi", 6, 6 }, { "abc","acedghi", 6, 6 }, { "abc","abcdfgi", 4, 4 }, { "abc","abcfgi", 3, 3 }, { "abc","abcfig", 3, 3 }, { "bcdef","abcdegh", 3, 3 }, { "bcdef","acdeghi", 4, 4 }, { "bcdef","acedghi", 5, 5 }, { "bcdef","abcdfgi", 4, 4 }, { "bcdef","abcfgi", 4, 4 }, { "bcdef","abcfig", 4, 4 }, { "abcdegh","acdeghi", 2, 2 }, { "abcdegh","acedghi", 4, 3 }, { "abcdegh","abcdfgi", 2, 2 }, { "abcdegh","abcfgi", 3, 3 }, { "abcdegh","abcfig", 3, 3 }, { "acdeghi","acedghi", 2, 1 }, { "cadeghi","acedghi", 3, 2 }, { "acdeghi","abcdfgi", 3, 3 }, { "acdeghi","abcfgi", 4, 4 }, { "acdeghi","abcfig", 5, 5 }, { "acedghi","abcdfgi", 4, 4 }, { "acedghi","abcfgi", 4, 4 }, { "acedghi","abcfig", 5, 5 }, { "abcdfgi","abcfgi", 1, 1 }, { "abcdfgi","abcfig", 3, 2 }, { "abcfgi","abcfig", 2, 1 } }; static const size_t nbArr = sizeof(tst_array)/sizeof(tst_array[0]); static boost::levenshtein<int> staticLev ; static boost::damerau<int> staticDam ; /// This is for checking the assembly code generated. static int assembly_levenshtein( const char * a, const char * b ) { return staticLev( a, b ); } static void tst_values(void) { for( size_t i = 0; i < nbArr ; ++i ) { const TstData * p = tst_array + i ; size_t valL = staticLev( p->_left, p->_right ); size_t valD = staticDam( p->_left, p->_right ); size_t edtL = edit_distance( std::string(p->_left), std::string(p->_right) ); size_t oldL = levenshtein_dist( p->_left, p->_right ); size_t oldD = damerau_dist( p->_left, p->_right ); if( ( valL != p->_lev ) || ( oldL != p->_lev ) || ( edtL != p->_lev ) ) { std::cout << "Error L:" << "\tvalL=" << valL << "\tp->lev=" << p->_lev << "\toldL=" << oldL << "\tedtL=" << edtL << "\tp->left=" << p->_left << "\tp->right=" << p->_right << "\n" ; }; if( ( valD != p->_dam ) || ( oldD != p->_dam ) ) { std::cout << "Error D:" << "\tvalD=" << valD << "\tp->dam=" << p->_dam << "\toldD=" << oldD << "\tp->left=" << p->_left << "\tp->right=" << p->_right << "\n" ; }; }; } int main( int argC, const char ** argV ) { tst_values(); if( argC > 1 ) { int nbTst ; sscanf( argV[1], "%d", &nbTst ); tst_perf(nbTst); }; /// So it it not optimized away. std::cout << assembly_levenshtein << "\n" ; }; /// This is for checking the assembly code generated. int assembly_damerau( const char * a, const char * b ) { return staticLev( a, b ); } /// This tests some specific compile-time conditions. template< class Formula > static int compile_formula(Formula refFrm) { std::list< char > chrLst ; vector< char > chrVec ; std::istream_iterator<char> chrStrm ; refFrm( chrLst, chrVec ); refFrm( chrStrm, chrStrm, chrVec.begin(), chrVec.end() ); refFrm( chrLst.begin(), chrLst.end(), chrStrm, chrStrm ); }; struct my_functor { short operator()( char a, char b ) const { return 2 ; }; short operator()( char a ) const { return 1 ; }; short operator()(void) const { return 1 ; }; }; /// This tests some specific compile-time conditions. static int compile_test(void) { boost::levenshtein<int> tmpLev ; compile_formula( tmpLev ); boost::damerau<long long> tmpDam ; compile_formula( tmpDam ); boost::levenshtein<short,my_functor> tmpLevF ; compile_formula( tmpLevF ); my_functor tmpFunc ; boost::damerau<short, my_functor> tmpDamF( tmpFunc ) ; compile_formula( tmpDamF ); };

2 1

boost 1.39 to 1.40 difference: missing toolset and threading tag from library filename?
by Todd Lovette 26 Oct '09

26 Oct '09

Is there a difference in the naming conventions of the libboost_*.so files from boost 1.39 to boost 1.40.0? When I build the boost 1.39 libs they have filenames like... "libboost_thread-gcc44-mt-1_39.so" ..but when I build boost 1.40.0 all the libs filenames are like so... "libboost_thread.so" Did the library naming change in 1.40 or are their new compile options to enable the library naming feature? Build options: (both used on 1.39 & 1.40.0) ------------------------- ./bootstrap.sh --prefix=/usr --libdir=/usr/lib64 ./bjam threading=multi System ------------- Slamd64 12.1(x86_64) using gcc 4.4.2 Any help would be appticiated! Todd :-)

2 2

[test] Errors #including test/floating_point_comparison.hpp
by Emil Dotchevski 26 Oct '09

26 Oct '09

The log below shows a warning and 3 errors in test/predicate_result.hpp from Comeau C++ 4.3.10. Is this easy to fix? (Incidentally, I am not using boost/test, I only need floating_point_comparison.hpp -- shouldn't floating point comparison be independent from boost/test?) Emil Dotchevski Reverge Studios, Inc. http://www.revergestudios.com/reblog/index.php?n=ReCode como-win.compile.c++ ..\..\..\..\..\..\bin\dev\boost-la\libs\la\test\col_matrix_test.test\como-win-4.3.10\debug\link-static\col_matrix_test.obj "C:\code\dev\boost-trunk\boost/test/utils/basic_cstring/basic_cstring.hpp", line 60: warning #68-D: integer conversion resulted in a change of sign enum npos_type { npos = static_cast<size_type>(-1) }; ^ "C:\code\dev\boost-trunk\boost/test/predicate_result.hpp", line 62: warning #54-D: too few arguments in macro invocation BOOST_READONLY_PROPERTY( bool, (predicate_result) ) p_predicate_value; ^ "C:\code\dev\boost-trunk\boost/test/predicate_result.hpp", line 62: error #40: expected an identifier BOOST_READONLY_PROPERTY( bool, (predicate_result) ) p_predicate_value; ^ "C:\code\dev\boost-trunk\boost/test/predicate_result.hpp", line 62: error #277: invalid friend declaration BOOST_READONLY_PROPERTY( bool, (predicate_result) ) p_predicate_value; ^ "C:\code\dev\boost-trunk\boost/test/predicate_result.hpp", line 62: error #65: expected a ";" BOOST_READONLY_PROPERTY( bool, (predicate_result) ) p_predicate_value; ^

1 0

boost policy against inline friend functions?
by Stefan Strasser 26 Oct '09

26 Oct '09

I've noticed boost::shared_ptr and other classes avoid using inline friend functions, e.g. operator < in class shared_ptr scope: public: template<class Y> bool _internal_less(shared_ptr<Y> const & rhs) const { return pn < rhs.pn; } in namespace scope: template<class T, class U> inline bool operator<(shared_ptr<T> const & a, shared_ptr<U> const & b) { return a._internal_less(b); } what's wrong with template<class Y> friend bool operator<(shared_ptr<Y> const & rhs) const { return pn < rhs.pn; } in class shared_ptr? compiler compatibility? other reasons? should boost libraries avoid inline friend functions in general?

5 6

[conversion] Motivation for two NEW generic conver_to and assign_to functions
by vicente.botet 26 Oct '09

26 Oct '09

Hi, I would like to share with you what motivated me to add two new free template functions convert_to<> and assign_to<> on the Boost.Conversion. I've needed recently to convert from boost::chrono::time_point<Clock, Duration> to boost::posix_time::ptime and from boost::chrono::duration<Rep, Period> to boost::posix_time::time_duration. This kind of conversions are needed quite often when you use code from two different libraries that have implemented the same concept using of course different representations and have hard coded the library interface to its own implementation. Well this is a normal situation, we can't avoid. Life is life. Quite often we need to convert unrelated types `Source` and `Target`. As these classes are unrelated, neither of them offers conversion operators to the other. Usually we get it by defining a specific function such as Target ConvertToTarget(Source& v); In my case I started by defining template <typename Rep, typename Period> boost::posix_time::time_duration convert_to_posix_time_time_duration( const boost::chrono::duration<Rep, Period>& from); template <typename Clock, typename Duration> posix_time::ptime convert_to_posix_time_ptime(const chrono::time_point<Clock, Duration>& from); Imagine now that you need to convert a `std::pair<Source, Source>` to a `std::pair<Target, Target>`. The standard defines conversions of pairs if the related types are C++ convertible: template <typename T1, typename T2> struct pair { ... template<class U, class V> //requires Constructible<T1, const U&> && Constructible<T2, const V&> std::pair(const pair<U, V>& p); template<class U , class V> //requires HasAssign<T1, const U&> && HasAssign<T2, const V&> std::pair& operator=(const std::pair<U , V>& p); ... }; But here the types Target and Source are not convertible other than using a specific function. Well we can again define a specific function std::pair<Target,Target> ConvertToPairOfTarget(std::pair<Source,Source>& v) { return std::make_pair(ConvertToTarget(v.fisrt), ConvertToTarget(v.second)); } While the `ConvertToTarget` could be specific, the `ConvertToPairOfTarget` should be generic template <typename Target1, typename Target2, typename Source1, typename Source2) std::pair<Target1,Target2> ConvertToPair(std::pair<Source1,Source2>& v); In order to do that we need that the pair template parameters define a common function, let it call `convert_to`: template <typename Target, typename Source) Target convert_to(Source& v); Thus `ConvertToPair` can be defined as template <typename Target1, typename Target2, typename Source1, typename Source2) std::pair<Target1,Target2> ConvertToPair(std::pair<Source1,Source2>& v) { return std::make_pair(convert_to<Target1>(v.fisrt), convert_to<Target2>(v.second)); } We need to specialize the `convert_to` function for the specific classes `Source` and `Target`. We can do it as follows template <> Target convert_to<Target, Source>(Source& v) {return ConvertToTarget(v);} In my case I need template <typename Rep, typename Period> boost::posix_time::time_duration convert_to<posix_time_time_duration, boost::chrono::duration<Rep, Period> > (const boost::chrono::duration<Rep, Period>& from) { return convert_to_posix_time_time_duration(from); } template <typename Clock, typename Duration> boost::posix_time::ptime convert_to<posix_time_ptime, chrono::time_point<Clock, Duration> > (const boost::chrono::time_point<Clock, Duration>& from) { return convert_to_posix_time_ptime(from); } So now I can convert std::pair<chrono::time_point<Clock, Duration>, boost::chrono::duration<Rep, Period> > to std::pair<boost::posix_time::ptime, boost::posix_time::time_duration> using the `ConvertToPair` function. What about converting `std::pair<Source,std::pair<Source,Source> >` to `std::pair<Target,std::pair<Target,Target> >`? The issue now is that `convert_to(std::make_pair<to, std::make_pair<to,to> >)` do not compiles because the conversion of `std::pair` is named `ConvertToPair`. So we need to specialize the function `convert_to` for pairs. template <typename T1, typename T2, typename S1, typename S2) static std::pair<T1,T2> convert_to<std::pair<Target1,T2>, std::pair<S1,S2> >( std::pair<Source1,Source2>& from) { { return std::pair<T1,T2>(convert_to<T1>(from.first), convert_to<T2>(from.second)); } There is still a last point. The preceding design works well with unrelated classes, but what about classes that already define some kind of conversion, using a constructor or a conversion operator. Do we need to make specialization for these conversion? The answer is no. We need just to define the default implementation of convert_to function to just return the explicit conversion. template < typename Target, typename Source> Target convert_to(const Source& from) { return Target(from); } With compilers supporting partial specialization of function templates there is no major problem. For the others, we need to use a trick; as it allows partial specialization of classes we can define convert_to by as relying to a specific function of a class, as follows: namespace partial_specialization_workaround { template < typename Target, typename Source > struct convert_to { static Target apply(const Source& val); }; } template < typename Target, typename Source > Target convert_to(const Source& val) { return partial_specialization_workaround::convert_to<Target,Source>::apply(val); } So now we can specialize `partial_specialization_workaround::convert_to` for pairs as follows: namespace partial_specialization_workaround { template <typename Target1, typename Target2, typename Source1, typename Source2) struct convert_to< std::pair<Target1,Target2>, std::pair<Source1,Source2> > { static std::pair<Target1,Target2> apply(std::pair<Source1,Source2>& v) { { return std::pair<T1,T2>(convert_to<T1>(from.first), convert_to<T2>(from.second)); } }; } Conclusion Classes or algorithms relying on a conversion by copy-construction or by the conversion operator can be made more generic by relaying in a function that explicitly states this conversion. Thus, instead of requiring Target(from) require convert_to<Target>(from) The same applies to classes or algorithms relying on the assignment operator. So instead of requiring to = from require assign_to(to, from); The default implementation of assign_to relies on the assignment operator template < typename Target, typename Source > To& assign_to(Target& to, const Source& from) { to = from; return to; } and with the workaround namespace partial_specialization_workaround { template < typename Target, typename Source > struct assign_to { static To& apply(Target& to, const Source& from) { to = from; return to; } }; } template < typename Target, typename Source > To& assign_to(Target& to, const Source& from) { return partial_specialization_workaround::assign_to<Target,Source>::apply(to, from); } For classes that are explicitly convertible and having a self assignment operator it is easy to make a specialization of assign_to as follows. to = convert_to<Target>(from); The rationale is that if there was not a copy constructor from a Source seems reasonable to think that there will not be an assignment operator. So in most of the cases, once we have specialized the convert_to function we recover a reasonable implementation for the assign_to function. When doing multiple assignments we use to do a = b = c; With assign_to we could do assign_to(a, assign_to(b, c)); and if we find this not really readable we can try with tie(a) = tie(b) = c; The behavior of tie recall the tie function of Boost.Tuple, but instead assigning multiple variable at once, assign only one by calling assign_to. So one of the advantages of using this common functions is uniformity. The other is that now we are able to find all the explicit conversions to one type, as we can do with explicit casts. We can even generalize this, so classes or algorithms relying on a member function, can be made more generic by relaying on a free function. The default function implementation could just call to the member function with the equivalent prototype, but this is out of the scope of this library. Note that this is already the case of the free functions as swap(), begin(), next(), end(), ... What about changing the C++ standard? C++1x has added explicit conversion operators, but they must always be defined in the Source class. The same applies to the assignment operator, it must be defined on the Target class. What it will interesting is to be able to add constructors and assignments operators to the class std::pair, so we can say that two pairs are convertible if the parameters are explicitly convertible using a convert_to function template<class U , class V> //requires HasConvertTo<T1, const U&> && HasConvertTo<T2, const V&> std::pair& operator=(const std::pair<U , V>& p) { return std::make_pair(convert_to<T1>(p.first), convert_to<T1>(p.second)); } But this is not possible. We can not add operators to a class from outside. A more generic alternative could be to make an evolution to the standard, so the convertible concept takes car of extrinsic conversions. We could be able to implicitly or explicitly add extrinsic conversion operators between unrelated types. Assignment operators could also be specialized. template < typename To, typename From > operator To(const From& val); template < typename To, typename From > To& operator=(To& to, const From& from); For example we could specialize the conversion from as chrono::time_point<Clock, Duration> to posix_time::ptime follows template < class Clock, class Duration> operator boost::posix_time::ptime(const boost::chrono::time_point<Clock, Duration>& from) { typedef boost::chrono::time_point<Clock, Duration> time_point_t; typedef boost::chrono::nanoseconds duration_t; typedef boost::duration_t::rep rep_t; rep_t d = boost::chrono::duration_cast<duration_t>(from.time_since_epoch()).count(); rep_t sec = d/1000000000; rep_t nsec = d%1000000000; return boost::posix_time::from_time_t(0)+ boost::posix_time::seconds(static_cast<long>(sec))+ boost::posix_time::nanoseconds(nsec); } The convert_to and the assign_to functions preted to be a library solution to the convertibility of unrelated types problem. Best regards, _____________________ Vicente Juan Botet Escribá

5 12

[rfc] a library for gesture recognition, speech recognition, and synthesis
by Stjepan Rajko 26 Oct '09

26 Oct '09

Hello, For the past few years I've been working on the AME Patterns library - a generic library for modeling, recognition and synthesis of sequential patterns. So far it's been applied mostly to gesture recognition (e.g., recognition of mouse gestures, full body gestures from video or motion capture data, accelerometer gestures), but recently it has also shown some good results on speech datasets. It can also be used to synthesize the same kinds of patterns it can recognize (e.g., you could use it to synthesize a gesture or speech, or purely numerical patterns). The library provides support for hidden Markov models and other related models. The design is concept-based, and the library uses the Boost Graph Library, Boost.Range (including the RangeEx extension), Boost.Fusion, Boost.Math, Boost.Random, and other boost libraries. The documentation for the library is available here: http://ame4.hc.asu.edu/amelia/patterns/ However, the documentation is lacking, so I'm curious to know which parts of the functionality (if any) are of interest to the boost community, so I know what parts of the documentation to focus on. I am also considering proposing a presentation of this library to BoostCon. The library is currently released under the GPL, which I realize is not acceptable to some. Please let me know your thoughts. If anyone is interested in using this library, please let me know what you'd like to use it for and I'd be happy to help you get started. Kind regards, Stjepan

2 3

[conversion] How to repere assignement to a variable? (was [property] interest in C# like properties for C++?)
by vicente.botet 26 Oct '09

26 Oct '09

Hi, in the thread about C# like properties we were talking about the advantage to be able to repere assignation to properties. I said that, another way to repare the assignments is to use a free function assign_to, like we use the free function swap, or the cast family functions. assign_to(a.p_X, 1); assign_to call by default the assignment operator. If we want transitive assignation a = b = c; we could do assign_to(a, assign_to(b, c)); and if we find this not really readable we can try with tie(a) = tie(b) = c; tie is a template function returning an ca_wrapper. template <typename T> ca_wrapper <T> tie(T& r) { return ca_wrapper<T>(r); } ca_wrapper is responsable to transforming the assignation and operator conversion on a call to assign_to and no more. template <typename T> class ca_wrapper { T& ref_; public: ca_wrapper(T& r) : ref_(r) {} template <typename U> T& operator =(U const& u) { return assign_to(ref_, u); } template <typename U> operator U() { return convert_to(ref_, u); } }; The advantage of having a specific function is that we can specialize the assign_to function for unrelated classes. The Boost.Conversion library (on the review schedule) defines two free functions convert_to and assign_to which by default use the conversion operator and the assignment. We can see convert_to as a getter and assign_to as a setter. The major advantage is that with a uniform syntax, the user can however specialize them to do conversion and assignations between unrelated types. I don't know if tie is a good name to manage with assignation of a variable, I have taken the name from the Boost.Tuple? Regards, _____________________ Vicente Juan Botet Escribá P.S. tie and ca_wrapper are new features of Boost.Conversion v.0.3

2 3

boost design details
by wildinto wildinto 26 Oct '09

26 Oct '09

hi all, because i'm studying the generic programming, i just want to study boost to get the most useful skills, but i can't find any design details about boost. such as boost bind, so, anyone who can tell where i can find the design details about the design of each boost lib ? thanks very much! best regards, Thunder

1 0

[BGL] [Property Map] PropertyGraph concept
by Cosimo Calabrese 26 Oct '09

26 Oct '09

Hi to all, I've taked a look to the PropertyGraph concept, and it defines the following valid expression: get(p, g, x) and its return type: boost::property_traits<Map>::*value_type* Also the docs of Property Map library says that the get() function return the property *by value*, making a copy of the property. But looking to the \boost\graph\detail\adjacency_list.hpp file, I've noticed that the return value of the get function is: typename boost::property_traits< typename boost::property_map<typename Config::graph_type, Property>::type >::*reference* Why this difference? Or they are the same think? Which is the correct specific? Thanks in advance, Cosimo Calabrese.

2 1

[RegEx] Performance degradation since 1.36
by Dave Vest 26 Oct '09

26 Oct '09

I've just downloaded boost 1.40, compiled the libraries, and re-compiled our application. Part of our application uses regular expressions extensively to search through source code and the performance appears to be up to 5 x slower in release mode than with the 1.36 libraries. Boost source (no modifications) compiled with Visual Studio 2008 on Win 7. (Note: 1.36 was compiled with VS 2008 on Win Vista.) bjam debug release --with-thread --with-regex --with-date_time link=static Regex creation: boost::regex::flag_type flags = boost::regex::perl | boost::regex::optimize | boost::regex::icase); boost::regex * pengine = new boost::regex(strSampleExpression, flags); .. Regex use: boost::regex_iterator<char const*> itMatch(pszStr, pszStr + nStrLen, *pengine); boost::regex_iterator<char const*> itEnd; if ( itMatch != itEnd ) { . } A simple for(int i=0;i<100000;++i) loop test shows huge differences. Any ideas why 1.40 is so much slower? Some change in default traits or some documentation note I've missed?

1 0