- Boost - lists.preview.boost.org

Re: [boost] [GSoC] Heaps & Queues (draft proposal)
by iaml 08 Apr '10

08 Apr '10

First of all, thank you, Andrew for your appreciation and Jeremiah for your information. I do not notice there exists d-ary in the BGL since I just focus on boost/pending and libs/pri_queue these days. But after a quick glance on the code in boost/graph/detail/d_ary_heap.hpp, I think that the container is supposed to have push_back() and pop()_back() because they are used directly in push() and pop(), This is something like the alias for vector type, not the parameter. Is that right or I just misunderstand the code in boost/graph/detail/d_ary_heap.hpp? As someone says: APIs design is main contributor to the Boost (I have read it today in somewhere in boost.org, but I can find it now :-( ). And I am lack of experience in APIs design for library. So I want to focus on my APIs design again. I know I am a bit annoying, but I want to do my best since it is my first time to join in GSoC. Feedback are welcome. It will be nice of you to do that. ==== description here ==== In order to be extendible, I would like to add iterator to the base class, which is more frequently used in programming, especially generic programming, than pointer. In some libraries, such as the STL, iterator is a bridge for container and algorithm. Since one of the goals of this project is to redevelop a new library for advance data structures and adaptors, I consider iterator to be necessary component to the library. Maybe it’ll take a little bit more memory, but in modern PCs, I think it acceptable.(*am I wrong about the usage of the iterator?*) template <class RandomAccessIterator, // iterator of the container class TreeNode, // key type class Comp = std::less<TreeNode>> class heap{ public: class iterator{ // implement iterator so that this class can be use as container // for other adaptors and algorithms public: TreeNode const& operator* () const; TreeNode const* operator->() const; iterator& operator++(); iterator operator++(int); bool operator== (iterator const& it); bool operator!= (iterator const& it); }; public: /* param: new_inserted points to the bottom of the container * where the new value has been inserted but not heapify. */ void insert(RandomAccessIterator new_inserted); void delete(RandomAccessIterator delete_node); void update(RandomAccessIterator update_node, TreeNode& new_node); // make the heap mutable RandomAccessIterator merge(RandomAccessIterator other_root); RandomAccessIterator getRoot(); RandomAccessIterator find(TreeNode& node); bool empty() const; size_type size() const; iterator begin() const; iterator end() const; void print() const; private: void print_recur() const; protected: RandomAccessIterator _root; }; NOTICE: operations print and print_recur is optional. But I prefer to include them because it'll be helpful when debugging the programs using this library. The class mentioned above is the base class for all the heap structures in the new library. The classes such as Fibonacci heap, relaxed heap, binomial heap and d-ary heap should inherit from this abstract class and add additional operations if needed. As the adaptor of heaps, the priority queue API may like: template< class RandomAccessIterator, class TreeNode, class Comp = std::less<TreeNode> class Container = fibonacci_heap<RandomAccessIterator, TreeNode, Comp>> class priority_queue{ public: /* param: new_inserted points to the place * where the new value has been inserted */ void push(RandomAccessIterator new_inserted); void pop(); // get the first value without popping it const TreeNode& front() const; TreeNode& front() ; RandomAccessIterator front() const; RandomAccessIterator find(TreeNode& node); void update(RandomAccessIterator update_node, TreeNode& new_node); // make the priority queue mutable RandomAccessIterator merge(RandomAccessIterator other_head); bool empty() const; size_type size() const; void print() const; private: void print_recur() const; protected: RandomAccessIterator _head; }; Thank you for your time. Yours sincerely, Tao Lin

2 3

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

Crypto Library - Draft Proposal
by Chad Seibert 08 Apr '10

08 Apr '10

Hello, Here's a draft of my proposal. If you have any suggestions, I'd greatly appreciate that. Also, we can discuss any potential issues or concerns you may have. I have enabled "public" mode so it should be visible to all of you. http://socghop.appspot.com/gsoc/student_proposal/show/google/gsoc2010/chads… Many thanks, Chad Seibert _________________________________________________________________ The New Busy is not the old busy. Search, chat and e-mail from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:…

3 2

Crypto Library Abstract
by Chad Seibert 08 Apr '10

08 Apr '10

Hi, Here's my abstract for the crypto library proposal. Any feedback would be greatly appreciated! "This proposal describes the porting of the cryptography library Botan and its integration with ASIO. Botan is released under the BSD license and the author has already agreed to porting it. The major reason for having a crypto library integrated with Boost is threefold: ASIO has SSL support that should be extracted out, adding TLS support for ASIO requires supporting many other block cipher types, and adding support for cryptography will add reasonable upgrades to Boost.Random and Boost.CRC as well. This is projected to take about 3-4 months to complete." Thank you, Chad Seibert _________________________________________________________________ The New Busy is not the old busy. Search, chat and e-mail from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:…

2 1

Status of Boost.Move(https://svn.boost.org/trac/boost/wiki/LibrariesUnderConstruction#Boost.Move)
by Anton Potapov 08 Apr '10

08 Apr '10

Hi, That is the status of boost.move library(https://svn.boost.org/trac/boost/wiki/LibrariesUnderConstruction#Bo… Regards

5 8

[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 07 Apr '10

07 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

Re: [boost] [msm] new version available
by Christophe Henry 07 Apr '10

07 Apr '10

>>>> Hi all, >>>> >>>> I just finished the newest MSM version. Unfortunately, I'm afraid I'm >>>> a bit late to get it shipped with boost v1.43 but at least it will >>>> give us time to have a look at it. >>>> What is new: >>>> - the doc was rewritten almost from the ground up. >>> <snip> >>>> You can find the new version, like always: >>>> - in the Vault (http://www.boostpro.com/vault/index.php?directory=Msm) >>>> - in the sandbox (http://svn.boost.org/svn/boost/sandbox/msm/) >>>> >>>> Regards, >>>> >>>> Christophe >>> >>> Hi, >>> >>> Just a form remark. We use to see the code highlighted. Have you the possibility to highligth the code? >>> >>> Best, >>> Vicente >> >> >> Done and committed in the Sandbox. > > Hi, I see that you used <programlisting>. Shouldn't you use <programlisting language="c++"> or somthing like that? > > Best, > Vicente I could but as I didn't see any difference in the generated html, I suppose it is an unimportant attribute. Regards, Christophe

1 0

Crypto Library
by Chad Seibert 07 Apr '10

07 Apr '10

> Hi, > > I've just got confirmation from Jack Lloyd that I can port Botan to Boost. He only uses Boost.Python currently because he was having issues with shared_ptr when compiling for ARM. However, I think that most of these issues will be resolved (or have been) when the porting process takes place. Is there any protocol for porting an entire library to Boost? I know that ASIO took a while for approval. > So I'm going to ask a heretical question: why do you/he want to add it > to Boost? > Please don't make it header only in the process or I will be forced to > look at CryptoPP which is guaranteed to make babies cry. I was just getting a community response to porting a library, in this case Botan, vs constructing a library from scratch. Given that Botan is not heavily templatized, so there shouldn't be a reason this lib is headers only. However, any specializations will have to be. Tomorrow morning I'll have a draft proposal up for peer review. Many thanks for your input, Chad Seibert _________________________________________________________________ The New Busy is not the old busy. Search, chat and e-mail from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:…

1 0

Porting Botan to Boost
by Chad Seibert 07 Apr '10

07 Apr '10

Hi, I've just got confirmation from Jack Lloyd that I can port Botan to Boost. He only uses Boost.Python currently because he was having issues with shared_ptr when compiling for ARM. However, I think that most of these issues will be resolved (or have been) when the porting process takes place. Is there any protocol for porting an entire library to Boost? I know that ASIO took a while for approval. Thanks, Chad _________________________________________________________________ Hotmail has tools for the New Busy. Search, chat and e-mail from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:…

4 3

[GSoC] Binomial and Fibonacci heap implementation project
by Суворов Дмитрий 07 Apr '10

07 Apr '10

Hello, My name is Dmitriy. I'd like to participate in GSoC2010 with the Boost project. I looked through you ideas list, and I think i could do Binomial heap and Fibonacci heap as a summer project. I've composed a draft of my proposal, could you comment on it? My name is Dmitriy Suvorov. I'm a student of Bauman Moscow State Technical University. I am a third course student of a Robotics department. My degree program is BS. My email is dmitriy_suvorov(a)inbox.ru. I don't have any homepage. I plan to spend 5-5.5 hours per day on coding in June and 8 hours per day in July and August. I plan to start coding on May 24th. And I am going to stop coding on 30th August. I can't spend more time in June because I have university's exams. I think I won't spend much time on coding in September because university courses will start. But I am going to continue my work on Boost library in autumn. My middle degree in university is 4.76 (maximum is 5.0). I've taken courses in mathematics, programming and electronics. I'm interested in coding with application of mathematical algorithms. Now I'm working on robotics computer vision to participate in international competitions "Eurobot 2010". I'm going to take part in open source project for the first time. I'm interested in contributing to the Boost C++ Libraries and I want to gain an experience in programming. I'd like to solve interesting problems. I have knowledge about data structures and want to apply my knowledge in practice. I'm going to read more information about data structures and Boost C++ Libraries in May. My rates, from 0 to 5 (0 being no experience, 5 being expert), of my knowledge of the following languages, technologies, or tools: C++ - 5 C++ Standard Library - 5 Boost C++ Libraries - 3 Subversion - 4 I like Visual Studio to write Windows programs and KDevelop to write Linux programs. The most familiar software documentation tool with me is Doxygen. I want to work on binomial heap. If I'll solve problem quickly I want to work on other data structure, for example, on Fibonacci heap. Binomial heap is implementation of the mergeable heap abstract data type which is a priority queue supporting merge operation. Binomial heap is a collection of binomial trees. A binomial tree is defined recursively: - A binominal tree of order 0 is a single node. - A binomial tree of order k has a root node whose children are roots of binomial trees of orders k-1, k-2, +, 1, 0. All operations work on O(log n) time on a binomial heap with n elements. Fibonacci heap is a heap data structure consisting of a forest of trees. It has a better amortized running time than a binomial heap. These heaps are used in to improve asymptotic time of important algorithms, such as Dijkstra's algorithm for computing shortest path in a graph, and Prim's algorithm for computing a minimum spanning tree of a graph. I have found implementations of binomial heap in C and Python at LITMUS project. The homepage of project is www.cs.unc.edu/~anderson/litmus-rt/ . I'm going to create a new class for the Binominal heap and polish current implementation of Fibonacci heap. I will use Introduction to algorithms by Cormen, Leiserson as a reference. Could you review this?

3 4

Re: [boost] [msm] new version available
by Christophe Henry 07 Apr '10

07 Apr '10

>> Hi all, >> >> I just finished the newest MSM version. Unfortunately, I'm afraid I'm >> a bit late to get it shipped with boost v1.43 but at least it will >> give us time to have a look at it. >> What is new: >> - the doc was rewritten almost from the ground up. > <snip> >> You can find the new version, like always: >> - in the Vault (http://www.boostpro.com/vault/index.php?directory=Msm) >> - in the sandbox (http://svn.boost.org/svn/boost/sandbox/msm/) >> >> Regards, >> >> Christophe > > Hi, > > Just a form remark. We use to see the code highlighted. Have you the possibility to highligth the code? > > Best, > Vicente Done and committed in the Sandbox. Thanks for your help, Christophe

2 1

Re: [boost] [GSoC] Heaps & Queues (draft proposal)
by iaml 07 Apr '10

07 Apr '10

First of all, thank you, Andrew and Luke, for pointing out my mistakes and misunderstanding in my draft project which I sent several days ago. After that, I have read some source code in the STL and do some more research on this topic. Now, I work out my draft proposal again. Please feel free to point out my stupidity. I will be very grateful for this. Besides, I still have some doubt on this project: What we need to do in this project is to build a new library as the result of decoupling boost/pending from the BGL. So the compatibility with the new library and the BGL need to be concerned. However, I have read the document in the BGL. It’s said that we can convert existing graphs to the BGL by implementing some functions. Dose it mean the APIs of the new library does not effect the compatibility of the new library and the BGL since we can change it properly. Is that right? ==== draft proposal v0.2 ==== Project Proposal * Please provide a description of your proposed work. ** Background There are a number of data structures in boost/pending that implement different kinds of heaps and queues that are used in a number of different Boost Graph (BGL) algorithms. These can be cleaned up, decoupled from the BGL and redeveloped into a useful library for advanced data structures. Why don’t we use them directly? We can’t use boost/pending or libs/pri_queue as the new library directly for several reasons: 1. Heaps don’t parameterize for container type. They use vector as default. In the STL, there is very clear abstraction between containers and algorithms (they use iterator to achieve this abstraction). Since abstraction is a goal of the project, it’s necessary to modify the data structure in boost/pending rather than use it directly. 2. The APIs designed in the boost/pending is not user-friendly. In my opinion, the heaps in boost/pending act as the container of the priority queue rather than as a data structure. So some operations are omitted since they are useless in priority queue, but useful in heap and maybe necessary for other adaptors. They lack some operations such as delete one key (not just pop the minimum or maximum key), update the key in heap. This leads to the necessity of redeveloping a new library. ** Benefit for Boost Heap is widely used in development such as heap sort, priority queue and other graph algorithm. It also can be the container for advanced data structures. But the heaps in boost/pending and libs/pri_queue is not extendable or highly abstract. This leads to the limited usage of this library. To redevelop a new library about heaps and priority queue more abstract and more user-friendly not only can broaden the user group of Boost, but also can fix the design deficiency in boost/pending and make it more conforms to the philosophy of Boost. ** Solution In my opinion, most of work is to rewrite and reuse the existing data structures in boost/pending and libs/pri_queue. The most important thing I should consider is the APIs design of the new library. It should be highly abstract and user-friendly. The compatibility with the new library and the BGL needs to be concerned. *In order to be extendible, I would like to add iterator to the base class, which is more frequently used in programming, especially generic programming, than pointer. In some libraries, such as the STL, iterator is a bridge for container and algorithm. Since one of the goals of this project is to redevelop a new library for advance data structures and adaptors, I consider iterator to be necessary component to the library. Maybe it’ll take a little bit more memory, but in modern PCs, I think it acceptable.(am I wrong about the usage of the iterator?)* * * Besides the heaps required, I would like to add d-ary heap into the new library. Because d-ary heap is a variation of binary heap (so I can use binary heap as a special case for d-ary) and has faster running time. If time permits, I want to add splay heap (because it has the attractive property that recently accessed elements are quick to access again. I think it will be very useful in application software programming) and other heaps mentioned in libs/pri_queue into the new library. Below is my design to the library APIs. template <class RandomAccessIterator, // iterator of the container class TreeNode, // key type class Comp = std::less<TreeNode>> class heap{ public: class iterator{ // implement iterator so that this class can be use as container // for other adaptors and algorithms public: TreeNode const& operator* () const; TreeNode const* operator->() const; iterator& operator++(); iterator operator++(int); bool operator== (iterator const& it); bool operator!= (iterator const& it); }; public: /* param: new_inserted points to the bottom of the container * where the new value has been inserted but not heapify. */ void insert(RandomAccessIterator new_inserted); void delete(RandomAccessIterator delete_node); void update(RandomAccessIterator update_node, TreeNode& new_node); // make the heap mutable RandomAccessIterator merge(RandomAccessIterator other_root); RandomAccessIterator getRoot(); RandomAccessIterator find(TreeNode& node); bool empty() const; size_type size() const; iterator begin() const; iterator end() const; void print() const; private: void print_recur() const; protected: RandomAccessIterator _root; }; NOTICE: operations print and print_recur is optional. But I prefer to include them because it'll be helpful when debugging the programs using this library. The class mentioned above is the base class for all the heap structures in the new library. The classes such as Fibonacci heap, relaxed heap, binomial heap and d-ary heap should inherit from this abstract class and add additional operations if needed. As the adaptor of heaps, the priority queue API may like: template< class RandomAccessIterator, class TreeNode, class Comp = std::less<TreeNode> class Container = fibonacci_heap<RandomAccessIterator, TreeNode, Comp>> class priority_queue{ public: /* param: new_inserted points to the place * where the new value has been inserted */ void push(RandomAccessIterator new_inserted); void pop(); // get the first value without popping it const TreeNode& front() const; TreeNode& front() ; RandomAccessIterator front() const; RandomAccessIterator find(TreeNode& node); void update(RandomAccessIterator update_node, TreeNode& new_node); // make the priority queue mutable RandomAccessIterator merge(RandomAccessIterator other_head); bool empty() const; size_type size() const; void print() const; private: void print_recur() const; protected: RandomAccessIterator _head; }; Thank you for reading

3 2

Gsoc Boost.Graph: implementing new algorithms
by Camillo Anania 07 Apr '10

07 Apr '10

Hi guys, I'm developing my thesis using BGL. Now it's some months I'm working on it and this is what I would like to see implemented on BGL and partially what I'm working on in those months: - check if graph have an euler tour(is eulerian) and find one and/or all possible euler tours - add the support for mixed graph - add the algorithm to find a minimum cost maximum matching I would like to know an opinion about that. Thanks Camillo

2 4

Crypto Suite
by Chad Seibert 07 Apr '10

07 Apr '10

> Hi, > > I was looking through previous GSoC ideas and I was interested in doing a crypto suite as described here: > > http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Google_Summe… > > I was wondering if this was still in high demand, as I've been tied between doing this and the BigInt library proposed on the ideas page. The only reason I ask is because I'd like to do the most good for this project and wonder which project that might be. > > Thank you for any input, > Chad Seibert > > _________________________________________________________________ > Hotmail is redefining busy with tools for the New Busy. Get more from your inbox. > http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:… > _______________________________________________ > Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost > > Sure you want to do this from scratch? Botan uses Boost - why not ask > Jack Lloyd if he'd let you pull bits of it down into Boost? Well, as I'm writing the proposal, I'm more emphasizing the structure of generic implementations of crypto-like stuff, not the actual implementations of MD5, AES, RSA, etc. The second half of my proposal was on actual implementation, where I discuss using either Crypto++ or Botan, with author permission. I'm in the midst of getting that permission. _________________________________________________________________ The New Busy is not the too busy. Combine all your e-mail accounts with Hotmail. http://www.windowslive.com/campaign/thenewbusy?tile=multiaccount&ocid=PID28…

3 2

License on Interprocess Containers
by Hal Finkel 07 Apr '10

07 Apr '10

Hello, boost/interprocess/containers/container/vector.hpp contains the following in the license header (directly underneath the BSL header): ////////////////////////////////////////////////////////////////////////////// // // This file comes from SGI's stl_vector.h file. Modified by Ion Gaztanaga. // Renaming, isolating and porting to generic algorithms. Pointer typedef // set to allocator::pointer to allow placing it in shared memory. // /////////////////////////////////////////////////////////////////////////////// // Copyright (c) 1994 // Hewlett-Packard Company // // Permission to use, copy, modify, distribute and sell this software // and its documentation for any purpose is hereby granted without fee, // provided that the above copyright notice appear in all copies and // that both that copyright notice and this permission notice appear // in supporting documentation. Hewlett-Packard Company makes no // representations about the suitability of this software for any // purpose. It is provided "as is" without express or implied warranty. [ With a similar license statement under the SGI copyright ] In my view, one of the strengths of the BSL is that it specifically does not require notice in "supporting documentation." It is possible that this portion of the license is no longer in effect, since the header on the STLport vector header now reads: * Copyright (c) 1994 * Hewlett-Packard Company * * Copyright (c) 1996,1997 * Silicon Graphics Computer Systems, Inc. * * Copyright (c) 1997 * Moscow Center for SPARC Technology * * Copyright (c) 1999 * Boris Fomitchev * * This material is provided "as is", with absolutely no warranty expressed * or implied. Any use is at your own risk. * * Permission to use or copy this software for any purpose is hereby granted * without fee, provided the above notices are retained on all copies. * Permission to modify the code and to distribute modified code is granted, * provided the above notices are retained, and a notice that the code was * modified is included with the above copyright notice. And in this case, perhaps the affected files can be updated to reflect the less-onerous STLport license. Otherwise, the files could be replaced with STLport-derived files, or HP and SGI could be asked to provide permission. Any opinions? Thanks again, Hal

2 3

Important: Server Upgrade Wednesday, April 7
by Doug Gregor 07 Apr '10

07 Apr '10

The main Boost server will be down for a Trac upgrade on Wednesday, April 7 from 8am-9am Eastern time. The following services will be affected: Web server (boost.org) Subversion Trac Mailing list archives Mailing lists should still function as normal. My apologies for the late notice. - Doug

1 0

[move] pre-review comments
by Jeffrey Lee Hellrung, Jr. 07 Apr '10

07 Apr '10

I have some (long overdue) comments concerning Ion Gaztanaga's proposed Boost.Move library. First, Ion, great job on the documentation and implementation. Both are very readable and usable. These comments stem from my own use and perceived deficiencies in the current state of affairs, but they might also lead to a more complex library. So take them however you want, and you (Ion) and others may respond at your own convenience. In below, when I refer to "C++03 compilers", I mean compilers without rvalue rferences; when I refer to "C++0x compilers", I mean compilers that do have rvalue references. Also, some details are lacking, as I'm writing this kind of haphazardly and over a couple hours while watching the Jazz-Lakers game... -------- boost::rv<T> ------------ The library should clearly define what requirements a class needs to satisfy to work with the library's facilities, specifically when rvalue references are not available. For C++03 compilers, this will involve defining boost::rv<T>, conversion operators to boost::rv<T>& and (if copyable) const boost::rv<T>&, and what constructors and assignment operators there should be and their semantics. I think this interface specification is of primary importance, and the remaining facilities are of secondary importance. boost::is_movable<T> -------------------- This should evaluate to a Boost.MPL integral constant, and it should still work for builtin types (and return false). BOOST_FWD_REF( T ) / boost::forward<T>(x) ----------------------------------------- I think there should be 2 forwarding mechanisms. One is BOOST_FWD_REF( T ) (paired with boost::forward<T>(x)), which expands to const T& on C++03 compilers and is able to capture rvalues. The other I've called BOOST_PERFECT_FWD_REF( T ) (paired with boost::perfect_forward<T>(x)), which expands to T& and will *not* capture rvalues, but will correctly forward lvalue references to non-const. I'm open to alternative names. The intent is that you can use BOOST_PERFECT_FWD_REF( T ) if you know you will never need to capture rvalues (e.g., it will only receive the result of a boost::forward or boost::perfect_forward). I think it might also be useful to provide metafunctions boost::forward_param<T> and boost::perfect_forward_param<T> that strips off any {const} boost::rv<T>&'s for use with Boost.ResultOf. BOOST_MOVABLE_BUT_NOT_COPYABLE / BOOST_COPYABLE_AND_MOVABLE ----------------------------------------------------------- I don't use these. Instead, I've created no fewer than 10 macros to enable move emulation, depending on the particular application: BOOST_BASIC_MOVABLE_COPYABLE( T ) BOOST_MOVABLE_NONCOPYABLE( T ) BOOST_MOVABLE_COPYABLE_DEFINE_COPY_ASSIGN_FROM_MOVE( T ) BOOST_MOVABLE_COPYABLE_DEFINE_COPY_ASSIGN_FROM_SWAP( T ) BOOST_OPTIMAL_MOVABLE_COPYABLE( T ) BOOST_FRIENDLY_MOVABLE_COPYABLE( T ) BOOST_OPTIMAL_MOVABLE_COPYABLE_IF( T, Cond ) BOOST_FRIENDLY_MOVABLE_COPYABLE_IF( T, Cond ) BOOST_OPTIMAL_MOVABLE_COPYABLE_IF_MOVABLE( T, U_seq ) BOOST_FRIENDLY_MOVABLE_COPYABLE_IF_MOVABLE( T, U_seq ) BOOST_BASIC_MOVABLE_COPYABLE provides a move constructor and a move assignment operator, but does not provide a mechanism to move assign automatically from rvalues. I typically use this in base classes. BOOST_MOVABLE_NONCOPYABLE should be self-explanatory. BOOST_MOVABLE_COPYABLE_DEFINE_COPY_ASSIGN_FROM_MOVE( T ) defines a by-value copy assignment via copy-and-move. Similarly, BOOST_MOVABLE_COPYABLE_DEFINE_COPY_ASSIGN_FROM_SWAP( T ) defines a by-value copy assignment via copy-and-swap. Implementing copy assignment to receive by value captures rvalues optimally via copy RVO. BOOST_OPTIMAL_MOVABLE_COPYABLE* and BOOST_FRIENDLY_MOVABLE_COPYABLE* differ in how rvalues are captured for assignment on C++03 compilers. OPTIMAL declares an operator=(T&) that forwards to the copy assignment operator, and an operator=(const rv<T>&) to move assign. As has been discussed previously, this has undesirable consequences if you rely on the compiler to generate the copy assignment operator in a class enclosing an "optimal movable" type. FRIENDLY declares an operator=(T) (on C++03 compilers) and implements it in terms of the move assignment operator. On C++0x compilers, both use an operator=(T&&) and operator(const &). BOOST_*_MOVABLE_COPYABLE_IF( T, Cond ) enables movability if Cond is true, and does not define a move constructor and move assignment operator if Cond is false. Similarly, BOOST_*_MOVABLE_COPYABLE_IF_MOVABLE( T, U_seq ) will enable movability if any type in the Boost.PP seq U_seq is movable (as determined by boost::is_movable). "The rest of the stuff" ----------------------- I'd consider iterator's and algorithm extensions to be of tertiary importance, and I haven't yet used them. - Jeff

2 6

[gsoc] heaps & queues
by Cezary Bartoszuk 06 Apr '10

06 Apr '10

Hi, I looked at APIs at https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/ The interfaces are quite well designed, but I don't understand one point: Why are there function templates used in methods providing mutability (for example change_top, change, decrease, increase for the lazy Fibonacci heap: https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/l_heap.html)? I think K stands there for "key", but there's already comparison functor (which defaults to std::less) provided, so we don't store key-value pairs (with key being the priority), do we? Why then K is used? The second key point I would like to ask about is the implementation. Are there any priority queues already implemented in BGL? If so, it would be nice for us to stay compatible with interfaces implemented already. Besides few doubts listed above I would like to propose implementing at least pri queues listed in https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/, so: * D-ary Heap (with standard - binary - heap as a special case) * Fibonacci Heap (btw, I thought, the Fibonacci heap is already lazy - maybe there's an discrepancy in the names) * Pairing Heap (didn't ever hear about them, but there are lots of references in the net) * Splay Heap (think it's a gret idea - simple implementaion and quite nice performance) * Radix Heap (also didn't hear about them, but the intuition is, that's a dara structure implementing radix-sort?) Speaking about stable priority queues (FIFO- or LIFO- stable) i have no fresh ideas for now, but I think it's quite useful, and would be happy to implement it. I have read that there are lots of people submitting proposals for the project; could any partition of work or time estimation be a part of the proposal (because there will surely be at least few of us working on the Heaps & Queues)? Best regards, Cezary Bartoszuk P.S. As I read threads about heaps & queues, I think also that the interfaces are a little bit too complicated. Quite good idea is implementing methods push, min, pop, decrease_key. Personally I don't see any algorithms using both decrease_key and increase_key. Usually there is intention of pushing priority "to the front" rather than "to the back". And there is also thing with iterators: I haven't seen any implementation iterating through pri_queue. So are interfaces based on push, min, pop, decrease_key accurate?

2 1

GSoC 20010: Boost.Thread towards the C++0x standard proposal
by vicente.botet 06 Apr '10

06 Apr '10

Hi, Is someone interested in adapting the current Boost.Thread interface to the C++0x stardard proposal? Best, _____________________ Vicente Juan Botet Escribá

4 5

GSoc Proposal - Crypto Suite
by Chad Seibert 06 Apr '10

06 Apr '10

Hi, I was looking through previous GSoC ideas and I was interested in doing a crypto suite as described here: http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Google_Summe… I was wondering if this was still in high demand, as I've been tied between doing this and the BigInt library proposed on the ideas page. The only reason I ask is because I'd like to do the most good for this project and wonder which project that might be. Thank you for any input, Chad Seibert _________________________________________________________________ Hotmail is redefining busy with tools for the New Busy. Get more from your inbox. http://www.windowslive.com/campaign/thenewbusy?ocid=PID28326::T:WLMTAGL:ON:…

3 2

[GSoC] Patterns - interest check
by Kornel Kisielewicz 06 Apr '10

06 Apr '10

Hello all, I'm (obviously) interested in joining boost as part of GSoC 2010. Apart from a repeated try of generating interest in the Boost.Matrix library I proposed last year (I'll probably post about it later), I'll share an idea of mine that has been around in my head since I was introduced to boost several years ago. It all began with the singleton pattern -- we were writing a project, and needed a singleton base class quick, hence the first place we turned to was boost. There, two surprises awaited us -- not only wasn't there a singleton library easily available, but in the boost sources there were several singleton base class implementations, few of them even exact the same. True it is that singleton implementations differ - we want to be able to sometimes control the initialization time and initialization order, we sometimes need thread safety, and sometimes not, we'd like to control how to handle creation, and how to handle referencing to a dead singleton -- obviously a bloated master-class is not the solution -- a policy based singleton template however would be. Once that came into my mind, I couldn't shake the idea of a general Boost.Patterns library. While indulging in a discussion of whether Patterns are beneficial or not isn't my goal, we must admit that they are commonly used, and several of those are already present in Boost in one form or another (signals and flyweight comes up to mind as an obvious example). Boost.Patterns would serve as a library for collecting those patterns that aren't big enough for their own library, and encompass the smaller class traits (like boost::noncopyable) too. Apart from the singleton, one obvious candidate for such a library that I'd like to code are the factory patterns, including the abstract factory pattern. A policy based implementation of those might provide a nice benefit for boost users not wanting to reinvent the wheel. Further out, there are a few more commonly used patterns that would be beneficial for a boost::patterns user. The way I see it, for the more complex solutions, some framework of base classes to be used would have to be designed, and then used between the patterns. Mind you, I'm not trying to convince anyone to the creation of a new Boost.Patterns library (although I'd really like to do that if possible), instead I'd like to ask you if there's a viable GSoC proposal in this post, one that one day might turn into a useful part of boost. -- regards, Kornel Kisielewicz http://chaosforge.org/

2 2

Re: [boost] [msm] new version available
by Christophe Henry 06 Apr '10

06 Apr '10

> On Monday 05 April 2010 09:12:14 Christophe Henry wrote: >> I just finished the newest MSM version. Unfortunately, I'm afraid I'm >> a bit late to get it shipped with boost v1.43 but at least it will >> give us time to have a look at it. > > You are still within the merge window and given that your documentation seems > to be in excellent shape, there is no reason to delay it past 1.43. Here's the > calendar for 1.43.0: > http://www.boost.org/development/index.html > > Regards, > Ravi Really? I thought Monday was deadline. What I am missing are regression tests, but if the Release managers allow it, I could write them this week (I never wrote a jamfile but for the sake of the argument, let's suppose I get this right). Release managers, is it still possible to ship MSM with 1.43? Christophe

2 1

[utility/result_of] decltype-based implementation breaking valid code on msvc-10
by Eric Niebler 06 Apr '10

06 Apr '10

I recently looked into some proto failures on msvc-10 and traced them back to the use of decltype in the implementation of boost::result_of. The program below demonstrates the problem: // Uncomment the next line to make the problem go away //#define BOOST_NO_DECLTYPE #include <boost/utility/result_of.hpp> template<class X, class Y> struct pair {}; template<class Base> struct S; struct wrapper { template<class T> struct result; template<class This, typename That> struct result<This(That)> { typedef S<That> type; }; template<typename That> typename result<wrapper(That)>::type operator()(That) const { return 0; } }; template<class T> struct S { S(int = 0) {} typename boost::result_of<wrapper(pair<T, T>)>::type foo() { return 0; } }; int main() { S<int> s; } The use of decltype in result_of causes the compiler to recursively instantiate templates until it blows its stack. To make the problem go away, you must #define BOOST_NO_DECLTYPE. I suspect the real problem is in a buggy implementation of decltype on msvc-10. For the upcoming boost release, I suggest that we stick with the non-decltype implementation of result_of on msvc-10, or risk massively breaking users' code, not to mention proto, spirit and xpressive on that compiler. -- Eric Niebler BoostPro Computing http://www.boostpro.com

5 7

Re: [boost] [utility/result_of] decltype-based implementation breaking valid code on msvc-10
by Eric Niebler 06 Apr '10

06 Apr '10

On 4/5/2010 6:05 PM, Daniel Walker wrote: > On Mon, Apr 5, 2010 at 6:39 PM, Eric Niebler<eric(a)boostpro.com> wrote: >> https://svn.boost.org/trac/boost/ticket/4072 >> >> A patch is attached to the ticket. I've confirmed that it un-breaks proto on >> msvc-10, but have not tested it further. > > Good catch. Seems reasonable to me. In general, if some vendor > releases an inadequate std:result_of or decltype, it would be good to > have boost::result_of as a functional fallback, which is yet another > reason to resolve the lambda/result_of issue. Enabling lambda to > support boost::result_of's signature protocol, as in ticket 864, would > do the trick. That way msvc-10 users would be able to enjoy > lambda/result_of compatibility, even if msvc-10 still has some > wrinkles. Daniel, I don't necessarily disagree, but I'm not really interested in getting this small issue mixed up with the larger issue of lambda/result_of compatibility. I just want result_of to work on msvc-10. -- Eric Niebler BoostPro Computing http://www.boostpro.com

3 4