July 2007 - Boost - lists.preview.boost.org

Proposed addition to the iterator library for iterating over all tuples.
by Alex Mendes da Costa 19 Jun '09

19 Jun '09

Hi folks: I quite often have to write code to do the following: Given N sequences, generate all the N-tuples s.t. the i'th element in each tuple is drawn from the i'th sequence. For example, if sequence S1 is { 1, 2, 3 } and sequence S2 is { 10, 20 }, I need to generate these tuples: (1, 10), (2, 10), (1, 20), (2, 20). I think this problem could be solved elegantly with a iterator similar to zip_iterator. I have some questions: (1) Is there already a way to do this in boost? (2) If not, would this be a worthwhile addition to the iterator library? (3) If so, could I contribute code for this, or must the existing library owners write it? (4) If so, how would I go about getting my code added? Most of the docs seem to be about submitting entire libraries, rather than extensions to existing libraries. Thanks, Alex

4 18

[fusion] list/detail/at_impl.hpp, Suggest recrusive elem_at_c instead of recursive apply
by Larry Evans 24 Oct '07

24 Oct '07

In boost/fusion/.../list/detail/at_impl.hpp the apply is recursive; however, the only reason for the recursion is to "find the right element type". The other reason for apply is the same as that of the apply in.../vector/detail/at_impl.hpp. "find the right element type" in vector's at_impl is done with mpl::at. The similarity between list and vector at_impl would be more apparent if: template <typename Sequence, int N> struct elem_at_c { typedef typename mpl::eval_if< mpl::bool_<N == 0> , mpl::identity<typename Sequence::car_type> , elem_at_c<typename Sequence::cdr_type, N-1> >::type type; }; were used to find the right element type. Then the frist part of list::at_impl::apply would be: template <typename Sequence, typename N> struct apply { typedef elem_at_c<Sequence, N::value> element; typedef typename mpl::eval_if< is_const<Sequence> , detail::cref_result<element> , detail::ref_result<element> >::type type; which is very similar to the counterpart in vector: template <typename Sequence, typename N> struct apply { typedef mpl::at<typename Sequence::types, N> element; typedef typename mpl::eval_if< is_const<Sequence> , detail::cref_result<element> , detail::ref_result<element> >::type type;

2 3

[soc] Boost.extension/reflection project advances
by Mariano Gabriel Consoni 16 Oct '07

16 Oct '07

Hi Community...! As some of you may know, I'm working on a SoC project called "Boost.extensions and reflection". This mail is just to keep you informed about the project advances. At this time, we have very good news. The library is now near completion, and we expect submitting it for revision in the next days. We've been worked the last two weeks in the following tasks: - Code style: continued improving the code style according Boost guidelines. - Build: improved the Jamfiles to work well in more platforms. - Boost::function: migrated some code to (optionally) use boost::function. - Benchmarks: made new benchmarks to test the new integrations. - Performance analysis: documented the results of the benchmarks. - Preprocessor: replaced a lot of boiler-plate code with (optional) boost::preprocessor macros. - Dependencies flags: documented the optional dependencies and how to enable them. As I have finished all the tasks planned in my proposal (and a lot more :) ) I will advance to Reflection part and Jeremy (Pack, original author) will finish some remaining tasks of Extension. Bye! -- Mariano

4 6

[ANN] Xpressive 2.0 pre
by Eric Niebler 12 Oct '07

12 Oct '07

It's a poorly kept secret that I've been adding new features to Xpressive on CVS HEAD for a while now. So here are the features already implemented (documentation forthcoming) for Xpressive 2.0: << Semantic Actions >> Specify code to execute when parts of a regex match, a-la Spirit's semantic actions. Eg.: if you want to parse a string of name/value pairs into a std::map, you might: std::map<std::string, int> result; std::string str("aaa=>1 bbb=>23 ccc=>456"); // Like "(\\w+)=>(\\d+)": sregex pair = ( (s1= +_w) >> "=>" >> (s2= +_d) ) [ ref(result)[s1] = as<int>(s2) ]; sregex rx = pair >> *(+_s >> pair); if(regex_match(str, rx)) { assert(result["aaa"] == 1); assert(result["bbb"] == 23); assert(result["ccc"] == 456); } The actions are placed on a queue and executed in order only when the regex match succeeds. << Custom Assertions >> Use the check() function to create a boolean predicate that can participate in the match. Here's a regex that recognizes two integers only if the first is less than the second: sregex rx = ( (s1= +_d) >> ' ' >> (s2= +_d) ) [ check( as<int>(s1) < as<int>(s2) ) ]; Unlike actions, predicates execute immediately. You can also define the predicate out-of-line as a function object. << Dynamic Regex Grammars with Named Regexes >> Using regex_compiler, you can map a name to a regex object, and then refer to that regex from another by name. In this way, you can build grammars from regexes at runtime. sregex_compiler comp; sregex rx = comp.compile("^bar(?$RE)baz$"); comp.compile("(?$RE=)\\d+ \\d+"); There's an alternate syntax for associating a name with a regex that you can use to nest a static regex in a dynamic one. Eg., the last line above could be: comp["RE"] = +_d >> ' ' >> +_d; With these changes, you can now nest static and dynamic regexes within each other freely, giving you lots of flexibility to build grammars and modify them on the fly. << Named Captures >> For dynamic regular expressions, you can create a named capture with (?P<name> ...). You can refer back to the named capture with (?P=name). In substitution strings (for use with regex_replace()), you can refer back to a named capture with \\g<name> when using the format_perl or format_all flags. And more .... I'd like to give props to Dave Jenkins who has been doing m4d things with this stuff already, and who has given me a laundry list of other features he'd like. The new features are only available in CVS HEAD, for now. Feedback is welcome. -- Eric Niebler Boost Consulting www.boost-consulting.com

