- Boost - lists.boost.org

Augmented trees
by Phil Endecott 12 Oct '12

12 Oct '12

Dear Experts, I find myself in need of an augmented tree. My problem is something like [but not exactly] this: - Say I have a line of text, i.e. a sequence of characters, in a variable-width font; each character stores its width in pixels. - I need to efficiently insert and remove characters. - I need to efficiently find the range of characters that spans a given range of pixels. It seems to me that an augmented tree lets me do all of those operations in log(N) time - and no other data structure offers the same performance. I'm aware of two augmented trees that have been proposed here. Francisco Jose Tapia has proposed "Countertree", but this only stores the count of elements not the sum of a property of the elements (i.e. the widths in my example). Vadim Stadnik has proposed stl_ext_adv, which is a doubly-augmented B+ tree. Has anyone looked at Vadim's code since it was proposed last year? I have a couple of concerns about Vadim's proposal: 1. It uses B+ trees, and in the discussion it was suggested that these are inferior to red-black trees in some way. 2. In order to get the property to be accumulated (i.e. the widths in my case) it requires that arithmetic can be done on the stored type itself; this is fine for e.g. a sequence of ints, but if the stored type is a struct it is necessary to add various "unnatural" operator overloads. I think I would prefer it to have some sort of user-supplied accessor to get the property to be accumulated. Is there any other work that I've overlooked? Is there a "friendly" red-black tree implementation somewhere that could be augmented relatively easily? Regards, Phil.

8 9

[1.52.0] Beta1 release available
by Daniel James 11 Oct '12

11 Oct '12

Boost release 1.52.0 beta 1 is now available from SourceForge See https://sourceforge.net/projects/boost/files/boost/1.52.0.beta.1/ This release contains numerous enhancements and bug fixes for existing libraries. For details of what's in the release, see http://www.boost.org/users/history/version_1_52_0.html. Please download the beta, give it a try, and report any problems you encounter. Thanks, -- The Boost Release Team

4 8

[thread] call_once doesn't call even once
by Kim Barrett 11 Oct '12

11 Oct '12

In boost 1.52.0 beta1 In boost/thread/pthread/once.hpp, near the head of the file, is the following conditional snippet: #ifdef SIG_ATOMIC_MAX typedef sig_atomic_t uintmax_atomic_t; ... #else ... #endif Well, sig_atomic_t may be a signed type, and in fact on the Linux system I'm testing on it is a typedef for int [suse12.1, but I suspect it doesn't really matter.] POSIX says "Possibly volatile-qualified integer type ...". This led to boost::call_once never calling the function, because there is a comparison in call_once (epoch<this_thread_epoch) where I'm seeing values of 0 and -2 respectively for those variables, that doesn't go in the expected direction when uintmax_atomic_t is a signed type rather than the expected unsigned type. I bet there are other places that get confused by this being an unexpectedly signed type. I'm working around this to continue my testing of 1.52beta1 by commenting out the offending conditional code and just using the code in the #else clause. The relevant code is new code, introduced since boost 1.51. This is a serious regression that should be a blocker for the 1.52 release. I've filed a bug for this: https://svn.boost.org/trac/boost/ticket/7499

2 1

[coroutine] new versions
by Oliver Kowalke 11 Oct '12

11 Oct '12

I've uploaded two re-factored versions - I think most of the suggestions from the review are implemented (namespace is not corrected and documentation not updated yet). 1.) http://ok73.ok.funpic.de/boost-coroutine-self.zip 2.) http://ok73.ok.funpic.de/boost-coroutine-coro.zip Version 1) requires that coroutine-fn has only one argument == coroutine<>::self_t. Other arguments are accessed via coroutine<>::self_t::get< int >() and results via coroutine<>::get(). interface provides input/output iterators. typedef coroutine< int( int, int> > coro_t; int fn( coro_t::self_t & c) { int x = c.get< 0 >(); int y = c.get< 1 >(); c.yield( x +y); ... } coro_t coro( fn); int res = c( 3, 7).get(); Version 2) requires that coroutine-fn has only one argument too == coroutine<> with inverted signature. Other arguments are access via coroutine<>::get(). interface provides input/output iterators. typedef coroutine< int( int, int> > coro_t; int fn( coroutine< tuple< int, int >( int) & c) { int x = c.get().get< 0 >(); int y = c.get().get< 1 >(); c( x +y); ... } coro_t coro( fn); int res = c( 3, 7).get(); Both implementations are not optimized - I think we should get a small and clean interface first. Comments? regards, Oliver

