On Sat, 23 Jul 2005 10:34:31 -0400, Rob Stewart wrote

From: FlSt@gmx.de

...

The new Perl 6 has a nice feature called junctions. See http://www.perl.com/pub/a/2003/07/29/exegesis6.html?page=4 and http://www.metaperl.com/talks/p6-junctions/ for more information. I think this is a interesting way to save the time for writing loops in some situations. I've tried to implement this for C++ and uploaded a

..

I took a quick look -- looks intersting to me :-) Jeff

Hello Rob.

...

[...]

I have a few questions about your design:

Why "super position" versus Perl's "junction?" When describing the enumerators, you use the Perl terminology, apparently because it makes sense. Frankly, I don't "get" "super position."

Before it was a built-in feature of Perl, something similar was available as a CPAN module called Quantum::SuperPosition. This naming comes from the quantum physics where elementary particles can have more than one state, called super position. But i think its more evident to call it "junction". (Furthermore "super position" sounds overblown ;-)

Why is the junction type a template parameter? Did you consider making four separate types? Does using one make it easier to compare instances of the four types? Should the client have to care about that? IOW, I think writing disjunction<T> is simpler and clearer than super_position<ANY, T>. Other name possibilities like "any_of" are possible, too.

I must admit that i don't spend time in tinking about this until now. The idea behind the diffrent types was, that i don't know how to handle assignments between diffrent junction types. I wrote an explicit constructor for assigning the eigenvalues. But what should the assignment operator copy? Only the values or also the junction type? Would it be better to store the type as an attribute? An another idea i had while writing this template class was, that i write a junction base class and make the is_result_true(...) function virtual and inherit for every junction type. That would fit with your second naming suggestion, which i like, because its more conform to the Perl-implementation. I aggree that writing super_position<ALL,T> is ugly, not only for the clients ;-). The comparisons between diffrent types is no problem, because the only diffrence between the junction types is the is_result_true() function. Has anyone an idea?

Why would one change the Container parameter? Why would the client of this class care about the associative container being used to implement it?

I'm using boost::hash_set<T> in my own applications. And i think there are cases where std::multiset<T> also can make sense. That was the reason for this optional template parameter. For example this is not possible with std::set<T>: http://www.metaperl.com/talks/p6-junctions/slide5.html

I noted that you wrote your loops to repeatedly evaluate x.end(). Algorithms avoid that problem; if you need your own loops, you should hoist calls to end() out of the loop.

That was my laziness, but you are right. :-) Thanks for your fair comments. Sincerly, Florian

<FlSt@gmx.de> wrote in message news:42E51034.7040508@gmx.de...

Hello Rob.

...

...

[...]

I have a few questions about your design:

Why "super position" versus Perl's "junction?" When describing the enumerators, you use the Perl terminology, apparently because it makes sense. Frankly, I don't "get" "super position."

Before it was a built-in feature of Perl, something similar was available as a CPAN module called Quantum::SuperPosition. This naming comes from the quantum physics where elementary particles can have more than one state, called super position. But i think its more evident to call it "junction". (Furthermore "super position" sounds overblown ;-)

Perhaps part of the confusion is that "superposition" is a single word and not two. Merriam Webster defines superposition: 1 : to place or lay over or above whether in or not in contact : SUPERIMPOSE 2 : to lay (as a geometric figure) upon another so as to make all like parts coincide That said, the functionality(in the 1st example) appears to me as a compile-time-set of values. Perhaps mpl already has much of the needed facilities to say(for the scalar case): if( compile_time_set<1,4,9>().count( dave ) ) ... Reading the link describing junction even further, it appears that std::set provides some of the desired functionality. There have been at least a few posting here and on comp.lang.c++* discussing making set operations more complete. I've been finding myself addressing these issue often enough these days to look at implementing a more general solution. So rather than creating new(as far as C++ is concerned) terminology, I'd find general expansion of set manipulating functionality more useful. Thanks, Jeff Flinn

"Rob Stewart" <stewart@sig.com> wrote in message news:200507251959.j6PJx7Qe022151@weezy.balstatdev.susq.com... ...

...

Perhaps part of the confusion is that "superposition" is a single word and not two. ... It's still not very good at communicating the potential in this context.

Agreed.

...

So rather than creating new(as far as C++ is concerned) terminology, I'd find general expansion of set manipulating functionality more useful.

There are many things that one can do with more fundamental components. The question is whether those things can be expressed better using a new component (where better can be interpreted variously).

For example, using std::set where std::vector (or similar) works better is premature pessimism. My last post on this subject suggested that the "all," "any," and "none" cases could be implemented using std::vector. Putting such functionality on std::set means you pay with higher per-element overhead and slower iteration.

In that case, rather than coercing std::set (or std::vector) to meet a new requirement, which enlarges its interface, you use it to provide the new behavior via composition.

A junctions component also seems worthwhile because it raises one's awareness of the functionality and its possible application. By contrast, one isn't likely to think of "junction" when looking for a solution to a problem. Thus, adding the functionality to std::set, for example, is likely to put the functionality in a known component, increasing the chances one will see the functionality as a solution.

I associate Junction with the result of joining/connecting, such as already used by boost::thread and boost::signal. I wasn't necessarily advocating expansion of std::set, but rather that the described functionality/behavior was more akin to the mathematical concept of a set. std::set carries additional baggage, notably the ordering, which is not always necessary. This conceptual_set may not even possess any internal storage at all. For example the set of odd numbers could be defined just as a function: bool ismember_odd_set( int n ){ return n % 2; }. Also as Darren Cooke mentioned in another post to this thread, ranges would be convenient, and is encompassed by the preceding concept. The key operations are defining sets, and comparing sets. The Defining operations would include: conceptual_set s0(5); conceptual_set s1(4,5,6); conceptual_set s2(3,4,5); conceptual_set s3 = intersection( s1, s2 ); // {4,5} conceptual_set s4 = union( s1, s2 ); // {3,4,5,6} The easy comparison(==,!=) are: if( intersection(s0,s1) ) std::cout << "uses operator bool to convey emptiness"; if( intersection(5,s1) ) std::cout << "implicit constructed {5}"; if( union(s1,s2) == s3 ) std::cout << "uses operator bool"; To avoid the unnecessary construction of temporaries when merely checking for emptiness, lazy evaluation could be used, ala phoenix/fusion. The less than comparisons may require enumerating the members of a conceptual_set. I'm not sure how that would be accomplished in the case of odd_set above. Jeff Flinn

From: "Jeff Flinn" <TriumphSprint2000@hotmail.com>

"Rob Stewart" <stewart@sig.com> wrote in message news:200507251959.j6PJx7Qe022151@weezy.balstatdev.susq.com...

...

...

So rather than creating new(as far as C++ is concerned) terminology, I'd find general expansion of set manipulating functionality more useful.

There are many things that one can do with more fundamental components. The question is whether those things can be expressed better using a new component (where better can be interpreted variously). [snip] A junctions component also seems worthwhile because it raises one's awareness of the functionality and its possible application. By contrast, one isn't likely to think of "junction" when looking for a solution to a problem. Thus, adding the functionality to std::set, for example, is likely to put the functionality in a known component, increasing the chances one will see the functionality as a solution.

I associate Junction with the result of joining/connecting, such as already used by boost::thread and boost::signal.

OK. I wasn't married to "junction," but the "ab," "dis," etc. prefixes were helpful to distinguish among the behaviors. However, "any," "all," "none," and "one" are even more meaningful.

I wasn't necessarily advocating expansion of std::set, but rather that the described functionality/behavior was more akin to the mathematical concept of a set. std::set carries additional baggage, notably the ordering, which is not always necessary. This conceptual_set may not even possess any internal storage at all. For example the set of odd numbers could be defined

I see.

just as a function: bool ismember_odd_set( int n ){ return n % 2; }. Also as Darren Cooke mentioned in another post to this thread, ranges would be convenient, and is encompassed by the preceding concept. The key operations are defining sets, and comparing sets.

The Defining operations would include: [snip] various set operations To avoid the unnecessary construction of temporaries when merely checking for emptiness, lazy evaluation could be used, ala phoenix/fusion.

Yes, you'd want compile-time set operations where possible. Let's compare notation. Given a set of values usable by the "any," "all," "none," and "one" types named s, a conceptual_set named c, and a test value named x: "junctions" | conceptual_set -------------|----------------------- x == any(s) | c.count(x) > 1 x == all(s) | c.count(x) == c.size() x == none(s) | c.count(x) == 0 x == one(s) | c.count(x) == 1 (I'm assuming that conceptual_set will provide count(), of course. Note that conceptual_set will probably include contains(), so "any" could be written as c.contains(x).) The junctions notation is shorter and clearer. One can envision layering the junctions notation over conceptual_set. (The expositional implementation I've shown above is inefficient: conceptual_set::count() can't know when you have enough information to arrive at the answer. For "any" and "one," you can stop as soon as count > 1. For "none," you can stop as soon as count == 1. For "all," you can stop as soon as an element doesn't match. You'd either have to make those operations be part of the conceptual_set interface, or you'd have to implement them via iteration.) Implementation details aside, junctions--or whatever you want to call them--seem like a good idea. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: FlSt@gmx.de

You can find a new version of my class to the sandbox file vault (flos_junction.zip). It implements some of the ideas from this

Don't include the editor swap files in your zip file, please.

discussion. But it's very inefficient, because it makes a lot of copies.

