RFC: Sequence Properties and Boost Algorithm/Functional
For a recent project, I needed to inquire about a sequence of objects and make a determination as to whether the sequences were: * Increasing * Strictly Increasing * Decreasing * Strictly Decreasing Looking through STL, Boost documentation, Boost sources and headers and the Boost mailing lists I was able to find neither an existing algorithm or stateful unary predicate functor for accomplishing this for a pair of input iterators. However, I was a bit surprised considering that this seems like a sequence property query that would tend to come up fairly often and serve a general utility. Did I just fail to form the proper search/query or am I overestimating the general utility? Regardless, I forged ahead with the rather naïve implementation (see below), which can be used as a predicate with for_each as shown: const int strictlyIncreasingValues[] = { 1, 2, 3, 4, 5 }; bool isStrictlyIncreasing; isStrictlyIncreasing = std::for_each(strictlyIncreasingValues, strictlyIncreasingValues + 5, is_strictly_increasing<int>()); assert(inStrictlyIncreasing == true); However, acknowledging the inefficient and naïveté of the first implementation, this is probably more algorithm than functional in that for_each with a stateful predicate is wasteful in walking the entire sequence (i.e. if any arbitrary subsequence fails to meet the property predicate criteria, the whole sequence fails). Is a smarter realization of this as an algorithm a potential candidate for boost::algorithm? Naïve, inefficient functional implementation to be used with for_each: #include <functional> #include <boost/function.hpp> template <typename T> struct creasing : public unary_function<T, bool> { protected: typedef unary_function<T, bool> base_type; typedef typename base_type::argument_type argument_type; typedef typename base_type::result_type result_type; typedef boost::function<result_type (const argument_type &a, const argument_type &b)> binary_predicate; creasing(const binary_predicate & inPredicate) : base_type(), mPredicate(inPredicate), mCreasing(true), mInited(false), mLast() { return; } public: result_type operator()(const argument_type & x) { if (mCreasing) { if (mInited) { mCreasing = mPredicate(mLast, x); } else { mCreasing = true; mInited = true; } mLast = x; } return (mCreasing); } operator result_type() const { return (mCreasing); } private: const binary_predicate mPredicate; result_type mCreasing; result_type mInited; argument_type mLast; }; template <typename T> struct is_increasing : public creasing<T> { typedef creasing<T> base_type; typedef typename base_type::argument_type argument_type; is_increasing(void) : base_type(std::less_equal<argument_type>()) {} }; template <typename T> struct is_decreasing : public creasing<T> { typedef creasing<T> base_type; typedef typename base_type::argument_type argument_type; is_decreasing(void) : base_type(std::greater_equal<argument_type>()) {} }; template <typename T> struct is_strictly_increasing : public creasing<T> { typedef creasing<T> base_type; typedef typename base_type::argument_type argument_type; is_strictly_increasing(void) : base_type(std::less<argument_type>()) {} }; template <typename T> struct is_strictly_decreasing : public creasing<T> { typedef creasing<T> base_type; typedef typename base_type::argument_type argument_type; is_strictly_decreasing(void) : base_type(std::greater<argument_type>()) {} }; Regards, Grant
Grant Erickson wrote:
For a recent project, I needed to inquire about a sequence of objects and make a determination as to whether the sequences were:
* Increasing * Strictly Increasing * Decreasing * Strictly Decreasing
Looking through STL, Boost documentation, Boost sources and headers and the Boost mailing lists I was able to find neither an existing algorithm or stateful unary predicate functor for accomplishing this for a pair of input iterators. However, I was a bit surprised considering that this seems like a sequence property query that would tend to come up fairly often and serve a general utility. Did I just fail to form the proper search/query or am I overestimating the general utility?
Regardless, I forged ahead with the rather naïve implementation (see below), which can be used as a predicate with for_each as shown: <snip> Regards,
Grant
Perhaps std::adjacent_find and std::less is all you need, e.g., to determine if a sequence is decreasing? I.e., a sequence is decreasing iff all adjacent pairs of elements xi, x[i+1] satisfies xi >= x[i+1] iff no adjacent pair of elements xi, x[i+1] satisfies xi < x[i+1] (assuming that (!>=) == (<)). - Jeff
On Jan 22, 2010, at 2:02 PM, Grant Erickson wrote:
For a recent project, I needed to inquire about a sequence of objects and make a determination as to whether the sequences were:
* Increasing * Strictly Increasing * Decreasing * Strictly Decreasing
Looking through STL, Boost documentation, Boost sources and headers and the Boost mailing lists I was able to find neither an existing algorithm or stateful unary predicate functor for accomplishing this for a pair of input iterators. However, I was a bit surprised considering that this seems like a sequence property query that would tend to come up fairly often and serve a general utility. Did I just fail to form the proper search/query or am I overestimating the general utility?
I've got this floating around from a while back (as well as the other three - increasing, decreasing, and strictly_decreasing ). Maybe these should go in the algorithms library: template<typename T> bool is_strictly_increasing ( T* begin, T* end ) { // Empty sequences are strictly increasing if ( begin == end ) return true; T* iter = begin; T val = *iter++; while ( iter != end ) { if ( ! ( *iter > val )) return false; val = *iter++; } return true; } template<typename I> bool is_strictly_increasing ( I begin, I end ) { // Empty sequences are strictly increasing if ( begin == end ) return true; I iter = begin; typename I::value_type val = *iter++; while ( iter != end ) { if ( ! ( *iter > val )) // if ( val >= *iter ) return false; val = *iter++; } return true; } -- Marshall
On Jan 22, 2010, at 3:24 PM, Marshall Clow wrote:
On Jan 22, 2010, at 2:02 PM, Grant Erickson wrote:
For a recent project, I needed to inquire about a sequence of objects and make a determination as to whether the sequences were:
* Increasing * Strictly Increasing * Decreasing * Strictly Decreasing
Looking through STL, Boost documentation, Boost sources and headers and the Boost mailing lists I was able to find neither an existing algorithm or stateful unary predicate functor for accomplishing this for a pair of input iterators. However, I was a bit surprised considering that this seems like a sequence property query that would tend to come up fairly often and serve a general utility. Did I just fail to form the proper search/query or am I overestimating the general utility?
I've got this floating around from a while back (as well as the other three - increasing, decreasing, and strictly_decreasing ). Maybe these should go in the algorithms library:
template<typename T> bool is_strictly_increasing ( T* begin, T* end ) { // Empty sequences are strictly increasing if ( begin == end ) return true;
T* iter = begin; T val = *iter++;
while ( iter != end ) { if ( ! ( *iter > val )) return false; val = *iter++; } return true; }
Funny that. Three minutes after posting my code, I noticed that I worked all the comparisons to use ">" (and the code *does* work), rather than using "<" (or std::less), which is what I meant to do when I wrote this code. Nothing like showing your work to a large audience to find problems. -- Marshall
Marshall Clow wrote:
On Jan 22, 2010, at 3:24 PM, Marshall Clow wrote:
template<typename T> bool is_strictly_increasing ( T* begin, T* end ) { // Empty sequences are strictly increasing if ( begin == end ) return true;
T* iter = begin; T val = *iter++;
while ( iter != end ) { if ( ! ( *iter > val )) return false; val = *iter++; } return true; }
Three minutes after posting my code, I noticed that I worked all the comparisons to use ">" (and the code *does* work), rather than using "<" (or std::less), which is what I meant to do when I wrote this code.
On that subject, why not use std::iterator_traits<I>::value_type in your iterator version and eliminate the pointer specialization? _____ 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.
Hi, Marshall,
Maybe these should go in the algorithms library:
Sounds good to me! Do you think "classifying" algorithms should get their own namespace in algorithms, or just live in boost::algorithm? While I'm at it, some of the feedback we've previously gotten has asked for "more algorithms", but not really said which ones people would like. So far, the collection represents "STL style" things that are commonly used and/or often useful. What are some suggestions? _Jesse Williamson ;-};
participants (5)
-
Grant Erickson -
Jeffrey Hellrung -
Jesse Williamson -
Marshall Clow -
Stewart, Robert