- Boost - lists.boost.org

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

[GSoC] - Graph.boost - Graph Connectives
by Davi Barbosa 09 Apr '10

09 Apr '10

Hi, I am interested in participation in GSoC 2010 in Boost.Graph. I liked the first two options, but between these two I am much more interested in the second (graph connectives) because it seems more useful and challenging. Unfortunately, I will be having classes until the end of June (some of them will end early), so I will have a restricted time at the beginning. Of course I am explaining this in my proposal and making the schedule work with this big restriction. Do you think this could be a big problem? I am having exams right now so I did not had the time to join the list, get in contact, etc. I already started writing a proposal, but I still have one exam in a 4 hours and only after that I will be able to really write it. After finishing a draft, I would like to know if I can send it in pvt to someone for a quick review. Is anyone able to do this big favor? I had some other questions, but I already asked them in the IRC channel (with the nick "recife"). Thanks for everyone who answered! Davi Barbosa.

2 1

[GSoC] Graph layout algorithms - proposal draft
by Milos Djuric 08 Apr '10

08 Apr '10

Hello everyone, I've put together a draft of my proposal for a GSoC project to work on graph layout algorithms. The proposal can be found here: http://socghop.appspot.com/gsoc/student_proposal/show/google/gsoc2010/djura… I'd really appreciate if I could get some feedback (especially from possible mentors, and maybe someone from the Parallel BGL ?). All suggestions are more than welcome. Thanks, Milos

4 4

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