I don't plan to look at the implementation until we reach some conclusion as to desirable interface and behavior. For example, your junction base class template provides size(), is_empty(), values(), operator container_type(), be(), and operator bool(). I'm not sure all of those are appropriate. Indeed, your design requires the junction to contain the values over which it operates. Why not have it reference the values over which it operates? I think it would be better to create a view of a container that gives it the junction behavior. That avoids copying elements, though it does require having a separate container with the elements. (Actually, I can envision the possibility of constructing a junction in such a way that it creates, populates, and owns a container if you don't have one already. Then, you can adapt an existing container or create one on demand.) That approach obviates the limited container interface you have created via size(), is_empty(), etc. BTW, the bool conversion should, probably, use the safe bool idiom.

I don't like the implementation, but it works and has the semantic I

Let's discuss the semantics apart from code (other than usage snippets) for now.

visualized. Probaly I will need some help to make it more efficient.

I'll gladly help with that when the time comes.

I see junctions as a expressive way to write comparisons and aritmethic operations on lists and as a alternative to loops.

Let's discuss the use cases. That discussion will form the basis for later documentation, and will focus the design.

Furthermore I must note that Perls junctions are not limited to sets. Junctions are more general. They can be applied to any list and are a logical linkage between the elements of the list, which determines the result of a comparison. That's exactly what my class implements. There

You make a good point. Junctions are useful to adapt other containers that match some concepts. That makes them more general than they otherwise would be. We need to decide what those concepts are, though.

are now four classes: conjunction<T>, disjunction<T>, abjunction<T> and injunction<T>. Whereas T is a Container-Type. And the Functions all_of, any_of, one_of, none_of create instances of this classes from a

Ah, you liked my ideas, eh?

container. See the examples. There is a base class junction, becaus elsewise I don't know how to support all the operators and circumvent writing duplicate code (There are already a lot of macros ;-). Is there a better way?

I'm not worried about that right now. My idea is that the junctions are given a range over which to operate and evaluate to a Boolean when compared with a given value. Using a range (Boost.Range) means that whole containers, iterator pairs, and more can be used to specify the elements that comprise the data over which the junction operates. Now let's look at usage: if (x == any_of(values)) Here, any_of() creates a disjunction over the supplied values. The namespace scope equality operator taking a right hand argument of a disjunction is called with x as the left hand argument. That might trigger a call to a function on the disjunction that returns a Boolean, which the equality operator returns. template <typename T> bool operator ==(T const & lhs_i, disjunction<T> const & rhs_i) { // do work // return answer } Since a call like the above is the likely usage, you don't want to copy the elements into the junction. You just want their extent. Then, the equality operator (indirectly?) iterates the range to figure out the correct answer. A complication is when comparing two junctions: if (none_of(values1) == any_of(values2)) This requires the cooperation of two junctions, if we forward to the junctions to get the answer. I suspect the better design is for the equality operators to do all of the work. template <typename T> bool operator ==(injunction<T> const & lhs_i, disjunction<T> const & rhs_i) { // do work // return answer } The equality operators can be friends of the junction classes so that they can iterate the elements. Just knowing which combination of types are used for the equality is sufficient to invoke the correct algorithm. So, for my first example, the equality operator would iterate the values looking for one that equals x. For my second example, the operator that expression invokes would iterate the values in values1 and check each one against all of the values in values2. Indeed, I see reuse there: for each element in values1, it degenerates to the first example. What do you think of this approach? Boost.Range gives us a wide range of types over which to operate, and putting the logic in the equality operators rather than the junction types gives us compile-time logic selection. The junction types merely serve as selectors for the appropriate equality operator. When I was writing the above, I had in mind that any_of() was a function template that created a disjunction. However, the class template could be called any_of. That way, "any_of(...)" is a constructor call; its use in the examples above creates temporary instances on which the equality operator can be invoked. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: FlSt@gmx.de

Rob Stewart wrote:

Using references instead of value copies is one of the points I wanted to think about. This would make the is_empty(), size() and values() functions unnecessary. The operator bool() is necessary for the duality of the junctions, because a false result of a comparison isn't mandatory an empty junction. And the be()-function exists just for completeness, but i think we can live without it. But when using container-references, how can I return junctions with a new container? Either there must be two types of junctions (one holding references and one holding a container) or a mechnism like this:

See below.

This is what i meant with "two types of junctions". How do I determine the type of the result container? One operand has a std::set and the other one has a std::vecor, which type should the resulting container stored in the junction have? Should they depend on the operands?

Why must there be a result junction? See more below.

...

That approach obviates the limited container interface you have created via size(), is_empty(), etc.

I should read the complete message before replying ;-) That's what I said above.

:)

...

BTW, the bool conversion should, probably, use the safe bool idiom.

It's on my ToDo list. I had already a problem with operator bool() and unary operators. That's why the unary operators now class members, because my compiler (an outdated gcc 2.95) converted the junction first to bool and then applied the unary operator. Why? I read about the safe bool idiom in Matthew Wilson / Imperfect C++ / Chapter 24. I don't know whether the extra complexity justifies the advantage.

I got that book recently, but I haven't read it yet. I just read his discussion of safe bool to be sure I knew to what you were referring. The complexity is worthwhile, though it needn't be as complex as his solution. It's interesting to note that his use of the generator class is erroneous until he puts in a "workaround" for Borland. On p404, he's still using "typedef boolean_type::return_type," but "return_type" is a dependent type, so standard C++ requires "typename" so his "workaround" was to make the code correct!

...

...

I see junctions as a expressive way to write comparisons and aritmethic operations on lists and as a alternative to loops.

Let's discuss the use cases. That discussion will form the basis for later documentation, and will focus the design.

Porbaly the discussions of the Perl community are a good source to get an idea. I think they don't added this feature to Perl without a reason.

I took another look at the Perl links you gave in your original post. Unless I've still missed something, no example applies arithmetic operations to a junction. They are simply membership queries. You probably got the other ideas from the "CPAN module called Quantum::SuperPosition," whatever that is. We have a fundamental disconnect that we must resolve. If there is or should be more to junctions than I've mentioned, I need to understand the use cases and rationale. It may also be that you're trying to combine different concepts into the same set of classes and we should tease them apart. Let's look at two examples and see what they mean:

But I think the most use cases are something like this, instead of writing loops:

if( any_of( a ) < 42 ) { /* one element of list is smaller then 42 */ }

I understand that one. "If any of the elements in a is smaller than 42, do something."

b = any_of( a ) * 2; /* multiply all elements with 2 */

I don't get that one; see below. Multiply any of the elements in a by 2? Which ones? How do you decide? I suppose "any_of(a) * 2" could be construed as an alias for "all_of(a) * 2," but what about "none_of(a) * 2" or "one_of(a) * 2?" The latter two are nonsensical, which makes the former two questionable at best. Besides, multiplying each element of a container by 2 is easily done using Boost.Lambda or similar libraries, right? Why must a junction support that?

In the Quantum::Superpositions module manual page are examples to get the min/max of a list in one line of code, which is based on the resulting junction of a comparison:

Minimum of a : any_of( a ) <= all_of( a ) Maximum of a : any_of( a ) >= all_of( a )

That's supported by my equality operator approach, too.

...

You make a good point. Junctions are useful to adapt other containers that match some concepts. That makes them more general than they otherwise would be. We need to decide what those concepts are, though.

The current implementation only needs a constructor for initializing with input iterators and forward-iterator support.

Boost.Range will expand that. However, my point was to contrast the adapter approach to that of the conceptual_set that was suggested.

...

...

What do you think of this approach? Boost.Range gives us a wide range of types over which to operate, and putting the logic in the equality operators rather than the junction types gives us compile-time logic selection. The junction types merely serve as selectors for the appropriate equality operator.

I think boost.range and junction would fit good together, but you forgot to adhire the duality of the result of a comparison. In the minumum/maximum example showed above the values of the resulting junctions were interesting.

I don't know what you mean by "adhere to the duality of the result of a comparison" unless you mean that your version always returns a new junction that can implicitly convert to a Boolean for comparisons. I don't see the value of that. My equality operator approach does the comparisons handily.

There are three ways how to use the result in the current implementation:

disjunction< Container > a, b;

disjunction< Container > r = a <= b; // assign to another junction

Why?

Container r_c = a <= b; // use values of the resulting junction ( if junctions are refs, then this isn't necessary )

Why?

bool r_b = a <= b; // use boolean result

Yes. If we can agree to forgo the arithmetic functionality you've thought should be part of the junction classes, we can simplify the design significantly. That, in turn, will make writing documentation easier and will increase the chances of acceptance into Boost. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

...

...

In the Quantum::Superpositions module manual page are examples to get the min/max of a list in one line of code, which is based on the resulting junction of a comparison:

Minimum of a : any_of( a ) <= all_of( a ) Maximum of a : any_of( a ) >= all_of( a ) ... For example "a" contains 1, 2, 3 then the resulting junction of any_of( a ) >= all_of( a ) contains 3, which is the maximum value of a.

I don't think you need to worry about supporting this; it is bad code as it will need a comment to say what it is doing, and C++ already has an idiom for finding min/max in a list: min_element() and max_element(). Darren

...

...

...

[...]

If that is a useful expression, it's more of a set operation than a junction operation (as exemplified by Perl's junctions) anyway,

http://www.linux-magazine.com/issue/38/Perl_BlackJack.pdf. This is the article from where my idea comes to have something similar in C++ (I read the German translation in Linux Magazin 12/2003)

right? Besides, normal algorithms can be used to express that quite succinctly. Do you need a new type for it? Maybe. I don't think it should be merged with the simpler ideas from Perl junctions. I think they are orthogonal behaviors, and the complexity argues against one type doing both tasks.

The Perl junctions aren't simpler, in Perl you can call functions either in a scalar context or in a list context. The called function can determine in which context it is called and return a scalar or a list. I think my mistake was, I tried to bring this concept into C++ for junctions, but it doesn't fit into the C++ type system. And there was no example for this in the article I denoted in my first message. A junction without junction result type and arithmetic operations is something completely different I had in mind at the beginning of this discussion. What remains now at the view point of the client are the four functions any_of<T>, all_of<T>, one_of<T> and none_of<T> and the comparison operators. The XXX_of functions should operate on ranges or containers. I aggree. Florian

From: "Jeff Flinn" <TriumphSprint2000@hotmail.com>

I just found this snippet of code in one of my projects:

#include <boost/algorithm/string.hpp> #include <boost/algorithm/string/classification.hpp>

bool NameValid( const std::string& aName ) { using namespace boost::algorithm;

return all( aName, !is_any_of(" -") );; }

looks familiar eh? I totally forgot about this. I haven't looked in Pavol Droba's string algorithm library to see if there are additional facilities that cover other cases. The 'string' in Pavol's library defines string as a general concept and not as std::string.

That expression would be easier to read with the junctions idea: none_of(aName) == any_of(" -"); (Assuming all of the above syntax can be made to work!) Don't you agree? -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: FlSt@gmx.de

...

...

...

...

[...]

Don't forget attributions for the text you quote.

...

If that is a useful expression, it's more of a set operation than a junction operation (as exemplified by Perl's junctions) anyway,