3 7

Variable Preprocess Metaprogramming?
by Atry 20 Sep '07

20 Sep '07

As we known, there is a preprocess metaprogramming library in boost, but it is not flexible enough. we are unable to define an custom preprocess loop(something like #for or #while ?), and we are also unable to use recursion. I have an idea to do that, C/C++ allows recursion of #include, so we can put the codes we want to evaluate repeatedly to a head, and include itself depends on a preprocess condition. But if we wrote code below, we would meet a error of macro redefinition. /**** foo.hpp ****/ #if FOO < 10 // do something with I # define FOO FOO + 1 # include "foo.hpp" #endif /**** foo.hpp ****/ /**** bar.hpp ****/ #define FOO 0 #include "foo.hpp" /**** bar.hpp ****/ The problem is that an macro must not depends on itself. Thus, to change a preprocess variant, I use a bit of #if to transfer value of a macro to some temporary macro. see my code below: /**** begin_set_value.hpp ****/ #if (BOOST_VPP_VALUE & (1 << 0)) == 0 #define BOOST_VPP_TEMPORARY_BIT_0 0 #else #define BOOST_VPP_TEMPORARY_BIT_0 1 #endif #if (BOOST_VPP_VALUE & (1 << 1)) == 0 #define BOOST_VPP_TEMPORARY_BIT_1 0 #else #define BOOST_VPP_TEMPORARY_BIT_1 1 #endif /* ... */ #if (BOOST_VPP_VALUE & (1 << 30)) == 0 #define BOOST_VPP_TEMPORARY_BIT_30 0 #else #define BOOST_VPP_TEMPORARY_BIT_30 1 #endif #if (BOOST_VPP_VALUE & (1 << 31)) == 0 #define BOOST_VPP_TEMPORARY_BIT_31 0 #else #define BOOST_VPP_TEMPORARY_BIT_31 1 #endif #undef BOOST_VPP_VALUE #define BOOST_VPP_VALUE \ (BOOST_VPP_TEMPORARY_BIT_0 << 0 ) \ + (BOOST_VPP_TEMPORARY_BIT_1 << 1 ) \ + (BOOST_VPP_TEMPORARY_BIT_2 << 2 ) \ + (BOOST_VPP_TEMPORARY_BIT_3 << 3 ) \ /* ... */ \ + (BOOST_VPP_TEMPORARY_BIT_29 << 29 ) \ + (BOOST_VPP_TEMPORARY_BIT_30 << 30 ) \ + (BOOST_VPP_TEMPORARY_BIT_31 << 31 ) \ /*BOOST_VPP_VALUE*/ /**** begin_set_value.hpp ****/ Now, the BOOST_VPP_VALUE is depends on some of BOOST_VPP_TEMPORARY_BIT_n, and can be used to change the former macro: #define FOO 0 #define BOOST_VPP_VALUE FOO #include "begin_set_value.hpp" #undef FOO #define FOO (BOOST_VPP_VALUE + 1) But, FOO depends on BOOST_VPP_TEMPORARY_BIT_ns, and can not be change again, the solution is that A must a variant depends on some other BIT_n definition instead of directly depends on BOOST_VPP_VALUE. Actually, I implements an variant stack to allocate and release these variant. I think the concept of variable preprocess is useful, if Boost.Typeof or Boost.Bind use that, these code they need would be less than copying same codes. I have upload a sample on vault, file name is variable_preprocess.zip. http://boost-consulting.com/vault/index.php?&direction=0&order=&directory=P… http://boost-consulting.com/vault/index.php?action=downloadfile&filename=va… All code is validated by wave, thank you for your attention.

6 12

[proto]context interface allowing "packaged" node args?
by Larry Evans 27 Aug '07

27 Aug '07

Hi Eric, I need a context with something like the following methods: template< typename Tag, typename Left, typename Right > result_type operator()(expr<Tag, Left, Right> const &expr) const { std::cout<<std::setw(indent) <<""<<"binary_expr:"<<expr.get_instance()<<"\n"; indent+=2; proto::eval(left, *this); proto::eval(right, *this); indent-=2; } where the expression tree node argument remains "packaged": (expr<Tag, Left, Right> const &expr) in contrast to the unpacked version: (Tag, Left const &left, Right const &right) shown in, for example: http://boost-sandbox.sourceforge.net/libs/proto/doc/html/boost_proto/user_s… IOW, the calculator.html page suggests an interface like: template< typename Tag, typename Left, typename Right > result_type operator()(Tag, Left const &left, Right const &right) const { std::cout<<std::setw(indent)<<""<<"binary_expr\n"; indent+=2; proto::eval(left, *this); proto::eval(right, *this); indent-=2; } where there's no access to the "packaged" extended node, expr<Tag,Left,Right>, where the extension is, for example: struct xmpl_domain; struct xmpl_delta { unsigned const my_instance; static unsigned our_instances; xmpl_delta(void) : my_instance(++our_instances) {} xmpl_delta(xmpl_delta const&) : my_instance(++our_instances) {} void operator=(xmpl_delta const&) {} unsigned get_instance(void)const { return my_instance; } }; unsigned xmpl_delta::our_instances=0; template<typename Expr> struct xmpl_expression : proto::extends<Expr, xmpl_expression<Expr>, xmpl_domain> , xmpl_delta { ... }; I've looked at the formated output of the preprocessed context.hpp; however, I'm still having difficulty figuring out if this "packaged" method interfaces is possible. Any help is appreciated. TIA. -regards, Larry

4 12

[range] range library proposal implementation rev.2
by shunsuke 26 Aug '07

26 Aug '07

Hi, all A new version of Oven, a range library proposal implementation, has been uploaded to Boost.Vault/Algorithm. The file: http://tinyurl.com/2axp2l Range Library Proposal: http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1871.html An example "infinite sequence of factorials": void test() { BOOST_AUTO(factorials, expression(counting(1, max_count)|scanned(1, regular(lambda::_1 * lambda::_2))) ); int const answer[] = { 1,1,2,6,24,120,720,5040,40320,362880 }; BOOST_CHECK( equals(factorials|taken(10), answer) ); } This library is highly preliminary, but moderately tested. Any feedback appreciated. Regards, -- Shunsuke Sogame

2 12

[BGL] Tools for planar graph testing/embedding/drawing in the vault
by Aaron Windsor 21 Aug '07

21 Aug '07

Hi all, I've implemented a small suite of tools for dealing with planar graphs and would like to add it to the BGL. The core of this suite is built around the recent Boyer-Myrvold algorithm for planarity testing/embedding. (see http://www.emis.de/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf) A graph is planar if it can be drawn in two-dimensional space with no edge crossings. A graph is non-planar exactly when it contains a subgraph that is an expansion of one of two special subgraphs, called "Kuratowski subgraphs." This face makes it possible not only to detect that a graph is non-planar, but to prove it's non-planar by isolating one of these subgraphs. In addition to the obvious applications to graph-drawing, planar graphs are often simpler to deal with in optimization problems, and many problems that are NP-complete (most likely requiring exponential time to solve) have efficient algorithms or better approximation guarantees for the special case of planar graphs. The functions I've implemented allow one to: - Test a graph for planarity. - Embed a planar graph in the plane. - Find and verify a minimal Kuratowski subgraph in a non-planar graph. - Create a straight-line drawing of a planar graph (a mapping of vertices to points in the plane such that all edges can be drawn with straight line segments). - Traverse the faces of a planar graph using generic visitor event points in the spirit of the BGL depth-first and breadth-first search algorithms. With appropriate visitors, this traversal can be used to count the faces of a planar graph, triangulate a planar graph, or find a dual of a planar graph, among other things. With a few caveats about the efficiency of vertex index maps, etc. all of the functions above run in linear time with respect to the number of vertices in the graph, which is optimal. I've put two sets of files in the vault under Home/Algorithms/graph: the first is called planar_graphs.zip (also planar_graphs.tar.gz) and contains the .hpp files, the documentation, and the examples. The second is called planar_graph_testing.zip (also planar_graph_testing.tar.gz) and contains over 1000 test graphs and a small program that can be compiled to give an example of how these planar graph tools can be used. I'd appreciate any comments! Regards, Aaron

5 18

[Ann] Variadic Templates
by Doug Gregor 20 Aug '07

20 Aug '07

Hello Fellow Boosters, I have just completed implementing support for "Variadic Templates" in GCC. Variadic templates are C++ templates that can accept any number of "extra" template arguments, just like a function that uses C-style varargs (with "...") can accept any number of extra arguments. Unlike C varags, however, variadic templates work both for class templates and function templates, and are completely type-safe. Why do variadic templates matter for Boost? For one thing, they will allow us to eliminate the use of preprocessor metaprogramming in many, many places throughout the library. This can simplify our library implementations drastically, and eliminate those annoying "caps" on the number of arguments one can use (ever tried to use bind () with 11 arguments?). Beyond that, variadic templates are just plain fun, and there are undoubtedly a great number of metaprogramming applications. Here are a few teasers to illustrate what variadic templates can do: We can implement an MPL-like type vector with one line of code: template<typename... Types> struct vector { }; The "ellipsis" means that we can pack any number of arguments into the "template parameter pack" called Types. Of course, we can do the same for MPL's vector_c: template<typename T, T... Values> struct vector_c { }; Unimpressed? Here's an implementation of tuple that accepts any number of element types: template<typename... Values> class tuple; template<> class tuple<> { }; template<typename Head, typename... Tail> class tuple<Head, Tail...> : private tuple<Tail...> { protected: Head m_head; }; We're using recursion to build up the tuple. The ellipsis operator works with partial specializations, too, packing together "extra" arguments at the end. Of course, all of this would be useless if we couldn't write some of the other tuple operations, like operator==: inline bool operator==(const tuple<>&, const tuple<>&) { return true; } template<typename T, typename... TTail, typename U, typename... UTail> bool operator==(const tuple<T, TTail...>& t, const tuple<U, UTail...>& u) { return t.head() == u.head() && t.tail() == u.tail(); } Variadic function templates can accept any number of function arguments, so we can now (finally!) implement a type-safe printf() without mangling the tried-and-true printf() syntax or restricting ourselves to POD types: void printf(const char* s) { while (*s) { if (*s == '%' && *++s != '%') throw std::runtime_error("invalid format string: missing arguments"); std::cout << *s++; } } template<typename T, typename... Args> void printf(const char* s, const T& value, const Args&... args) { while (*s) { if (*s == '%' && *++s != '%') { std::cout << value; return printf(++s, args...); } std::cout << *s++; throw std::runtime_error("extra arguments provided to printf"); } I've also built prototypes of of Function and Bind, among other things. The Bind example is especially interesting, and worth a read (see below) Interested? There is more information and a complete implementation in GCC available at: http://www.generic-programming.org/~dgregor/cpp/variadic- templates.html I've written two documents describing variadic templates in more detail: http://www.generic-programming.org/~dgregor/cpp/brief-intro.pdf : A brief introduction to variadic templates, that walks through the printf() implementation. http://www.generic-programming.org/~dgregor/cpp/variadic- templates.pdf : A complete proposal to introduce variadic templates into C++0x. This contains annotated versions of the tuple, function, and bind prototypes along with a detailed description of the capabilities of variadic templates. The GCC implementation is complete, supporting all of the features described in the proposal. I've used it for proof-of-concept implementations of several libraries. In the (near) future, I hope to introduce variadic templates support into the "official" GCC, but I need your help! Are variadic templates worthwhile? Will they help us build better, cleaner Boost libraries in the future? Should we bring variadic templates to the C++ committee, to enable better implementations of TR1 components and eliminate the need for much of the preprocessor metaprogramming we do today? Feedback is greatly appreciated. Cheers Doug Gregor Open Systems Lab @ Indiana University

20 39

[Important] Boost Subversion repository is now online
by Douglas Gregor 20 Aug '07

20 Aug '07

Hello all, The Boost Subversion repository is now back online. All of the files in CVS (including their histories) have been imported into the Subversion repository. CVS is still available for anonymous, read- only access for now, but will not be updated. The main Boost development branch is available via anonymous, read- only checkout at: http://svn.boost.org/svn/boost/trunk/ Or for developer read/write access at: https://svn.boost.org/svn/boost/trunk/ Information about accessing the Boost Subversion repository is available at: http://svn.boost.org/trac/boost/wiki/BoostSubversion Please report any problems to me to the main Boost list, and we will try to resolve them as quickly as possible. We still need help porting the regression-testing script over to use Subversion. See Trac ticket #1122: http://svn.boost.org/trac/boost/ticket/1122 Also, there is more documentation that will need to be updated within the Boost tree. - Doug Subversion tip: when you commit a change to Subversion that fixes ticket number NNN, include the text "Fixes #NNN" in your commit log. Trac will automatically close the ticket and cross-reference the commit with the ticket. See, for example, http://svn.boost.org/trac/ boost/changeset/38330

24 112