April 2010 - Boost - lists.preview.boost.org

[Boost.process] GSoc proposal
by Kasra 05 Apr '10

05 Apr '10

Hi, I have decided to polish up the current boost.process this summer. It has been on the list far too many times without much further progress. After checking out the code I've begun working, so I need to start working on the new API which I intend to be similar to boost.thread. Are there any volunteering mentors? class process { class id; class status; class priority; typedef std::bitset<?> affinity_type; static process& this_process(); static std::vector<process> processes(); static std::vector<process> processes(const std::string& machine); static std::vector<process> processes_by_name(const std::string& name); static std::vector<process> processes_by_name(const std::string& name, const std::string& machine_name); static process start(const std::string& proc); static process start(const std::string& proc, const std::string& params); const id& get_id() const throw(); void terminate(bool kill = false ); status wait(); status idle_wait(); const boost::posix_time::ptime& start_time() const; affinity_type processor_affinity() const throw(); void processor_affinity(const affinity_type& affinity); const priority& priority() const throw(); void priority(const priority& new_priority) const throw(); postream& standard_input() const; pistream& standard_output() const; pistream& standard_error() const; boost::posix_time::time_duration kernel_time() const; boost::posix_time::time_duration user_time() const; boost::posix_time::time_duration total_time() const; const void* max_working_set() const; void max_working_set(const void* value); const void* min_working_set() const; void min_working_set(const void* value); uintmax_t peak_paged_memory() const; uintmax_t peak_private_memory() const; uintmax_t peak_virtual_memory() const; uintmax_t peak_working_memory() const; uintmax_t paged_system_memory() const; uintmax_t paged_memory() const; uintmax_t private_memory() const; uintmax_t virtual_memory() const; uintmax_t working_memory() const; }; With Best Regards Mr. Kasra Nassiri Department of Computer Science Imperial College London

3 2

Re: [boost] python/test/Jamfile.v2 help needed
by Ralf W. Grosse-Kunstleve 05 Apr '10

05 Apr '10

I think I figured it out: I moved the new "rule" block up in Jamefile.v2 . Now monitoring the build summaries again... Ralf ----- Original Message ---- From: Ralf W. Grosse-Kunstleve <rwgk(a)yahoo.com> To: boost(a)lists.boost.org Sent: Mon, April 5, 2010 1:05:20 PM Subject: Re: [boost] python/test/Jamfile.v2 help needed The recent build summaries for boost.python come up all blank. I'm guessing this is a bad sign. Are the log files somewhere from which I could tell what's wrong? Given boost svn trunk, I found out I can run bootstrap.sh to get a bjam executable. But I couldn't figure out how to build and run the python tests. Could some help with the commands I need? I have Fedora 6, 8, 11, 12. Ralf ----- Original Message ---- From: Vladimir Prus <ghost(a)cs.msu.su> To: boost(a)lists.boost.org Sent: Sat, April 3, 2010 11:21:04 PM Subject: Re: [boost] python/test/Jamfile.v2 help needed Ralf W. Grosse-Kunstleve wrote: > 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? Yes. Create a function as follows (in your Jamfile): rule require-windows ( properties * ) { if ! <target-os>windows in $(properties) { return <build>no ; } } then, in requirements of your tests, use <conditional>@require-windows, e.g: [ bpl-test calling_conventions : : <condiitonal>@require-windows ] Note that cygwin is a different OS from windows, so if the test must be run on cygwin, you need to adjust conditional accordingly. Does this help? - Volodya _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

1 0

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

05 Apr '10

>>> Hi, >>> >>> Just a form remark. We use to see the code highlighted. Have you the possibility to highligth the code? >>> >>> Best, >>> Vicente >>> >> >> Probably. I just need to find out if there is another DocBook tag for >> this. At the moment, I'm using <code>. >> I'm not a BocBook expert, but if one reads this, please help ;-) > > I have never used DocBook but I have found that http://www.sagehill.net/docbookxsl/SyntaxHighlighting.html. > > There are some uses of <programlisting> already in Boost.Function. > > Hoping this helps > Vicente Oh yes it does. And it looks much better, you're right. Great! Then it'll be done fast. Thanks a lot, Christophe

1 0

[Log] Problem with attributes + gcc -fvisibility=hidden
by Tony Astolfi 05 Apr '10

