February 2005 - Boost - lists.preview.boost.org

format lib patch
by François Dumont 23 Feb '05

23 Feb '05

Config: STLport 5.0 beta and MSVC 8 (but also reported with 7.1) It looks like this compiler has a problem with the relation between the basic_string::size_type and basic_format::size_type as soon as the library is not the native one. Here is a patch proposition that return a basic_string::size_type rather than the basic_format::size_type. I think it is quite a secure patch as the method is already using a static_cast<typename string_type::size_type> to return its result and not a simple static_cast<size_type>. Bests

2 1

[Determine interest] Deterministic/nondeterminisatic multitape Turing machine
by Alex Vinokur 23 Feb '05

23 Feb '05

Is there any interest in a library which simulates a deterministic/nondeterminisatic multitape Turing machine? Current version C++ Simulator of a Turing Machine can be downloaded at : * http://sourceforge.net/projects/turing-machine/ * http://alexvn.freeservers.com/s1/turing.html The program simulates Deterministic and Nondeterministic Multitape Turing Machine (TM). Detailed log file is generated. Resources used (input size, output size, TM-space, TM-time) are computed as well. A simulated Turing machine is defined by the set of setup files and data : * description file (optional), * number of tapes, * state file, * alphabet file, * transition file, * file(s) of input word(s). Set of simulated Turing machines is defined by a metafile. Each row of the metafile contains data related to some Turing machine. The following demo Turing machines are demonstrated with using the C++ Simulator : 1. An addition program : Deterministic, 1 tape 2. An addition program with marker : Deterministic, 1 tape 3. An addition program : Deterministic, 2 tapes 4. A multiplication program : Deterministic, 1 tape 5. An Euclid algorithm : Deterministic, 1 tape 6. Recognition of palindromes : Deterministic, 2 tapes 7. Partition problem : Nondeterministic, 3 tapes 8. Conversion unary-to-binary : Deterministic, 1 tape 9. Computing Fibonacci numbers : Deterministic, 1 tape 10. Computing Huffman codes : Deterministic, 3 tapes Log file fragments are shown below ----------------------- --- File metafile ----------------------- add.dsc 1 add.sta add.abt add.rul add1.in add2.in add3.in add4.in add5.in add6.in add7.in addm.dsc 1 addm.sta add.abt addm.rul add1.in add2.in add3.in add4.in addt.dsc 2 addt.sta addt.abt addt.rul addt1.in addt2.in mult.dsc 1 mult.sta mult.abt mult.rul mult1.in mult2.in mult3.in euclid.dsc 1 euclid.sta euclid.abt euclid.rul euclid1.in euclid2.in euclid3.in euclid4.in euclid5.in palindr.dsc 2 palindr.sta palindr.abt palindr.rul palindr1.in palindr2.in palindr3.in part.dsc 3 part.sta part.abt part.rul part1.in part2.in part3.in un2bin.dsc 1 un2bin.sta un2bin.abt un2bin.rul un2bin1.in un2bin2.in un2bin3.in fib.dsc 1 fib.sta fib.abt fib.rul fib1.in fib2.in fib3.in fib5.in fib7.in huffman.dsc 3 huffman.sta huffman.abt huffman.rul equ.in fib.in arb.in ----------------------- ========== Data selected from Metafile metafile ========== ---------- Nondeterministic Turing Machine# 1 ---------- Description file name : add.dsc Number of tapes : 1 States file name : add.sta Alphabet file name : add.abt Transitions file name : add.rul Input words files names : add1.in add2.in add3.in add4.in add5.in add6.in add7.in %%=========================================== %%=== Nondeterministic Turing Machine# 1 ==== %%======= Machine Definition : BEGIN ======== %%=========================================== ###### Nondeterministic Turing Machine Definition ###### ###### This Machine is actually Deterministic!!! ###### ====== Description ====== An addition program. The program adds two numbers. A number 'n' is represented by n 1-s. Sample : 5 is represented as 1 1 1 1 1 3 is represented as 1 1 1 Input : Two numbers separated by symbol '*' Sample : 1 1 1 1 1 * 1 1 1 Output : Resulting number without '*' Sample : 1 1 1 1 1 1 1 1 ====== States Definition ====== Initial states : q0 Halting states : qf Internal states : q1 q2 ====== Alphabet Definition ====== ------ Tape# 0 ------ Empty symbols alphabet : b Input alphabet : 1 * Internal alphabet : x ====== Transition Rules Definition ====== Rule# 0 : q0 [ * ] ---> q1 [ (1, N) ] Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] Rule# 2 : q0 [ b ] ---> q0 [ (b, R) ] Rule# 3 : q1 [ 1 ] ---> q1 [ (1, R) ] Rule# 4 : q1 [ b ] ---> q2 [ (b, L) ] Rule# 5 : q2 [ 1 ] ---> qf [ (b, L) ] %%=========================================== %%======= Machine Definition : END ======== %%=== Nondeterministic Turing Machine# 1 ==== %%=========================================== %%=========================================== %%=== Nondeterministic Turing Machine# 1 ==== %%========= Processing Input Words ========= %%============= Set# 1 : BEGIN ============== %%=========================================== ##### < Run 1.1 > Input word(s) & head start position(s) on tape(s) ##### Tape#0 : Word = 1 1 1 1 1 * 1 1 1 ; Head pos = 0 ##### < Run 1.1 > Processing ##### ----- < Run 1.1 > Initial Configuration ----- State : q0 Tape#0 : [1] 1 1 1 1 * 1 1 1 < Run 1.1 > Applied Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] ----- < Run 1.1 > Configuration#1 ----- State : q0 Tape#0 : 1 [1] 1 1 1 * 1 1 1 < Run 1.1 > Applied Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] ----- < Run 1.1 > Configuration#2 ----- State : q0 Tape#0 : 1 1 [1] 1 1 * 1 1 1 < Run 1.1 > Applied Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] ----- < Run 1.1 > Configuration#3 ----- State : q0 Tape#0 : 1 1 1 [1] 1 * 1 1 1 < Run 1.1 > Applied Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] ----- < Run 1.1 > Configuration#4 ----- State : q0 Tape#0 : 1 1 1 1 [1] * 1 1 1 < Run 1.1 > Applied Rule# 1 : q0 [ 1 ] ---> q0 [ (1, R) ] ----- < Run 1.1 > Configuration#5 ----- State : q0 Tape#0 : 1 1 1 1 1 [*] 1 1 1 < Run 1.1 > Applied Rule# 0 : q0 [ * ] ---> q1 [ (1, N) ] ----- < Run 1.1 > Configuration#6 ----- State : q1 Tape#0 : 1 1 1 1 1 [1] 1 1 1 < Run 1.1 > Applied Rule# 3 : q1 [ 1 ] ---> q1 [ (1, R) ] ----- < Run 1.1 > Configuration#7 ----- State : q1 Tape#0 : 1 1 1 1 1 1 [1] 1 1 < Run 1.1 > Applied Rule# 3 : q1 [ 1 ] ---> q1 [ (1, R) ] ----- < Run 1.1 > Configuration#8 ----- State : q1 Tape#0 : 1 1 1 1 1 1 1 [1] 1 < Run 1.1 > Applied Rule# 3 : q1 [ 1 ] ---> q1 [ (1, R) ] ----- < Run 1.1 > Configuration#9 ----- State : q1 Tape#0 : 1 1 1 1 1 1 1 1 [1] < Run 1.1 > Applied Rule# 3 : q1 [ 1 ] ---> q1 [ (1, R) ] ----- < Run 1.1 > Configuration#10 ----- State : q1 Tape#0 : 1 1 1 1 1 1 1 1 1 [b] < Run 1.1 > Applied Rule# 4 : q1 [ b ] ---> q2 [ (b, L) ] ----- < Run 1.1 > Configuration#11 ----- State : q2 Tape#0 : 1 1 1 1 1 1 1 1 [1] < Run 1.1 > Applied Rule# 5 : q2 [ 1 ] ---> qf [ (b, L) ] ----- < Run 1.1 > Configuration#12 ----- State : qf Tape#0 : 1 1 1 1 1 1 1 [1] < Run 1.1 > Success : Current state (qf) is halting one ------------------------------------------------------------- --- < DTM #1, Input #1 > Result : Input word(s) ACCEPTED --- ------------------------------------------------------------- < DTM #1, Input #1 > Resource Report ------------------------------------- < DTM #1, Input #1 > * Input size : 9 symbols < DTM #1, Input #1 > * Output size : 8 symbols < DTM #1, Input #1 > * TM-Space used : 10 cells < DTM #1, Input #1 > * TM-Time used : 12 transitions |==================| |--- Statistics ---| |... Transition ...| |------------------| | Rules : Times | |------------------| | 0 : 1 | | 1 : 5 | | 2 : 0 | | 3 : 4 | | 4 : 1 | | 5 : 1 | |------------------| | Total : 12 | |==================| %%=========================================== %%============= Set# 1 : END ============== %%========= Processing Input Words ========= %%=== Nondeterministic Turing Machine# 1 ==== %%=========================================== -- Alex Vinokur email: alex DOT vinokur AT gmail DOT com http://mathforum.org/library/view/10978.html http://sourceforge.net/users/alexvn