http://www.linux-magazine.com/issue/38/Perl_BlackJack.pdf. This is the article from where my idea comes to have something similar in C++ (I read the German translation in Linux Magazin 12/2003)

I see. That elucidates the duality concept you've been discussing.

...

right? Besides, normal algorithms can be used to express that quite succinctly. Do you need a new type for it? Maybe. I don't think it should be merged with the simpler ideas from Perl junctions. I think they are orthogonal behaviors, and the complexity argues against one type doing both tasks.

The Perl junctions aren't simpler, in Perl you can call functions either in a scalar context or in a list context. The called function can determine in which context it is called and return a scalar or a list. I think my mistake was, I tried to bring this concept into C++ for junctions, but it doesn't fit into the C++ type system. And there was no example for this in the article I denoted in my first message.

OK. You did mislead me with the initial references, but I now understand what you were trying to do.

A junction without junction result type and arithmetic operations is something completely different I had in mind at the beginning of this discussion. What remains now at the view point of the client are the

I think the creation of a new container with elements from another container that match a criteria is already well supported. It may yet be that some syntactic sugar can be overlaid to simplify it, however, so do keep that in mind. So, I think we're agreed that we're discussing four things that can be compared to each other as well as to single values. The supported comparisons are ==, !=, <, >, <=, and >=. If we're agreed, then we can discuss design.

four functions any_of<T>, all_of<T>, one_of<T> and none_of<T> and the comparison operators. The XXX_of functions should operate on ranges or containers. I aggree.

For the extraction of elements matching some criteria, you would likely use function templates. For the functionality we've whittled down junctions (or whatever name still fits) to include, you need types plus namespace scope operators: template <typename T> struct junction { range<T> range_; // for exposition only }; template <typename T> struct all_of : junction<T> { }; template <typename T> struct any_of : junction<T> { }; template <typename T> struct none_of : junction<T> { }; template <typename T> struct one_of : junction<T> { }; template <typename LHS, typename T> bool operator ==(call_traits<LHS>::param_type lhs_i, any_of<T> rhs_i); // maybe by reference to const template <typename LHS, typename T> bool operator !=(call_traits<LHS>::param_type lhs_i, any_of<T> rhs_i); // maybe by reference to const template <typename LHS, typename T> bool operator <(call_traits<LHS>::param_type lhs_i, any_of<T> rhs_i); // maybe by reference to const template <typename LHS, typename T> bool operator >(call_traits<LHS>::param_type lhs_i, any_of<T> rhs_i); // maybe by reference to const template <typename LHS, typename T> bool operator <=(call_traits<LHS>::param_type lhs_i, any_of<T> rhs_i); // maybe by reference to const template <typename LHS, typename T> bool operator >=(call_traits<LHS>::param_type lhs_i, any_of<T> rhs_i); // maybe by reference to const template < typename T, typename RHS> bool operator ==(any_of<T> rhs_i, // maybe by reference to const call_traits<RHS>::param_type rhs_i); etc. template <typename LHS, typename T> bool operator ==(call_traits<LHS>::param_type lhs_i, all_of<T> rhs_i); // maybe by reference to const etc., including those to compare any_of with all_of, all_of with one_of, and so on. Many of these operators will be defined in terms of others. For example, once you have the (lhs_i, any_of) operators, the (any_of, rhs_i) operators can be defined in terms of the former. Also, you can define the (lhs_i, all_of) operators in terms of the (lhs_i, any_of) operators, provided you can create an any_of<T> from an all_of<T>: template <typename T> struct any_of : junction<T> { explicit any_of(junction<T> junction_i); // maybe by reference to const }; Indeed, most cases can be handled once you implement the any_of and one_of variants. A better approach is probably for the operators to be implemented in terms of a number of implementation function templates that work only on junction<T>'s. Then, there's no conversion needed; the operators just need to call the right implementation function. That leaves the four derived types as just selectors for the right operator. Ideally, junction<T> will hide its range and the implementation function templates will be made friends. Using namespace scope operators, with the four derived types as selectors, we can support any combination of x op all_of(s), x op any_of(x), x op none_of(s), x op one_of(s), where x is a type convertible to the range's value type or another all_of, any_of, none_of, or one_of. What do you think of these ideas for the design? There's still the issue of naming. Should these be called junctions since they don't do all that Perl's junctions do? Besides, I think "junction" somehow fits better the notion of producing a result container that includes those elements of the range that satisfy the criteria. Quantum physics' superposition concept doesn't fit very well, because we're not talking about particles that can be in various places. That suggests "supervalue," but one might then ask, what makes the value so super? A common theme suggests "smart value," but that's not really helpful. At least the one-word "supervalue" is somehow indicative of "superposition." So, when someone is looking for a library to do what this one does, what name(s) would they think to look for? I'm at a loss for a good name. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

Hello. I uploaded a 3rd version (flos_junction_v3.zip) which is a trade-of of Rob Stewart's and my ideas. Sincerly Florian

From: FlSt@gmx.de

I uploaded a new version of the junction comparison of ranges to boost sandbox file vault ( flos_junction_v6.zip ). When find it useful or you

You just keep churning them out! Please describe the differences as you add a new version.

have critism on the implementation tell it to me. There is still the naming problem, i don't want call them junctions. Has anyone an idea?

I've been working on my own implementation which takes a different tack from yours (as of v3 or 4, I think, anyway). That has raised some questions, but first, I have an idea for the naming: namespace: boost::multivalues base class: multivalue all_of: all_values any_of: any_value none_of: no_values one_of: one_value Are all (in)equality comparisons symmetric? I was pondering what the following expression means: any_of(s1) == one_of(s2) You could make that case that as long as any one of the values in s1 matches exactly one of the values in s2, the result is true. Given that interpretation, should the following expression mean the same thing? one_of(s2) == any_of(s1) When written that way, it seems easy to think that there should only be one value in s1 that matches a value in s2. IOW, if more than one value in s1 matches exactly one value in s2, the expression would be false. Thus, the first expression could also be true iff there is just one value in s1 that matches exactly one value in s2. If you think the latter interpretation, then how does that differ from the following expression? one_of(s1) == one_of(s2) That expression clearly says exactly one value in s1 must match exactly one value in s2. Consequently, I think it argues for the first two expressions to be true if one or more value in s1 matches exactly one value in s2. Do you agree?

There are four functions for creating junction-objects from a range: any_of, all_of, one_of and none_of and you can compre the objects with one of the comparion operators (==,!=,<,<=,>,>=). You also can use something different when you write:

any_of( a ).do_comparison( <Function object>, all_of( b ) ); The function object exspected is bool(element_type,element_type) wheather element_type is the type of a range element.

As soon as you open up that interface, you permit opportunity for confusion. This is especially true of comparisons with none_of. It is also a point of customization that must be documented. Do you think there's enough reason to justify that? -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: FlSt@gmx.de

Rob Stewart wrote:

...

That has raised some questions, but first, I have an idea for the naming:

namespace: boost::multivalues base class: multivalue all_of: all_values any_of: any_value none_of: no_values one_of: one_value

Sounds a bit like a container type for me. It's nothing more than a functional extension for ranges (or container), some kind of algorithm. I don't know!

It does sound a little like a container type, but what container would be named like those? That is, I don't think they would make good container names, so I think they fit our purposes reasonably well. I'm hoping someone else will jump in soon enough with other suggestions since the release furor is mostly past now. Still, I do like these names.

...

Are all (in)equality comparisons symmetric? I was pondering what the following expression means:

any_of(s1) == one_of(s2)

I understand xxx_of as giving a logical linkage to the values of a list and I think this is what Perl also does: all_of = and, any_of = or, one_of = xor and none_of = not any_of. Do you agree?

I'm not certain I can agree. I understand that using that definition does simplify the implementation, but "all" doesn't quite evoke "and," nor "any" "or," nor "none" "not." "one" does reasonably evoke "xor," however. I didn't pay enough attention to the details of the Perl approach, so I didn't get mired in them. That left me to interpret "all," "and," "none," and "or" at face value. That also left me to find some strange combinations that were confusing. (More below.)

false <---- different result! This is the proove that in my interpretation not all equality comparisons are symetric

I think allowing asymmetry in these expressions will cause great confusion. This is especially true when it isn't required.

I hope the explanation of my interpretation of junctions was evident.

Yes. I'd forgotten the Perl equivalencies to AND, OR, XOR, and NOT.