05 Apr '10

I'm evaluating boost::log for use in a project I'm working on, and I found a potential issue. If I compile my program using gcc with the '-fvisibility=hidden' option enabled, then some log event attributes don't show up in the output. For example: #include <boost/log/attributes/clock.hpp> #include <boost/log/common.hpp> #include <boost/log/utility/init/to_console.hpp> int main () { boost::log::init_log_to_console( std::cout, boost::log::keywords::format = "[%TimeStamp%] %_%" ); boost::log::core::get()->add_global_attribute( "TimeStamp", boost::make_shared< boost::log::attributes::local_clock >() ); boost::log::sources::logger l; BOOST_LOG( l ) << "Error!"; return 0; } Output: % g++ main.cpp -I../../../glnxa64/include -L../../../glnxa64/lib -lboost_log -lboost_system -lboost_log_setup && ./a.out [2010-Apr-05 12:39:14.872961] Error! % g++ main.cpp -I../../../glnxa64/include -L../../../glnxa64/lib -lboost_log -lboost_system -lboost_log_setup -fvisibility=hidden && ./a.out [] Error! I've found issues like this in the past caused by boost libraries not marking certain types as export-visibility, resulting in a failure later on to match two type-id objects that ought to be identical. Could something like this be happening in the recently accepted Boost.Log library? Is this something the author would be interested in fixing/supporting?

1 0

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

05 Apr '10

> Hi, > > Just a form remark. We use to see the code highlighted. Have you the possibility to highligth the code? > > Best, > Vicente > Probably. I just need to find out if there is another DocBook tag for this. At the moment, I'm using <code>. I'm not a BocBook expert, but if one reads this, please help ;-) Christophe

2 1

[test] How to have a simple unit test compile on Borland/CodeGear?
by Niels Dekker - address until 2010-10-10 05 Apr '10

05 Apr '10

Is the following still a proper way to write a unit test for a Boost library component? #define BOOST_INCLUDE_MAIN #include <boost/test/test_tools.hpp> int test_main(int, char*[]) { // TODO Some testing here... return 0; } I can't get the above code compiling on the latest Borland/CodeGear compiler (Embarcadero C++ 6.21), installed by c++builder_2010_3615_win_esd.zip, downloaded from www.embarcadero.com/downloads Even though I already patched boost/smart_ptr (ticket #4067) and boost/exception (ticket #4068). I just do: bjam toolset=borland Which tries to compile <boost/test/utils/runtime/cla/dual_name_parameter.hpp> apparently, and it yields an error at line 43: template<typename Modifier> void accept_modifier( Modifier const& m ) { if( m.has( prefix ) ) { set_prefix( m[prefix] ); // line 43, "Error E2094"! ... The complete error message is down here. Interestingly, the message says that operator+ is missing (while I don't see a need for operator+ in this context). Any help is appreciated! Kind regards, Niels ------------------------------------------------------------ CodeGear/Embarcadero C++ 6.21 output: Error E2094 ..\..\..\..\boost/test/utils/runtime/cla/dual_name_parameter.hpp 43: 'operator+' not implemented in type 'nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<const unit_test::const_string,description_t,const unit_test::const_string &>,nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<bool,optional_t,bool>,nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<bool,guess_name_t,bool>,nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<const unit_test::const_string,separator_t,const unit_test::const_string &>,nfp::named_parameter<const unit_test::const_string,prefix_t,const unit_test::const_string &> > > > >' for arguments of type 'nfp::typed_keyword<unit_test::const_string,prefix_t,0>' in function void dual_name_policy::accept_modifier<nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<const unit_test::const_string,description_t,const unit_test::const_string &>,nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<bool,optional_t,bool>,nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<bool,guess_name_t,bool>,nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<const unit_test::const_string,separator_t,const unit_test::const_string &>,nfp::named_parameter<const unit_test::const_string,prefix_t,const unit_test::const_string &> > > > > >(const nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<const unit_test::const_string,description_t,const unit_test::const_string &>,nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<bool,optional_t,bool>,nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<bool,guess_name_t,bool>,nfp::nfp_detail::named_parameter_combine<nfp::named_parameter<const unit_test::const_string,separator_t,const unit_test::const_string &>,nfp::named_parameter<const unit_test::const_string,prefix_t,const unit_test::const_string &> > > > > &)

1 0

