June 2011 - Boost - lists.boost.org

Re: [boost] First Boostcon videos available....
by Marat Abrarov 08 Jun '11

08 Jun '11

Marshall, > Keynote: http://blip.tv/boostcon/hans-boehm-threads-and-shared-variables-in-c-0x-key… > Chris Kohloff (Monday): http://blip.tv/boostcon/thinking-asynchronously-designing-applications-with- > boost-asio-5250947 > Hartmut (Monday): http://blip.tv/boostcon/phoenix-v3-an-overview-5250984 Long awaited videos! Why not youtube? blip.tv is rather slow (at least in Russia). Regards, Marat Abrarov.

3 2

[Heaps] Compiler error: ‘optional’ was not declared in this scope
by Phil Endecott 08 Jun '11

08 Jun '11

Dear All, I'm trying to do some simple tests with the proposed Heaps library, but I get a mountain of compiler errors that start like this: ./boost_heap-HEAD-449f378/boost/heap/priority_queue.hpp:32: error: ‘optional’ was not declared in this scope ./boost_heap-HEAD-449f378/boost/heap/priority_queue.hpp:32: error: template argument 1 is invalid ./boost_heap-HEAD-449f378/boost/heap/priority_queue.hpp:32: error: expected unqualified-id before ‘,’ token I thought this was probably due to me having a too-old boost installation, but I believe I'm now compiling with 1.46.1 and I get the same error (though I need to verify that my paths are all set correctly). Any ideas anyone? (I've arrived late to this review having been away, but I'd like to do some quick benchmarks if I have time.) Thanks, Phil.

3 5

Re: [boost] Gauging interest in new library re: multiscale/multigranular containers
by nathaniel＠tierblend.org 07 Jun '11

07 Jun '11