(It's difficult for me writing texts in englisch, reading is easier for me ;-)

You're doing quite well. I'm sure I would do quite poorly in your native language!

...

When written that way, it seems easy to think that there should only be one value in s1 that matches a value in s2. IOW, if more than one value in s1 matches exactly one value in s2, the expression would be false.

Thus, the first expression could also be true iff there is just one value in s1 that matches exactly one value in s2.

If you think the latter interpretation, then how does that differ from the following expression?

one_of(s1) == one_of(s2)

That expression clearly says exactly one value in s1 must match exactly one value in s2. Consequently, I think it argues for the first two expressions to be true if one or more value in s1 matches exactly one value in s2. Do you agree?

See above. This should answer all questions if you agree with me of what the junction comparison does.

I think it would be more sensible when read, and remains easy enough to explain if we provide symmetry and these definitions: all_of: every value must satisfy the test with the same other value any_of: at least one value must satisfy the test each_of: every value must satisfy the test n_of: exactly n values must satisfy the test none_of: no value may satisfy the test one_of: exactly one value must satisfy the test I invented n_of (n_values) when I was considering none_of and one_of and I thought to generalize it. all_of is different from the others in that all of the values have to satisfy the test against the same other side. That is, all_of(x) OP any_of(y) means all values in x must OP the same value in y all_of(x) OP each_of(y) means all values in x must OP every value in y all_of(x) OP n_of(y) means all values in x must OP the same N values in y all_of(x) OP none_of(y) means all values in x must OP no values in y all_of(x) OP one_of(y) means all values in x must OP the same one value in y The same applies when you reverse the arguments. For the one_of(x) == one_of(y) example, I think it is reasonable to think of it as finding exactly one value from x and exactly one from y that satisfies x[n] == y[m]. That's how it reads. (I haven't even attempted to see whether that's how your interpretation would answer.)

There are some combinations of "xxx_of(s1) OP yyy_of(s2)" which are not useful. I think it would be a good idea to extract useful and not so useful expressions and document it. At the first sight it seems that

I don't think there's a need to document what isn't useful. If a combination is never satisfied or is more efficient if expressed another way, we can implement them on behalf of the user accordingly. That is, if a combination is never true, we can define it to just return false. If a combination is inefficient and it can be expressed more efficiently, we can forward to the efficient implementation. (My design makes that simple to do.)

junctions (multivalues) are trivial, but i must admit they aren't.

Indeed. I have to review my design to make sure I'm doing everything correctly, and I have a couple of tests that fail still. Once I finish, I'll upload it for your inspection. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

Rob Stewart wrote:

From: FlSt@gmx.de

...

Rob Stewart wrote:

...

[...] namespace: boost::multivalues base class: multivalue all_of: all_values any_of: any_value none_of: no_values one_of: one_value

Sounds a bit like a container type for me. It's nothing more than a functional extension for ranges (or container), some kind of algorithm. I don't know!

It does sound a little like a container type, but what container would be named like those? That is, I don't think they would make good container names, so I think they fit our purposes reasonably well.

I aggree that they wouldn't make good container names (multivalues could be another name for array). And I think multivalues are a better name than junctions, because the concept we are discussing differs a lot from the perl idea, what is a good reason for an other name. The name "junctions" distinguishes the relation between the values, which would fit better to my interpretation I described in my previous posting. So I will aggree with "multivalues" until someone has a better idea.

...

...

[...]

I understand xxx_of as giving a logical linkage to the values of a list and I think this is what Perl also does: all_of = and, any_of = or, one_of = xor and none_of = not any_of. Do you agree?

I'm not certain I can agree. I understand that using that definition does simplify the implementation, but "all" doesn't quite evoke "and," nor "any" "or," nor "none" "not." "one" does reasonably evoke "xor," however.

My interpretation (and i think also perl does so) is based on the boolean algebra where the operators "All of" (the A on it's head) and "Exists" (the mirrored E) are used in analogy to the sum and product operators in numeric algebra. So i think the names have sense. Your interpretation has is a higher-level approach. The longer I think about this, the more I belife there are justifications for both interpretations. What do you think? BTW: Today I tried to install the Perl 6 interpreter Pugs, but I didn't get it to work. I wanted to analyze the Perl 6 implementation of junctions especially the behaivor of comparisons, because I don't want to tell something wrong here. The only experiences I have are with the Quantum::Superpositions module which behaves like my implementation, except that my current implementation doesn't return a new junction and doesn't support algebraic operations.

I didn't pay enough attention to the details of the Perl approach, so I didn't get mired in them. That left me to interpret "all," "and," "none," and "or" at face value. That also left me to find some strange combinations that were confusing. (More below.)

That is want I meant above. I really don't think that your approach is wrong or bad, but I must rethink completely to follow your thoughts.

...

false <---- different result! This is the proove that in my interpretation not all equality comparisons are symetric

I think allowing asymmetry in these expressions will cause great confusion. This is especially true when it isn't required.

From your viewport of multivalues I aggree and understand what you mean.

[...]

I think it would be more sensible when read, and remains easy enough to explain if we provide symmetry and these definitions:

all_of: every value must satisfy the test with the same other value any_of: at least one value must satisfy the test each_of: every value must satisfy the test n_of: exactly n values must satisfy the test none_of: no value may satisfy the test one_of: exactly one value must satisfy the test

I must admit that I can't say something useful about this now, I need some more time to think about it, because I'm still affected by the Perl implementation.

I invented n_of (n_values) when I was considering none_of and one_of and I thought to generalize it.

You can generalize it a step further when you can give a range to n_m_of(): n minimum number of values that must satisfy the test and m maximum number of values that must satisfy the test. Ok, ok no more complexity as necessary ;-) Your n_of would also be useful with the junctions approach (This provides all steps between "and" and "or" inclusive "xor" in one function).

[..]

For the one_of(x) == one_of(y) example, I think it is reasonable to think of it as finding exactly one value from x and exactly one from y that satisfies x[n] == y[m]. That's how it reads. (I haven't even attempted to see whether that's how your interpretation would answer.)

In my interpretation this would be equivalent to: ( x[1] == y[1] ^^ x[1] == y[2] ^^ ... ^^ x[1] == y[m] ) ^^ ( x[2] == y[1] ^^ x[2] == y[2] ^^ ... ^^ x[2] == y[m] ) ^^ ... ( x[n] == y[1] ^^ x[n] == y[2] ^^ ... ^^ x[n] == y[m] ) What means this expression is true when x has exactly one value which is equal to exactly one value of y.

I have to review my design to make sure I'm doing everything correctly, and I have a couple of tests that fail still. Once I finish, I'll upload it for your inspection.

I'm very courious about it. Sincerly Florian

What does the following expression mean? all_of(x) != any_of(y) 1) It could mean that each of the values in x must not be equal to any one of the values in y. OTOH, should that expression be symmetrical? any_of(y) != all_of(x) 2) When expressed that way, it suggests that as long as any of the values in y is not equal to all of the values in x, the result is true. That is, given the following sets of values s1 = { 1, 2, 3 } s2 = { 3, 4, 5 } what should be the value of this expression? all_of(s1) != any_of(s2) Intuitively, that seems to suggest 1), which means it evaluates to false. When reversed any_of(s2) != all_of(s1) the expression seems to suggest 2), which means it evaluates to true. I don't like the idea of these expressions being asymmetrical. Perhaps we need each_of to mean each value should be compared against the other side and, provided all of those comparisons succeed, the expression evaluates to true. Then, all_of can mean that all of the values must satisfy the *same* comparison. Put another way, all_of(x) op any_of(y) must be implemented by iterating y and comparing against all_of(x). With those two types, and given s1 and s2 from above, we'd have the following expressions evaluate to true: all_of(s1) != any_of(s2) !(each_of(s1) != any_of(s2)) -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: "Pavel Vozenilek" <pavel_vozenilek@hotmail.com>

<FlSt@gmx.de> wrote:

________________________________________________________ 3. There should be overloads of "xyz_of" who take pair of iterators, in the old-fashioned STL way.

Hmmm. That's a good idea. Ranges are nice, but they don't support two iterators unless they are paired somehow.

________________________________________________________ 4. Perhaps the could be rewritten not to use macros as code generators.

It is not possible to debug it as it is now, for example.

That's a good point. I've encountered the issue myself in my implementation.

________________________________________________________ 5. The classes like conjuction etc may be likely moved into sub-namespace like boost::junction_details.

The idea is that you may wish to create and hold onto instances, though I'll grant that most uses are likely to be via the *_of function templates.

________________________________________________________ 6. Would it be possible to have other qualifiers, e.g.: "more_than_half_of"

if (more_than_half_of(a) >= any_of(b)) ...

or more complex versions like:

more_than(10).items_of(a) >= ... more_than(30.1).percents_of(a) == ...

less_than(2).items_of(a) >= ... less_than(95).percents_of(a) == ...

between(1, 5).items_of(a) >= ... between(10.5, 20.0).percents_of(a) == ....

Those are possible but are they sufficiently useful? Do you think they would be used enough to justify creating/documenting them?

exactly(10).items_of(a) >= ....

I already proposed n_of for that: n_of<10>(a) That doesn't read as well as your version, of course.

Comparison between two "mores" would be disabled.

Why?

________________________________________________________ 7. Will it be possible to use other predicates than

...

, <=, etc in following form:

if ( is_true_that(all_of(a), a_binary_functor, one_of(b)) ) ...

where the functor could be lambda:

