Re: [boost] [Review:Algorithms] Order of args to clamp

Subject: Re: [boost] [Review:Algorithms] Order of args to clamp
From: Dave Abrahams (dave_at_[hidden])
Date: 2011-09-25 21:25:05

on Sun Sep 25 2011, "Jeffrey Lee Hellrung, Jr." <jeffrey.hellrung-AT-gmail.com> wrote:

> On Sun, Sep 25, 2011 at 10:48 AM, Dave Abrahams <dave_at_[hidden]> wrote:
>
>>
>> on Sun Sep 25 2011, Steven Watanabe <watanabesj-AT-gmail.com> wrote:
>>
>> >> Here's an exercise:
>> >>
>> >> 1. Write down the documentation for both the multi-type and single-type
>> >>    "clamp" algorithms.  Describe both the concept requirements on the
>> >>    algorithm parameters, and the result of each algorithm (without
>> >>    making reference to its implementation).
>> >>
>> >
>> > It seems fairly straightforward.  All that's necessary
>> > is to require that comparing objects of different types
>> > is equivalent to converting to the same type and then
>> > comparing and define the result to be the same as though
>> > we converted first and called the single type version.
>>
>> So, do the exercise.  And, BTW, which of the types involved is "the same
>> type" in this case?
>>
>
> Okay, I'll try.
>
> clamp(T x, L lo, H hi) -> common_type<T,L,H>::type
>
> Let U = common_type<T,L,H>::type.

Okay, so this is an algorithm on types for which
common_type<T,L,H>::type is well-defined?  

I'm already suspicious about the semantic validity of a
HasCommonType<X,Y> concept, but I'll let it slide for now.

> Precondition:  operator< defines an ordering on objects of type U.   For any
> 2 objects a and b of types A and B, respectively, where A and B are each one
> of {T,L,H}, a < b is equivalent to (U)a < (U)b.  !(hi < lo).
>
> [Note: I'm not sure yet precisely what "ordering" would be desired
> here (probably a "strict weak ordering" is sufficient, as for many
> other STL algorithms, but I confess I'm a bit rusty on various
> ordering properties), 

Try http://cpp-next.com/archive/2010/02/order-i-say (I just did, as
review).

> and it should certainly be specified if you want
> to be precise, but it's the same ordering as would be required for
> clamp(T,T,T), so it's somewhat tangential to this exercise.]  

I'm not sure.  It's crucial to the question of what you mean by this
algorithm, and it probably affects the ultimate complexity of your
requirements.  That is, I believe there will be some relationship
between the ordering requirements chosen for the single-type algorithm
and the requirements you end up with for the three-type algorithm.

> Returns: If x < lo or hi < x (these are mutually exclusive assuming an
> appropriate precise ordering), returns (U)lo or (U)hi, respectively.

Why is that the right definition?  In your case, 

  when !(x < lo) and !(lo < x), are we returning (U)lo or (U)x

and why is that the right (most meaningful) answer?

> Otherwise, returns (U)x.  [Note: I believe the above requirements
> yield at least 2 nontrivially different implementations: (x < lo ? lo
> : hi < x : hi ? x) or (hi < x ? hi : x < lo ? lo : x).]
>
> Is this what you had in mind?

Not quite.  I still don't know what this algorithm means.  I don't think
I know enough about what it means to convert a value of one type to its
common type with two others.  You also didn't show the algorithm
description for the case where they're all required to be the same type,
so we can compare.  

I understand what that algorithm does when applied to a strict total
order.  *I* would describe it something like this:

    REQUIRES: < imposes a strict total ordering over T.  
    RETURNS: The value y of T nearest to x such that !(y < lo) and !(hi
    < y).

<waveshands>where "nearest to" is suitably defined for any total
order.</waveshands>

I haven't given this one enough time to percolate; I'm sure there's a
way to express _precisely_ what I mean in roughly that many words,
though.

When applied to a strict weak order, it's unclear to me which
element of the various equivalence classes should be returned in several
cases.  Now, probably someone has thought this through more deeply than
I, but maybe you can understand now why I'm reluctant to complicate the
definition of this algorithm with the consequences of multi-type
signatures.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com