[boost] RFC: Sequence Properties and Boost Algorithm/Functional

Subject: [boost] RFC: Sequence Properties and Boost Algorithm/Functional
From: Grant Erickson (gerickson_at_[hidden])
Date: 2010-01-22 17:02:32

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