June 2007 - Boost - lists.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

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

13 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

[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

Boost building with CMake
by Bill Hoffman 17 Aug '07

17 Aug '07

Hi, I noticed the "boost development process / scope" thread on your list. A CMake user posted a link to your discussion. There is significant interest in the CMake community to help boost transition to CMake. Several people on the CMake list have volunteered to help, and Kitware is willing to put about 2 man weeks of effort into the conversion. I think that CMake has all the features to do what you need at this point, but if any bugs or issues are discovered during the process, we can fix them and/or provide work-arounds for the issues. I realize you have not yet decided on moving to CMake, but I thought I would put out this offer so that you could consider "free" support as one of the benefits you will receive from the port to CMake. I can see this happening in two ways. One would be for a CMake developer to create initial cmake files for boost, and get the basics working. Then, the work would be turned over to the Boost community. The other way would be to have a boost developer create the build files with help and support from the CMake community. Either way works for me. Of course, no one will want to do anything unless there is a commitment to actually use CMake. I will stay on this list while you decide, and answer any questions about CMake that may come up. Thanks, and I look forward to working with the boost community in the future. -Bill

47 194

Submission to "Who's Using Boost?"
by Seweryn Habdank-Wojewódzki 09 Aug '07

09 Aug '07

Hi! I am using Boost library in Open Source library for Kohonen Neural Networks construction and training. I would like (if possible) join to famous list of Open Source users of the Boost library :-). * The name of the Application/Product/Service. Kohonen Neural Network Library (KNNL) * The name of the company (where appropriate). --- Personal initiative --- Authors: * Seweryn Habdank-Wojewódzki * Janusz Rybarski * A paragraph describing the Application/Product/Service. Kohonen neural network library is a set of classes and functions for design, train and use Kohonen networks (self organizing maps). * Any information you can provide about which parts of Boost you used, along with any comments you may have on how Boost helped your product development. KNNL Library requirements: * Boost Library ver. 1.33. o Core of library needs: + boost::bind, + boost::function, + boost::type_traits o Demonstration program uses: + boost::program_options * URLs to your companies home page, and the home page of the Application/Product/Service if there is one. http://knnl.sourceforge.net/ Best regards. -- |\/\/| Seweryn Habdank-Wojewódzki \/\/

2 1

boost::factory?
by Tobias Schwinger 22 Jul '07

22 Jul '07

Dear Boost community, do we have a function object template to wrap arbitrary constructor calls / operator new expressions somewhere in Boost, already? If not, is there any interest in such a thing? Interface draft: ================ factory<T> // constructs X and returns it by value factory<T*> // uses operator new, returns a pointer Where operator() takes a variable number of arguments, forwarded to the constructor. Should there be an optional 'Allocator' template parameter? Some use cases: =============== o Transform through an explicit constructor, e.g: std::transform(from,to,out,factory<X>()); or a constructor that takes more than one argument, e.g: std::transform(from,to,out, boost::bind(factory<Y>(),12,_1)); o Generate data, e.g: std::generate_n(out,12,boost::bind(factory<Y>(),123,12)); o Creating homogeneous, polymorphic factories from heterogeneous constructors, e.g: void register_factory( std::type_info const &, boost::function<void*()> const &); // ... at function scope: register_factory( typeid(X), factory<X>() ); register_factory( typeid(Y), boost::bind(factory<Y>(),12,1) ); Implementation notes regarding the Forwarding Problem: ====================================================== For now (C++89) it might be good enough to just have operator() take its arguments by non-const reference. As usually the call will be deferred and as long as the arguments are L-Values they will be deduced even if const qualified (this might break the code of the first use case above - wrapping the factory specialization into a Boost.Bind function object without actually binding anything will work around the problem, though). Alternatively we could solve the forwarding problem (within the function object itself) using a "hammer and crowbar utility" in Fusion (overloading operator() with all combinations of templatized const/non-const reference parameters) until we have better means to do so. I personally prefer the former because it's more lightweight and might allow us to be more portable than Fusion is, however. Curiously awaiting your feedback, Tobias

8 18