March 2010 - Boost - lists.boost.org

[GSOC] summary of .BigInt library details.
by Ankit Malpani 12 Apr '10

12 Apr '10

hi all, thank you Scott McMurray, Vicente and Bruno for the prompt feedback regarding my proposed BigInt library ideas .(Sorry for the delayed reply as was busy with mid-semester exams.) In general this is what i have gathered from your responses regarding what exactly is being expected by the community from a BigInt library for Boost. 1. frontend based off Boost.Proto 2. backend implemented with the help of Boost libraries like Boost.Math. 3. probably provide two levels of implementations. ( although it would really help if you could weigh the pros and cons of both and eliminate one the the two) 3a. looking at bit-level implementation(less space and probably more execution time) 3b.) digit level manipulation (more space - and probably less execution time). i.e. for an n-digit number is it ok to use up [n/2 to n] bytes of space or necessary to stick to log n amount of space for a BigInt object. my questions are :- 1. Please give your feedback/concerns regarding the above design. 2. Any other libraries like Boost.Math which would help with the backend. -- Ankit Malpani 3rd Year Undergraduate | BE. (Hons) Computer Science BITS Pilani Goa Campus

5 5

[utility/value_init] boost::value_initialized<T> direct-initialized?
by Niels Dekker - address until 2010-10-10 09 Apr '10

09 Apr '10

Can anybody please have a look at the following feature request by Edward Diener? https://svn.boost.org/trac/boost/ticket/3472 He proposed to add an explicit constructor, value_initialized(T const&), to boost::value_initialized<T>. This constructor would copy the value of its argument to the object held by value_initialized<T>. When such a constructor would be added, an object held by value_initialized<T> might no longer be value-initialized. Instead it might be direct-initialized. Does anybody have any moral (?) objections against the idea that value_initialized<T> might hold a non-value-initialized object? Personally I think it would be useful to allow the wrapped object to be direct-initialized. But I do think there's a small risk that the new explicit constructor might cause ambiguities in legacy user code. Therefor I suggested adding an extra "tag" parameter to the new constructor, of a new type, boost::direct_initialized_t: struct direct_initialized_t { }; value_initialized(T const&, direct_initialized_t) Does anyone else also think that's a good idea? Or does anyone prefer the explicit value_initialized(T const&) constructor originally proposed by Edward? See also the thread starting at: "Re: [boost] Transfer of Maintenance Rights (utility/value_init)" http://lists.boost.org/Archives/boost/2010/03/164125.php Kind regards, Niels -- Niels Dekker http://www.xs4all.nl/~nd/dekkerware Scientific programmer at LKEB, Leiden University Medical Center

6 32

GSoC 2010: Heaps and Queues
by Dan Larkin 09 Apr '10

09 Apr '10

I'm another potential student throwing my hat in the ring for the heap project. I'll save most of my personal details for my proposal, but for right now I thought I'd try to get a bit of a dialogue going with the community to help me understand what it is you guys are looking for and what it is I can work towards. So I'll start with my current understanding of the situation. The way I see it, the current heap implementations in boost/pending are rather fractured. They just have simple push/pop interfaces with no mutability (well, there's mutable_heap.hpp, but that's separate and not fleshed out). All in all, what seems to be needed is a standardized heap concept/API along with a few fully-implemented models. Standard heap functionality begs the following functions: - findMin - deleteMin - insert - changeKey - merge These can all be implemented quite efficiently (either worst case or amortized O(logn) time or better) for any heap model. I would be looking to implement the d-ary, binomial, and Fibonacci heaps for sure, with relaxed and Brodal heaps as a possibility, should time allow it. These heap models would be built as extensions of a base Heap class, which could be easily wrapped in a PriorityQueue class which takes the heap-type as a construction parameter (and defaults to a d-ary heap for instance). I know that a stable priority queue was mentioned in earlier discussion, but I'm not sure what to do about that just yet. It'll take a little more thinking before I could say whether I think it'd fall under the scope of the summer project, or if it should be put on the back-burner for later addition to the library. I guess that's basically how I see the problem so far. Please let me know what you think, or what other sort of information/planning/etc. you would like to hear from me prior to my proposal/draft. Dan Larkin

7 34

GSoC Generic Sweep Algorithm
by Sweta Yamini 09 Apr '10