if (is_true_that(all_of(a), _1 >= _2, one_of(b)) ....

It feels more natural than the asymetric "do_comparison".

I agree with the asymmetry of do_comparison(), but is it necessary to provide the additional predicate support? Reasoning over the result of using none_of() with a user-defined predicate gets quite difficult when compared against an all_of() or other junction/multivalue objects. Doing so against a single value is much easier. I think "evaluate" is better than "is_true_that:" if (evaluate(all_of(a), _1 >= _2, one_of(b))) ... Should the normal operators rely on lambda support? My implementation uses structs with templated operators to permit heterogenous comparisons, so there's no need for lambda's heavy lifting.

________________________________________________________ 8. If the "is_true_that" will be implemented than a filter "where" could be considered, like:

if ( is_true_that(all_of(a), _1 >= _2, one_of(b) ).where(_1->does_fulfill_condition()) ) ...

and the "where" fould have unary predicate as parameter, this predicate would filter out undesirable items from both ranges.

That doesn't sound like what you've described. I'd expect this to do what you've described: if (evaluate(all_of(a).where(filter1) , _1 >= _2 , one_of(b).where(filter2))) ... However, this would be even better as it wouldn't confuse behavior: if (evaluate(all_of(from(a).select(filter1)) , _1 >= _2 , one_of(from(b).select(filter2)))) ... Nevertheless, the question arises whether all of this is warranted. Indeed, if we support iterator pairs in addition to ranges, there are other libraries that one can employ to do the filtering, so this one doesn't need to. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: "Pavel Vozenilek" <pavel_vozenilek@hotmail.com>

"Rob Stewart" wrote:

...

...

Comparison between two "mores" would be disabled.

Why?

Because if (more_than_half_of(a) >= more_than_half_of(b)) ... doesn't make sense.

It does to me. Suppose a is the set of female students and b the male students. Further suppose that >= compares grades. Then the expression asks whether more than half of the girls got grades at least as high as more than half of the boys.

________________________________________________________

...

...

7. Will it be possible to use other predicates than

...

, <=, etc in following form:

if ( is_true_that(all_of(a), a_binary_functor, one_of(b)) ) ...

where the functor could be lambda:

if (is_true_that(all_of(a), _1 >= _2, one_of(b)) ....

It feels more natural than the asymetric "do_comparison".

I agree with the asymmetry of do_comparison(), but is it necessary to provide the additional predicate support?

Yes. Forcing user to define == etc operators doesn't make good design and there could be many, many possible predicates for single class.

If you allow that, then symmetry cannot be guarranteed. There's already a question as to whether the operators must be symmetrical. I've posited that asymmetry will lead to confusion, but many comparisons sound asymmetrical. Consider these two expressions: none_of(a) == any_of(b) // 1 any_of(a) == none_of(b) // 2 1. Sounds like it should be true if none of the values in a equal any value in b. 2. Sounds like it should be true if any of the values in a equals none of the values in b. Florian's notion of these operators, derived from Perl, is that they are not symmetrical. To make expressions like 1 and 2 symmetrical, I've taken to swapping arguments depending upon the combination of types, which means I'm forcing the symmetry. Maybe I'm just off the mark and they should be allowed to be asymmetrical.

...

Reasoning over the result of using none_of() with a user-defined predicate gets quite difficult when compared against an all_of() or other junction/multivalue objects. Doing so against a single value is much easier.

Yes but the documentation should say what combinations are potentially dangerous.

Dangerous? Inefficient or useless, maybe, but dangerous?

...

I think "evaluate" is better than "is_true_that:"

if (evaluate(all_of(a), _1 >= _2, one_of(b))) ...

People who also code in scripting languages with an "eval" function would get confused.

I was actually thinking of that when I wrote it. However, eval usually has some value, though I think it is really just a status code, not related to the expression being evaluated. Perhaps we should consider a functional style: if (compare(all_of(a), one_of(b), _1 >= _2)) or if (compare(all_of(a), _1 >= _2, one_of(b)))

________________________________________________________

...

if (evaluate(all_of(a).where(filter1) , _1 >= _2 , one_of(b).where(filter2))) ...

This may be also useful. Either specific filters for each side, or one common, or both or one or none.

For a common filter, you can just reuse it.

...

Nevertheless, the question arises whether all of this is warranted. Indeed, if we support iterator pairs in addition to ranges, there are other libraries that one can employ to do the filtering, so this one doesn't need to.

The filters could be lambdas. Result syntax could be smaller and easier to read then with another object (a filtering iterator).

That may be true, but I'm concerned about duplicating functionality and, thus, limiting flexibility. I guess we just need to be sure that this library interoperates easily with filters created using the facilities of the other libraries. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: David Abrahams <dave@boost-consulting.com>

Rob Stewart <stewart@sig.com> writes:

...

Florian's notion of these operators, derived from Perl, is that they are not symmetrical. To make expressions like 1 and 2 symmetrical, I've taken to swapping arguments depending upon the combination of types, which means I'm forcing the symmetry. Maybe I'm just off the mark and they should be allowed to be asymmetrical.

I think that's right. These things reflect the syntax and semantics of english, not of math anymore.

That's always a bad sign! ;-)

Besides, >, >=,<=, < aren't symmetric ;^)

I swapped predicates accordingly.

...

...

...

Reasoning over the result of using none_of() with a user-defined predicate gets quite difficult when compared against an all_of() or other junction/multivalue objects. Doing so against a single value is much easier.

Yes but the documentation should say what combinations are potentially dangerous.

Dangerous? Inefficient or useless, maybe, but dangerous?

...

...

I think "evaluate" is better than "is_true_that:"

if (evaluate(all_of(a), _1 >= _2, one_of(b))) ...

Yuck.

Do you prefer "is_true_that" or were you registering distaste for both?

...

Perhaps we should consider a functional style:

if (compare(all_of(a), one_of(b), _1 >= _2))

or

if (compare(all_of(a), _1 >= _2, one_of(b)))

IMO that's a *lot* harder to read than

all_of(a) >= one_of(b)

Of course.

I'm not sure if I'm going to like the latter style in the long run, but so far it's looking pretty sweet.

What about user-supplied predicates? You can't use infix notation then. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

David Abrahams wrote:

Rob Stewart <stewart@sig.com> writes:

...

From: David Abrahams <dave@boost-consulting.com>

...

Rob Stewart <stewart@sig.com> writes:

...

Florian's notion of these operators, derived from Perl, is that they are not symmetrical. To make expressions like 1 and 2 symmetrical, I've taken to swapping arguments depending upon the combination of types, which means I'm forcing the symmetry. Maybe I'm just off the mark and they should be allowed to be asymmetrical.

I think that's right. These things reflect the syntax and semantics of english, not of math anymore.

That's always a bad sign! ;-)

Not when english expresses what we mean more concisely.

I think that a clean mathematical definition of a topic like this would be a good idea. Furthermore I uploaded a new implementation of my junctions calss to the sanbox file vault junction/boost_junction_v8.zip and a draft of a document which describes the junctions from a mathematical view. (It's just a draft and the notation needs to be explained) Lambda is removed from the current version, because to many compilers don't compile this. I'm using boost::bind instead to change the operands order. Sincerly Florian Sincerly Florian

Rob Stewart wrote:

From: FlSt@gmx.de

...

Furthermore I uploaded a new implementation of my junctions calss to the sanbox file vault junction/boost_junction_v8.zip and a draft of a document which describes the junctions from a mathematical view. (It's just a draft and the notation needs to be explained) Lambda is removed from the current version, because to many compilers don't compile this. I'm using boost::bind instead to change the operands order.

I just tried that version tonight. So far, it has taken well over 30 minutes to compile junction_example.cpp, and it's still going. That's on a 3 GHz dual Pentium box running SUSE linux using GCC 3.2.3. By comparison, my test program with my library takes less than a minute.

On my Pentium III 900Mhz (512 MB) (I know this machine is outdated like my gcc 2.95) it takes 15Minutes with g++ 4.0.1 and the compilation never finished with g++ 3.3.6 and 2.95.?, because my virtual memory was full ;-). I uploaded a new version to the sandbox file vault (junctions/boost_junction_v9.zip). This version compiles a little bit faster, but it's still slow. I don't know exactly why, but I think this has todo with the many operator template instances are generated with my test program. I removed the xxx_of functions for STL-Iterators, because Ranges of STL-Iterators can be generated with make_iterator_range( begin, end ).

I'll try rewriting my test program to work with your library so we can compare them a little more fairly. I'll let you know what I find.

Good idea. Sincerly Florian

Rob Stewart wrote:

From: FlSt@gmx.de

...

Rob Stewart wrote:

...

From: FlSt@gmx.de

I just tried that version tonight. So far, it has taken well over 30 minutes to compile junction_example.cpp, and it's still

It took just over 39 minutes to complete.

g++ 4.0.1 is a lot faster, but needs more RAM (as I saw with top). Compilation times of my test program with the new version: g++4.0.1 1,5 minutes g++3.3.6 7,5 minutes g++2.95 3,75 minutes I'm using Linux and tested the compilers with -O0 -g -Wall -W options (no optimizing and debug infos) and the "time" command for the compilation time measurement. I think comparisons with optimizing activated makes no sense, because the compiler version are to different.

...

test program. I removed the xxx_of functions for STL-Iterators, because Ranges of STL-Iterators can be generated with make_iterator_range( begin, end )

I haven't looked at supporting pairs of iterators yet. You're right that one can use make_iterator_range, but if we can use a pair right out of the box, all the better

see below. There is another reason why I removed them.

...

I switched back to your test program and it again took a very long time to compile. When I ran it, it dumped core due to what looks like infinite recursion (SIGSEGV).

No, the problem is that you removed the storage of the Range. When you create a instance of a junction with the STL-iterator-range with boost::range::make_iterator_range() it creates a temporary object which is lost after creating the junction creation. That was the secons reason I removed the STL Ranges support. ;-) In my new version (v9) I use references to the range. ( But I think the cost of holding a range would be minimal. )

BTW, you should consider writing your tests such that you don't have to visually inspect each test each run to decide whether you're getting the correct answer. Do you save a vetted copy of the output and diff the output of a new run against that each time?

No :-). I have seperate test programs, which I haven't put into the zip file, because they are still under construction.

Also, you should not put your code directly into namespaceboost. Following Boost guidelines, you'd create a "junctions" namespace for everything.

Ok, will be done for the next version Sincerly Florian

Rob Stewart wrote:

Would "some_of" be a better name than "n_m_of?" The latter isn't the most inventive name and I was hoping to find something better (if there is anything). Both would be parameterized with two values (min and max). I know "some" is quite vague, like "any," but the required parameters would force supplying the minimum and maximum.

We could also try "min_max_of," but that suggests a function that returns a pair of values.

"n_m_of" uses anti-alphabetical ordering of the letters. That rather suggests the template argument order of maximum then minimum. Perhaps changing to "x_y_of" or "a_z_of" would be better?

How about 'subrange_of'? 'subset_of' would sound better, but 'subrange' indicates that the desired subset would be min/max bounded. Matt

From: Matthew Vogt <mattvogt@warpmail.net>

Matthew Vogt wrote:

...

How about 'subrange_of'?

Actually, scratch that; it doesn't sound right. It *is* a subset you're finding, albeit with extra constraints. Maybe 'bounded_subset_of'?

I like the 'between' formulation in your other post.

I've uploaded yet another revision of multivalues.zip. I decided to go with "some" for n_m/subrange/subset/i_j/a_z/x_y/etc. New features: - some_values/some_of: if (some_of(3, 5, r) > 3) ... // at least 3 and less than 6 > 3 (I selected the argument order shown because "some" precedes "of" and "values" and so it rather suggests that the minimum and maximum should precede the range. - implementing n_of/n_values and one_of/one_value in terms of some* which should reduce template instantiations - some_of/some_values (formerly n_m_of/n_m_values) and n_of/n_values are now implemented using data members for the minimum and maximum count to reduce template instantiations and to support between and exactly - adds between if (between(3, 5).items_of(r) > 3) ... - adds exactly if (exactly(3).items_of(r) > 3) ... - all of the above work with pairs of iterators, too (no need to use boost::make_iterator_range()) - separated code into distinct headers plus one multivalues.hpp to suck in everything - added detail subdirectory This one runs 2016 tests and compiles in just over nine minutes on my system (still GCC 3.2.3). There are still some things missing: - tests for some_of, between, and exactly. - support for user-defined predicates that only know how to compare to values and not multivalues - documentation If there is reasonable consensus for what we have thus far, among those interested in this library, I think we should start to work on some documentation so more people will take a look at the library. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: Florian Stegner <FlSt@gmx.de>

Rob Stewart wrote:

...

From: Matthew Vogt <mattvogt@warpmail.net>

...

Matthew Vogt wrote:

I've uploaded yet another revision of multivalues.zip. I decided to go with "some" for n_m/subrange/subset/i_j/a_z/x_y/etc

I aggree with it. But each_of is still confusing for me. You implemented it as the negation of all_of: "( all_of( a ) > x ) != ( each_of( x ) > x )" is true for all a and x. each_of in your implementation is equivalent to not_all_of in mine. not_all_of in your implementation is the negation of one_of, what is ok. But each_of( a ) == x means that none or more but not all elements of a are equal to x. There must be a better name as each_of. I had just a quick look on your new implementation. I will post my results later.

I just took a look at my implementation of all and each. At least in my latest version, it's worse than you describe. They are identical. Regardless of how I've implemented them, these are the intended semantics: all: all of the values must match *the same* other value each: all of the values must match *some* other value Thus, all_of({1, 2, 3}) < any_of({3, 4}) means: 1 < 3: true 2 < 3: true 3 < 3: false 1 < 4: true 2 < 4: true 3 < 4: true result: true But, each_of({1, 2, 3}) < any_of({3, 4}) means: 1 < 3: true 2 < 3: true 3 < 3: false 3 < 4: true result: true

Could you send me the testfiles .cpp or upload them to the sandbox file vault?

Oops! I'll do that tonight.

Then I could help you to complete them. What is about the tests for the relations between the multivalues I sent you?

I'm not sure I understand the question. Are you asking if I ran your tests? No, I didn't.

...

There are still some things missing:

- tests for some_of, between, and exactly.

I found also relations between expressions with one_of.

Are you saying they were missing from your tests? (They are in the missing tests.hpp.)

...

- support for user-defined predicates that only know how to compare to values and not multivalues

My implementation (v11) can compare two multivalues (junctions) with user defined predicates. I wrote swap_operands as a function object wrapper, if the rhs-parameter is a multivalue. There is still the problem with lambda-expressions. The only working idea I found to allow

That's what I've been working on. I'll have a look.

the usage of lambda expressions would be to have a function like this:

compare( all_of( a ), _1 < _2, any_of( b ) )

But what is about the []-operator?

all_of( a ) [ _2 > _1 ] any_of( b )

Then we would have no more problems with operator precendence. :-)

