June 2011 - Boost - lists.boost.org

Gauging interest in new library re: multiscale/multigranular containers
by nathaniel＠tierblend.org 06 Jun '11

06 Jun '11

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. I believe that this project is also well-suited to carry over into C++0x, because new features proposed there (such as Concepts, which I know keep moving in and out of the specification) have potential to make this library increasingly generic or "fine-tuneable"; for example, users should be able to specify custom allocators not only for T's but for aggregates or connectors between T's which might be recognized as part of the inner structure of a T-collection. Thanks in advance for any comments or suggestions.

3 2

none_t I/O operators
by Gregory Crosswhite 05 Jun '11

05 Jun '11

Hey everyone, I have recently run into a scenario where it was useful to have << and >> I/O operators defined for none_t. I was using Boost Program Options to create a list of program options, and I wanted one of my options to be a help message. Since this option has no value except for the side effect of printing a help message and exiting, I gave it the type none_t, i.e.: options.add_options() ( "help" ,opts::value<none_t>()->zero_tokens()->notifier(...function that prints help message...) ,"print help message and exit\n" ) When I did this, it complained that the >> operator was not defined for none_t, so I went ahead and defined my own I/O operators, which are essentially just no-ops: inline std::istream& operator>> (std::istream& in, boost::none_t& _) { return in; } inline std::ostream& operator<< (std::ostream& out, const boost::none_t& _) { return out; } It seems to me that these are the natural I/O operators to define for this type, and so it would be useful to have them be officially part of Boost. Although it is unlikely that a user would ever call them directly, their existence could prove useful in various circumstances where a generic I/O function is being applied to a none_t, such as the case I ran into/ If people were willing to accept a patch that adds these operators to Boost, then I would be willing to write such a patch. Obviously I would need to generalize the istream/ostream types to the full generic versions which include the template parameters for character traits, etc. I would also add forward declarations of istream and ostream just before these declarations so that the implementation would not need to have the <istream> and <ostream> headers as dependencies, though this would be tricky because I'd need to figure out how to detect if <istream> and/or <ostream> have not been included yet. Thoughts? Cheers, Greg

3 6

Re: [boost] [msm] need to increase the fusion set and map size to 30
by Christophe Henry 05 Jun '11

05 Jun '11

> So i added these two statements at the beginning, and this solved the > problem. > > # define FUSION_MAX_SET_SIZE 30 > # define FUSION_MAX_VECTOR_SIZE 30 > > Perhaps we can add this somewhere in the doc. Hi Kim, Maybe I should make this subject more visible. It is described here: http://www.boost.org/doc/libs/1_46_1/libs/msm/doc/HTML/ch05.html I think that FUSION_MAX_VECTOR_SIZE is actually enough, but it's only due to the fact that set is implemented in terms of vector (to be exact, as I only use fusion::set, FUSION_MAX_SET_SIZE ought to be enough, but it's not, so I suppose it's a fusion bug). Regards, Christophe

2 2

Re: [boost] [review] Heaps: size and stability
by Brent Spillner 05 Jun '11

05 Jun '11