[cpp0x] Macro to support some C++0x syntax and functionality
by Lorenzo Caminiti 05 Apr '10

05 Apr '10

Hello all, Consider the following C++0x-like example (inspired by ConceptC++ http://www.generic-programming.org/languages/conceptcpp/tutorial/ and C++ Contract Programming proposal n1962): // Example strangely uses pointers instead of iterators just to have preconditions. template<std::CopyConstructible T> requires Addable<T>, Assignable<T> // Concepts. precondition { first; last; } // Pointers not null. postcondition (total) { total == result; } // Returning result. T sum(T* first, T* last, T result) { for (; first != last; ++first) result = result + *first; return result; } What do you think of the following macro that implementes this in ISO standard C++ while keeping the above C++0x-like syntax by wrapping it within a preprocessor sequence? BOOST_CPP0X_FUNCTION( (template)( (std::CopyConstructible)(T) ) (requires)( (Addable<T>) (Assignable<T>) ) (precondition)( (first) (last) ) (postcondition)(total)( (total == result) ) (T) (sum)( (T*)(first) (T*)(last) (T)(result) ) ({ for (; first != last; ++first) result = result + *first; return result; }) ) The idea is that using the preprocessor I can parse the specified signature-sequence so I have all the tokens I need to declare/define the C++ function plus I can add the concepts (Boost.Concept), contracts (Boost.Contract), named parameters (Boost.Parameter), etc. Furthermore, the syntax of signature-sequence can be any valid preprocessor sequence that uses words (but not symbols) for keywords -- e.g., (requires) and (preconditions) are OK but (=) is not. This way I can define the signature-sequence syntax to closely match the syntax of C++0x (for concepts) and of other C++ standard proposals (like n1962 for contracts). DISCLAIMER: I think this is possible but I would need to try to implement it in order to be 100% sure and to identify possible limitations. Regards, Lorenzo P.S. I started considering this in reference to a previous email thread "Re: [boost] [contract] Contract Programming Library": On Sat, Feb 13, 2010 at 9:44 AM, Lorenzo Caminiti <lorcaminiti(a)gmail.com> wrote: > On Fri, Feb 12, 2010 at 3:39 AM, Andrzej Krzemienski <akrzemi1(a)gmail.com> wrote: >> I would be very interested in trying such a library. I have one >> it is inevitable, etc., but.. read on. I know at least one library in >> Boost that also spoils function declarations in order to provide >> additional functionality: Concept Check library; they may be others >> too (MPL?). >> My suggestion is that if there are (or will be) libraries that require >> spoiling function declarations, they should all provide the same >> "spoiled" syntax. Otherwise I will be always asking "how do I declare >> a function in this library?". It would be very convenient if Boost >> provided one alternative function definition syntax that when used >> would enable all its libraries to work. > I agree. However, in the past I did look into harmonizing my library > API with the ones of Boost.ConceptCheck and/or Boost.Parameter but it > did not seem feasible... I will double check it.

2 1

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

05 Apr '10

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

3 4

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

05 Apr '10

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

3 7

[GSoC] data structures library for summer of code 2010
by Dan Fox 05 Apr '10

05 Apr '10

Hi everyone, My name is Daniel Fox. I'm interested in working on making the advanced data structures library project idea for this year's Google Summer of Code. I've spent some time looking at the current structures in boost/pending and I believe I have an idea of what I would like to do for it.

1 0

[string_algo] first_finderF hoist empty check out of loop
by Jeff Flinn 04 Apr '10

04 Apr '10

In trying to get string algorithm icontains to work with spirit's file_iterator (which I still haven't been successful with) I noticed that the check for an empty search string is in side the loop. As: // Outer loop for(input_iterator_type OuterIt=Begin; OuterIt!=End; ++OuterIt) { // Sanity check if( boost::empty(m_Search) ) return result_type( End, End ); Wouldn't it be better to hoist this check out of the loop and only do it once? Thanks, Jeff

2 1

Semantic graphs for GSOC 2010
by Alexander Golec 03 Apr '10

03 Apr '10

Hey all, My name is Alexander Golec, and I'm a student at Fordham University studying mathematics, transferring to Columbia University to study CS engineering. I would like to ask about some specifics of the heaps and queues project. Have the items to be added to the advanced data structures library already been decided? How are the structures coupled to the BGL? Also, I would like to implement the binomial heap structure. Would anyone have any pointers for getting to know Boost's internals? Thanks, Alex

