- Boost - lists.boost.org

[1.41.0] New libraries?
by Beman Dawes 03 Sep '09

03 Sep '09

Are there any new libraries that will be ready for 1.41.0? There is a New Library Checklist that needs to be gone over with the release managers before merging new libraries into branches/release. See http://svn.boost.org/trac/boost/wiki/ReleasePractices/ManagerCheckList#NewL… Thanks, --Beman

2 1

[graph] quickbook reference docs and formatting
by Andrew Sutton 03 Sep '09

03 Sep '09

Jeremiah, Nick, others with opinions.... Two questions: First, I need a second opinion on some formatting alternatives for the quickbook docs w.r.t the documentation of member/non-member functions of the graph classes. These should be mostly buildable - there are some errors about missing links, but they aren't fatal. Let me know if there are issues building them. I got the doc toolchain working a while ago and I'm afraid to mess with it. I may not have the same set up as everybody else. Hopefully I do. The HTML docs give a flat listing with each function separated by a HR element, which is effective (although not especially navigable). Other lib**raries (e.g., Boost.Filesystem) present a similar listing although without the HR's to divide the content. I've tried putting these in a table to improve readability, and it works a little but, but I don't have enough control over the table to prevent auto-wrapping, which can break a function declaration line in weird places. So what's better: a flat listing or a table? Is there a third option? Generating reference docs via Doxygen (like ProgramOptions) probably isn't a viable solution since there's a lot of metaprogramming and atypical class construction going on in the BGL. Second, all of the reference docs for graph classes cite their associated types via the graph_traits and property_map templates. For most of these types, this strikes me as superfluous at best and slightly disingenuous at worst. Traits classes are only required in a generic context, not when working with a concrete type. If your graph class defines a nested type, vertex_iterator, why not use it directly? I feel that the reference documentation for data structures would be better served by focusing on the specifics of the data structure, not its generic interfaces. That's what the concepts are for. Thoughts? Andrew Sutton andrew.n.sutton(a)gmail.com

2 1

[date_time, Boost 1.40.0]
by Christoph 03 Sep '09

03 Sep '09

including boost/date_time/posix_time/posix_time.hpp or boost/date_time/gregorian/gregorian.hpp gives lots of warning for the following line(s): (boost/date_time/gregorian/conversion.hpp; posix_time, tooo) line 44 std::tm datetm = {}; // zero initialization is needed for extension members, like tm_zone I admit I don't understand the comment. Is it possible to fix that (correctly) such that including the header does not produce like 20 warnings in each .cpp file including the header? (I am using linux running gcc 4.1.2) Best regards Christoph

4 5

[serialization] using boost::serialization::collection_size_type and backwards compatibility
by joaquin＠tid.es 03 Sep '09

03 Sep '09

An observant colleague has noticed that Boost.MultiIndex serialization uses std::size_type instead of the adviced boost::serialization::collection_size_type: https://svn.boost.org/trac/boost/ticket/3365 My question is: if I just change std::size_type with boost::serialization::collection_size_type in Boost.MultiIndex serialization code, will backwards compatibility be preserved, i.e. will users be able to load archives saved with the old std::size_type variant? If not, what's the suggested way to handle this issue? Thank you, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

3 3

compile-time for-loop
by klaus triendl 03 Sep '09

03 Sep '09

I wonder whether a compile-time for-loop is useful enough so that it would get included in the mpl library; it's very similar to what fold does but it can be used for computations with types other than sequence containers. The loop construct takes a start value, a loop condition and a function calculating the next start value for the next loop recursion and additionally a state together with a binary operation serving as loop body: namespace boost { namespace mpl { template< typename Start, typename UnaryLoopTest, typename BinaryNext , typename State, typename BinaryOp > struct for_: eval_if< // loop as long as the loop condition yields true typename apply< UnaryLoopTest, typename Start::type >::type, // next loop iteration: recursive call for_< // calculate next loop value typename apply< BinaryNext, State, typename Start::type >::type, // pass on UnaryLoopTest and pass on BinaryNext UnaryLoopTest, BinaryNext, // calculate next state typename apply< BinaryOp, State, typename Start::type >::type, // pass on BinaryOp BinaryOp >, // loop termination if loop condition yields false State > {}; } } // That's an example how to use the for-loop: using namespace boost; template<typename T, T N> struct cross_total: mpl::for_< // start mpl::integral_c<T, N>, // loop condition mpl::not_equal_to<mpl::_1, mpl::integral_c<T, 0> >, // calculate next value mpl::divides<mpl::_2, mpl::int_<10> >, // state = current cross sum of already iterated digits mpl::int_<0>, // binary function is loop body: crosstotal += digit mpl::plus< mpl::_1, mpl::modulus<mpl::_2, mpl::int_<10> > > >::type {}; </code> More useful may be to calculate a number's digits for any base, which can be used to calculate the required maximum storage size for a type (I know that there's std::numeric_limits<> but this one would be more general). Klaus Triendl

