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

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

On Fri, 22 Jan 2010 14:13:31 -0800 Jeffrey Hellrung <jhellrung_at_[hidden]>
wrote:
On 1/23/10 12:35 AM, boost-request_at_[hidden] 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?
>> 
>> Is a smarter realization of this as an algorithm a potential candidate for
>> boost::algorithm?
> 
> 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 (!>=) == (<)).

On Fri, 22 Jan 2010 15:24:32 -0800 Marshall Clow <mclow.lists_at_[hidden]>
wrote:
> I've got this floating around from a while back...
>
> [ examples omitted ]

Marshall and Jeff:

Thanks for the feedback. Marshall's feedback seems to indicate that, yes,
there is likely general utility need for such functions and Jeff, you are
correct that these algorithms are trivially composed from
std::adjacent_find, std::not2 and
std::{greater,less,greater_equal,less_equal}:

    namespace boost {
    
        namespace detail {
    
            template <typename ForwardIterator, typename BinaryPredicate>
            bool
            is_creasing(ForwardIterator first, ForwardIterator last,
                        BinaryPredicate binary_pred)
            {
                return std::adjacent_find(first,
                                          last,
                                          std::not2(binary_pred)) == last;
            }
    
        } // namespace detail
    
        template <typename ForwardIterator>
        bool
        is_increasing(ForwardIterator first, ForwardIterator last)
        {
            typedef typename std::iterator_traits<ForwardIterator>::
                value_type value_type;
    
            return detail::is_creasing(first,
                                       last,
                                       std::less_equal<value_type>());
        }
    
        [ ... other three instances follow trivially ... ]
    
    } // namespace boost

Unless there's any other feedback, I'll work on posting an implementation to
Boost Vault.

Regards,

Grant