2 1

GSOC Bigint Proposal.
by swagat konchada 03 Apr '10

03 Apr '10

I would like to receive comments on my proposal for Bigint this year. To design, implement, test and document an expression template system("a wrapper for swappable Bigint providers") for the Boost.bigint around NTL, GMP(Is there enough interest around Xint?) in view of the numeric_adaptor scheme developed by Barend Gehrels in providing as many possible operators as possible. My mid-term examinations are going on and It's being impossible for me to hang around the list and study about Xint. I hope you understand... :)() -- Problem is a phenomenon indicating lack of thought. Swagat Konchada

2 1

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

03 Apr '10

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

7 14

Re: [boost] [range] Permission to merge to the Release branch
by Beman Dawes 03 Apr '10

03 Apr '10

On Fri, Apr 2, 2010 at 12:27 PM, Neil Groves <neil(a)grovescomputing.com> wrote: > Beman, > > I am seeking permission to merge the trunk version of Boost.Range into the > release branch. The regression test results have not detected new > regressions, however there are a number of the new features that are not > passing unit tests on several compilers. Since the new features would not be > usable if I did not merge my opinion is that it is worth merging to allow > the use of the newer features on more compliant compilers. In the meantime I > can seek to improve the support of adaptors and algorithms on the less > capable compilers. Go ahead and merge. For the tests that are expected to fail (because of older compilers, or whatever), please mark them up as expected failures. Ask if you need help with the markup. > > Of course, I respect that being a newbie to the Boost development and > release process that I may not be making the most informed judgement and > hence I respectfully seek your guidance. It is best to ask such questions on the main list. That allows others to comment, and if I'm not available one of the other release managers can reply. Thanks, --Beman

3 2

Graph class, an idea
by Alexander Golec 03 Apr '10

03 Apr '10

Hey all, I have recently been working on a project that has led me to some interesting ideas for a graph class. Chief among them is the structure of the cycle matrix. This is a matrix representing the fundamental cycles of a graph. With this matrix, one can easily determine if, given an arbitrary set of vertices, if there is a cycle that passes through all of them. Whats more, it can easily provide that cycle if it exists. I'd like to ask if this sounds like something that would be useful in Boost's Graph class. Thanks, Alex

2 1

Re: [boost] [GSoC 2010]: BGL Graph Connectives ideas
by Yaroslav Vorontsov 03 Apr '10

03 Apr '10

>> > I have some ideas about implementing graph connectives. I think that the >> > best way to implement first four binary operations (union, join, >> > intersection and difference) is to use adjacency matrices. >> > >> > I think variants of these algorithms for non-adjacency matrices are just as > important. It would be best to focus on these problems and their generic > solution than to propose more solutions for a smaller set of graphs. > OK, let it be so. The implementation of graph connectives using the adjacency matrices isn't too difficult. Regarding adjacency lists or incidency matrices, it's more difficult and intererestring to perform such operations. I meant that it's more convenient to do the operations for adjacency matrices and then to convert them into another graph representation, but now I doubt that this will be more effective (it needs some time to convert a graph from one representation to another (and a lot of memory), and the algorithm needs time and memory, too).

1 0

Re: [boost] Boost Digest, Vol 2869, Issue 5
by Yaroslav Vorontsov 03 Apr '10

03 Apr '10

>> > I have some ideas about implementing graph connectives. I think that the >> > best way to implement first four binary operations (union, join, >> > intersection and difference) is to use adjacency matrices. >> > >> > I think variants of these algorithms for non-adjacency matrices are just as > important. It would be best to focus on these problems and their generic > solution than to propose more solutions for a smaller set of graphs. > OK, let it be so. The implementation of graph connectives using the adjacency matrices isn't too difficult. Regarding adjacency lists or incidency matrices, it's more difficult and intererestring to perform such operations. I meant that it's more convenient to do the operations for adjacency matrices and then to convert them into another graph representation, but now I doubt that this will be more effective (it needs some time to convert a graph from one representation to another (and a lot of memory), and the algorithm needs time and memory, too).

1 0

A Pimpl variant
by vicente.botet 03 Apr '10

03 Apr '10