5 19

[preprocessor] Variadics suggestion
by Kitten, Nicholas 11 Oct '12

11 Oct '12

Hi Folks, First of all, I'd like to say "thank you" to Edward Diener and Paul Mensonides for incorporating variadics support into Boost.Preprocessor, which has been on my wishlist for a long time. In fact, I wanted it badly enough that I've been using my own slightly modified version of the library assuming variadics for a while now, and I was interested to see what a cross-platform version would look like (mine was only tested on MSVC). I think the chosen approach of converting variadics to non-variadics is probably superior to the breaking algorithm changes I made in my own version, and I would humbly suggest a few more additions in the same spirit. The reason I chose to use variadics in the first place was to simplify the user interface for the common case of manipulating what I'll call a "variadic sequence," (a series of concatenated tuples), which I wanted to look similar to the following: #define FILTER_PARAMETERS (A, int, 3)\ (B, float, 2.0f)\ (C, const char*, "Howdy!") Of course, without variadics you need either a set of macros for each tuple size, or else double parenthesis around each tuple, which becomes even more burdensome when users are also required to parenthesize inner arguments, leading to gems like this one: #define FILTER_PARAMETERS ((A, (TypeConverter<double, float>), (TypeConverter<double,float>())) My solution admitting the preferred format was to replace most private SEQ_*(X) macros with SEQ_*(...), which also required modifying SEQ_ELEM() and SEQ_HEAD() to return (X) instead of X. However, it occurs to me now that a conversion function to go from variadic to regular sequences would've been easier to implement and backwards compatible; see the attached file, which I've tested in basic cases on MSVC 10 and gcc-4.3.4. The usage would be: #define SEQ (a,b,c)(1,2,3,4) BOOST_PP_VARIADIC_SEQ_TO_SEQ( SEQ ) // expands to ((a,b,c))((1,2,3,4)) I'm submitting this because I couldn't find a way to use some combination of TUPLE/VARIADICS and SEQ transformations to do the same thing succinctly, but if I'm just missing something, please let me know. Next, I would suggest having a documented IS_EMPTY(...) function for detecting an empty variadic list. Since is_empty.hpp already exists for single arguments (though undocumented), I would guess the variadic version would look quite similar. My own (MSVC) version is attached. Finally, I would suggest using the preceding IS_EMPTY(...) function to allow VARIADIC_SIZE(...) to return 0, i.e. something along the lines of: # define BOOST_PP_VARIADIC_SIZE(...) BOOST_PP_IIF( BOOST_PP_IS_EMPTY(__VA_ARGS__), 0, BOOST_PP_VARIADIC_SIZE_I( __VA_ARGS__ ) ) where BOOST_PP_VARIADIC_SIZE_I is the current definition of BOOST_PP_VARIADIC_SIZE. Thanks, -Nick Kitten Software Engineer Center for Video Understanding Excellence ObjectVideo, Inc.

9 29

[GIL] interleaved_ptr as part of API?
by Mateusz Loskot 11 Oct '12

11 Oct '12

Hi, I wonder, why the definitions of interleaved_ptr [1] and and interleaved_ref [2] are provided as examples, instead of included as part of the Boost.GIL API? IMO, these make useful general-purpose utility and it could be easily copied into <boost/gil/utilities.hpp>, couldn't it? Or, into official set of Boost.GIL extensions, at least. [1] http://www.boost.org/doc/libs/release/libs/gil/example/interleaved_ptr.hpp [2] http://www.boost.org/doc/libs/release/libs/gil/example/interleaved_ref.hpp Best regards, -- Mateusz Loskot, http://mateusz.loskot.net

