Re: [boost] Proposed templated integer_sort

Subject: Re: [boost] Proposed templated integer_sort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2009-01-15 08:40:14

On Wed, Jan 14, 2009 at 2:48 PM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:
>
>
>  That's what the functor versions are there for: sorting classes or
>> structures based upon a key.  All you have to do is define the correct
>> functor.
>>
>
> I still believe that "rightshift" is the wrong name for this functor in
> these cases.

It's an arithmetic right shift, or alternatively division by a power of 2.
What do you want to call it?

>
>  Fixed-point types can sort as an integer of the same size in bytes.  The
>> only real requirement is that they must return a data type that when
>> subtracted from an item of the same type returns something convertible to
>> a
>> size_t, that if (b - a) < (c - a) then b < c, and that bitshifting works
>> as
>> division by a power of two would, reducing the difference by a power of
>> two
>> per shift.
>>
>
> Can you clarify that a bit?  Say I have this:
>
> class fixed {
>  ....
>  some_integer_type impl;
>  ....
>  bool operator<(const fixed& other) const;
>  fixed operator>>(unsigned int shift_mt) const;
> };
>
> What do I need to do?

You < operator is fine, and usable without modification.
If your - operator returns something castable to a size_t, then you don't
need any functors, that will do (return impl - right.impl;)
If your - operator doesn't return something castable to a size_t, then you
need to define a rightshift functor that does.  How about:
struct rightshift {
    some_integer_type operator()(const fixed &x, unsigned offset) { return
x.impl >> offset; }
};

>
>  I would
>>> have thought that the floating-point algorithm would just be an instance
>>> of
>>> the generic algorithm with custom functors, with a bit of specialisation
>>> to
>>> cope with the reverse-order-for-negatives thing.
>>>
>>
>> Positive floats can be sorted just like integers, with the right functor.
>> Negative floats have to be sorted backwards.  I didn't see any efficient
>> way
>> to write a functor to handle negative floats.
>>
>
> Can't you just pass a "greater" functor instead of "less"?

Yes, but that would hurt efficiency.