Hi, I don't know if this is the correct ML to talk about this subject, but as there was recently a discussion about wether Boost should or not use Pimpl, I have decided to post this here. In http://www.gotw.ca/publications/mill05.htm H. Sutter states "There are four main alternative disciplines: 1. Put all private data (but not functions) into XImpl. 2. Put all private members into XImpl. 3. Put all private and protected members into XImpl. 4. Make XImpl entirely the class that X would have been, and write X as only the public interface made up entirely of simple forwarding functions (another handle/body variant)." My experience is that I add more private member functions than private member data. I have explored a different variant 5. Put all private funtion and static data (but not instance data) into XImpl. XImpl needs only to store the back pointer. While this approach doesn't encapsulates all the private members has some advantages: * The XImpl class has no inherent instance data, so no space overhead * The class doesn't needs to store any XImpl pointer as there is no data to maintain, so no need to allocate/deallocate it. * Reduce the performance overhead of the Pimpl idiom. The drawbacks are: * Need to include the headers needed for the private instance data. * There is yet a minimal performance overhead on the construction of the temporary XImpl class and the derreference of the back pointer. Next follows an implementation exaple. * Grant friend access to the private implementation class class C { public: void f(); void g(); protected: // ... private: struct impl; friend struct impl; // the private part contains only instance data and virtual functions int priv; }; * Identify the private functions and the private static data and put them on the implementation class struct C::impl { C::impl(C* thisC) : that(*thisC) {} void ifct() { that.priv = ... // use of private data that.g(); // call to a public function jfct(); // call another private function } C& that; static int icount; }; * Prefix all the ex private function calls by impl(this) impl(this).ifct(); * Access without constraints the impl static data impl::icount; There is a proposal from Francis Glassborow, N1742: Auxiliary class interfaces:<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1742.pdf> that address this problem in a general context. What do you think of this variant? Best, _____________________ Vicente Juan Botet Escribá

6 11

[lambda] [result_of] Lambda enhancements
by Adam Butcher 03 Apr '10

03 Apr '10

Hi Perhaps this would have been better as two separate mails but since it is all lambda related I have included it as one (despite one patch actually being to the result_of library). [lambda] I discovered recently that member-function-ptrs wrapped in boost::lambda objects do not apply directly if the subject is held in a smart-ptr (unless that smart-ptr has an implicit conversion to T*). There are a number of places in our code base where we have worked around this by using something like *free1 rather than simply free1 which ends up calling the 'apply member-function to object-by-reference' adaptor. This works providing the smart-ptr defines a type 'element_type' to be the underlying object type (as shared_ptr et al do). It does not work for third-party smart-ptrs that do not define this type. It struck me that since boost.bind uses boost.mem_fn's get_pointer template to handle this use case it would be reasonable to add an overload of 'apply' to lambda/detail/function_adaptors.hpp that deferred to that. I knocked up a perl script which adds the necessary overloads to each specialization in function_adaptors which I have attached (I have also attached the resulting diff). It may be that this yields some unpleasant side-effects that I haven't thought of or observed but so far it seems to work okay with our code base. The get_pointer overload is disabled if the argument is convertible to ref-to-const-object-type (e.g. if it is a derived type) since then the reference overload should be used. I would appreciate any feedback on the idea and implementation. [result_of] Whilst implementing a front-end template for a set of functions that accept boost.function objects with various return types, I discovered that boost.result_of does not implement support for the nested sig<tuple> template used by boost.lambda objects. My intent was to accept any user-supplied function at the front-end and, based on the given function's return type when applied to a specific set of arguments, forward to the appropriate implementation. This determination currently fails if the user supplies a lambda object. The attached result_of patch adds detection of the nested sig template in order to support determining the return type of lambda functions (providing the necessary arguments are given). This is done in a non-intrusive way; i.e. there is no physical dependency on boost.lambda or boost.tuple, though the boost.tuple classes 'cons' and 'null_type' are forward declared. Since they are only ever instantiated when a boost.lambda object is provided (which will have already brought in their definitions) I think it should be okay. In order to provide the sig template with its required tuple, a facility has been added (with implementation generated by some additional preprocessor code) that converts from function-type to tuple (i.e. F(A,B...) -> cons<F,cons<A, cons<B,...null_type>>>). Since only the type declarations are required this can be done without pulling in any tuple headers. One thing I am a little concerned about is that the determination mechanism for the existence of the sig template is probably not very portable (I have only tried it on GCC 4 and VC9). Is there an MPL/type_traits predicate generator for portable nested template detection? I am aware of BOOST_MPL_HAS_XXX_TRAIT_(NAMED_)DEF but I couldn't see any generator around that area that would do nested template detection. We have such a facility in our code base but it will have only been tried on GCC 4 and VC9 (maybe also VC7.1). Again I would appreciate any feedback on these diffs and whether or not they are suitable for inclusion into the respective libraries. Regards, Adam

