- Boost - lists.boost.org

[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

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

06 Apr '10

> Christophe Henry wrote: >> 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. >> - internal transitions: for all front-ends, and both ways: either in >> the transition table or inside state's internal transition tables >> - more row types (yes, even more) allowing actions to be defined in >> state machines or in states >> The last 2 points aim at making states more useful >> > > Christophe - > > I'm looking forward to trying it out. > > michael I'm counting on your always very useful comments! Thanks, Christophe

1 0

python/test/Jamfile.v2 help needed
by Ralf W. Grosse-Kunstleve 06 Apr '10

06 Apr '10

I've merged the current boost/python and libs/python trunk into the release branch, followed by this patch: Index: libs/python/test/Jamfile.v2 =================================================================== --- libs/python/test/Jamfile.v2 (revision 61033) +++ libs/python/test/Jamfile.v2 (working copy) @@ -184,8 +184,10 @@ # bpl-test bienstman5 ; # } -[ bpl-test calling_conventions ] -[ bpl-test calling_conventions_mf ] +# XXX disabled on release branch only, +# XXX to avoid failures on platforms other than Windows +# [ bpl-test calling_conventions ] +# [ bpl-test calling_conventions_mf ] # --- unit tests of library components --- Is it possible to have those two tests built and run only under Windows? Thanks! Ralf

3 5

[GSOC2010] HEAPS & QUEUES draft proposal
by Alexandru Damian 06 Apr '10

06 Apr '10

Hello everyone, My name is Alexandru Damian. I am a second year student at the Polytechnic University of Bucharest, Romania. I am very interested in the Heaps & Queues idea, and with both a good programming and mathematical background, I believe that I can offer valuable ideas to this project. Below is a draft proposal for this. I didn't know what you would expect from such a proposal (talked to grafikrobot on freenode and he redirected me here), so the structures that are to be implemented are rather vague. If the proposal is on track, I will detail them. I have also talked so some guys on the irc channel about a more generic approach to trees and tries. What's your opinion on that (given that tree structures are already implemented in /intrusive)? I hope I'm not too annoying :). ***STUDENT PROPOSAL: HEAPS & QUEUES*** NOTE: My Student Proposal follows the template listed on: https://svn.boost.org/trac/boost/wiki/SoCSubmissionTemplate **PERSONAL DETAILS** NAME: Alexandru Damian UNIVERSITY: Polytechnic University of Bucharest MAJOR: Computer Science and Engineering DEGREE PROGRAM: B.Sc. EMAIL: alexdamian1989(a)gmail.com AVAILABILITY: According to the official timeline, there will be 11-12 weeks at my disposal: March 24 - August 9 (16). However, I plan to contract the "Community Bonding Period" to 2-3 weeks, so that I may have at least one week advance in coding. This will help me better organize my time during the summer, when I will be unavailable for about 2 weeks (in June) because of my exams. **BACKGROUND INFORMATION:** EDUCATIONAL & WORK BACKGROUND: I have been preparing in the fields of Computer Science and Mathematics since high-school when I have competed in numerous national and international competitions, gaining important experience and always finishing among the best. My interest in personal and professional growth has continued at university as well, with even better results at contests and scientific research. My work background and coursework have supplied me with many skills in theoretical computer science, data structures, algorithms and programming languages. In addition, I have broad experience in Mathematics and problem solving techniques. In the year 2009, I have worked at different projects for the Faculty of Automatic Control and Computers, including the research and development of a way to store and illustrate the temperature ratio in the University server room. The same year, I worked as a volunteer student consultant and I offered support in Mathematics for students taking the admission examinations. EXPRESSION OF INTEREST: Boost C++ Libraries has caught my attention in 2008, when I had my first important encounters with the Open Source Community. A library that offers more advanced data structures and algorithms than STL is needed on a daily basis when optimizing complex code. It is only natural for me to choose the "Heaps & Queues" project, as I have valuable experience in the algorithms that power these structures and their real-world applications. My plans for further support and development of the Boost C++ Libraries will extend even after the GSOC deadline, with plans to implement more algorithms supplementary to the work done during the summer and in other areas (such as the BigInt idea, or AI algorithms: neural networks, genetic algorithms, fuzzy systems etc.). PROGRAMMING SKILLS: Strong background in theoretical computer science, algorithms, data stuctures and optimization . Strong background in advanced mathematics. Programming Languages: C (4/5), Java (4/5), C++ (3/5), C# (3/5), Shell scripting (2/5), ASM (2/5). Other programming languages and their proficency levels are illustrated in the Resume. **PROJECT PROPOSAL** ABSTRACT The purporse of this project is to create a library that involves heap and queue creation and manipulation. This will be very useful in implementing more complex algorithms or data structures that take advantage of these structures (a basic example is Dijkstra's shortest path algorithm). The library will include basic implementations of heap structures (i.e. binary heap) and queues, as well as the more complex (and more relevant) structures. PROJECT CONTENTS The current version of the Libraries has little support for heaps and queues. Therefore, the following will be implemented, with a discussion on every structure's difficulty, speed and memory used. Firstly, a well-known table of complexities for the binary min(max)-heap: findMin(findMax) : O(1) | deleteMin(deleteMax) : O(log N) | insert : O(log N) | merge : O(N) * D-ARY HEAP : a more general implementation of the binary heap (2-ary heap). The main advantage a d-ary heap has is that insertion will be significantly faster, requiring a theoretical O(log_d N) operations. However, finding an element's parent is rather difficult if d is not a power of 2, since we can not use bitwise shifting operations. However, delete-min is slower, because of the d-1 comparisons to find the minimum value, using a standard algorithm (probable fix: use a min-heap). * BINOMIAL HEAP, BINOMIAL TREES : a mergeable heap; although the complexity for findMin(findMax) is O(log N), this heap, along with the ones below (also mergeable), offer a better complexity for merge : O(log N). Since binomial heaps use binomial trees, this data structure will also be implemented. * FIBONACCI HEAP : another mergeable heap, with better amortized time complexity than the binomial heap * RELAXED HEAP, RELAXED FIBONACCI HEAP (an idea at: http://www.google.ro/url?sa=t&source=web&ct=res&cd=1&ved=0CAYQFjAA&url=http…) * SKEW HEAP : a structure that is easier to merge than a binary heap, but is unbalanced. This could be considered optional, as it is a median option between d-ary heaps and mergeable heaps (binomial, fibonacci). * TREAP : although treaps are already implemented, they should be adapted to use the new heap library. * QUEUE : a basic implementation of the queue structure (possibly use the STL container) * DEQUEUE : although an implementation already exists /fusion/container, that has to be documented. A new implementation using the generic queue structure mentioned above. * PRIORITY QUEUE : implemented with the use of a heap. * BUFFER (CIRCULAR QUEUE) : fixed size, circular queue (if queue is full, the oldest data is overwritten). Such a queue could be used to implement a structure similar to RRDs. * (BONUS) SKIPLISTS : randomized search structure. * (BONUS) B-TREES : extended binary trees with excellent complexity when comparisons are not the most time-consuming operations. * (BONUS) INTERVAL TREES : extended complete binary trees supporting fast segment intersection queries. Some of these structures can use a fixed size array (use /boost/array). However, it would be good to eliminate the constraints of fixed size arrays. This will require using STL's <vector> or, should it be decided not to include a binary, a local implementation of it, i.e. ARRAY LIST. TIMELINE As stated above, I would like to start with an advance of one week (May 17). WEEKS -2, -1, 0 (April 26 - May 16) : Community Bonding Period These three weeks will offer me the possibility to accomodate with the code, the coding conventions and the community. During these 3 weeks, I will also discuss with the organization whether binary libraries should be included or proprietary structures should be implemented (variable sized arrays, basic queue, basic priority queue (heap)). Modifications in the timeline (reordering, additions, deletions) can also occur. Finally, I will decide if I clean up the implementations from /pending (i.e. queue, fibonacci_heap, relaxed_heap, etc.) or create new structures, based on the newly implemented structures. Implement some simple structures so as to better get used to the code (probably ARRAY LIST or BINARY HEAP). WEEK 1 (May 17 - May 23) : Implement D-ARY HEAP, BINARY HEAP (2-ARY HEAP). Decide whether to first implement the d-ary heap and then the binary heap as a particular case, or implement the binary heap first, and after that the d-ary heap, associating a binary min(max)-heap to each array of children; solve the excess memory. WEEKS 2, 3 (May 24 - June 6) : Implement BINOMIAL TREES, BINOMIAL HEAPS, FIBONACCI HEAPS (don't adapt, usage for relaxed fibonacci heaps), RELAXED HEAPS and RELAXED FIBONACCI HEAPS. Official start of the coding phase. All of these heaps follow the same basic ideas, therefore progress should be relatively easier after the binomial heaps are implemented. Initial algorithms will probably be those specified (and variations) in Cormen or Knuth, as well as the idea suggested in the above mentioned link. WEEKS 4, 5 (June 7 - June 20) : University Exams WEEKS 6, 7 (June 21 - July 4) : Fix any problems with previous heaps. Implement SKEW HEAPS. Adapt TREAPS. WEEKS 8, 9 (July 5 - July 18/16) : Add mutable behaviour to the heaps. Apply optimizations. Create some automated tests. Week 8 will mark the mid-term evaluation deadline. The objective is to complete HEAP structures. The timeline offers roughly 2 weeks for bug fixing, so that should be enough. WEEK 10 (July 19 - July 25) : Implement QUEUE, DEQUEUE. WEEK 11 (July 26 - August 1) : Implement CIRCULAR QUEUE, PRIORITY QUEUE. WEEK 12 (August 2 - August 8) : Fix bugs related to the QUEUE structures. Add mutable behaviour to the queues. Apply optimizations and custom algorithms for fixed-length data types. Create automated tests. WEEK 13 (August 9 - August 16): Finalize code and documentation. NOTES: 1. The Exams period is, actually, 4 weeks (June 7 - July 5), comprising 5 exams. However, I should be able to compress the total time to only 2 weeks by moving some of my studying in May. 2. Weeks 6 and 8 are reserved for fixing heap bugs. Should there be less problems than expected, I can gain one bonus week. 3. If we choose to implement the structures using STL binaries, I could gain one more bonus week from weeks 1, 10 and 11. 4. With (2) and (3) in mind, I could implement any of the bonuses written above (at the end, if everything else is complete). a) SKIPLISTS : a randomized search structure with very good practical complexity. b) INTERVAL TREES : given the already implemented Interval structure (/numeric/interval), it would be nice to have such a structure, for easy geometric intersection queries. c) B-TREES : adaptation of the Balanced Binary Trees, typically used in situations where the comparison operation is not the most time consuming one (disk seeking). WORK FLOW I plan to organize my time and coding in such a manner that I am able to post changes on a forum / blog every 4 days (except the period with exams). That means roughly 2 times per week, as I will have no problem working in weekends. TODO Cheers, -- Alexandru Damian Polytechnic University of Bucharest Faculty of Automatic Control and Computers

2 1