09 Apr '10

Hi, I am writing my proposal for GSoC and I'm interested in writing a generic sweep algorithm. I want to write a generic algorithm which takes in functions to determine the priority of the elements to be considered in the sweep line, and a function to perform necessary computations at each such point. And supplement it with inbuilt functions for line sweep, angular sweep about a point for 2 dimensions and plane sweep for 3 dimensions. Also, implement some algorithms like Voronoi diagrams, Delaunay triangulations, visibility problems using the generic sweep algorithm. I have looked through the documentation and could not find anything related to this. Is there something I have missed? Also, could I contact anyone to discuss? Sweta Yamini Fourth Year Student Department of Computer Science And Engineering Indian Institute of Technology, Kharagpur

3 5

Re: [boost] New Boost.XInt Library, request preliminary review
by Anders Dalvander 08 Apr '10

08 Apr '10

Chad Nelson wrote: > > > This disables the copy-on-write optimization that the library uses by > > > default [...] > > > > > I'm not convinced that integers should be COW. What situations do you > > forsee where COW would be helpful but move semantics wouldn't suffice? > > > As described on the rationale page of the documentation, the primary > reason I'm using copy-on-write is that move semantics aren't widely > available yet. Portability is one of my primary goals, and while I've > seen references to a move-semantics-emulator in Boost, I've also seen > suggestions that it relies on the compiler to somehow recognize it. That > doesn't sound fully portable to me. > No offense, but I'm not confident that COW semantics for the integer class is a wise design choice. I assume you have tested the performance with and without COW semantics, as well tested the performance for thread safe operations with and without COW semantics, before making that decision. Care to disclose the numbers? I guess that you have read the COW string article (http://www.gotw.ca/gotw/045.htm) by Herb Sutter, and his conclusions. Optimizations on other parts should perhaps have been made before converting to COW semantics. Using COW semantics could also complicate the complexity requirements for most functions, as they may be "amortized O(something)" instead of just "O(something)". Another concern I have is that NaN is "signaling" as most operations on a NaN integer will throw an exception. I think it would be more sound if operations on NaN integers would result in NaN integers, compare with float NaN. Don't take these comments the wrong way, I'm very glad to see development of an arbitrary precision integer boost licensed library. Best regards, Anders Dalvander

18 136

[contract] Macro syntax?
by Lorenzo Caminiti 08 Apr '10

08 Apr '10

Hello all, I would like you to vote between one of the two options below. Which option do you prefer? (-) OPTION 1 requires programmers to repeat the function signature tokens twice -- in the function declaration and in the CONTRACT_FUNCTION() macro. (+) However, OPTION 1 seems to make the code more readable -- users not familiar with Boost.Contract can "skip" the tokens in the CONTRACT_FUNCTION() signature-sequence and just read the usual C++ function declaration. OPTION 1: The function declaration is programmed using the usual C++ syntax just before the CONTRACT_FUNCTION() macro. template<typename T> class myvector { CONTRACT_INVARIANT( ({ ... }) ) public: void push_back(const T& element) // Usual C++ push_back() declaration. CONTRACT_FUNCTION( (class) (copyable)(myvector) (public) (void) (push_back)( (const T&)(element) ) (precondition)({ ... }) (postcondition)({ ... }) (body)({ ... }) ) ... }; OPTION 2: The CONTRACT_FUNCTION() macro automatically programs also the function declaration. template<typename T> class myvector { CONTRACT_INVARIANT( ({ ... }) ) public: // No usual C++ push_back() declaration here. CONTRACT_FUNCTION( (class) (copyable)(myvector) (public) (void) (push_back)( (const T&)(element) ) (precondition)({ ... }) (postcondition)({ ... }) (body)({ ... }) ) ... }; Thank you. Lorenzo

4 7

[Review Results] Boost.Polygon library accepted into boost
by Fernando Cacciola 08 Apr '10

08 Apr '10

Dear Boosters, [first of all allow me to apology for not doing this before. My small consulting bussines suddenly grew out of proportion and now is way over my head, keeping me working/managing 16 hours a day] I am pleased to announce that the Boost.Polygon library from Lucanus Simonson has been accepted into boost provided some of the most critical concerns, detailed below, are addressed first. First of all I would like to thank Lucanus and Intel Corporation for making this work available to all C++ developers around the world. I would also like to thank all the reviewers that participated (in no particular order nor degree of participation) Thomas Klimpel Frank Mori Hess Barend Gehrels Andreas Fabri Jeffrey Hellrung Tim Keitt Markus Werle Paul A. Bristow Robert Stewart Mathias Gaunard Michael Fawcett Steven Watanabe Joachim Faulhaber John Bytheway Sebastian Redl Mika Heiskanen John Phillips Kai Benndorf Hartmut Kaiser Arash Partow Maurizio Vitale Brandon Kohn David Abrahams Gordon Woodhull Daniel James John Maddock Tom Brinkman Bo Persson Mateusz Loskot Christian Henning Jean-Sebastien Stoezel The library had 6 yes votes and 4 no votes. Those who voted no made the following major complains and remarks (they are numbered as I will refer to them back later): Barend Gehrels: (1) According to his benchmarks, intersection algorithms are unnecesarily slow as if something where fundamentally wrong in the design and/or implementation. AFAICT the implication has not been proved or disproved so far, hence I consider it a red herring and cannot take it as a reason for rejecting the library, but it is important to look at it in detail. (2) As a major complain, the library is unusable in those domains where floating point support is a requirement (like GIS). (3) The library should contain some basic polygon geometry algorithms such as convex hull and centriod Phil Endecott: (4) There is no concept checking in the code so it is difficult to adapt. (5) There where too many warnings and build errors (but Luke fixed these) (6a) The documentation needs a better overview of operations supported by the concetps. (6b) It also needs the details on the algorithms complexities. (6c) It also misses the numerical requirements for the coordinate type. (6d) And tutorials. (7) Some operators are ambiguous and it would be better to keep just one of each "flavor". (8) The polygon_data template class is parameterized by a coordiante type rather than a point type. This makes it useless for integration with existing geometric data types Michael Fawcett: (5), (6a), (6d) (9) T9he API should provide versions using output iterators in addition to output container references. (10) Theoreticall the library would be usable with a user defined coordinate type (metting certain requirements now undocumented), for example a fixed point data type, but some details in the internal design and implementation prevents this. (11) As a major complain, the library is unusable in those domains where floating point support is a requirement (like GIS). Hartmut Kaiser: (11), (1) Fernando Cacciola: (12) The name of the library should change to better indicate that is restricted to Integral coordinates and two-dimensions. (13) The documentation must contain a "credits" section acknowledging all the people that participated in the review. For the library to be effectively accepted, points (5),(6a-d),(10), (12) and (13) should properly addressed ((5) is already done AFAICT) It would be quite significant if point (1) where looked into. Once again I thank Lucanus, Intel Corporation and all the reviwers. Best regards -- Fernando Cacciola SciSoft Consulting, Founder http://www.scisoft-consulting.com

4 4

[google summer of code] student
by Cezary Bartoszuk 05 Apr '10

05 Apr '10

Hello, I am a CS student and I would like to patricipate in developing Heaps & Queues in Boost during Google Summer Of Code '10. Where, besides the source code, should I search for information about what's already in Boost (in the meaning of heaps/queues)? Who should I talk to about participating in Boost? Best regards, Cezary Bartoszuk, --- Faculty of Mathematics Informatics and Mechanics, University of Warsaw, Poland

3 4

Interested in Boost.Graph
by Piyush Garg 05 Apr '10

05 Apr '10

hi I am interested in upgrading the boost graph library to parallel boost graph library. I want to ask that do i have to chose one of the projects in boost.graph or i have to make them all during summer. Can i make the project on that or i have to suggest my own idea? Thanks Piyush Garg.

3 7

GSoC: Enforcing Code Feature Requirements
by vicente.botet 03 Apr '10

03 Apr '10

Hi, I have recently reread the article "Enforcing Code Feature Requirements in C++" by Scott Meyers <http://www.artima.com/cppsource/codefeaturesP.html> I have posted some ideas that could improve the design (<http://www.artima.com/forums/flat.jsp?forum=226&thread=238798&start=0#372622>) I wanted to know if this could be a good subject for GSoC, if the approach I purpose to solve some issues is acceptable and if there is some students interested. Of course any comments are welcome. Best, _____________________ Vicente Juan Botet Escribá

7 14