3 3

RE: [boost] [iterators] request for utility iterator
by Eyal Farago 23 Feb '05

23 Feb '05

you can easily achieve this using (make_)transform_iterator and boost bind: make_transform_iterator( map.begin(), boost::bind( &MAP_TYPE::value_type::first, _1 ) ) (give or take a typename before MAP_TYPE::...) I think it's so simple that you don't really need a utility class for it. I'm also quite sure that boost bind takes better care of const/mutable return type and any other bad things that you may stumble across when trying to implement this functor youself (same goes for boost.lambda). eyal. -----Original Message----- From: Thorsten Ottosen [mailto:nesotto@cs.auc.dk] Sent: Monday, February 14, 2005 4:19 AM To: boost(a)lists.boost.org Subject: [boost] [iterators] request for utility iterator Hi all, I often want to iterate over just the values of a map or perhaps just the keys of a map. Therefore I would like to see the following iterator adapters in the iterator library: template< class Map > struct map_key_iterator; template< class Map > struct map_value_iterator; template< class Map > struct map_const_value_iterator; I have outlined an implementation in the attached file, but basically it just a wrapper around transform_iterator<typename Map::iterator>. Comments? br Thorsten

4 8

typeid wrapper
by Felipe Magno de Almeida 22 Feb '05

22 Feb '05

