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

proposal interval container; ITL moved to the boost sandbox
by Joachim Faulhaber 11 Nov '09

11 Nov '09

Dear boosters, after completion of a lot of boostification work I moved my Interval Template Library to the boost sandbox in the boost project centric form: https://svn.boost.org/trac/boost/browser/sandbox/itl itl boost itl [itl_xt] [validate] libs itl [itl_xt] [validate] I have split up the original library into three parts: (1) itl, (2) itl_xt and (3) validate. Core part 1 'ITL' contains all interval container class templates. Only this part will be prepared for a formal submission. Part 2 'itl_xt' contains extended parts of the original library that do not belong to the core interval container data structures and might be proposed for later extensions. Part 3 'validate' contains the sources for the law based test automaton 'LaBatea' that has been used for an automated check of the ITLs correctness. Parts 2 and 3 do not yet conform boost standards and naming conventions and are not yet intended as contributions to boost. On the core ITL-part I have done the following: + Removed all virtual functions via introduction of mixins + Integrated deeper into boost libraries replacing own code by e.g. boost::type_traits and boost::mpl + Minimized the class template interfaces by transforming member functions into non member function templates. + Made interval containers more interoperable by overloading operators and global function templates. + Wrote a test suite using boost unit test tools. Tested for boost-instance types boost::date_time and boost::rational + Provided jamfiles to build and run examples and tests. + All examples and tests have been compiled, linked and run successfully with msvc_9.0 and gcc_3.4.4(cygwin). Next I am going to write boost style html-documentation. >From the boost web page I don't see a clear recommendation for a preferable way of doing that. Handcoded? Generated with BoostBook? Is there a reference library that has an exemplary standard documentation? Cheers Joachim

3 4

[utility] auto_buffer v2
by Thorsten Ottosen 07 Oct '09

07 Oct '09

Dear All, Hereby an updated class. Thanks to all who contributed with comments to the first try. I have made the following changes: 1. push_back() overloads are now growing 2. added swap() (boy, was this nasty to implement). I assume the allocator can be wapped without throwing. How do other people copy with this problem? 3. added copy-constructor + copy-assignment 4. made the min capacity equal to N, the number of elements in the stack buffer 5. the size of the internal buffer is now controlled via two policies: template< unsigned N > struct store_n_objects; template< unsigned N > struct store_n_bytes; the default is store_n_objects<256>. The reason is that we don't want the capacity to change just because we compile on a different platform. 6. added comparison operators Comments most welcome! best regards -Thorsten

4 7

[Endian] Version 0.10 available - Binary I/O added
by Beman Dawes 16 Sep '09

16 Sep '09

Version 0.10 of the Endian Integers library is available. Docs: http://mysite.verizon.net/beman/endian-0.10/libs/integer/doc/endian.html Zip: http://mysite.verizon.net/beman/endian-0.10.zip Sandbox: http://svn.boost.org/svn/boost/sandbox/endian This version adds binary I/O for both endian integers (<boost/integer/endian_binary_stream.hpp>) and C++ built-in types + std::string (<boost/integer/endian_binary_stream.hpp>). Support for C++0x features has also been added, ensuring that an Endian integer on C++0x is a POD. Comments appreciated! My Endian TODO list is pretty well cleared, so there are comments to the contrary, the library will be submitted for formal review in a few days. --Beman

3 4

RFC: interest in Unicode codecs?
by Cory Nelson 23 Jul '09

23 Jul '09

Is there interest in having a Unicode codec library submitted to Boost? Here is what I have (only tested with GCC 4.3 on Debian, and VC++ 2008): http://svn.int64.org/viewvc/int64/snips/unicode.hpp Right now it is pretty simple to use: transcode<utf8, utf16le>(forwarditerator, forwarditeratorend, outputiterator, traits [, maximum]); transcode<wchar_encoding, utf32be>(inputrange, outputrange, traits [, maximum]); There is also a codecvt facet which supports any-to-any. Supports UTF-8, UTF-16, and UTF-32, in little or big endian. Has a special wchar_encoding that maps to UTF-16 or UTF-32 depending on your platform. A traits class controls error handling. -- Cory Nelson

11 30

Re: [boost] RFC: interest in Unicode codecs?
by Graham 18 Jul '09

18 Jul '09