Thanks to the two comments (so far). I am happy to provide a more detailed discussion but thought it appropriate to keep my original posting shortish if possible. For a little backstory, although I have been working on code related to my original posting for a while, I decided to formally submit a "gauging interest" after some emails to Barry Smith, the head of the National Center for Ontological Research, who sent me a stack of research papers with new data structures and algorithms relevant to "multiscale" analysis. This gave me a range of functions or algorithms to implement on top of those I was already working on. There's going to be a conference on biomedical ontology in about six weeks' time, so I decided to assign myself the task of completing at least part of a library in preparation for that. NCOR seems to be working on a "partition theory" which takes a top-down approach to scale. I'll base my comments on "A Theory of Granular Partitions": http://ontology.buffalo.edu/smith/articles/partitions.pdf. Partitions are defined as collections of "cells" which can be nested, including one "maximal cell". For lack of a more elegant term, suppose a collection class is called cell_set, as in template<typename CELL_Type> class cell_set; If this class is to model the theory then any instance will need a "maximal cell" or "root" in which all others are contained, which could be autogenerated with a member function. Moreover, it needs a "subcell" relation and an "insert" function which probably would take an existing cell as parent to any new cell and that would default to the root. I think a variation on this class should allow multiply parents, but for now I'll assume along with the above paper that parenthood is unique. The paper also defines a "parthood" relation and "mereological product" such that c * c' represents the set of subcells shared by two cells (which given unique parenthood must be either c or c* or null). They define two notions of summation, one of which simply groups all subcells of c + c' into a set, and another which looks for the least cell actually defined in the partition that contains all of those subcells. I could mention further structures which they define (and which could be member or namespace-scoped functions), but you get the idea. As a practical tool, this construction seems to be used as a kind of sorting machine. In the simplest case, there is one class of "target objects" which are to be fit into the set of cells (they use the term "projection" for a cell "projecting" onto one or more of those objects). So cell_set then takes two type parameters as in template<typename CELL_Type, typename TARGET_Type> class cell_set; the idea being that any cell_set instance would have a "location" function which takes a TARGET_Type value or collection and "locates" it within a cell in cell_set (defaulting to root if nothing else works). Users would have to provide a boolean "fit" function testing whether a TARGET_Type object fits into a CELL_Type object. Scale can be defined on cell_set instances by assigning the largest scale to root and stipulating that subcells are smaller-scaled than parent cells. A default implementation could assign a scale 1 to root, define "depth" as the number of parent cells between a given cell and root, assign scale 0 to the "deepest" cell, and if D is the max depth assign scale to other cells c using 1 - depth(c)/D. More nuanced implementations could consider the number of different subcells which a cell contains, with the idea that cells with more "inner structure" should be assigned larger scale. Scale can also be used to filter cell_sets into more maximal or more minimal calls, providing a kind of granular query machine. Imagine, for example, that a store is building a database for inventory, which fits into a collection of nestable categories. Scalar filtering might come into play if the store wants to temporarily "reassign" products to new categories to prevent categories being listed on their website with too few products, or conversely if the store wants to spotlight categories for some sort of promotion but only ones with no subcategories. Now, personally, I find that parent uniqueness is too restrictive and does not really fit real-world situations (for the same reasons that single inheritance is problematic...). Easing this restriction makes cell_sets more complex in a number of ways. They end up being graphs rather than trees, with parenthood one edge-type among others. I'm not saying that "partition theory" is the last word on multiscale modeling; I think another useful class would be some sort of multi_graph<CELL_Type> which shares many features with cell_set but allows multiple parents and perhaps allows the maximal cell to be undefined. This latter class would be more "bottom up". Instead of introducing new subcells as partitions of existing cells, new cells would be constructed as "mergers" of existing cells. In addition, edge types could be classified based on whether c <> c' (for some link type <>) implies that c is a subcell of c' or that c and c' are both potential subcells of some parent. These differences give rise to different kind of "walks" or constraints on walks, e.g., only follow edges to parents, or to children, or to siblings. Of course, cell_set as I described could be considered a special case of this more general multi_graph structure, but if multi_graph is to inherit cell_set's features it should support the construction of a "sort machine" for one or more target types; that is, provided a user-defined function "fitting" objects "into" vertices in the multi_graph, it should provide location functions for single or collections of objects of the proper type(s). Scalarity and granularity functions would work much as described for cell_sets, although graph-theoretic measures such vertex degree can be used to refine scale quantification for cells. I am particularly interested in using multi_graphs so defined for modeling GUIs. I've read some interesting work by RedWhale software, in Palo Alto, concerning algorithms for matching data elements to UI controls, which they call "interactors". For example, numeric data field would be mapped to spinners, list boxes, edit fields, scrollers, radio buttons, etc., based on their range of allowed values. Assume that the links between data components and interactors are represented by a multigraphs, so that for one edge type <v>, c <v> c' implies that c is a data field and c' is an interactor type which will visually represent c in a GUI. Suppose moreover that c <s> c' implies that c and c' are both interactors but c' is a higher-scales control, such as a notebook or dialog box; and that c <c> c' implies that c and c' are data components with c contained inside c'. The visual clarity of a GUI can be analyzed by studying how these three edge types interact in the graph, and any patterns which emerge could be used to refine algorithms to automatically generate GUIs based on data models. This could be extended by also introducing user-generated-events and application tasks, such as saving updated data to disk, so that c <t> c' could mean that c is a event meaning that the user wants to perform task c' (e.g., save to disk). Finally, to respond to a couple of points raised. For argument's sake, suppose I develop a single cell_graph class which incorporates both the partition and multigraph functionality I've described. (Actually I'd probably want instead to do a small group of related classes rather than one monolith, but, again, this is for argument's sake). Certainly this could be implemented in terms of existing STL containers, but the choice of which container to use is affected by how the cell_graph itself is used. As far as I can tell, for optimal memory usage cell_graph should work on values rather than pointers, but the values should never be copied, if possible, so that pointers into the cell_graph remain valid indefinitely. On the other hand, there are occcasions when it is useful to use cell_graph more as a vector than as a list. I won't go into the precise memory layout I've been using because I have not worked out all the details yet, but I think the choice of something nonstandard is justified. Conversely, even if (say) cell_graph<CELL_Type, PROJECTION_Type> is implemented in terms of standard STL containers behind the scenes, there is enough extra functionality to implement that it makes sense to develop it as a separate library. There are actually several other type parameters which I have not mentioned (although they take defaults), so using "bare" vector or set would yield very unwieldy code; better to hide as much as possible behind typedefs, partial specializations, or inhertiance: template <typename VERTEX_Type, typename CONNECTOR_Type, typename NODE_WRAP_Type, typename NODE_SERVICER_Type> void TierBlend::Route_Matrix_Compiler <VERTEX_Type, CONNECTOR_Type, NODE_WRAP_Type, NODE_SERVICER_Type>::compile(NODE_SERVICER_Type* servicer) ... Stuff like this should be library code, not user code. Finally, there is no single meaning to "scale" or "granularity". A scale metric can be induced on a partition or "partition-graph" based solely on nesting (e.g. subcells inside parent cells) but in real world situations there is no reason why "sibling" cells should have the same scale. The point is merely that classes representing these structures should provide for a scale measure associated with cells, graph vertices, and/or subgraphs, and should be a possible constraint or characterization of edge types as well (e.g. it could be stipulated that c <> c' implies c < c' for edge type <> and parthood relation <). Similarly, "granularity" could be associated with a given filter, query, or operation which specifies a range of scales on which the operation is to be performed. Thanks again for the comments. ---------------------------------------- From: "Edward Diener" <eldiener(a)tropicsoft.com> Sent: Sunday, June 05, 2011 8:18 AM To: boost(a)lists.boost.org Subject: Re: [boost] Gauging interest in new library re: multiscale/multigranular containers On 6/4/2011 4:55 PM, nathaniel(a)tierblend.org wrote: > > Hi: I would like to submit a library which would allow functionality > related to scale and granularity to be performed on STL-like containers. > Until recently I was in a doctoral program specializing in the philosophy > of science, and I am especially interested in multiscale data modeling and > its applications to e.g. GUI design, code generation, decision procedures, > and DSL implementation. For example, one of my projects involves a DSL > implemented through multiscale graphs in lieu of conventional syntax trees. > I used to study at Buffalo, which houses the National Center for > Ontological Research -- headed by the quite broad-ranging scholar Barry > Smith -- and has done pioneering work in biomedical ontology and also in > ontological models related to complex or "vague" aggregative structures. > In these structures collections of objects of some base type T can be > defined as aggregates but with varying degrees of looseness or "individual > coherence"; and this aggregation can be iterated to produce multiscaled > structures which can be queried or represented at different granularities. > There are a number of analytic procedures which can be implemented on such > structures, some overlapping with graph theoretic or statistical methods. > These structures also possess alot of internal structure above and beyond > their underlying list of values, so they are suited to memory-optimized C++ > code rather than higher-level languages like Java. However, I am not aware > of generic libraries which really incorporate these kind of data structures > and their analysis in a systematic way, although I have come across > non-template libraries which implement some similar features. What I > propose is a library which could be used in a fashion similar to > std::vector or std::set but which support additional functions along the > lines of, e.g., building multigraphs out of T-type nodes; partitions of > T-sets with functions to define or measure e.g. intrapartition relevance; > defining (or extending) a scale metric on T-objects, T-sets, T-arrays, or > other "T- data structures" and using it for rescaling, scale-filter, and > other scale-related transformations; defining iterators or "walks" on > T-collections which take scale and granularity into account; etc. In a > number of cases the algorithms for these kinds of operations have been > described in theoretical form or even already implemented in languages like > Scheme. You generally need to define "scale" and "granularity" in mathematical terms for computer programmers, else you are just interesting scientists in our particular area. Also would it not be possible to create a class which consists of an STL container and some other objects which represent "scale" and "granularity" and add the necessary functionality to that class rather than attempting to re-engineer some STL container ? _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