Ive searched in boost a typeid wrapper like the one Andrei Alexandrescu uses in his book (Modern C++ Design), but didnt found any, except one in the python library. It seemed very much what Im searching, so I'm wondering why it is in the python library. I think it is a very useful feature outside python library either. So Im asking if it shouldnt be a general class in the boost library, instead of being a feature to be used by the python library only? Thanks in advance, -- Felipe Magno de Almeida UIN: 2113442 email: felipe.almeida@ic unicamp br, felipe.m.almeida@gmail com I am a C, modern C++, MFC, ODBC, Windows Services, MAPI developer from synergy, and Computer Science student from State University of Campinas(UNICAMP). To know more about: Unicamp: http://www.ic.unicamp.br Synergy: http://www.synergy.com.br current work: http://www.mintercept.com

7 7

Proposal: Library to manage processes
by Julio M. Merino Vidal 22 Feb '05

22 Feb '05

Hi everyone, a while ago, I started to write a little utility that aims to interact with multiple VCS systems. I chose C++ (and I don't regret that decision at all), so I had to create multiple classes to interact with system internals and keep the "real" application code clean from such OS-specific calls. A few days ago, I decided to switch to use Boost in that project, basically because I was interested in the Filesystem library. Doing so, I have been able to remove some of my custom classes that dealt with files and directories (and which were quite ugly). Furthermore, this change has allowed me to use many other Boost goodies. Among the classes I wrote, there are some that provide an abstraction layer to launch other (child) processes. Once the process is launched, the code can access its standard input/output/error streams by using the standard iostreams framework. I'm willing to reorganize (well, mostly rewrite from scratch) such process-management classes to follow the Boost policies, aiming for future integration in Boost. But, before I start to do so, I would like to know if such library will be adequate to be integrated and/or if there is interest in it. FWIW, I've searched the mailing lists and found some people that said that they missed this functionality in Boost. Any comments? Thanks in advance, -- Julio M. Merino Vidal <jmmv84(a)gmail.com> http://www.livejournal.com/users/jmmv/ The NetBSD Project - http://www.NetBSD.org/

12 20

Dynamic Exception Handlers [repost]
by David Abrahams 22 Feb '05

22 Feb '05

Can it really be two years ago that I talked about refactoring the mechanism in Boost.Python? http://aspn.activestate.com/ASPN/Mail/Message/boost/1537162 Well, I had to do it for a talk I'm giving, so here it is. It could easily be boost::detail-ized. Is there still interest? -- Dave Abrahams Boost Consulting www.boost-consulting.com

2 7

Preprocessor question
by Arkadiy Vertleyb 22 Feb '05

22 Feb '05

Hi, Suppose I have the following macro: #define DO(x)\ BOOST_PP_CAT(STEP3, BOOST_PP_CAT(STEP2, BOOST_PP_EXPAND(STEP1 x))) #define STEP2STEP1 Now, DO(5) should IMO expand into STEP35. For some reason, VC71 expands it into STEP3 5. Where does the space come from? Can one CAT two tokens, and get a space between them? Is it a bug in VC71 or is it supposed to be like this? If I use BOOST_PP_SEQ_CAT outside, it does what I expect. Can anybody explain why? (the above exersize may not make sence out of context. I don't think the context is relevant, although I can provide it if necessary) Thanks in advance. Regards, Arkadiy

2 6

Priority Queue in boost::graph::dijkstra_shortest_paths
by Lloyd J Lewins 21 Feb '05

21 Feb '05

Perhaps I am missing something, but I don't see how dijkstra_shortest_paths works currently. The priority queue (mutable_queue) in dijkstra_shortest_paths should order (gray) vertices by their distance from the source vertex. The ordering of the mutable_queue is achieved by the compare function, which therefore should order vertices by examining the distance map. However, the default compare function is simply std::less<D>(), where D is the value_type of the distance map. I.e., the compare simply orders the vertices by their vertex_descriptor, using less for the value_type (essentially a cast). I would think what is really needed is a less function which is bound to the distance map, and compares based off distance. For example: template<class Map> class less : public std::binary_function<typename boost::property_traits<Map>::value_type, typename boost::property_traits<Map>::value_type, bool> { typedef typename boost::property_traits<Map>::key_type key_type; typedef typename boost::property_traits<Map>::value_type value_type; public: explicit less(Map& m) : m(m) { } bool operator() (const key_type k1, const key_type k2) const { return m[k1] < m[k2]; } private: const Map& m; }; In which case the compare function would be somethink like: less<DistanceMap>(distance). Lloyd J. Lewins Fellow, Raytheon Co., llewins(a)raytheon.com +1 (310) 647-8832

2 1

Apple GCC conditional in boost.python ??
by Marshall Clow 21 Feb '05

21 Feb '05

In boost/libs/python/src/converter/registry.cpp, I found: >#if defined(__APPLE__) && defined(__MACH__) && defined(__GNUC__) \ > && __GNUC__ == 3 && __GNUC_MINOR__ <= 4 && !defined(__APPLE_CC__) ># define BOOST_PYTHON_CONVERTER_REGISTRY_APPLE_MACH_WORKAROUND >#endif I have no idea what defining that big long symbol does, but I think that the conditionals are incorrect. <http://developer.apple.com/technotes/tn2002/tn2071.html> says: __APPLE__ This macro is defined in any Apple computer. __MACH__ This macro is defined if Mach system calls are supported. __APPLE_CC__ This macro is set to an integer that represents the version number of the compiler. This lets you distinguish, for example, between compilers based on the same version of GCC, but with different bug fixes or features. Larger values denote later compilers. I can't see any case where __APPLE__ and __GNUC__ are defined, and __APPLE_CC__ is not defined. Metrowerks? ==> No __GNUC__ Not on a Mac? ==> No __APPLE__ __APPLE_CC__ was defined for Apple-released versions of GCC, starting with 2.95.2 (so says Chris Espinosa at Apple). More historical info is at <http://developer.apple.com/releasenotes/DeveloperTools/GCC2.html> So, I think that that whole #if expression always evaluates to "false". -- -- Marshall Marshall Clow Idio Software <mailto:marshall@idio.com> It is by caffeine alone I set my mind in motion. It is by the beans of Java that thoughts acquire speed, the hands acquire shaking, the shaking becomes a warning. It is by caffeine alone I set my mind in motion.

2 2

[boost::signals] connect/disconnect management suggestion
by kolach56＠yandex.ru 21 Feb '05

21 Feb '05

I used boost::signals in number of projects and found one thing inconvenient. I could easily connect anything to signal but sometimes it became hard to disconnect form it. It's ok if a connection time is bounded by a lifetime of trackable or connection objects. I used to use Group id for disconnection, but sometimes I needed it for call priority. ( In that case I would write a special GroupCompare function but it looked ugly. ) For experimental purposes, I constructed an alternative approach. For connection/disconnection management I used the following syntax: struct Test { void test( bool, int ); }; void f( bool ); signal<void (bool)> s; s.connect( &Test::test, t, _1, 5 ); s.disconnect( &Test::test, t, _1, 5 ); s.connect( &f, _1 ); s.disconnect( &f, _1 ); I just form a hash code from the arguments. It certainly makes the process longer, but in most cases I don't need something extremely fast there. In my projects, the performance is important in invocation process. It's only a variant, there might be a lot of other ways. So actually my suggestion is why not to have both approaches of connection/disconnection management? One for fast connection/disconnection and the other for extra control over it. -- Best regards, Nick mailto:kolach56@yandex.ru

1 0