2 3

[GIL] interleaved_ptr not advances correctly
by Mateusz Loskot 11 Oct '12

11 Oct '12

Hi, Recently, I suggested [1] to include interleaved_ptr as part of Boost.GIL API. Unfortunately, I have been experienced problems while using interleaved_ptr. I posted Christian with a small code example and brief testing suggests interleaved_ptr does not advance correctly, what leads to images corruption. I assumed using interleaved_ptr would be a nice way to avoid reinterpret_cast when attaching raw bytes buffer into image views. Despite the cast is perfectly fine, it potentially raises red alert questions (not uncommon already, here or on StackOverflow). The simple test is to iterate over pixels and rewrite from input array (vector bitmap) to output array (vector bitmapOut) using views created in two ways: 1) cast to pixel type pointer 2) using interleaved_ptr Here are two images of what I get generated into bitmapOut array: Case 1) gives correct output http://www.flickr.com/photos/mloskot/8074130396/ Case 2) gives incorrect output http://www.flickr.com/photos/mloskot/8074130218/ Here is code [2] of the sample test: (there is no load_image() provided as it would bloat the example with too specific details) /// BEGIN /////////////////////////////////////////////////////////////////////////////////////////////////// // How to use Boost.GIL views attached to bytes array with interleaved_ptr, // versus view constructed with cast to pixel type ////////////////////////////////////////////////////////////////////////////////////////////////////// std::size_t w = 512; std::size_t h = 256; std::size_t sizeRow = 1536; // 24 bits per pixel, Windows DIB std::size_t sizeImage = sizeRow * h; std::vector<unsigned char> bitmap(sizeImage); std::vector<unsigned char> bitmapOut(sizeImage); // here bitmap is filled with data (e.g. read from file, generated in memory, etc.) // bitmap = load_image() // 1) //////////////////////////////////////////////////////////////////////////////////////////////// auto src = boost::gil::interleaved_view(w, h, reinterpret_cast<boost::gil::rgb8_pixel_t const*>(&bitmap[0]), sizeRow); auto dst = boost::gil::interleaved_view(w, h, reinterpret_cast<boost::gil::rgb8_pixel_t*>(&bitmapOut[0]), sizeRow); assert( !boost::gil::equal_pixels(src, dst) ); // loop taken from boost::gil::transform_pixels for (std::ptrdiff_t y=0; y<src.height(); ++y) { auto srcIt=src.row_begin(y); auto dstIt=dst.row_begin(y); for (std::ptrdiff_t x=0; x<src.width(); ++x) { // Simple rgb8_pixel_t to rgb8_pixel_t assignment dstIt[x] = srcIt[x]; } } assert( boost::gil::equal_pixels(src, dst) ); // 2) //////////////////////////////////////////////////////////////////////////////////////////////// typedef interleaved_ptr<unsigned char*, rgb_layout_t> rgb8_interleaved_ptr; typedef interleaved_ptr<const unsigned char*, rgb_layout_t> rgb8c_interleaved_ptr auto src = boost::gil::interleaved_view(w, h, gil::rgb8c_interleaved_ptr(&bitmap[0]), sizeRow); auto dst = boost::gil::interleaved_view(w, h, gil::rgb8_interleaved_ptr(&bitmapOut[0]), sizeRow); assert( !boost::gil::equal_pixels(src, dst) ); // loop taken from boost::gil::transform_pixels for (std::ptrdiff_t y=0; y<src.height(); ++y) { auto srcIt=src.row_begin(y); auto dstIt=dst.row_begin(y); for (std::ptrdiff_t x=0; x<src.width(); ++x) { // Interleaved_ref points to first channel of current pixel, right? // Is this access and assignment of colour components incorrect? dstIt[x][0] = srcIt[x][0]; // R dstIt[x][1] = srcIt[x][1]; // G dstIt[x][2] = srcIt[x][2]; // B } } assert( boost::gil::equal_pixels(src, dst) ); // This assertion fails! // 1/2 to 1/3 of bitmapOut is black (pixels with value 0) /// END ////////////////////////////////////////////////////////////////////////////////////////////////////// Perhaps the access to pixels and colour components should be realised with srcIt[x * num_channels]; My e-mail is not a request for help, in fact, but a kind of bug report or warning. Because the interleaved_ptr is not part of Boost.GIL but provided as an example, I don't think it's worth a ticket on Trac. I just thought it may be worth to archive this issue in the list and make the interleaved_ptr authors and other users aware of the problem. [1] http://lists.boost.org/Archives/boost/2012/10/197199.php [2] https://gist.github.com/3866213 Best regards, -- Mateusz Loskot, http://mateusz.loskot.net