On 6/2/2011 at 19:27, Tim Blechmann wrote: > The stability issue relates to a previous discussion from a couple > months ago (brought up by Cliff Green, > http://article.gmane.org/gmane.comp.lib.boost.devel/219330) Cliff was > concerned that the implementation of stability added overhead to the > normally unstable heaps (i.e., an extra size_t, I think) from the > implementation. I worry that the use of a policy parameter to specify > stability will result in "accidental overhead" in cases where users > don't fully understand the impact of their configuration choices. >it is not possible to write every heap algorithm as `stable' heap. i do not >recall the exact point that will break stability if one just orders the nodes in >the tree, but there was a non-trivial issue (possibly related to mutable heaps). It should be possible to preserve the correctness of most operations (certainly find, insert, delete, merge, and rebalancing) for ordinary heaps by storing items with the same key value in leftist heap order, i.e. preserving the invariants that: (1) if a subtree contains multiple items with the same key as the subtree root, the item at the root is logically first in the order (i.e., standard heap ordering); (2) if both the left and right subtrees contain items with the same key as the subtree root, all items with that key in the left subtree are logically ordered before any item having the same key in the right subtree (leftist property); and (3) if a subtree contains multiple items with a particular key value K, every item with key value K has as its parent another item with key value K, with the possible exception of the subtree root (locality/compactness property) These properties are preserved by right- or left- rotation around the subtree root. To keep the heap at minimum height, you will also occasionally need a prune-and-splice operation (items with key value K in the right subtree become children of the rightmost node with key value K in the left subtree), followed by further rotations. The compactness property should allow find, insert, and delete to continue running in O(lg n) time when rebalancing is not required. The prune-and-splice operations add O(|K|), where |K| is the total number of nodes having key value K, to the worst-case rebalancing operation, but this |K| quite reasonably ~O(lg n) when the key values are sufficiently distributed. Some merge algorithms would clearly violate the invariants above, but stable merge is still possible in O(n) time. >iac the node versioning seems to be the usual approach for implementing stable >heaps. the type of the version should be exposed to the interface, though, so >one can specify arbitrary-sized integer types to avoid overflows ... Versioning is the simplest way to adapt a non-stable heap implementation for stability, but the space overhead (and concomitant loss of flexibility in using a preexisting array to store the heap) and the risk of overflow make it unsuitable for some applications, including the quite common event queue. With a 32-bit counter value, a queue that receives and average of 100 events/second will overflow in about 16 months--- i.e. 32 bits is just enough space for your library to pass a reasonable test battery and still fail in the real world. (Of course, you need not increment the counter on every single insertion, as I just noted in the Code Collaborator review.) Another option would be chaining, where each heap node contains either a single item or a linked list of items with the same key value. This would minimize the required changes to existing algorithms, support fancier heap types and heaplike structures, and only impose some storage overhead (one or two pointers into the list, perhaps a length counter, and a means of synchronizing list access (which could be an atomic update protocol for the head/tail pointers and/or length counter)) when you actually need it, at the cost of some type erasure within the generic heap structure and possibly extra copying at runtime (when a singleton node first becomes a linked list.) On the subject of counters: On 6/2/2011 at 10:19, Tim Blechmann wrote: >will have a look ... in general boost.heap does not throw any exceptions by >itself, but of course the held type, the container or the allocator can throw Lines 231 & 232 of the review version of stable_heap.cpp are: if (counter_ == std::numeric_limits<std::size_t>::max()) BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow")); (to be fair, this does seem to be the only case in the library... but Thorsten is right that it should be clearly documented.)

3 2

[review] Heaps: mutability
by Andrew Sutton 05 Jun '11

05 Jun '11

Tim, I'm trying to figure out how I can use a mutable queue to write something like Dijkstra's SP. Here's a skeleton with the relevant parts. Queue<Vertex*, Comp> q; Map<Vertex*, Queue::handle_type> h; h[start] = q.push(start); v->distance += x; q.update(h[v]); Comp is an indirect comparison of vertex distances (u->distance < v->distance). Does the mutable heap support this application (i.e., where I'm not directly updating the value type)? It's not clear from the examples supplied with the program. I suspect that it is, but it's not clear. Andrew

3 4

Help with shared_ptr usage?
by Johnny Willemsen 03 Jun '11

03 Jun '11

Hi, I can need some help with getting similar behavior as with shared_ptr for my classes., I have used std::shared_ptr with C++0x which matches the boost support. I have two classes, Base and Derived. Now I want to give our users not directly access to these implementation classes, but to some reference to them. I have created two templates, BaseRef_T and Derived_objref (see below). In Derived_objref I need to add some additional typedefs and type definitions. I have tried first to add these typedefs to a specialization of shared_ptr<> but couldn't get a clean solution. If I now use shared_ptr I can take a shared_ptr for a Derived and assign it to a BaseRef_T. That works without problems. But how to accomplish this with my own wrapper classes. This should only be possible when the types are related to inheritance. If I have now a D that is not derived from Base than that shouldn't work. Johnny #include <memory> class Base { public: }; class Derived : public virtual Base { public: }; template <typename T> class BaseRef_T { public: BaseRef_T (std::shared_ptr <T> t) : impl_ (t) {}; BaseRef_T (T* t) : impl_ (t) {}; BaseRef_T (void) : impl_ () {}; typedef T element_type; inline T* operator-> () { return impl_.get ();} inline T* get() const { return impl_.get ();} explicit operator bool() const // never throws { return impl_ == 0 ? false : true; } void operator=(const std::nullptr_t& t) // never throws { impl_ = t; } // protected: typedef std::shared_ptr <T> shared_ptr_type; shared_ptr_type impl_; }; typedef BaseRef_T <Base> BaseRef; template <typename T> class Derived_objref : public virtual BaseRef_T <T> { public: Derived_objref () : BaseRef_T<T> () {} Derived_objref (T *s) : BaseRef_T<T> (s) {} Derived_objref (const BaseRef_T <T>& o) : BaseRef_T <T> (o) {} void operator=(const std::nullptr_t& t) { this->impl_ = t; } typedef int my_index_type; // Needed as additional typedef for Derived struct Foo {int a;}; }; typedef Derived_objref <Derived> DerivedRef; int main (int,char*[]) { std::shared_ptr<Base> bs (new Base); std::shared_ptr<Derived> ds (new Derived); std::shared_ptr<Base> cs = ds; BaseRef b (new Base); DerivedRef d(new Derived); BaseRef c = d; // <== how to get this working? return 0; }