4 6

[Polygon] performance
by Simonson, Lucanus J 03 Sep '09

03 Sep '09

Performance has become a critical aspect of this review with the revelation that Barend claims significant performance advantage with his recent implementation. I would like to address this issue directly and, unfortunately, I must do so by addressing Barend's implementation and comparing it to my own, which I would have preferred to avoid. I realize that this comparison of the two algorithms may appear confrontational. My intention is to focus on technical issues to allow people to understand Barend's performance claims in the context of what the two algorithms have in common and how they differ. My understanding of Barend's algorithm is based solely on what he has told me, and he refused to tell me enough to allow me to implement it myself, so if I am in error in my description of it I trust he will promptly correct me. First, I do not believe that Barend's implementation is numerically robust when instantiated with float or double. Successfully passing tests is not proof that his algorithm will not generate self intersecting polygons at its output. Specifically, it is my understanding that his algorithm snaps intersection points to the floating point grid at the end of computation when he writes out output polygons. This means that edges may move laterally a distance dependent on the exponent of the floating point value of the result. In floating point coordinates a vertex may lie arbitrarily close to a nearby edge. Even a very small lateral movement of that edge due to loss of precision in the floating point representation has the potential to cross a nearby vertex and interduce self intersection in the output polygons. Since "simple polygons" is a common precondition to many algorithms (including Barend's own) it is simply unacceptable for there to be any chance of this post condition not being satisfied. Note that infinite precision floating point calculations don't solve this problem if you convert the output to regular floating point at some later stage, which is the common way the algorithm's output would be consumed. Second, Barend has stated that his algorithm does the same thing as mine. This is simply not true. Barend's algorithm imposes quite a few preconditions on its inputs (non-self intersecting being just one example) while mine imposes none. The two arguments of a boolean operation in my library may be any number of intersecting and overlapping polygons, Barend requires that all polygons be simple and non-overlapping. My algorithm accepts a broader range of inputs, which makes it more general and more powerful than Barend's algorithm and a better algorithm to use in a generic interface where preconditions become concept requirements for input geometry data. Furthermore, my algorithm has more output modes such as trapezoidization and keyholing as well as the flexibility to perform n-layer operations such as connectivity extraction and map overlay. Barend's algorithm does not. Comparing Barend's intersection algorithm to my own is not an apples to apples comparision, it is an apple to fruit basket which happens to contain an apple comparision. For these two reasons I think we should take Barend's performance claims with a grain of salt. When compared to other libraries that are known to be numerically robust (GPC, CGAL, Geos) my library is sometimes slower, sometimes faster in Barend's own benchmarking. Only Barend's algorithm is always faster in his benchmarking. However, if Barend's library has the potential to produce self intersecting output it is not even in the same class as these others. My benchmark data can be reproduced using the forcgal.cpp file in the sandbox/gtl directory. I provided it when Andreas asked. I admit that my algorithm could be faster. For the benchmarks I performed I estimated it could be up to 10X faster. For Barend's benchmarks with many pointed star polygons which result in O(n^2) pathological performance of my admittedly suboptimal line segment intersection algorithm that number might be higher sill. I would prefer that the focus of the review be the concept interfaces (function declarations) and how the typesystem is implemented so that we can decide whether it is a good model for a generic geometry API. Changes to eg. the line intersection algorithm or internals of polygon_set_data class can be made without breaking code that depends on the library API. If someone implements a true drop in replacement for my polygon intersection algorithm (or just for line segment intersection) and licenses it under the boost license we can drop it in if it is faster and all any user should notice is that the library is faster in a new release of boost. I don't think there are any decisions I made in the design or implementation of the concept type system or library interfaces that prevent or even make difficult such a change to its implementation details. Overall, I don't think we should view this review as an either or Boost.Polygon now or GGL later decision. There is no reason both libraries cannot be accepted in due time. Barend has made quite a bit a progress since boostcon and I am genuinely happy for him for what he has achieved. Thanks, Luke

3 2

Formal Review of Boost.Polygon extended one more week: until September 9, 2009
by Fernando Cacciola 02 Sep '09

02 Sep '09

Dear developers, The review of Boost.Polygon was initially scheduled to end today. However, the discussions are in their best moment only now so the review period was extended by one week, until September 9, 2009 (that is next Wednesday). Best Fernando Cacciola Review Manager

1 0

[pool] patch to make pool support zero sized allocations.
by Steven Watanabe 02 Sep '09

02 Sep '09

AMDG The patch at https://svn.boost.org/trac/boost/attachment/ticket/386/pool.patch allows the pool classes to support zero sized allocation, by returning a null pointer. std::vector sometimes allocates a zero sized block, so this is necessary for pool_allocator. Returning a null pointer is the simplest solution and I'm that the standard allows an allocator to return the null pointer when asked for a block of zero elements. Okay to commit? In Christ, Steven Watanabe

1 1

Re: [boost] [mpl, units] rational and static_rational
by Matthias Schabel 02 Sep '09

02 Sep '09

> I am looking for a template library that can handle compile time > rationals, ideally with a similar interface to mpl::int_ and that > plays well with boost::rational (the dynamic type). > > First I found boost/mpl/math/rational_c.hpp but soon I realized that > it doesn't work with basic operations like mpl::plus, it doesn't even > simplify reducible fractions (i.e. 2/4 -> 1/2), in fact it looks like > it is just the storage of two (static) integers. Is this something > that will be developed in the future or am I using it in the wrong > way? > > Then I found boost::units::static_rational which is more promising, > because it simplifies fractions and works with mpl::plus, but it is > not integrated with boost::rational nor has an interface similar to > that of mpl metatypes. > > Is there a way of extending mpl::math::rational_c with the existing > libraries in boost, or a simple way to make > boost::units::static_rational have an interface similar to mpl and > also have a value type that returns it runtime boost::rational value? I certainly would have no objection to repackaging the static_rational type used in Boost.Units as an MPL type that plays nicely with Boost.Rational. My advice would be to put together a functional implementation and propose it for a mini-review. We could easily typedef units::static_rational -> mpl::rational_ in the units library. Matthias

1 0

[polygon] Overload resolution for operators fails
by Joachim Faulhaber 02 Sep '09

02 Sep '09

Hi Luke and polygonists, trying to set up some law based tests for boost::polygon I faced difficulties with the overload resolution of operators under msvc-9. This is the code sniplet where the problems occur: ----------------------------------------------------------- #include <boost/validate/laws/law.hpp> #include <boost/polygon/polygon.hpp> // Here I map a PolygonSet class to geometry_concepts according to // the docs: #include <boost/itl_xt/custom_polygon.hpp> namespace boost{namespace itl { template <typename Type> class PolygonCommutativity : public Law<PolygonCommutativity<Type>, LOKI_TYPELIST_2(Type,Type), LOKI_TYPELIST_2(Type,Type)> { // a o b == b o a . . . bool holds() { using namespace boost::polygon; using namespace boost::polygon::operators; Type value_a = this->template getInputValue<operand_a>(); Type value_b = this->template getInputValue<operand_b>(); Type left = value_a; left += value_b; // Compiler fails to find the appropriate overload // but // this works self_assignment_boolean_op<Type,Type,0>(left, value_b); // and also this works boost::polygon::operators::operator+=<Type,Type>(left, value_b); // and this boost::polygon::operators::operator+=(left, value_b); . . . return equivalence(left, right); } }; ----------------------------------------------------------- moreover, if my custom PolygonSet conainer implements an operator += this operator is *silently* chosen by the compiler, so the wrong addition function is called! Contrary to the traditional understanding of a concept, that defines *requirements* for a parameter class it can use, we have to take care here, that the client class *does not* implement certain operations. I am afraid this is not a good thing. I hope this is fixable, may be the error is on my side but I can't see it yet. Regards Joachim

2 2