Dear Phil, >Having said all that, I must say that I actually use the code that I >wrote quite rarely. I now tend to use UTF8 everywhere and treat it as >a sequence of bytes. Because of the properties of UTF8 I find it's >rare to need to identify individual code points. For example, if I'm >scanning for a matching " or ) I can just look for the next matching >byte, without worrying about where the character boundaries are. Using UTF-8 can work well if you are only targeting American and Western Europe for non-literary use. If you need to support the rest of the world you really need to move to UTF-32 due to the large number of characters and the grapheme and glyph handling [e.g. in Urdu you can type 3 characters and they are displayed as a single combined glyph, and the cursor should never be placed between them]. Even in UTF-8 things can get a bit tricky. For example, where do you break the line if you needed in the middle of: joe)jack -> joe) <br> jack joe(jack -> joe <br> (jack joe+jack -> guess which is the standard ! For programmers we don't mind too much, but when you are writing text editors this can be really important. Now think how many characters there are with special rules on whether they can be split before, after, or never split, and you start to touch on the reason for the Unicode standard and why you need character properties. Yours, Graham

5 4

Mark throw_exception as noreturn?
by Andrey Semashev 05 Jul '09

05 Jul '09

Hi, I was wondering why the throw_exception function is not marked as noreturn? This makes it troublesome to use it as a drop-in replacement for throw statements as it starts to flag compiler warnings about missing return statements in non-void functions. I suggest to mark the function as noreturn at least for compilers that support it. GCC has __attribute__((noreturn)), MSVC has __declspec(noreturn).

4 6

[Graph] iterator range splitting
by Tim Keitt 28 Jun '09

28 Jun '09