3 2

[review] Heaps
by Andrew Sutton 07 Jun '11

07 Jun '11

All, I'd like to announce the beginning of the review of the Heap library, written by Tim Blechmann, and resulting from Tim's 2010 Google Summer of Code project The library implements a number of different heaps (or priority queues) including, a binary heap, d-ary heap, binomial heap, fibonacci heap, pairing heap, and skew heap. The library also provides an adaptor to make heaps mutable, allowing a programmer to modify a value and update its position within the heap. The library also also supports stability, ensuring that elements pushed into a heap with the same priority are popped in the same order. The library is not targeted in any specific domain nor directly related to any specific libraries, but intended to be a collection of general purpose data structures (not unlike the Boost.Unordered library). The documentation and source code can be downloaded from here: Documentation: http://tim.klingt.org/boost_heap Code: http://tim.klingt.org/git?p=boost_heap.git;a=snapshot;h=HEAD;sf=tgz Unlike previous reviews, this review will be assisted by a code review application, Code Collaborator (by SmartBear). The product was tested during a BoostCon session, and we are eager to see how well it scales to a community review. You can use the link below to access and review the Heap library. http://demo.smartbear.com/boost/go?page=ReviewDisplay&reviewid=4 The application allows line-by-line comments of the submitted source code in addition to providing features for general defect and issue reporting. If you are interested in using this system, we will have to register you as a user of the site. You can request access by replying to this message. I'm still learning my way around the system, so there are bound to be some missteps along the way :) If you are not interested in using the system, then feel free to send email like any other review. Reviews of the library should address the following questions. What is your evaluation of the design? What is your evaluation of the implementation? What is your evaluation of the documentation? What is your evaluation of the potential usefulness of the library? Did you try to use the library? With what compiler? Did you have any problems? How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? Are you knowledgeable about the problem domain? And finally, every review should answer this question: Do you think the library should be accepted as a Boost library? Be sure to say this explicitly so that your other comments don't obscure your overall opinion. Please note that some questions may be easier to answer in email than with the review tool. As always, reviews are important to the continued quality of the Boost C++ Libraries. Thank you in advance for your comments and contributions. Andrew PS. The review was slated to start on Sunday, but I was not able to make the announcement until today.

