April 2004 - Boost - lists.boost.org

Re: C++ subranges
by Brian Martin 05 Apr '04

05 Apr '04

Brian Martin wrote: >I'll have another think about some of the compile time check issues. I have and have done the following: 1) Compile time checks would be nice but are basically impossible. At least the ones that count. Such as: subrange<int, 1, 20> sub_20(30); or sub_20 = 300; Pascal traps this kind of thing but C++ can't, as far as I can see. Runtime only, I'm afraid. I am of the opinion that the compile time checks that were given in Maciej's example code are of limited use since the real benefit of subranges is runtime (in my humble opinion). In the example code, it was possible to assign/copy different subrange types, provided the source had a range inside the destination. For now, my subrange doesn't allow different subrange types to mix. 2) Agonised over whether or not to remove the typename T (I call it a "base type" a la Pascal terminology) from the template. In my previous post I said that it allows any type to be stored in the subrange, forgetting of course that you can't have doubles, classes and C strings as non-type template parameters. Doh! Actually, this is what I want since subranges of classes is a bit odd. Floating point subranges would have been nice, but Pascal doesn't allow them either. There is a way of doing it, but it messes up the syntax. I've kept the base type because you waste storage if you're storing anything smaller than a long. There's no class overhead (on my compiler) so this doesn't make the wastage trivial. The waste is ok if you're only using a few subranges but in one project I'm storing potentially large numbers of subranges (of shorts) in STL containers and then reading/writing them in binary from/to files. Didn't like the files being 2 times bigger than they should be. So, reluctantly, I've kept the base type. 3) I've used a conversion operator. I usually avoid these but in this case it integrates subranges nicely into the type system so that built in types and subranges can mix freely in expressions. The template is, after all, supposed to be a (restricted) integral type. 4) Removed operator~(). It always fails since the value gets its upper bits set to 1 which will exceed the subrange unless you've set the upper limit to the maximum the type can store. There are obvious problems with signed types too. 6) Have attached some code - the subrange class itself and a test program for anyone who wants to give it a go.

3 2

Re:Re: [boost] Serialization: versioning and XML.
by Robert Ramey 05 Apr '04

05 Apr '04

Anatoli Tubman wrote: >Robert Ramey wrote: >> I briefly considered this approach. I imagined that upon archive >> creation the XML input could be parsed into a node tree. (insert plug >> for spirit >> here) The load_override function would be altered to search the >> correct part of the tree. So this would work and be pretty clean. >> I'm sure other approaches such as using SAX or DOM to parse the tree would work as well. >> Maybe there's another way I never thought of. >> >> The main reason I rejected the idea was that I didn't see it working >> with arbitrarily size streams. I envision serialization being used with stream >> much larger then available memory. This suggested to me an "on the fly" >> loader rather than a "pre-loaded". >Loading the entire archive is not necessary. The other approach is to >acquire a *description* of the data structure being deserialized, and >process the XML stream sequentially. That is, operator<< does not do >deserialization by itself, but inserts a member *descriptor* into a map. >When all data members are collected in this fashion, they are deserialized >as corresponding tags come in. >IOW one needs random access to *either* the data stream *or* to the data >structure being deserialized. Data streams are too big, so we should choose >data structures instead. >One doesn't need the entire tree of data structures either, only the node >currently being processed, because descendants changing parent nodes are >not supported. I don't see how to do this while keeping archive and serialization descriptions independent. >This works because a typical class is much smaller than a typical data >stream, which usually contains many instances of the same class. >I have some experience with one (pre-XML, pre-C++) serialization library >that does (approximately) just that. It uses a custom tagged format, but >there's no reason why it shouldn't work with XML and C++. My focus was finding the most expedient and efficient way to use XML format with the rest of the serialization library. In the course of investigating my options, I had occasion to look more deeply into XML. One thing that occurred to me was the possibility of making an archive implementation which generated an XML schema rather than the XML data. This would generate and XML data schema either in parallel with the XML data archive or as a separate operation. An XML tagged input implementation might make use this as well. I would guess others might find a use for such a schema that would automatically be in sync with the program code that generated the data. Robert Ramey

2 1

Re: Re: [BGL] forced client complexity
by Johnny Yune 05 Apr '04

05 Apr '04