That won't work. "all_of(a)::operator [](_2 > _1)" yields an object, but you end up with "result any_of(b)," where "result" is the object returned by operator [].

...

- documentation

I will help you so good I can.

I know it will be a challenge given that English isn't your native language. The Boolean logic is certainly one area I'll need your help. We can also discuss--privately, I think--the layout and outline.

...

If there is reasonable consensus for what we have thus far, among those interested in this library, I think we should start to work on some documentation so more people will take a look at the library.

There is a boost-sandbox CVS. Now after we have a common version ( Now it makes no sense develop my prototype further ) this would be a good place for our library. Or is the stage to early?

I think we should have some documentation first. Don't you agree? -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: Florian Stegner <FlSt@gmx.de>

Rob Stewart wrote:

...

From: Florian Stegner <FlSt@gmx.de>

...

Rob Stewart wrote:

...

From: Matthew Vogt <mattvogt@warpmail.net>

...

Matthew Vogt wrote:

I will try to summarize all types of multivalues:

any_of ( s ) <PRED> x -> is true if one or more elements of s satisfy the test "element <PRED> x"

Yes.

all_of( s ) <PRED> x -> is true all elements of s satisfy the test "element <PRED> x"

Yes.

none_of( s ) <PRED> x -> negation of any_of( a ): is false if one ore more elements of s satisfy[...]

Yes.

???_of( s ) <PRED> x-> negation of all_of( a ) ( in my implementation not_all_of( a ) ): is false if all elements of s satisfy[...]. This is

Yes.

still missing in your implementation. Your implementation of not_all is the negation of any_of.

I think it was a copy and paste error.

one_of( s ) <PRED> x -> is true if exact one element of s statisfy[...]

Yes.

n_of( n, s ) <PRED> x -> is true if exact n elements of s satisfy[...]

Yes.

some_of( n, m, s ) <PRED> x -> is true if more than n and less than m+1 elements of s satisfy[...]

I don't agree. Why the strange treatment of the two limits? We need to decide whether the count is inclusive, exclusive, or both (left inclusive, right exclusive). My assumption has been inclusive for both values.

From your description of each_of: Your implementation of all_of() is correct. I'm right? And each_of needs to refactored?

My all_of implementation was correct. I think we can eliminate each_of. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

I've uploaded an update to multivalues.zip in the vault. Changes: - percent_of() support for between and exactly - added less_than - added more_than - added between and exactly tests - fixed not_all_of implementation - untested supported for ordinary predicates -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: David Abrahams <dave@boost-consulting.com>

Rob Stewart <stewart@sig.com> writes:

...

Thus, all_of({1, 2, 3}) < any_of({3, 4}) means:

1 < 3: true 2 < 3: true 3 < 3: false 1 < 4: true 2 < 4: true 3 < 4: true result: true

But, each_of({1, 2, 3}) < any_of({3, 4}) means:

1 < 3: true 2 < 3: true 3 < 3: false 3 < 4: true result: true

IMO that's terribly confusing. The first one should be

all_of({1, 2, 3}) < one_of({3, 4})

And the second one should be

all_of({1, 2, 3}) < any_of({3, 4})

Hmmmm. That is what I'm after, isn't it. Fine: we should forget about each_of. Users simply need to formulate the expression correctly with the other operations. I'll have to look at the implementation to ensure we get that behavior when those types are mixed. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: Florian Stegner <FlSt@gmx.de>

Rob Stewart wrote:

...

From: FlSt@gmx.de

"n_m_of" uses anti-alphabetical ordering of the letters. That rather suggests the template argument order of maximum then minimum. Perhaps changing to "x_y_of" or "a_z_of" would be better?

Hmm... i,j,k are typical letters for indexes.. After that i_of and i_j_of are good choices.

Not all ranges are random access and we're not specifying two indices. We're instead specifying a maximum and minimum count. I rather liked the "subrange" or "subset" names that Matthew Vogt suggested (though he later recanted his suggestion of "subrange"). Unfortunately, those don't suggest the min/max counts needed. It occurs to me that most of these names are suggestive of creating a subrange ("i_j_of" suggests the i'th through j'th values in the range, for example) which then participates in the comparison. That, of course, isn't what happens. Instead, we need to indicate that between the minimum and maximum number of elements, inclusive, satisfy the predicate. As Matthew mentioned, the between(1, 2).items_of(a) spelling is clear, but I find it rather long compared to subrange_of<1,2>(a) or n_m_of<1,2>. Besides, we still need a name for the resulting type that users might need to put in a variable. In my library, there are these correspondences (Florian has a different set of names): function class template template -------- ---------- all_of all_values any_of any_value each_of each_value n_of n_values n_m_of n_m_values none_of no_values one_of one_value Thus, you could write: typedef std::set<int> range_type; range_type r; // populate r; all_values<range_type> const all(all_of(r)); What about n_m_of? n_m_values<range_type> const some(between(3, 5).items_of(r)); I picked "some" as the variable name. Would "some_of" work? some_values<range_type> const some(some_of(3, 5, r)); or some_values<range_type> const some(between(3, 5).items_of(r)); "exactly" has also been suggested n_values<range_type> const n(exactly(3).items_of(r)); as an alternative to n_values<range_type> const n(n_of(3, r)); Should that actually return a "some_values?" some_values<range_type> const n(exactly(3).items_of(r)); If we use "some_values" do we need "n_of" or "n_m_of?" They're shorter, but certainly not as clear. ("all," "none," and "one" provide efficiency, so I plan to keep them.) -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

Rob Stewart <stewart@sig.com> writes:

...

...

What about user-supplied predicates? You can't use infix notation then.

all_of(a)._(frobnicates, any_of(b))

all_of(a)._,frobnicates, any_of(b)

all_of(a)._ %frobnicates% any_of(b)

all_of(a)._ |frobnicates| any_of(b)

all_of(a)._ <frobnicates> any_of(b)

(etc)

That gives some notion of infix, but it seems entirely too contrived to me.

What about this:

all_of(a)(frobnicates, any_of(b))

It seems a little better.

I started there, but the placement of parens seems to arbitrary and unbalanced. Also, the whole point of infix is to get rid of those. -- Dave Abrahams Boost Consulting www.boost-consulting.com

Rob Stewart <stewart@sig.com> writes:

From: David Abrahams <dave@boost-consulting.com>

...

Rob Stewart <stewart@sig.com> writes:

...

all_of(a)(frobnicates, any_of(b))

I started there, but the placement of parens seems to arbitrary and unbalanced. Also, the whole point of infix is to get rid of those.

So you think this is better?

...

...

...

all_of(a)._,frobnicates, any_of(b)

Yes, but not as nice visually as all_of(a)._ <frobnicates> any_of(b)

Is the _ member needed?

It is if you're going to support all_of(a) , all_of(b) just the same way as you'd support all_of(a) > all_of(b) If you give up support for the comma operator, you can use it for this purpose.

What about this:

all_of(a)@frobnicates@any_of(b)

That only needs, using the type names from my library,

Needs what? A new language that supports the @ character? -- Dave Abrahams Boost Consulting www.boost-consulting.com

Rob Stewart <stewart@sig.com> writes:

From: David Abrahams <dave@boost-consulting.com>

...

Rob Stewart <stewart@sig.com> writes:

...

From: David Abrahams <dave@boost-consulting.com>

...

Rob Stewart <stewart@sig.com> writes:

...

all_of(a)(frobnicates, any_of(b))

I started there, but the placement of parens seems to arbitrary and unbalanced. Also, the whole point of infix is to get rid of those.

So you think this is better?

...

...

...

all_of(a)._,frobnicates, any_of(b)

Yes, but not as nice visually as

all_of(a)._ <frobnicates> any_of(b)

Maybe.

...

...

Is the _ member needed?

It is if you're going to support

all_of(a) , all_of(b)

just the same way as you'd support

all_of(a) > all_of(b)

Why would we need that? I don't see a use case for it.

Generality.

...

If you give up support for the comma operator, you can use it for this purpose.

I think that's viable.

...

...

What about this:

all_of(a)@frobnicates@any_of(b)

That only needs, using the type names from my library,

Needs what? A new language that supports the @ character?

Surely you understood I was using "@" as a placeholder for any overloadable, binary operator.

