AMDG Stewart, Robert wrote:

What about types that only support operator <? They are pretty common and operator >, operator >=, and operator <= can be implemented in terms of operator <, right? (Obviously, detecting whether the other operators are defined and using them is better. Using a provided operator <= likely would be more efficient than synthesizing it from operator <. The others are less likely to differ in efficiency.)

Why is <= likely to be less efficient when implemented in terms of operator<? a <= b == !(b < a) In Christ, Steven Watanabe

On 1/25/10 6:18 AM, Stewart, Robert wrote:

Grant Erickson wrote:

...

The creasing algorithm templates define four template functions for determining the order properties of sequences, specifically:

* Increasing * Decreasing * Strictly Increasing * Strictly Decreasing

The implementation is a fairly trivial composition of the STL adjacent_find, not2 and {greater,less,greater_equal,less_equal}.

What about types that only support operator <? They are pretty common and operator >, operator >=, and operator <= can be implemented in terms of operator <, right?

Rob: Thanks for the prompt feedback. Regarding the fundamental nature of operator < and the syntactic sugar that is operators >, ¾ and „, sure: x > y -> y < x x ¾ y -> !(y < x) x „ y -> !(x < y)

(Obviously, detecting whether the other operators are defined and using them is better.

I am familiar with type traits; however, I am not familiar with operator traits. Are you suggesting a (pseudocode) implementation such as: template <typename ForwardIterator> bool is_increasing(ForwardIterator first, ForwardIterator last) { typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; if (is_less_equal_comparable<value_type>) { return detail::is_creasing(first, last, std::less_equal<value_type>()); } else { return detail::is_creasing(first, last, std::not2( swizzle( std::less<value_type>())); } }

Using a provided operator <= likely would be more efficient than synthesizing it from operator <. The others are less likely to differ in efficiency.)

You could simply require all four operators, given the existence of Boost.Operators, but it would be easy enough to support a wider range of types with this library.

Failing the above example, if you could provide a more concrete example, I'd welcome that. Best, Grant

Joachim Faulhaber wrote:

Hi Grant,

2010/1/24 Grant Erickson <gerickson@nuovations.com>:

...

The creasing algorithm templates define four template functions for determining the order properties of sequences, specifically:

   * Increasing    * Decreasing    * Strictly Increasing    * Strictly Decreasing

in your implementation of 'creasing' you provide the four specific algorithms is_[strictly_]{in_,de_}creasing while hiding the general algorithm is_creasing in namespace detail.

I'd suggest to implement only the latter. This would make your extension both more minimal and more general.

template <typename ForwardIterator, typename BinaryPredicate> bool is_ordered(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred) { return std::adjacent_find(first, last, std::not2(binary_pred)) == last; }

This looks a lot like the is_sorted algorithm from n3000: template<class ForwardIterator, class Compare> bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp); which also includes is_sorted_until: template<class ForwardIterator, class Compare> ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);

On 1/27/10 7:45 AM, Joachim Faulhaber wrote:

2010/1/27 Eric MALENFANT <Eric.Malenfant@sagem-interstar.com>:

...

Joachim Faulhaber wrote:

...

2010/1/24 Grant Erickson <gerickson@nuovations.com>:

...

The creasing algorithm templates define four template functions for [..]

in your implementation of 'creasing' you provide the four specific algorithms is_[strictly_]{in_,de_}creasing while hiding the general algorithm is_creasing in namespace detail.

I'd suggest to implement only the latter. This would make your extension both more minimal and more general.

template <typename ForwardIterator, typename BinaryPredicate> bool is_ordered(ForwardIterator first, ForwardIterator last,   BinaryPredicate binary_pred) {   return std::adjacent_find(first, last,       std::not2(binary_pred)) == last; }

This looks a lot like the is_sorted algorithm from n3000:

   template<class ForwardIterator, class Compare>    bool is_sorted(ForwardIterator first, ForwardIterator last,                   Compare comp);

which also includes is_sorted_until:

   template<class ForwardIterator, class Compare>    ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,                                    Compare comp);

Thank you for this hint. I think this is what we need to express sortedness or orderedness.

Eric and Joachim: Agreed that these completely satisfy the problem at hand. I also note that boost currently has: boost/detail/algorithm.hpp which contain variant implementations. What is the best process for getting these "detail" implementations and/or N3000 proposals promoted into full-fledged implementations in Boost? Regards, Grant

On 1/27/10 11:03 PM, vicente.botet wrote:

I would made a ticket on the tract system requesing what you want. As already implemented (at least in part) it is possible that a review be not needed.

Vincente: A great idea. Reference at: https://svn.boost.org/trac/boost/ticket/3873 Regards, Grant

Simonson, Lucanus J wrote:

Joachim Faulhaber wrote:

...

2010/1/24 Grant Erickson <gerickson@nuovations.com>:

...

The creasing algorithm templates define four template functions for determining the order properties of sequences, specifically:

