On 10/8/2011 11:04 AM, Andrei Alexandrescu wrote:
On 10/08/11 10:01, Xinok wrote:
On 10/8/2011 9:15 AM, Andrei Alexandrescu wrote:
On 10/07/11 23:00, Xinok wrote:
Thanks, I'll look into it when I have a little more time.
Looking forward to it.
If my algorithm were to be implemented in Phobos, the template
arguments
for std.algorithm.sort would need to be modified. For my algorithm
to be
stable, it requires defining two conditions, both a 'less' and
'greater'.
Wouldn't swapping the argument to less work?
Andrei
The merge step in my algorithm is similar to Timsort, in that it can
merge left to right as well as right to left. This needs two conditions
to do a stable sort, 'less or equal' and 'greater or equal'.
By swapping the arguments, you can only get 'greater or equal'. You're
still missing 'less or equal', which is required for my algorithm to be
stable.
I don't understand. Say all you have is "<". Then you can do everything:
a <= b is !(b < a)
a > b is b < a
This is an absolute classic. Probably it's negation that is missing from
your assumptions? You can always negate a predicate.
Andrei
I actually wasn't aware you could do that O.o, although you got the
operators wrong in your example.
It does add overhead though. It requires two comparisons, and possibly
twice the number of lookups, such as in this statement:
lef[c] > rig[off - c]
How about, if the greater argument is empty, then it fills it
automatically with this. But also give the programmer the option to
define both conditions for more efficient code.