No I didn't. And stop calling me Surely. Anyway, that suffers the same issue as the comma. for which operators will all_of(a) @ any_of(b) be unsupported? -- Dave Abrahams Boost Consulting www.boost-consulting.com

From: David Abrahams <dave@boost-consulting.com>

Rob Stewart <stewart@sig.com> writes:

...

From: David Abrahams <dave@boost-consulting.com>

...

Rob Stewart <stewart@sig.com> writes:

...

From: David Abrahams <dave@boost-consulting.com>

...

Rob Stewart <stewart@sig.com> writes:

...

all_of(a)(frobnicates, any_of(b))

I started there, but the placement of parens seems to arbitrary and unbalanced. Also, the whole point of infix is to get rid of those.

So you think this is better?

...

...

> all_of(a)._,frobnicates, any_of(b)

Yes, but not as nice visually as

all_of(a)._ <frobnicates> any_of(b)

I updated my library to support user-supplied predicates. http://boost-sandbox.sourceforge.net/vault/index.php?action=downloadfile&filename=multivalues.zip&directory=rob_stewart& -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

I uploaded a new version to the sandbox file vault (junction/boost_junction_v10.zip). There was a bug in my detail::binary_op_type struct. I removed it ;-) Now all my test programs give the same results as Rob's implementation. An now it compiles faster .

Rob Stewart wrote:

From: FlSt@gmx.de

[...]

0. Your *junction classes need to be in your junctions namespace. I know Pavel questioned why they weren't in the detail namespace, but it is reasonable to think that some will want to create a variable to hold such an object for repeated comparisons.

Thats a good point. Hmm, but how should a client declare them? set<int> a; junction< disjunction< set< int > > > a_junction = all_of( a ); looks a little confusing. I would prefer something like disjunction< set< int > > a_junction; But this is not compatible with my junction<> - class. Do you have an idea?

1. Aside from the junction type in the base class, plus naming and stylistic differences, your library looks a great deal like mine.

It was a little funny: After I fixed my compilation time problems I looked at your implementation and saw that it was very similar to mine. Then I tried to bring the best ideas of both implementations together.

2. You don't have iterator range support yet.

This will be the next point I will work on.

3. Your detail::do_comparison() functions would be clearer if named "compare," don't you think?

Good idea. I don't remeber why I called them so.

4. I see that you've made good use of implementing one type in terms of another. I did that early on in my operator intensive version and ignored it after refactoring my library. I need to revisit that.

That was the thing which makes the 10% runtime differences between our implementations without optimizing.

5. Your n_m_junction do_comparison() tests against count <= M in the return statement unnecessarily. The loop is terminated with a return if count ever exceeds M.

You are right.

6. Do you like | better than ^ as the user-predicate delimiter? I didn't even examine the operator precedence when selecting one. ^ is higher than |, but both are higher than && and ||. That will force the use of parentheses in many expressions. Perhaps we should consider the comma.

Ok you are right, when you say it's important to examine the operator precedence. But the comma operator looks confusing: all_of(a) ,equal(), any_of(b). From the readability viewpoint I like the bitwise-or operator | more than the bitwise-xor operator ^. But now I'm a little bit confused. The precedence must be higher, or I'm wrong? For example someone writes: any_of( a ),equal(),all_of( b ) && any_of( c ),equal(),all_of(d); So all_of( b ) && any_of( c ) will be evaluated before the ",". If you write any_of( a )|equal()|all_of( b ) && any_of( c )|equal()|all_of(d) It will give the correct answer.

9. You have no operator << support. I figure that folks will want to be able to stream these objects if they create instances (see item 0).

I removed them, but it's no problem to add them again. I thought, there was no need for them. Ok could be useful for debugging.

11. You should name the "Range" template parameter "FwdRange" or "ForwardRange" to clarify that it needs to model the ForwardRange concept from Boost.Range.

Ok I aggree with that. Naming is important.

It would be nice if Boost.Range offered a ForwardRangeConcept concept checking class so we could use

function_requires< ForwardRangeConcept<FwdRange> >();

in the function templates and

BOOST_CLASS_REQUIRE(FwdRange, boost, ForwardRangeConcept);

in the class templates to help user's diagnose errors.

I think this is the correct forum to ask for such a feature ;-)

It's clear that you've adopted many ideas from my mails and library and you've brought many innovative ideas of your own. Great work!

Thanks. Sincerly Florian

Rob Stewart wrote:

From: Florian Stegner <FlSt@gmx.de>

...

Rob Stewart wrote:

Nah, like this:

set<int> a; all_values<set<int> > all_of_a(all_of(a));

I've nearly got that ready plus I'm using your dispatch technique. I'll upload it when I get it compiling.

...

...

...

2. You don't have iterator range support yet.

This will be the next point I will work on.

Take a look at mine. My next version will follow your dispatch technique, so you might just want to wait for that one.

I will wait. :-)

...

...

4. I see that you've made good use of implementing one type in terms of another. I did that early on in my operator intensive version and ignored it after refactoring my library. I need to revisit that.

That was the thing which makes the 10% runtime differences between our implementations without optimizing.

Mine is 10% faster or slower because of that? I've lost track of which is faster now.

Yours was faster. I think my implementation of the do_comparison functions for one_junction, n_junction, injunction and abjunction are the reason.

...

But now I'm a little bit confused. The precedence must be higher, or I'm wrong? For example someone writes: any_of( a ),equal(),all_of( b ) && any_of( c ),equal(),all_of(d); So all_of( b ) && any_of( c ) will be evaluated before the ",". If you write any_of( a )|equal()|all_of( b ) && any_of( c )|equal()|all_of(d) It will give the correct answer.

That's a good point. I was thinking about the lambda expressions one might write for the predicate. I suppose the use case you've mentioned is more important, so we should have higher precedence than the logical operators.

The operators with the highest precedence we can use are "*" "/" "%".... I think "/" would look fine: all_of( a ) /expr()/ any_of(b). But there is a little problem with lambdas expressions using this operators. I tried following example: any_of( a ) |( lambda::_2 >= lambda::_1 )| all_of( b ). I got an error message from gcc 4.0.1 that the call to the second |-operator is ambiguous, because also lamda implements the | operator. How can this be avoided? The only idea I have is the ","-operator. See below the error message. Antoher point is the naming. I think, after reading a book about logic, that "junction" would be the best name. Error message: junction_example.cpp:166: error: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second: /home/stegner/include/boost/lambda/detail/operators.hpp:117: note: candidate 1: const boost::lambda::lambda_functor<boost::lambda::lambda_functor_base<boost::lambda::bitwise_action<boost::lambda::or_action>, boost::tuples::tuple<typename boost::lambda::const_copy_argument<const A>::type, boost::lambda::lambda_functor<Arg>, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type> > > boost::lambda::operator|(const A&, const boost::lambda::lambda_functor<Arg>&) [with A = boost::junctions::junction<boost::junctions::detail::n_m_junction<2u, 3u, std::set<std::string, std::less<std::string>, std::allocator<std::string> > > >, Arg = boost::lambda::lambda_functor_base<boost::lambda::relational_action<boost::lambda::greaterorequal_action>, boost::tuples::tuple<boost::lambda::lambda_functor<boost::lambda::placeholder<2>

, boost::lambda::lambda_functor<boost::lambda::placeholder<1> >, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type> >] /home/stegner/include/boost/junctions/junction.hpp:76: note: candidate 2: boost::junctions::detail::partial_expr<JunctionType, Predicate> boost::junctions::junction< <template-parameter-1-1> >::operator|(const Predicate&) const [with Predicate = boost::lambda::lambda_functor<boost::lambda::lambda_functor_base<boost::lambda::relational_action<boost::lambda::greaterorequal_action>, boost::tuples::tuple<boost::lambda::lambda_functor<boost::lambda::placeholder<2> , boost::lambda::lambda_functor<boost::lambda::placeholder<1> >, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type> > >, JunctionType = boost::junctions::detail::n_m_junction<2u, 3u, std::set<std::string, std::less<std::string>, std::allocator<std::string> > >]

Sincerly Florian

"David Abrahams" <dave@boost-consulting.com> wrote

Rob Stewart <stewart@sig.com> writes:

...

...

all_of(a)._(frobnicates, any_of(b))

all_of(a)._,frobnicates, any_of(b)

all_of(a)._ %frobnicates% any_of(b)

all_of(a)._ |frobnicates| any_of(b)

all_of(a)._ <frobnicates> any_of(b)

...

all_of(a)(frobnicates, any_of(b))

Yuck and Yuck FWIW. AFAIK only prefix user defined operations work in C++. if ( frobnicates(all_of(a), any_of(b))) { frazzle(a); }else{ frazzle(b); } At least until user defined operators are allowed: frazzle a if all_of a frobnicates any_of b else frazzle b; But till then keep it simple please ! regards Andy Little

"David Abrahams" <dave@boost-consulting.com> wrote

"Andy Little" <andy@servocomm.freeserve.co.uk> writes:

...