7 38

[type_traits] is_constructible, ... when decltype is supported?
by Vicente Botet 07 Jun '11

07 Jun '11

Hi, when decltype is supported (as it is the case for gcc 4.6.0) we can define the C++0x traits is_constructible, is_assignable and the ones that depend on them. These traits are really important to conform with some of the C++11 interfaces. Next follows one examples from the standard: template (*class... UTypes*) explicit tuple(UTypes&&... u) noexcept; 8 Requires: sizeof...(Types) == sizeof...(UTypes). is_constructible(*Ti, Ui&& *)::value is true for all i. 10 Remark: This constructor shall not participate in overload resolution unless each type in UTypes is implicitly convertible to its corresponding type in Types. In Boost there are some libraries as Boost.Array, Boost.Fusion tuple that defines these kind of constructors or assignments and that require that the template types must be constructible or assignable. The problem when these constructors/assignments don't use of SFINAE to avoid that these functions participate on overload resolution is that is_constructible or is_assignable will give false positive results as the expression could be valid, even if the definition doesn't compiles. I don't know if it is worth including these traits in Boost when the compiler supports decltype so we can start writing conforming interfaces, but at least it would be nice if the Boost libraries start using these standard traits when them are available. Any thoughts? Best, Vicente -- View this message in context: http://boost.2283326.n4.nabble.com/type-traits-is-constructible-when-declty… Sent from the Boost - Dev mailing list archive at Nabble.com.

4 6

[review] Heaps: Mergeable Heaps
by Andrew Sutton 07 Jun '11

07 Jun '11

Tim, I think you should define a MergeableHeap that describes heaps that can be merged in O(log n) (i.e., binomial, fibonacci, pairing, skew). Actually, the only heaps that don't satisfy this requirement are binary heaps, b-heaps and d-ary heaps (they all seem to be linear). This is similar to the the AdjacencyMatrix in the BGL. This poses a serious problem, however. The mutable priority queue wrapper implements merge() as, at best, a linear operation, meaning that no mutable priority queue could model the MergeableHeap concept. Andrew

4 13

[Review] Boost.Convert review decision
by Edward Diener 07 Jun '11

07 Jun '11

Because Vladimir Batov has expressed himself by saying that he does not want to continue to offer his Boost.Convert library as a library for Boost, I am respecting his decision and his library is NOT accepted into Boost. I am still going to reserve the right to do an analysis of the various viewpoints and offer some way forward for the Boost.Convert library, if Vladimir Batov wishes to pursue it, or for any other library which wishes to present a convert-like interface. I will post this analysis sometime later in the week. There is also still one person who had asked me personally to do a late review by the end of Wednesday, and if that person still wants to do so I would still appreciate his input. I would like to thank Vladimir Batov for offering the library to Boost and all those who did reviews or offer comments about the library even if they did not do an actual formal review. Edward Diener

3 2