"Vladimir Prus" <ghost(a)cs.msu.su> wrote: > Hi, > (btw, if possible, it would be nice to > know your real name, so that I could > write "Hi <your real name>") Ah, excuse me. It would please me for you to call me Johnny Yune. <snip> > In fact, something like > > typedef graph<City, Road> Road_map; > > looks quite reasonable to me. > > > If the node's "index" is > > related to the object, why would it not be a natural > > member of the node-type's class? > > I don't think "index" should be type of 'City' class. Nor does it seem a logical candidate for a member. In fact, as a client, you shouldn�t and needn�t know anything about it. > > If, instead, it is a > > synthesized construct for communication between a > > graph and the algorithm operating over it, why should > > the client be responsible for its maintenance instead > > of the framework? What are the advantages of this > > approach? What are the disadvantages of simplifying > > things for the client? This is the type of design > > issue that I intended to question with my initial > > post. > > I think the biggest problem is: It seems like you�re looking at this from the framework side instead of the client side. That�s fine, but it still isn�t clear to me why adding another layer of abstraction should affect the internal workings so heavily. I�ll try to address your questions with respect to how I would probably do it, though. >how do you identify vertices? If you use > "City&" you'd have some problems: > > 1. How vertices are really identified? Using operator==? Really identified by whom and for what purpose? >Is it possible to > insert two 'City' objects which are equal? I think that should probably depend on the underlying graph type. > If not, how to insure uniqueness? I guess you would want to make sure to not insert duplicate vertices. > Do we really want 0(log n) lookup on each 'add_vertex'. Huh? I admit to not being intimate with BGL�s internals, but it seems like a hashed set of Cities to indexes or whatever the underlying graph structure wants to use to identify nodes would be reasonable and speedy. > > 2. Even if 'City' objects in a graph are unique, how will add_edge be > implemented? Do you need O(log n) lookup to find internal adjacency >lists? Again, using a City as a node-type shouldn�t affect the runtime. If you can think of a way to define a vertex that allows o(1) lookup, I can probably give you a city->your_vertex_type hashmap that allows you to maintain that speed. > > 3. What's edge, and how it is identified? I would leave that up to the underlying container. You�ll notice that in my original post, my scratchy pseudocode declared a graph as g<vertex_type, edge_context_type>. I kind of imagined edge_context as being some sort of arbitrary meta-data about the link, generally useful only to the client. Maybe the edge context could be a simple member of the graph-managed property map? >For example, 'Road' might not > contain source/target vertices, but still we need to be able to find > source/target vertices. The whole point of the abstraction is to free the client from trying to figure out how to fit cities into roads. The underlying container could certainly keep a mapping from one to another. > > One possible solution that I see is the make > vertex_descriptor be always > pointer type. It will point at some > internal structure but also provide > operator* which will return 'City'. Would that simplify things for the client? >Or, maybe, it should be possible to > iterate over values of 'City', not only over values of >vertex_descriptor. Iterating over cities sounds absolutely reasonable to me. Much more so than iterating over some arbitrary vertex_descriptors, even. > > I still don't know if using City to identifiy vertices is feasible. I have no reason to think otherwise and I do think it sounds simpler from a client-side perspective. Food for thought. Thanks, prs __________________________________ Do you Yahoo!? Yahoo! Small Business $15K Web Design Giveaway http://promotions.yahoo.com/design_giveaway/

2 1

Spirit skip parser questions.
by Jia Pu 05 Apr '04

05 Apr '04