* Increasing * Decreasing * Strictly Increasing * Strictly Decreasing

I'd suggest to implement only the latter. This would make your extension both more minimal and more general.

I'm a little confused why there is such a narrow focus on ordering relationships here. What seems to be the most

Why is it confusing? The OP focused the thread and no one generalized it beyond the is_ordered idea.

general solution to this is a generic range adaptor that given a range over elements of type T returns an adapted range over pairs of elements of type T that are adjacent to eachother in the input range. I'm constantly writing such adaptors to convert polygon vertices to polygon edges as pairs of vertices. Combine that with a foreach or just a while loop and you can apply the predicate. We can

You say that like there's no code involved.

generalize the adjacent-pair-range-adaptor seperately from the foreach-element-in-a-range-apply-functor algorithm.

OK. Doing that doesn't preclude handy tools like is_ordered, however.

As it happens we have boost libraries that provide a basis for each of these generally useful constructs. It seems a little pointless to propose a library to combine them to solve a very specific problem. Nobody is at a loss as to how to code up something to figure out whether elements in an iterator range are sorted, and nobody would or even should look in boost for such a simple thing.

If you say so. I don't happen to agree. Unless one does such a thing with any regularity, one must find a recipe or reinvent it again each time. Your statement seems rather like suggesting that std::for_each shouldn't be in the Standard Library because "nobody is at a loss as to how to code up something" to do such a loop.

Did the author skip the determining interest step and ask for a review prematurely, or am I missing something about the proposed library?

Any time a library can provide a useful, robust, *named* solution to a common problem, it seems worthwhile. As could be seen from this thread, using std::adjacent_find was not immediately obvious, so there is room to write less than optimal solutions, making a Boost library solution helpful. Furthermore, if there are any compiler-specific quirks that should arise, the library can account for those and user code need not do so. Have I missed something in your concern? Do you still disagree with including such tools in Boost, possibly in addition to your generalization? _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

Simonson, Lucanus J wrote:

Stewart, Robert wrote:

...

Simonson, Lucanus J wrote:

...

...

I'm a little confused why there is such a narrow focus on ordering relationships here. What seems to be the most

Why is it confusing? The OP focused the thread and no one generalized it beyond the is_ordered idea.

...

general solution to this is a generic range adaptor that given a range over elements of type T returns an adapted range over pairs of elements of type T that are adjacent to eachother in the input range. I'm constantly writing such adaptors to convert polygon vertices to polygon edges as pairs of vertices. Combine that with a foreach or just a while loop and you can apply the predicate. We can

You say that like there's no code involved.

I'm paraphrasing, but given the adaptor and foreach the solution is a one liner:

foreach_with_early_termination(a in pair_range_adapt(input_range)), predicate());

To write that requires knowledge of foreach_with_early_termination, pair_range_adapt, whatever "a in pair_range_adapt(input_range)" means in code, and the correct way to wire them together. is_ordered looks quite compelling by contrast. That code looks almost write only. I'd expect a comment explaining it each time it appeared, so why not create a named algorithm that makes the code self documenting?

...

...

As it happens we have boost libraries that provide a basis for each of these generally useful constructs. It seems a little pointless to propose a library to combine them to solve a very specific problem. Nobody is at a loss as to how to code up something to figure out whether elements in an iterator range are sorted, and nobody would or even should look in boost for such a simple thing.

If you say so. I don't happen to agree. Unless one does such a thing with any regularity, one must find a recipe or reinvent it again each time. Your statement seems rather like suggesting that std::for_each shouldn't be in the Standard Library because "nobody is at a loss as to how to code up something" to do such a loop.

You can take my statement and apply the falicy of taking to an absurd extreme, but that doesn't prove anything. In your example for_each is a more general feature than the proposed library. We could similarly say that for loops are not needed in the language because while loops can always get the job done and nobody is at a loss as to how. This misses the point of what I was saying.

I don't think I was being absurd or extreme, or that I missed the point. I was trying to make the point that something specific is often much easier to use -- and find, for that matter -- than a more generalized solution.

...

Any time a library can provide a useful, robust, *named* solution to a common problem, it seems worthwhile. As could be seen from this thread, using std::adjacent_find was not immediately obvious, so there is room to write less than optimal solutions, making a Boost library solution helpful. Furthermore, if there are any compiler-specific quirks that should arise, the library can account for those and user code need not do so.

Have I missed something in your concern? Do you still disagree with including such tools in Boost, possibly in addition to your generalization?

Creating a named solution for a problem incurrs a cost in complexity in addition to a benefit. The benefit of convenience of having a named solution for a problem people face regularly needs to be greater than the cost of learning the name for all the people who need the solution. In this

That's not quite accurate. Those that know the general tools and find their assembly obvious and straightforward, can always use the general tools. Those that only want to determine whether a sequence is ordered are likely to look for is_ordered or use some search terms that easily locate it. That algorithm will be easy to understand for the simple purpose at hand.