I've run into some problems with the Graph library as there is a lot of code that splits iterator ranges. An example of this is: (from depth_first_search.hpp) template <class VertexListGraph, class DFSVisitor, class ColorMap> void depth_first_search(const VertexListGraph& g, DFSVisitor vis, ColorMap color) { // // should the below not be: // graph_traits<VertexListGraph>::iterator vi, vend; // tie(vi, vend) = vertices(g); // if ( vi == vend ) ... ??? // or perhaps to be more terse // if ( empty_range(vertices(g)) ) // where empty_range(g) compares first and second // if (vertices(g).first == vertices(g).second) return; depth_first_search(g, vis, color, *vertices(g).first); } This is causing problems in my code where I have defined custom graph classes. In my case out_edges(g) != out_edges(g) because memory is allocated within the out_edges call and successive calls will return different ranges (vertex ranges are not a problem in my case as I use a simple counting iterator). Must out_edges(g) == out_edges(g) for a graph class to meet the Graph library requirements? If not, then a good bit of the code needs to be altered and possibly some of the iterator macros deprecated. Below I've located every instance where the first or second member of an iterator pair is thrown away. These cases are only problematic if the retained iterator is later compared to an iterator from another range. The fix is simple. One only needs to retain both members of the iterator pair. I am willing to provide a patch if it is agreed that the current code is wrong. THK egrep '(vertices|edges)\(.*\)\.(first|second)' * adjacency_list_io.hpp: for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi){ adjacency_list_io.hpp: for (ei = edges(graph).first; ei != edges(graph).second; ++ei){ adjacency_list_io.hpp: for (vi = vertices(this->graph).first; vi != vertices(this->graph).second; ++vi){ adjacency_matrix.hpp: return *vertices(g).first; adjacency_matrix.hpp: return *vertices(g).first; adj_list_serialize.hpp: for (vi = vertices(graph).first; vi != vertices(graph).second; ++vi) { adj_list_serialize.hpp: for (ei = edges(graph).first; ei != edges(graph).second; ++ei){ bc_clustering.hpp: if (edges(g).first == edges(g).second) return; bc_clustering.hpp: edge_descriptor e = *max_element(edges(g).first, edges(g).second, cmp); bc_clustering.hpp: } while (!is_done && edges(g).first != edges(g).second); cuthill_mckee_ordering.hpp: if (vertices(G).first == vertices(G).second) cuthill_mckee_ordering.hpp: if (vertices(G).first == vertices(G).second) depth_first_search.hpp: if (start_vertex != implicit_cast<Vertex>(*vertices(g).first)){ vis.start_vertex(start_vertex, g); depth_first_search.hpp: if (vertices(g).first == vertices(g).second) depth_first_search.hpp: depth_first_search(g, vis, color, *vertices(g).first); depth_first_search.hpp: if (vertices(g).first == vertices(g).second) depth_first_search.hpp: *vertices(g).first), edge_connectivity.hpp: std::set_difference(vertices(g).first, vertices(g).second, edge_connectivity.hpp: std::set_difference(vertices(g).first, vertices(g).second, fruchterman_reingold.hpp: Dim minX = position[*vertices(g).first].x, maxX = minX; fruchterman_reingold.hpp: Dim minY = position[*vertices(g).first].y, maxY = minY; graph_test.hpp: bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; graph_test.hpp: bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; howard_cycle_ratio.hpp: if (boost::out_edges(vd1, m_g).first == boost::out_edges(vd1, m_g).second) throw bad_graph(m_vim[vd1]); howard_cycle_ratio.hpp: mcr_edge_t ed = *boost::out_edges(vd1, m_g).first; howard_cycle_ratio.hpp: good_vertex = boost::target(*boost::out_edges(good_vertex, m_pi_g).first, m_pi_g); howard_cycle_ratio.hpp: pi_edge_t tmp_ed = *(boost::out_edges(vd, m_pi_g).first); howard_cycle_ratio.hpp: remove_edge(*(out_edges(m_g2pi_g_vm[vd], m_pi_g).first), m_pi_g); is_kuratowski_subgraph.hpp: bipartition_start = next(next(next(vertices(K_3_3).first))); is_kuratowski_subgraph.hpp: si = vertices(contracted_graph).first; isomorphism.hpp: for (typename graph_traits<Graph1>::edge_iterator e1 = edges(g1).first; isomorphism.hpp: e1 != edges(g1).second; ++e1) { isomorphism.hpp: for (typename graph_traits<Graph2>::edge_iterator e2 = edges(g2).first; isomorphism.hpp: e2 != edges(g2).second && !found_edge; ++e2) { iteration_macros.hpp: bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second; iteration_macros.hpp: BGL_FIRST(__LINE__) = vertices(GNAME).first, BGL_LAST(__LINE__) = vertices(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = vertices(GNAME).first, BGL_LAST(__LINE__) = vertices(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = edges(GNAME).first, BGL_LAST(__LINE__) = edges(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = edges(GNAME).first, BGL_LAST(__LINE__) = edges(GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = adjacent_vertices(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = adjacent_vertices(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = adjacent_vertices(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = adjacent_vertices(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = out_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = out_edges(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = out_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = out_edges(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = in_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = in_edges(UNAME, GNAME).second; \ iteration_macros.hpp: BGL_FIRST(__LINE__) = in_edges(UNAME, GNAME).first,\ iteration_macros.hpp: BGL_LAST(__LINE__) = in_edges(UNAME, GNAME).second; \ johnson_all_pairs_shortest.hpp: typename Traits2::vertex_descriptor s = *vertices(g2).first; kamada_kawai_spring_layout.hpp: for (vertex_iterator ui = vertices(g).first, end = vertices(g).second; kamada_kawai_spring_layout.hpp: vertex_iterator ui, end = vertices(g).second; kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: vertex_descriptor p = *vertices(g).first; kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { kamada_kawai_spring_layout.hpp: for (ui = vertices(g).first; ui != end; ++ui) { king_ordering.hpp: if (vertices(G).first == vertices(G).second) king_ordering.hpp: if (vertices(G).first == vertices(G).second) metric_tsp_approx.hpp: Vertex v(*vertices(g).first); metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, w, metric_tsp_approx.hpp: metric_tsp_approx_from_vertex(g, *vertices(g).first, w, id, vis); metric_tsp_approx.hpp: Tree t(mst, *vertices(mst).first, minimum_degree_ordering.hpp: adj_iter nu = adjacent_vertices(u_node, G).first; planar_canonical_ordering.hpp: vertex_t first_vertex = *vertices(g).first; prim_minimum_spanning_tree.hpp: choose_param(get_param(params, root_vertex_t()), *vertices(g).first), prim_minimum_spanning_tree.hpp: (g, *vertices(g).first, predecessor_map(p_map). property_iter_range.hpp: return std::make_pair(iter(vertices(graph).first, get(tag, graph)), property_iter_range.hpp: iter(vertices(graph).second, get(tag, graph))); property_iter_range.hpp: return std::make_pair(iter(vertices(graph).first, get(tag, graph)), property_iter_range.hpp: iter(vertices(graph).second, get(tag, graph))); property_iter_range.hpp: return std::make_pair(iter(edges(graph).first, get(tag, graph)), property_iter_range.hpp: iter(edges(graph).second, get(tag, graph))); property_iter_range.hpp: return std::make_pair(iter(edges(graph).first, get(tag, graph)), property_iter_range.hpp: iter(edges(graph).second, get(tag, graph))); push_relabel_max_flow.hpp: current(num_vertices(g_), out_edges(*vertices(g_).first, g_).second), push_relabel_max_flow.hpp: current[u] = out_edges(u, g).first; push_relabel_max_flow.hpp: current[v] = out_edges(v, g).first; push_relabel_max_flow.hpp: for (ai = current[u], ai_end = out_edges(u, g).second; push_relabel_max_flow.hpp: current[u] = out_edges(u, g).first; push_relabel_max_flow.hpp: for (; current[u] != out_edges(u, g).second; ++current[u]) { push_relabel_max_flow.hpp: if (current[u] == out_edges(u, g).second) { push_relabel_max_flow.hpp: ai = out_edges(u, g).first; push_relabel_max_flow.hpp: while (excess_flow[u] > 0 && ai != out_edges(u, g).second) { push_relabel_max_flow.hpp: ai = out_edges(u, g).first; random.hpp: i = vertices(g).first; random.hpp: return *vertices(g).first; random.hpp: i = edges(g).first; random.hpp: return *edges(g).first; sloan_ordering.hpp: s = *(vertices(G).first); undirected_dfs.hpp: if (start_vertex != *vertices(g).first){ vis.start_vertex(start_vertex, g); undirected_dfs.hpp: undirected_dfs(g, vis, vertex_color, edge_color, *vertices(g).first); undirected_dfs.hpp: *vertices(g).first), -- Timothy H. Keitt http://www.keittlab.org/

6 16

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

[mpl] is there a or_seq like logical metafunction?
by vicente.botet 17 Jun '09

17 Jun '09

Hello, I needs calculate the mlp::or_ of a sequence of nullary logical metafunction. This seams quite simple. I have do the following: <code> template <typename Seq> struct or_seq; template <typename Seq, long N> struct or_seq_aux : mpl::or_< typename mpl::front<Seq>::type, or_seq<typename mpl::pop_front<Seq>::type> > {}; template <typename Seq> struct or_seq_aux<Seq, 1> : mpl::front<Seq>::type {}; template <typename Seq> struct or_seq : or_seq_aux<Seq, mpl::size<Seq>::value> {}; </code> Is there a boost or_seq like logical metafunction? Is there a better way to do it? I would be extremely interested in any suggestions. Best regards --------------------------- Vicente Juan Botet Escriba

5 34

[mpl]iter_fold_if Forward Backward rationale?
by Larry Evans 10 Jun '09

10 Jun '09

Why is there both a ForwardOp and BackwardOp template argument to iter_fold_if? https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/iter_fold_if.hpp#L… I would have thought that only 1 was needed. Since iter_fold_if is not documented here: http://www.boost.org/doc/libs/1_38_0/libs/mpl/doc/refmanual/refmanual_toc.h… I assume it's not meant to be used by the user, but is only an implementation detail; however, it, or a variation, might be useful to implement the and_seq mentioned here: http://article.gmane.org/gmane.comp.lib.boost.devel/186204 As shown in that post, the template, while_if_then was used, and it does not require anything like both a ForwardOp and BackwardOp, it just requires the If and Then unary metafunctions. One problem I encountered with while_if_then was moving to the end of the sequence, at which time the Then metafunction couldn't be called; hence, I had to make it lazy to avoid dereferencing the end iterator. Is that somehow related to the need for BackwardOp in iter_fold_if. IOW, because iter_fold_if might reach the end iterator, it has to backup? I'm really asking because in the variadic template version of mpl, I wondering if iter_fold_if could be replaced with something like while_if_then (which may be renamed fold_if to be more consistent with other names with similar function). Any insight about the rationale for the iter_fold_if would probably save me considerable time in deciding whether it can be replaced with the proposed fold_if. -regards, Larry

3 28