4 4

Review results missing for boost.log
by Michael Caisse 03 Apr '10

03 Apr '10

In an attempt to reduce the FUD on IRC I pointed people to the review schedule page to find results on the Boost Log review. To my sheepish chagrin the results are not in the table. Not sure who has permissions to update the table. The following link is Volodya's posted review results. http://article.gmane.org/gmane.comp.lib.boost.devel/201541 thanks - michael -- ---------------------------------- Michael Caisse Object Modeling Designs www.objectmodelingdesigns.com

1 0

[GSoC] Heaps & Queues (draft proposal)
by iaml 02 Apr '10

02 Apr '10

Hi everyone. I am Lintao from Sun Yat-sen University, China. This is my first time to send mail on mailing list. I'm a little nervous:-). I am interested in Heaps & Queues provided by Boost in 2010 GSoC. And I have finished my draft proposal after viewing the mailing list these days. Thank you for your comments and suggestions. ====== project proposal ====== In my opinion, most of work is to reuse and rearrange the existing data structure in boost/pending and other data structures which have already existed.[1] The most important thing I should consider is the APIs design of the new library. So for each data structure, it should not only agree to the formulation provided by the BGL, but also should be easy to remember and user-friendly. Besides, I would like to add d-ary heap and splay heap into the new library. Because d-ary heap is a variation of binary heap and has faster running time. As for splay heap, 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. If time permits, I want to add others implementations of heap [2] into the new library. Below is my design to the library APIs. template <class T, class Compare = std::less<T>> class heap{ public: * void insert(T& key);* * void delete(T* key);* * void update(T* t, T& new_key);* T* getRoot(); T* find(T& key); bool empty() const; size_type size() const; void print() const; private: void print_recur() const; protected: T* _root; }; NOTICE: * operations in bold mean it should be implement by the subclass. * 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 splay heap should inherit from this abstract class and add additional operations if needed. And I would prefer to use lists rather than vectors (as shown in boost/pending/fibonacci_heap.hpp) to implement it for three reasons. 1. It will save memory since the later needs extra space to store the key to value mapping. 2. Vector requires continuous memory while list doesn’t. It does not matter when the amount of data is small. But when the amount of data becomes large, it will be a tough problem; 3. It takes time to resize and reallocate the memory for vectors. Of course, list implementation has its own drawback such as easy to leak memory and cost more time when searching the heap. From my point of view, it is acceptable comparing with the problems mentioned before. As the adaptor of heaps, the priority queue API may like: template<class T, class Compare = std::less<T>, class Container = fibonacci_heap<T, Compare>> class priority_queue{ public: void push(T& key); T pop(); const T& front() const; T& front(); T* find(T& key); void update(T* t, T& new_key); bool empty() const; size_type size() const; void print() const; private: void print_recur() const; }; [1][2] It means the data structure in this URL: https://svn.boost.org/svn/boost/sandbox/libs/pri_queue/ Thank you for reading.

3 3

[GSoC 2010]: BGL Graph Connectives ideas
by Yaroslav Vorontsov 02 Apr '10

02 Apr '10