I am trying to write a parser which skipps white space and C, Java style comments. To get familiar with spirit, I did some experiments, here is a question. First, I write a simple grammar to accept some non-white space chars. //////////////////////////////////////////////////////////////////////////////// struct FOO_GRAMMAR : public grammar<FOO_GRAMMAR> { template <typename ScannerT> struct definition { typedef rule<ScannerT> rule_t; definition(ABNF_GRAMMAR const & self) { r_LETTER = range_p('a','z') | range_p('A','Z') | '.'; r = (+r_LETTER); } rule_t r, r_LETTER; rule_t const& start() const { return r; } }; }; //////////////////////////////////////////////////////////////////////////////// I used FOO_GRAMMAR with space_p as skip parser: ////////////////////////////////////////////////////////////////////////////// FOO_GRAMMAR g; std::string line = "This is a test parser."; parse_info<> info = parse(line.begin(),line.end(), g, space_p); //////////////////////////////////////////////////////////////////////////////// This works perfectly. Then, I tried to wrap the skip parser in a skip grammar, since eventually I need a more complicated parser. So I wrote the skip grammar as: /////////////////////////////////////////////////////////////////////////////// struct SKIP_GRAMMAR : public grammar<SKIP_GRAMMAR> { template <typename ScannerT> struct definition { typedef rule<ScannerT> rule_t; definition(SKIP_GRAMMAR const & self) { rule_t r_SKIP = space_p; } rule_t r_SKIP; rule_t const& start() const { return r_SKIP; } }; }; ///////////////////////////////////////////////////////////////////////// I tried to parse the same sentence as before: /////////////////////////////////////////////////////////////////////////// FOO_GRAMMAR g; SKIP_GRAMMAR skip; std::string line = "This is a test parser."; parse_info<> info = parse(line.begin(),line.end(), g, skip); ////////////////////////////////////////////////////////////////////////// This time the parsing failed. Can anyone tell me why? I thought grammars are just like rules. And any suggestion on building a parser skipping certain pattern? I just can figure it out by reading the doc. Thank you. _________________________________________________________________ Persistent heartburn? Check out Digestive Health & Wellness for information and advice. http://gerd.msn.com/default.asp

2 1

lexical_cast<wstring>(string)
by Jared McIntyre 05 Apr '04

05 Apr '04

Some time ago I read a discussion about possibly adding the ability to perform a lexical_cast of a regular to a wide string, and vice-versa. There was also discussion of possibly adding similar functionality to string_algo (though I tend to like the lexical_cast better for this). Has anyone looked more deeply into solving this problem? I've found these operations to be extremely common in my work on applications that are written in unicode, but may have to talk with non-unicode network protocols, libraries, etc. Jared

1 0

Review Result: Indexed Set
by Pavel Vozenilek 05 Apr '04

05 Apr '04

Indexed set library by Joaquín Mª López Muñoz has been accepted into Boost. Thanks Joaquín for innovative and professional work and for keeping up during moments when feedback was rather low. Review of the library was very positive. Thanks to all people who spent time contributing. Several points to improve had been identified during review. Consistent names for the library were discussed and hopefully identified. Some points Joaquín did or plans to address: _________________________________________ FUNCTIONAL REQUESTS 1. Issue BOOST_STATIC_ERROR if duplicate tags. This I've already done in my local version. Works OK. 2. Extend operator== and familiy to support indices over elements of different types (Gary Powell). I've done it in my local version, no problems arose. 3. Improve efficiency of equal_range (Arkadiy). 4. Include bimap in the roadmap. 5. Include ranked indices in the roadmap. 6. Include serialization support in the roadmap (it's already there.) 8. compose_key and lex_compare promoted to the library (they are implemented in examples now.) No problem from my part. 9. Include a concepts section for multi-indexed containers. David accepted that this be delayed. STYLISTIC REQUESTS 1. Navigation bar in the docs. 2. Limit source code to 80 chars per row (already done.) 3. Limit source code in the docs to 80 chars per row. 4. Rename "far pointer" to "chained pointer". I don't like this. 5. Other stylistic improvements that I've already applied. As for header organization, I'll move to a fine-grained policy. _________________________________________ New features and usage techniques are identified and will likely be implemented and documented. Care is taken keep the library easy to use. /Pavel PS: could someone try to run test "test_all_main.cpp" with VC 6.5 or 6.6. and report result exit code, please?

1 0

boost/graph/push_relabel_max_flow::is_flow() bug?
by Arun Bhalla 04 Apr '04

04 Apr '04

Hi, I'm not really a user of Boost, but I've been referring to the Boost Graph Library code for another project. In particular, I've been looking at push_relabel_max_flow.hpp. I was writing a unit test which followed the same ideas of the is_flow() test, and it was failing on what should be a flow network with a valid maximum flow. The code in question: // a is an edge_descriptor if (capacity[a] > 0) if ((residual_capacity[a] + residual_capacity[reverse_edge[a]] != capacity[a]) || (residual_capacity[a] < 0) || (residual_capacity[reverse_edge[a]] < 0)) return false; I contend the test should actually be: // a is an edge_descriptor if (capacity[a] > 0) if ((residual_capacity[a] + residual_capacity[reverse_edge[a]] ! != capacity[a] + capacity[reverse_edge[a]]) || (residual_capacity[a] < 0) || (residual_capacity[reverse_edge[a]] < 0)) return false; I refer to an example network in CLR (1st ed.), p.589. There are several vertices, but I focus on vertices v1 and v2. In this graph, we have capacities c(v1,v2) = 10 c(v2,v1) = 4 and residual capacities cf(v1,v2) = 11 cf(v2,v1) = 3 With the above (original) test, it would fail because 11 + 3 (the sum of residual capacities) != the capacity of either edge. This would hold true if the sum of residual capacities were compared with the sum of capacities. Ordinarily this test would work if reverse_edge[a] has a capacity of 0, which would be the case if the edge (a) is in the flow network, but its reverse is not. I'm not a graph theory expert, though, so I defer to anyone who is. :) Thanks, Arun