[preprocessor] [variadic] VMD_SIZE using ADD -- why?
by lcaminiti 06 Jun '11

06 Jun '11

Hello all, I am using the VMD Boost Library Under Construction to handle variadic macros. On MVSC, this library uses PP_ADD to calculate the variadic size VMD_SIZE(__VA_ARGS__). However, it does not provide a reentrant version of VMD_SIZE (like VMD_SIZE_D) which is a problem when nesting size calculations within while iterations because PP_ADD uses PP_WHILE. I think, if this implementation is kept, the library should also provide the reentrant variant VMD_SIZE_D that invokes PP_ADD_D instead of PP_ADD. #if defined(BOOST_MSVC) #define BOOST_DETAIL_PP_VMD_DETAIL_DATA_SIZE(...) \ BOOST_PP_ADD(BOOST_DETAIL_PP_VMD_DETAIL_APPLY(BOOST_DETAIL_PP_VMD_DETAIL_ARG_N, (__VA_ARGS__, BOOST_DETAIL_PP_VMD_DETAIL_RSEQ_N())),0) \ /**/ #else #define BOOST_DETAIL_PP_VMD_DETAIL_DATA_SIZE(...) \ BOOST_DETAIL_PP_VMD_DETAIL_APPLY(BOOST_DETAIL_PP_VMD_DETAIL_ARG_N, (__VA_ARGS__, BOOST_DETAIL_PP_VMD_DETAIL_RSEQ_N())) \ /**/ #endif BTW, why is PP_ADD(size, 0) used on MSVC? If this is just for forcing proper macro expansion, I think other techniques (like the ones used by PP_EXPAND) should be used so no PP_WHILE reentrancy dependency is introduced. Thanks, --Lorenzo -- View this message in context: http://boost.2283326.n4.nabble.com/boost-preprocessor-variadic-VMD-SIZE-usi… Sent from the Boost - Dev mailing list archive at Nabble.com.

2 4

[none_t] I/O operators patch
by Gregory Crosswhite 06 Jun '11

06 Jun '11

Hey everyone, Since my idea to add I/O operators for none_t has been approved by the community according to the three-week rule --- which as you all know states that any proposals that have received no feedback on the list after three weeks are therefore automatically approved by the community ;-) --- I have written a patch based on the feedback I have received to implement these operators and attached it to this e-mail. To summarize my earlier e-mail, the advantage of having these operators around is that they allow generic I/O code to be applied to data of type none_t. One decision that I made in this patch that I have mixed feelings about is that I put the operators in the boost namespace. The advantages of this approach are obvious, but the disadvantage is that this "hides" them from the user who might not realize that he or she needs to import operator>> and operator<< in order to access them (since importing qualified operators is something that is not usually done) but instead conclude they they don't exist at all. Alternatives include putting them in the global namespace and putting them in the std namespace. Any thoughts on this? Since the window for adding new features to Boost closes tomorrow, and this patch is relatively small and should be fairly innocuous, is there a chance that this or something like it could be considered for the next release? Thanks! :-) Greg

3 5

Process library with child process events
by Klaim - Joël Lamotte 06 Jun '11

06 Jun '11

Hi, On Wed, Jun 1, 2011 at 14:12, Jeff Flinn <Jeffrey.Flinn(a)gmail.com> wrote: > Gregory Crosswhite wrote: > >> Hey everyone, >> >> Since there is not yet a Boost.Process library, does anyone have a >> suggestion for a lightweight cross-platform C++ library for launching and >> monitoring (i.e. being able to tell if they die) child processes? >> > > I've put the code from the recent boostcon "boost process" presentation > that Boris Schaeling and I gave at: > > https://github.com/JeffFlinn/boost-process > > Initial documentation is at: > > > https://docs.google.com/document/pub?id=1qdpxcJB51WMuNYlKYPkPcZZGuPj7zmeUPI… > > The intent is to get this completed and ask for review this summer. The > areas needing work are: > > I've read the current (clearly incomplete w.i.p.) doc and parsed the headers and I like the design so far. However, I can't find a way to be notified if a child process did end, by getting to the end of the program or by having crashed or by having being shut down by external processes, the OS or the user. Did I miss something? If not, what is supposed to happen in the parent process if a child do get to an end (whatever the cause)? Joël Lamotte

6 11