2 1

Invitation to connect on LinkedIn
by kannan k v via LinkedIn 03 Jun '11

03 Jun '11

LinkedIn ------------ kannan k v requested to add you as a connection on LinkedIn: ------------------------------------------ Yuriy, I'd like to add you to my professional network on LinkedIn. - kannan Accept invitation from kannan k v http://www.linkedin.com/e/bv6hcz-goh9zloe-1g/uV9CsZkavY-uKU5A7C-1JbkavY-u5P… View invitation from kannan k v http://www.linkedin.com/e/bv6hcz-goh9zloe-1g/uV9CsZkavY-uKU5A7C-1JbkavY-u5P… ------------------------------------------ Why might connecting with kannan k v be a good idea? People kannan k v knows can discover your profile: Connecting to kannan k v will attract the attention of LinkedIn users. See who's been viewing your profile: http://www.linkedin.com/e/bv6hcz-goh9zloe-1g/wvp/inv18_wvmp/ -- (c) 2011, LinkedIn Corporation

3 3

parsing strings at compile-time
by Andrzej Krzemienski 03 Jun '11

03 Jun '11

Hi Everyone, This is not directly related to any of the boost libraries, but I thought people from this list may find it interesting or useful. The below are links to three posts where I tried to describe how we can parse strings at compile time and convert them to data structures, still at compile-time in C++0x with generalized constant expressions. I do not have enough time to write a library myself, but perhaps someone would be able to use such techniques for their library. I think Regular Expressions library would benefit from this technique if the compiler would be able to check the correctness of a regex. http://akrzemi1.wordpress.com/2011/05/06/compile-time-computations/ http://akrzemi1.wordpress.com/2011/05/11/parsing-strings-at-compile-time-pa… http://akrzemi1.wordpress.com/2011/05/20/parsing-strings-at-compile-time-pa… Regards, &rzej

2 1

[Proto] Expression as fusion/MPL sequence
by Joel Falcou 03 Jun '11

03 Jun '11

Seems somethign crooky on this front. Calling fusion::at_c on expression ends up in error even after including boost/proto/fusion.hpp. Same way, flatten used as a transform seems to not give me a type that can be passed to any fusion or mpl function. Looking at proto/fusion.hpp I noticed that the iterator is indeed random_access but not the view itself which as a forward_traversal tag. Even after fixing this, no dice, at_c<N>(some_proto_expr) still fails to compile.

3 3

[test] Running regression tests
by Edward Diener 02 Jun '11

02 Jun '11

Attempting to run regression tests for the 'test' library on the Boost trunk I receive as output: "..\..\..\libs\test\build\Jamfile.v2:107: in modules.load rule boost-install unknown in module Jamfile</C:/Programming/VersionControl/boost/libs/test/build>. C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:314: in load-jamfile C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:62: in project.load C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:766: in project.use C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:89: in load-used-projects C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:73: in load C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:115: in load-parent C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:464: in initialize C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:309: in load-jamfile C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:62: in load C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:115: in load-parent C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:464: in initialize C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:309: in load-jamfile C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:62: in load C:/Programming/VersionControl/boost/tools/build/v2/build\project.jam:168: in project.find C:/Programming/VersionControl/boost/tools/build/v2\build-system.jam:570: in load C:\Programming\VersionControl\boost\tools\build\v2/kernel\modules.jam:283: in import C:\Programming\VersionControl\boost\tools\build\v2\kernel\bootstrap.jam:142: in boost-build C:\Programming\VersionControl\boost\boost-build.jam:17: in module scope" All other regression tests for libraries produce no Boost Build errors. Can anybody tell me what is wrong here ?

4 4