1 0

[Windows 8 Apps]
by Johannes Sartisohn 11 Oct '12

11 Oct '12

Hello everyone, I've searched the boost website and the mailing list archives back to january and didn't find any helpful information on my subject. My question is whether there are plans to support compiling the boost library for Windows 8 using only the WinRT APIs. That is, to support boost for Windows Store/Metro Style apps in Windows 8. Or is there already a way (e.g. via preprocessor direcitve) that I didn't find, to disable the unsupported Win32 API calls when compiling on Windows? Cheers Johannes

3 3

[build] Boost Build v2 documentation refer to "bjam"
by Klaim - Joël Lamotte 11 Oct '12

11 Oct '12

Hi, http://www.boost.org/boost-build2/doc/html/bbv2/overview/invocation.html I suppose this doc have not been updated in a long time? It still use "bjam" instead of "b2". Joel Lamotte

3 3

[boost-python, boost-build] building "hello" boost-python tutorial sample with python 3.2 on Archlinux
by Roland Puntaier 10 Oct '12

10 Oct '12

Hello! Today I have tried boost-python tutorial with Arch Linux and Python3.2. In case somebody else tries this, here are the problems that I've encounter: - I've created ~/user-config.jam with this line using python : 3.2 : /usr/bin/python ; - the current boost-build of arch is 2.0_m12-3 This still uses "print" without "(" in boost-build/tools/python.jam The nightly build of boost-build has it corrected: local full-cmd = $(python-cmd)" -c \"from sys import *; print('"$(format:J=\\n)"' % ("$(exprs:J=,)"))\"" ; - Arch has python3.2 includes in /usr/include/python3.2mu (I wonder why!) This is not detected by b2 / bjam. I worked around this by changing boost-build/tools/python.jam: includes ?= $(prefix)/include/python$(version)mu ; - the sample jamroot file in the tutorial http://www.boost.org/doc/libs/1_51_0/libs/python/example/tutorial/Jamroot assumes a boost root folder. Since boost include and lib are separate with the arch boost installation, I've commented out "use-project". Then I had to give a direct reference to libboost_python3.so. diff -u Jamroot.org Jamroot =========================== --- Jamroot.org 2012-10-10 22:21:32.928426203 +0200 +++ Jamroot 2012-10-10 22:23:15.318762363 +0200 @@ -13,14 +13,13 @@ # Specify the path to the Boost project. If you move this project, # adjust this path to refer to the Boost root directory. -use-project boost - : ../../../.. ; +#use-project boost : ../../../.. ; # Set up the project-wide requirements that everything uses the # boost_python library from the project whose global ID is # /boost/python. project - : requirements <library>/boost/python//boost_python ; + : requirements <library>/usr/lib/libboost_python3.so ; # Declare the three extension modules. You can specify multiple # source files after the colon separated by spaces. It would be great to have comments pointing to the right solution for python 3.2 and an installed boost directly in the tutorial's sample jamroot file. - Roland

1 0