case I think the proposed library fails the test. I find it easier to figure out how to code up whether a iterator range is sorted based on the stl alone, or on general boost capabilities than to remember a name, order of arguments and header file to include to get a library solution. In this

You propose that all must follow that approach though not all will find things as easy to figure out as you? Most folks I know of would not even begin to think in the terms you've outlined.

particular case all four uses for creasing are covered by std::is_sorted directly with predicate less<T>, greater<T>, less_equal<T> and greater_equal<T>. If you pass greater_equal<T> to is_sorted it returns true only if all elements in the range are decreasing and there are no duplicates. Now, I agree that is_sorted(b, e, greater_equal<T>()) is kind of hard to understand as meaning decreasing with no duplicates, rather than write a new library function it would be better to put /*decreasing with no duplicates*/ preceding that line in your code. So the named solution in this case is to the problem that people don't know to use the existing named solution? I hardly think adding more named solutions is going to solve that problem.

It could well be that is_ordered is sufficient, as Joachim suggested, given the set discussed before you joined the thread, but only if there were specific examples in the documentation to show how and why to use those four predicates. However, is_ordered remains far easier to grasp and use than what you described above. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

Joachim Faulhaber wrote:

'is_sorted' is an important predicate. But it lives as an invariant to be maintained rather than a function to computed. So we have happily coded all kinds of sorted things without explicitly using and not necessarily needing it.

My question: Other than inside BOOST_ASSERTS, where do we really need is_sorted in production code. Are there convincing use cases?

That's an excellent question. I, too, foresaw its usefulness in assertions. I can imagine those doing DBC would like it, too. However, I can imagine examining file, network, or user input to ensure the data fits some ordering criteria, too. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

Joachim Faulhaber wrote:

...

That's an excellent question. I, too, foresaw its usefulness in assertions. I can imagine those doing DBC would like it, too. However, I can imagine examining file, network, or user input to ensure the data fits some ordering criteria, too.

. . . more of the (initially) asserting-the-invariant type of use.

The latter were not, in my mind, assertion uses, but rather run-time, production code tests to determine whether to accept or reject an input.

Yet, the question no longer is: Is "is_sorted" (aka is_ordered, is_creasing) an important predicate, that needs to be included into boost algorithms, because *it already is*. As Grant hinted there is boost::is_sorted in boost/detail/algorithm.hpp. Moreover std::is_sorted is in the sgi-stl

That's nearly the same as *not* being in Boost as its being in the detail directory implies that it is an unsupported implementation detail.

and std::is_sorted will probably be in the new standard (see N3000): So is_creasing is ceasing I dare say.

The round number confused me when I saw it before and I didn't take the time to check on it. I now understand N3000 to be a reference to a standards process document, which means that only now do I understand that is_sorted is likely coming in C++1x. Because folks will continue to use C++98/03 for some time, it is reasonable for Boost to provide a fallback for what's to come. Consequently, there's room yet to put this predicate into Boost.

Remains the question, if the variants of is_[strictly_]{in_,de_}creasing are to be added as algorithms, which conjures up another intersting question:

Are there criteria to be fulfilled to maintain the minimality of a set of free algorithms?

I understand the desire to keep the set small enough to be manageable, but it should be large enough to avoid the need to repeat (and rediscover) common recipes. Are those four predicates sufficiently useful to justify being documented, tested, and maintained in Boost? If not, they can be illustrated as examples for use of is_sorted. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.

Joachim Faulhaber wrote:

2010/1/27 Stewart, Robert <Robert.Stewart@sig.com>:

...

Joachim Faulhaber wrote:

...

...

Are there criteria to be fulfilled to maintain the minimality of a set of free algorithms?

I understand the desire to keep the set small enough to be manageable,

I think the clearness of the library interfaces is very important and the quest for criteria and guidelines is helpful.

I wasn't discounting your quest. I was contributing to it, or so I intended. Among the goals are to ensure the set is as small as possible, to keep documentation, testing, and maintenance burdens as low as possible, while ensuring the set provides complete coverage. The former I considered part of "manageable." The latter covers this part:

...

but it should be large enough to avoid the need to repeat (and rediscover) common recipes.

...

Are those four predicates sufficiently useful to justify being documented, tested, and maintained in Boost? If not, they can be illustrated as examples for use of is_sorted.

I'd prefer the latter.

I'm in no position to argue otherwise. I hope we get broader input for the decision, though. Lacking that, when is_sorted is made a first class predicate, there should be a (fast track?) review in which the question of including is_strictly_decreasing, etc., can be posed. That, perhaps, will get a broader response. I don't know whether the N3000 version differs, but it should be the one we use, if so, even at the cost of having to change existing Boost code. In order to provide backward compatibility, with automatic use of C++1x implementations when available, something akin to Boost.TR1 is needed. That implies more than a fast track review. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.