- Boost - lists.boost.org

[GSoC] Students; Please note..
by Rene Rivera 09 Apr '10

09 Apr '10

GSoC students, Now that the GSoC submission deadline has passed it is vitally important that you pay attention to your proposals and the comments the mentors add to them. Please address questions and suggestions we put on the comments ASAP. As it will both make our lives easier, and hence more likely to make accurate assesments of proposals. And it will increase the chances that we consider your proposals serious enough to want to move forward, if we get our feedback resolved. Good luck to all :-) -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail

1 0

[config] New defect macro: BOOST_NO_COMPLETE_VALUE_INITIALIZATION
by Niels Dekker - address until 2010-10-10 09 Apr '10

09 Apr '10

FYI, John Maddock has just added the tests to trunk/libs/config that I wrote for a new defect macro: BOOST_NO_COMPLETE_VALUE_INITIALIZATION https://svn.boost.org/trac/boost/changeset/61153 And some documentation: https://svn.boost.org/trac/boost/changeset/61154 A test failure indicates that the specific compiler doesn't have completely implemented value-initialization. In the coming few days, the test is likely to cause regression failures, because I still need to define the defect macro for those specific compilers (at boost/config/compiler). Although I already expect certain compilers to fail (MSVC <= 2010, CodeGear/Borland <= 2010, GCC < 4.4, and various versions of Sun) I chose not to define the defect macro /beforehand/, because the test output provides some extra information about the particular compiler issue. Moreover, once the defect macro is defined, the test framework no longer indicates whether the compiler defect is really there. I'll keep an eye on the regression page, http://www.boost.org/development/tests/trunk/developer/config_.html and fix them one by one, but please don't hesitate to remind me if there's a regression failure regarding the new defect macro that I overlooked. The defect macro will allow fixing ticket #3869, "Unconditional call to memset in value_initialized()", reported by Aleksey Gurtovoy: https://svn.boost.org/trac/boost/ticket/3869 by adding an #ifdef to utility/value_init.hpp: #ifdef BOOST_NO_COMPLETE_VALUE_INITIALIZATION std::memset(&x, 0, sizeof(x)); #endif Kind regards, Niels -- Niels Dekker http://www.xs4all.nl/~nd/dekkerware Scientific programmer at LKEB, Leiden University Medical Center

1 1

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

09 Apr '10

> The new package on Vault is missing boost/msm/back/default_compile_policy.hpp. > Everything seems to compile fine once I grabbed it from the sandbox, so I assume > the other files in the package are the proper versions. I found the problem. SVN refuses to correctly update the directory I used to build the zip. Even cleanup has no effect, so I will delete the whole stuff and checkout again. There are actually 2 important files missing, so I had no other choice than to upload the correct version again. For all who downloaded from the vault, sorry about it, you will need to download again (the sandbox is ok though). > Also, I very much dislike that metafunctions.hpp does 'namespace mpl = > boost::mpl;' in global scope. Isn't putting anything in global scope against the > boost guidelines? Even if not, I find it quite inappropriate to inject another > library's namespace into global scope. This line is not even needed as all mpl types are qualified inside the library with ::boost::mpl so I just removed the line. This problem is there since at least the 1.20 and went unnoticed. Sadly, some of the tutorials fail to fully qualify the mpl types, so I updated them too. Both versions, sandbox and vault should now be up to date and with these 2 problems solved. Thanks, Christophe

1 0

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

Boost.Botan final proposal
by Chad Seibert 09 Apr '10

09 Apr '10

Hi, Pending any other revisions, here's my final proposal: http://socghop.appspot.com/gsoc/student_proposal/edit/google/gsoc2010/chads… Thanks to all who gave advice, please ask if you have any questions! 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:…

2 2

[GSoC] Bits & Ints proposal
by Murilo Adriano Vasconcelos 09 Apr '10

09 Apr '10

Here is my proposal for Bits & Ints idea: http://socghop.appspot.com/gsoc/student_proposal/show/google/gsoc2010/muril… Any comments? -- Murilo Adriano Vasconcelos

1 0

boost::interprocess
by Rohit Goel 09 Apr '10

09 Apr '10

Hi, How can I synchronize mutlipe read/single write on a file available on a shared folder ? The multiple read/write need to be synchronized b/w different processes running on different machine. -Rohit

2 1

[msm] new version available
by Christophe Henry 09 Apr '10