2 1

License oddity
by David Abrahams 04 Apr '04

04 Apr '04

I just noticed something strange about the license. It seems to require that derivative works and copies don't use the "by reference" technique we're using to refer to the license in our own sources: The copyright notices in the Software and this entire statement, including the above license grant, this restriction and the following disclaimer, must be included in all copies of the Software, in whole or in part, and all derivative works of the Software... I'm beginning to wonder if the current "by reference" technique is really compatible with the license. Will the intrigue never end? -- Dave Abrahams Boost Consulting www.boost-consulting.com

2 2

Re:Re: [boost] Serialization: versioning and XML.
by Robert Ramey 04 Apr '04

04 Apr '04

Anatoli Tubman wrote: >It absolutely certainly will be a new archive class. Sorry if it wasn't >clear from the start. >I just think such an archive/serialization library is (a) useful enough >to bea part of boost and (b) similar enough to the existing boost >library to share the namespace with it. I've got no problem with this. >I understand fully that this idea works only with tagged formats (not >necessary just XML), that's why I'm saying that it should probably >use a different syntax or maybe a sub-namespace under boost::serialization. Within the boost::archive namespace I've got things like: basic_xml_iarchive xml_iarchive xml_wiarchive etc. I would think there is plenty of room for something like: basic_tagged_iarchive basic_tagged_xml_iarchive tagged_xml_iarchive tagged_xml_wiarchive etc. >I'm staying within program-structure-drives-data-format school of >thought. As long as you can stick with this, I think you can be successful. I briefly considered this approach. I imagined that upon archive creation the XML input could be parsed into a node tree. (insert plug for spirit here) The load_override function would be altered to search the correct part of the tree. So this would work and be pretty clean. I'm sure other approaches such as using SAX or DOM to parse the tree would work as well. Maybe there's another way I never thought of. The main reason I rejected the idea was that I didn't see it working with arbitrarily size streams. I envision serialization being used with stream much larger then available memory. This suggested to me an "on the fly" loader rather than a "pre-loaded". My implementation does require that tags remain in sequence and are all anticipated. Your proposal wouldn't have this restriction and might be preferred in certain applications. So I'm happy to encourage your efforts. I also hope that other users will be inspired to address more particular needs by creating their own archives class variations. In the long run, I'm trying to get out of the archive creation business in the same way I'm trying to get out of the class serialization business. >I don't precisely understand how going in the other direction >is ever useful. Okay, given a DTD, you can generate a program that could >read and write a bunch of data structures; but what will it *do* with >them? I can see the need for and utility of this. It's just that it's a whole different problem than what serialization addresses. Good Luck with this. Robert Ramey

2 1

Bug fix for BCP
by Edward Diener 04 Apr '04

04 Apr '04

Evidently I either don't have access to the Boost CVS repository on SourceForge or I still can't figure out how to use CVS, so here is a fix to a serious problem with John Maddock's BCP program, and someone else can make the fix. In bcp_imp.cpp, line 17 needs to be changed from: : m_list_mode(false), m_cvs_mode(false), m_unix_lines(false), m_scan_mode(false) to : m_list_mode(false), m_licence_mode(false), m_cvs_mode(false), m_unix_lines(false), m_scan_mode(false)

2 1