> > I'm Yaroslav Vorontsov (or simply Jerry Lee :-)), a student of Computer > > Science Department of Voronezh State University, Russia. I'm interested in > > both generic programming and graph theory, and I also would like to > > participate in Google Summer of Code 2010. I had some experience of generic > > programming before when I tried to implement my own generic graph library in > > C# (of course, as a task on one of programming courses at the university). > > I've read that (quote) "The Boost.Graph library is missing connectives...". > > I'm quite familiar with C++ and the idea of generic programming and I'm > > working with some graph theory aspects at the moment, so I want to know: > > what particular skills (in programming, of course) are needed to develop > > graph connectives? > > > > Hi Simply Jerry Lee:), > > Good question. Working on the Boost graph library requires a sound > understanding of its organization and its construction. There are a lot of > techniques used in its construction that are atypical of most OO libraries > (even C# generic data structures). You should be able to identify aspects of > an algorithm that aren't "universally generic" and understand how to > abstract them using templates, types, metaprogramming, etc. > > Most of that can be learned on the job, so to speak, but having a good eye > for abstraction certainly helps. > > Andrew Sutton > andrew.n.sutton(a)gmail.com > > Mr Sutton, Many thanks for your exhaustive explanation! :-) I have some ideas about implementing graph connectives. I think that the best way to implement first four binary operations (union, join, intersection and difference) is to use adjacency matrices. Also I'd like to add an operation which wasn't mentioned in the task proposal. It's ring sum of two graphs. Here is a short description: let A(Va,Ea) and B(Vb,Eb) be two graphs, where Va and Vb are sets of vertices of these graphs and Ea and Eb are sets of edges. The ring sum of A and B is a new graph C=A(+)B which has no isolated vertices and which has edges included only in Ea or in Eb (but not in both sets). It's something like symmetric difference between two sets in the set theory. As for unary operations, adjacency matrices may be useful in the implementation of graph closure, removal of edge and shrinkage of graph. Yaroslav Vorontsov DarthYarius_0990(a)mail.ru

2 1

use case of [move] rvalue reference emulation
by DE 02 Apr '10

02 Apr '10

hi all once i needed to pass around an object of a reference-like type i.e. a class with reference semantics something as trivial as template<typename type> struct ref { typedef typename type::value_type value_type; type &reference; const size_t index; ref(ref &a) : reference(a.reference), index(a.index) {} ref(type &a, size_t i) : reference(a), index(i) {} ref &operator=(const value_type &a) { /*setting value, e.g. 'reference.set(index, a)'*/ return *this; } operator value_type() const {/*return appropriate value, e.g. 'reference.at(index)'*/} }; so an access function returned an object of that ref type by value and no function wanted to take it because eventually a rvalue could not be bound to a non-const reference then an idea of using a rvalue emulation proposed by boost move library came in my mind although it's not a move constructor it allows to construct objects of type 'ref' from rvalues: ref(rv_ref<ref> &a) : reference(a.reference), index(a.index) {} and also a conversion to rv_ref sholud be added: operator rv_ref<ref>&() { return *static_cast<rv_ref<ref>*>(this); } see fully working code example at http://codepad.org/rRM93AFo defining a reference type "rvalue copy assignable" makes it behave almost the same as ordinary c++ references also constness is preserved perfectly and it happend so that all limitations of the emulation only strengthen the design of such reference types (e.g. unavailability of 'type(const type&)' constructor) an example of the application of such reference types may be an advanced map class when you subscript an stl map object like map[key]; a record with the 'key' is created in the map if it's not there already so not to overpopulate our map we write something like value_type value; if (map.is_there(key)) value = map[key]; of course there is no such 'is_there()' member function in an stl map i'm just trying to make my intention clear so were that smart reference typedefed in the map like template</*...*/> class map { public: //... typedef map_ref<map> reference; //... }; it could have slightly better semantics: map[key]; //always does nothing map[key] = new_value; //if there is no record with 'key' -> creates it //assignes 'new_value' to the value of the record value = map[key]; //retrieves a value associated to 'key' in the last case if there is no such record in the map it may return an invalid value or throw an exception anyway i consider this semantics more natural than that of the current std::map not to mention that you may pass a reference to a function: void foo(map::reference a) { a = "42"; } //if there was no record -> creates it //... foo(map[key]); //does not create record at this point and it will work flawlessly -- Pavel P.S. if you notice a grammar mistake or weird phrasing in my message please point it out

1 1

[contract] Released Contract Programming Library on SourceForge
by Lorenzo Caminiti 02 Apr '10

02 Apr '10

Hi all, I have released on SourceForge a library that implements Contract Programming (a.k.a. Design by Contract(TM) ) for C++. I am considering to submit this library to Boost (as Boost.Contract). Contract++ Library * Download http://sourceforge.net/projects/dbcpp/ * Documentation http://dbcpp.sourceforge.net/ * Examples http://dbcpp.sourceforge.net/contract__/examples.html Comments? Regards, Lorenzo

2 9