09 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. - 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 - some performance gain - new eUML syntax to get rid of parens and to better support attributes - policy for better compile-time at cost of dispatch speed. And a few minor improvements. It was not possible to implement every wish and excellent idea offered during the review at this point, but they are in no way forgotten and I do not intend to stop development now. I'm interested in any comments, especially about the doc, which, like everything new, probably is not perfect but I hope, still an improvement. 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

5 4

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

[GSoC] Some new ideas for this year's GSoC
by Stefan 09 Apr '10

09 Apr '10

Hello, I am Stefan and this is my first year at GSoC as it's the first time I'm eligible to participate as a student. Since I have been using C++ and the Boost libraries for quite some time, I would be thrilled to be able to code for Boost. I have quite a few ideas, and I was wondering which ones you consider to benefit the most, therefore I'm awaiting for your feedback. Also, please let me know if any of these ideas are already implemented in any of the libraries. Here we go: * Selection algorithm (find the kth smallest element in a container, O(n) worst-case, very easy to implement) * Optimize Boost String Algorithm finders to use an efficient substring matching algorithm as opposed to the naive algorithm. Most likely because of the fact that boost has implemented the finders for strings as generic algorithms, they haven't used efficient algorithms such as KMP, Boyer-Moore, Rabin-Karp etc. \see boost/algorithm/string/detail/finder.hpp The idea is to implement efficient algorithms such as the ones mentioned above to replace the current naive implementation. Note: it may be difficult to find nth matching substring position using some of these algorithms. Difficulty: easy-medium * Implement a string algorithm for generating the suffix array. The suffix array, after being precomputed on a certain string, allows for very efficient substring searches in the future. This is useful when the string doesn't change too often but there are plenty of substring to search against. * Yet another efficient associative data structure, skip lists? * Space partitioning data structures? kd-trees? quadtrees? octtrees? collision detectors? closest neighbors? * A parser capable of evaluating mathematical expressions which contains operands,operators,function calls,variable names and constant names (also considering priority of operators): 1. a list of valid operators described by: a) number of operands (unary/binary/ternary?); b) allowed operand types; c) the precedence (priority of the operator) 2. a list of existent functions described by: a) function name; b) number of parameters; c) type of each parameter and return type; d) a callback (maybe just automatically deduce type based on the callback's type if possible) 3. a list of constants 4. a list of allowed variable names and types Here's a pseudo-C++ code sample on how it should look like: namespace m = boost::math_expressions_parser; m::parser p; p.add_operators() ('+', 1, ret<int32_t>(_1+_2)) // binary +, precedence 1 ('*', 2, ret<int32_t>(_1*_2)) // binary -, precedence 2 ('+', 3, ret<int32_t>(_1)) // unary +, precedence 3 ('-', 3, ret<int32_t>(-_1)); // unary - (also a funny face), precedence 3 p.add_functions() ("sin", ret<int32_t>(sin(_1))); p.add_constants() ("PI", 3); p.add_allowed_variables() (allowed_var<int32_t>("x")); m::expression E("1 + 3*sin(PI*x)", p); // evaluates mathematical expression E against parser p if (!E.valid()) { /* ... */ } else { std::cout << E.evaluate( ("x", 3) ); // evaluate this expression by letting x=3 E.let() ("x",4); std::cout << E.evaluate(); } //Maybe an optimization so only the parts that depend on the changed variable will be recalculated every time?. E.g.: for expression f(x)+y, f(x) is recomputed only when x is changed. This may cause problems for functions that do not always yield the same results for the same input. Maybe make this optimization optional, only if the user marks the function/operator as "volatile" or something Difficulty: hard-very hard * Someone suggested on this ml earlier that a crypto suite would be useful for boost. Maybe, but it would take a lot of time and dedication to implement. I believe that we should at least add some Cryptographic hash functions (such as md5, sha1, sha256 etc.). No one wants to install Crypto++ or something similar just to be able to compute the SHA1 sum of a file. It is a common necessity to want to compute a hash function of a string. Difficulty: very easy if you copy the implementation and just create a boost-ish interface * In-place radix sort? Radix sort is a very efficient algorithm which performs better than std::sort (my implementation) (also asymptotically better) for some particular types such as: uint8_t, uint16_t, uint32_t, unsigned char, unsigned char[2], unsigned char[4] etc. Radix sorting takes linear time, but unfortunately, linear memory. It is very useful for sorting very large amounts of numbers tho (or genetic codes and maybe some other stuff). I am able to implement some of these stuff and I'm waiting for your opinion in what would be most useful to be part of boost. Let me know if you believe that none will have any use. Yours sincerely, Stefan

8 15