if ( frobnicates(all_of(a), any_of(b))) {

You can't do that unless you ask people to put smarts about all_of and any_of inside of frobnicates. The goal is to use a general predicate such as std::less<int>()

Ok I see. Of course you can achieve this simply via one overloaded function. bool b1 = question<std::less>(all_of(a),any_of(b) ); bool b2 = question(frobnicates,all_of(a),any_of(b) ); The use of the dummy expression |frobnicates| is a poor substitute for a user defined operator. Should C++ incorporate a facility to define ones own operators? regards Andy Little

"David Abrahams" <dave@boost-consulting.com> wrote in message news:u64ujvtre.fsf@boost-consulting.com...

"Andy Little" <andy@servocomm.freeserve.co.uk> writes:

...

The use of the dummy expression |frobnicates| is a poor substitute for a user defined operator.

Best we can do today. And it's not bad, once you understand how the library works. Just like in Boost.Lambda a+b doesn't add anything: it builds a function object. Just like in Boost.Spirit the operators are used for parsing.

The inbuilt operator you choose to subvert influences how the expression is evaluated of course: #define OP1 |frobnicates| #define OP2 *frobnicates* int a=0,b=0; double c=0.,d=0.; a+c OP1 b+d; a+c OP2 b+d; regards Andy Little

"Rob Stewart" wrote:

...

if (more_than_half_of(a) >= more_than_half_of(b)) ... doesn't make sense.

It does to me.

Suppose a is the set of female students and b the male students. Further suppose that >= compares grades. Then the expression asks whether more than half of the girls got grades at least as high as more than half of the boys.

You are right. Seems my deductive thinking isn't as strong as I always thought. ________________________________________________________

...

...

...

if ( is_true_that(all_of(a), a_binary_functor, one_of(b)) ) ...

If you allow that, then symmetry cannot be guarranteed. There's already a question as to whether the operators must be symmetrical. I've posited that asymmetry will lead to confusion, but many comparisons sound asymmetrical. Consider these two expressions:

none_of(a) == any_of(b) // 1

any_of(a) == none_of(b) // 2

1. Sounds like it should be true if none of the values in a equal any value in b.

2. Sounds like it should be true if any of the values in a equals none of the values in b.

No, the (2) should be true if any value from 'a' cannot be equaled to some single value from 'b'. This would make it symetrical to (1). Say: a = green, blue, blue b = blue, red none_of(a) == any_of(b) is false because there is blue (even 2 of them) from 'a' that match something in 'b' any_of(a) == none_of(b) is false because there are two different cases when blue from 'a' is in 'b'. Not because 'b' lacks 2 blues. IOW any_of() should care about cardinality. For the any_of(s1) == one_of(s2) one_of(s2) == any_of(s1) I think the "one_of" should read as "exactly_one_and_only_one_of" and "any_of" as "any_individual_item_of" This should restore the symetry. This is my understanding how these qualifiers should be implemented and thought about. The other interpretation didn't occured to me but perhaps I am still missing the 'aha!' moment. I didn't study the implementation deep enough (I would need to step through) but it should be symetrical.

Perhaps we should consider a functional style:

if (compare(all_of(a), one_of(b), _1 >= _2))

That would be if (compare(_1 >= _2, all_of(a), one_of(b))) woudn't it? ________________________________________________________

...

...

if (evaluate(all_of(a).where(filter1) , _1 >= _2 , one_of(b).where(filter2))) ...

That may be true, but I'm concerned about duplicating functionality and, thus, limiting flexibility. I guess we just need to be sure that this library interoperates easily with filters created using the facilities of the other libraries.

IMO syntax should decide what to use. If filter iterator is as easy to use as hypothetical embedded filter than I am all for for it. Expression that could be written on single line it is much prefered to alternatives: vector<int> a; set<int> b; if ( is_true_that(any_of(a), _1 * 2 >= _2, all_of(b)).where(_1 >= 0 && _2 > 10) ) { is still somehow readable (as long as the filter is simple). /Pavel

"Pavel Vozenilek" <pavel_vozenilek@hotmail.com> writes:

...

2. Sounds like it should be true if any of the values in a equals none of the values in b.

That sounds right to me.

No, the (2) should be true if any value from 'a' cannot be equaled to some single value from 'b'. This would make it symetrical to (1).

That sounds completely counterintuitive.

Say: a = green, blue, blue b = blue, red

none_of(a) == any_of(b) is false because there is blue (even 2 of them) from 'a' that match something in 'b'

any_of(a) == none_of(b) is false because there are two different cases when blue from 'a' is in 'b'.

No, it should be true, because there is something in a that is equal to nothing in b. any_of(x) == whatever should always be equivalent to x[0] == whatever x[1] == whatever x[2] == whatever Anyway, saying that symmetry requires none_of(a) == any_of(b) to be equivalent to any_of(a) == none_of(b) is about as valid as saying 3*x == 1+y must be equivalent to 1+x == 3*y It makes no sense to me. -- Dave Abrahams Boost Consulting www.boost-consulting.com

...

...

...

...

"David" == David Abrahams <dave@boost-consulting.com> writes: > Anyway, saying that symmetry requires > none_of(a) == any_of(b) > to be equivalent to > any_of(a) == none_of(b) > is about as valid as saying > 3*x == 1+y > must be equivalent to > 1+x == 3*y > It makes no sense to me.

But it does break symmetry when none_of(a) == any_of(b) [no x in a equals to any y in b] is different from any_of(b) == none_of(a) [some x in b equals to nothing in a]

Liu Jin <cpp@vip.163.com> writes:

...

...

...

...

...

"David" == David Abrahams <dave@boost-consulting.com> writes: > Anyway, saying that symmetry requires > none_of(a) == any_of(b) > to be equivalent to > any_of(a) == none_of(b) > is about as valid as saying > 3*x == 1+y > must be equivalent to > 1+x == 3*y > It makes no sense to me.

But it does break symmetry when none_of(a) == any_of(b) [no x in a equals to any y in b] is different from any_of(b) == none_of(a) [some x in b equals to nothing in a]

Yes. But as I said earlier, I don't think it's important for == to be symmetric in this case. You had no problem reading the different meanings of those two expressions. Unless people start putting any_of(b) in containers (which we can easily prevent) I think the risk of having an assymetric equality operator is vanishingly low. -- Dave Abrahams Boost Consulting www.boost-consulting.com

"Rob Stewart" wrote:

We presently support these operations:

all any each n_m n none not_all one

...

|each | if each succeeds independently, the expression | | is true

I didn't find time to study neither of the current implementations (you both code faster than I can read ;-) so I am bit confused by the difference between "each" and "all". "all_except_one" is quite common situation which may be considered too. Is the "more_of(x) < more_of(y)" feature implementable?

How do these look?

at_least(n).of(a) between(x, y).of(a) exactly(n).of(a) less_than(n).of(a) more_than(n).of(a)

The "of" may be easily overlooked. A "item_of" or so would be harder to miss.

Should we include "percent_of?"

With this (or "fraction_of" or so) user won't be bothered to extract size of a range manually. His code would be bit simpler. If the range size is hard to compute (some std::list implementations) it may be also more efficient.

Should we provide the alternate spellings like "at_least," "more_than," and "one?"

IMO yes. It would allow user to pick the best word in given context (Or at least ability to use a convenient word w/o searching through documentation for the oficially blessed variant.) ----------------------- Will it be possible to have one range in the expressions above fitting InputIterator model? For example: none_of(integers_stored_in_large_and_slow_file) > any_of(values) Perhaps the library may detect such situation and work around the InputIterator limitations. Alternatively: would be possible to give a hint to the algorithm which range is larger (more expensive to traverse) to optimize the result? Say something as: none_of(a).traverse_once() > all_of(b) /Pavel

From: FlSt@gmx.de

Pavel Vozenilek wrote:

...

"Rob Stewart" wrote

I didn't find time to study neither of the current implementations (you both code faster than I can read ;-) so I am bit confused by the difference between "each" and "all".

When I wouln't know the implementation I would be also confused. each_of means the same like not_all_of in my implementation.

My suggestion for each_of was to handle the situation in which each could match independently, whereas with all_of, each must match the same other value. IOW, given ranges L and R, each_of(L) == any_of(R) means that each value in L may match any value in R, whereas all_of(L) == any_of(R) means each value in L must match any single value in R. Thus, if L[n] == R[m] for any n in L and m in R, each_of(L) == any_of(R) is true. However, for all_of(L) == any_of(R), all values of L must equal R[m] for any m in R. Does that make sense?

...

"all_except_one" is quite common situation which may be considered too.

This is also the same like not_all_of

No. "all_except_one," or maybe "all_but_one," means exactly N - 1 matches, where N is the length of the range. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: Florian Stegner <FlSt@gmx.de>

Rob Stewart wrote:

...

From: FlSt@gmx.de

My suggestion for each_of was to handle the situation in which each could match independently, whereas with all_of, each must match the same other value. IOW, given ranges L and R, each_of(L) == any_of(R) means that each value in L may match any value in R, whereas all_of(L) == any_of(R) means each value in L must match any single value in R. Thus, if L[n] == R[m] for any n in L and m in R, each_of(L) == any_of(R) is true. However, for all_of(L) == any_of(R), all values of L must equal R[m] for any m in R.

Now I understand it. If you compare our implementations, this is exactly what not_all_of in my implementation does.

Does that mean that your not_all_of presently means all, but each taken individually, like my each_of, and that you will change it to mean any number less than all? Or have I misunderstood what you were saying?

...

...

...

"all_except_one" is quite common situation which may be considered too.

This is also the same like not_all_of

No. "all_except_one," or maybe "all_but_one," means exactly N - 1 matches, where N is the length of the range.

Yes your are right. It is the same like one_of where the result of the predicate is negated. I wouldn't add too much xxx_of operators, because the most expressions of them can be formulated with others. one_of( a ) > x means the same as all_except_one( a ) <= x

We can get to the point of adding too many *_of operations, but we do need to cover the common ones. Certainly all_but_one is the same as one_of after negating the predicate, but it may prove to be sufficiently common that users will want it. It's a balancing act, but if there's enough interest, it is better that we define the operation once in the library. Perhaps the right initial approach is to provide those needed to build everything one might need, plus a few very common simplifying ones, and perhaps document the others that one could define. We'll also want to document how to create new ones. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;

From: Paul <elegant_dice@yahoo.com>

Rob Stewart wrote:

...

From: FlSt@gmx.de

If I read this correctly, Rob's interpretation of the set algebra is slightly incorrect.

...

...

( any_of( a ) >= any_of( b ) ) <= any_of( c )

Or if the comparison returns an container:

any_of( any_of( a ) >= any_of( b ) ) <= any_of( c )

Why would you write those? What do they mean?

any_of(a) >= any_of(b) would return a subset of values from 'a', where those items are >= than any item in 'b'.

We have been discussing expressions that return a bool, not a subset, for quite some time. You snipped quite a bit of context, so I'm not sure how old this discussion really is.

You can't do this:

...

(any_of(a) >= min_element(b)) <= max_element(c)

because you are placing a total-ordering requirement on all sets.

I don't know what interpretation you're referring to; you apparently snipped something from my reply. Otherwise, I was just questioning the value of such an expression.

what if the sets only satisfy the partial-ordering definition?

Example, let there be b[i] < b[j], but a[k] < b[i] and a[k] > b[j]. So the any_of/any_of variant's result would include a[k] (a[k] > b[j]) but min_element won't, as a[k] < min_element (which is b[i])

Possibly so, but that's for a different library than we are now discussing. -- Rob Stewart stewart@sig.com Software Engineer http://www.sig.com Susquehanna International Group, LLP using std::disclaimer;