got a question on this range stuff. in stl partition is partition(begin, mid, end). neat. in std.algorithm partition is partition(range, mid). so-so. never like it mucho. in the new stuff with ranges n all there are two choices partition(range, leftsubrange) or partition(range, rightsubrange). question is, is there a better choice between the two or are they just the same. would be cool to have a clear rule with some advantage. and that's easy to remember too.

like steve i think ranges are cool n all but fraid iterators are still good at sumthin'. either-way choices ain't a good sign.

superdan <super@dan.org> wrote:
> got a question on this range stuff. in stl partition is partition (begin, mid, end). neat. in std.algorithm partition is partition(range, mid). so-so. never like it mucho. in the new stuff with ranges n all there are two choices partition(range, leftsubrange) or partition(range, rightsubrange). question is, is there a better choice between the two or are they just the same. would be cool to have a clear rule with some advantage. and that's easy to remember too.
> 
> like steve i think ranges are cool n all but fraid iterators are still good at sumthin'. either-way choices ain't a good sign.

Two is too little a number, don't you think?  ;)  I'd better off with 4.

partition(range, mid);	// mid here is an empty range
partition(leftsubrange, rightsubrange);

I personally prefer the mid thing.

superdan wrote:
> got a question on this range stuff. in stl partition is partition(begin, mid, end). neat. in std.algorithm partition is partition(range, mid). so-so. never like it mucho. in the new stuff with ranges n all there are two choices partition(range, leftsubrange) or partition(range, rightsubrange). question is, is there a better choice between the two or are they just the same. would be cool to have a clear rule with some advantage. and that's easy to remember too.
> 
> like steve i think ranges are cool n all but fraid iterators are still good at sumthin'. either-way choices ain't a good sign.

To throw another version into the mix, Tango's partition routine is declared as partition(range, pred) and uses the result of pred to determine what to do with each element.  In std.algorithm parlance, that would be equivalent to partition!("a < 5")(range), for example.


Sean

Sean Kelly wrote:
> superdan wrote:
>> got a question on this range stuff. in stl partition is partition(begin, mid, end). neat. in std.algorithm partition is partition(range, mid). so-so. never like it mucho. in the new stuff with ranges n all there are two choices partition(range, leftsubrange) or partition(range, rightsubrange). question is, is there a better choice between the two or are they just the same. would be cool to have a clear rule with some advantage. and that's easy to remember too.
>>
>> like steve i think ranges are cool n all but fraid iterators are still good at sumthin'. either-way choices ain't a good sign.
> 
> To throw another version into the mix, Tango's partition routine is declared as partition(range, pred) and uses the result of pred to determine what to do with each element.  In std.algorithm parlance, that would be equivalent to partition!("a < 5")(range), for example.

Ours too. I think superdan is making a slight confusion somewhere. But the question is valid if you s/partition/partialSort or s/partition/rotate in his message.

Still thinking of it.

Andrei

Sean Kelly wrote:
> superdan wrote:
>> got a question on this range stuff. in stl partition is partition(begin, mid, end). neat. in std.algorithm partition is partition(range, mid). so-so. never like it mucho. in the new stuff with ranges n all there are two choices partition(range, leftsubrange) or partition(range, rightsubrange). question is, is there a better choice between the two or are they just the same. would be cool to have a clear rule with some advantage. and that's easy to remember too.
>>
>> like steve i think ranges are cool n all but fraid iterators are still good at sumthin'. either-way choices ain't a good sign.
> 
> To throw another version into the mix, Tango's partition routine is declared as partition(range, pred) and uses the result of pred to determine what to do with each element.  In std.algorithm parlance, that would be equivalent to partition!("a < 5")(range), for example.

I was looking at that the other day, and it made me wonder...

Why does tango's partition use a bool predicate instead of an int predicate (returning -1, 0, or 1 like opCmp does)?

Using the int predicate would enable a qsort routine that avoids pointlessly swapping adjacent elements if they have equal values. It's very handy for collections with lots of duplicate entries.

(Of course, then your partition value can't be a single index/cursor/iterator/whatever. It has to be a range, but that's nicely supported by the new design anyhow.)

--benji

Benji Smith wrote:
> Sean Kelly wrote:
>> superdan wrote:
>>> got a question on this range stuff. in stl partition is partition(begin, mid, end). neat. in std.algorithm partition is partition(range, mid). so-so. never like it mucho. in the new stuff with ranges n all there are two choices partition(range, leftsubrange) or partition(range, rightsubrange). question is, is there a better choice between the two or are they just the same. would be cool to have a clear rule with some advantage. and that's easy to remember too.
>>>
>>> like steve i think ranges are cool n all but fraid iterators are still good at sumthin'. either-way choices ain't a good sign.
>>
>> To throw another version into the mix, Tango's partition routine is declared as partition(range, pred) and uses the result of pred to determine what to do with each element.  In std.algorithm parlance, that would be equivalent to partition!("a < 5")(range), for example.
> 
> I was looking at that the other day, and it made me wonder...
> 
> Why does tango's partition use a bool predicate instead of an int predicate (returning -1, 0, or 1 like opCmp does)?

Simply because it's more natural.  I don't really like having to store the result of a compare and then switch off it.

> Using the int predicate would enable a qsort routine that avoids pointlessly swapping adjacent elements if they have equal values. It's very handy for collections with lots of duplicate entries.

Tango's sort routine already optimizes for duplicate entries.  Partition and whatnot don't though.


Sean

superdan wrote:
> got a question on this range stuff. in stl partition is
> partition(begin, mid, end). neat. in std.algorithm partition is
> partition(range, mid). so-so. never like it mucho. in the new stuff
> with ranges n all there are two choices partition(range,
> leftsubrange) or partition(range, rightsubrange). question is, is
> there a better choice between the two or are they just the same.
> would be cool to have a clear rule with some advantage. and that's
> easy to remember too.
> 
> like steve i think ranges are cool n all but fraid iterators are
> still good at sumthin'. either-way choices ain't a good sign.

I think I have an answer. All algorithms supposed to take begin, middle, and end should take range(begin, end) and range(middle, end) and not any other combination. Moreover, whenever a collection can choose to returns a subrange or another, it should return the range to the right.

This is because right-open ranges are the most general, e.g. singly-linked lists with range==Node* (or other similar sentinel-terminated collections).

Imposing a range of the kind range(begin, middle) would make that algorithm not work for singly-linked list unless they implement a "fat" range containing two Node*.

So rotate should be:

R rotate(R)(R range, R subrange);

Description: moves subrange to the front of range, and whatever was in front of the subrange right after it. Preconditions: subrange is a subrange of range (duh). Returns the range after the moved subrange. (In fact I already mentioned I plan to give rotate the more descriptive name moveToFront.)

Makes sense?


Andrei

On Thu, Sep 11, 2008 at 11:41 AM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> superdan wrote:
>>
>> like steve i think ranges are cool n all but fraid iterators are still good at sumthin'. either-way choices ain't a good sign.
>
> I think I have an answer. All algorithms supposed to take begin, middle, and end should take range(begin, end) and range(middle, end) and not any other combination. Moreover, whenever a collection can choose to returns a subrange or another, it should return the range to the right.
>
> This is because right-open ranges are the most general, e.g. singly-linked lists with range==Node* (or other similar sentinel-terminated collections).
>
> Imposing a range of the kind range(begin, middle) would make that algorithm not work for singly-linked list unless they implement a "fat" range containing two Node*.


Agreed completely.  That's basically what I just got finished sayin'.  :-)


> So rotate should be:
>
> R rotate(R)(R range, R subrange);
>
> Description: moves subrange to the front of range, and whatever was in front of the subrange right after it. Preconditions: subrange is a subrange of range (duh). Returns the range after the moved subrange. (In fact I already mentioned I plan to give rotate the more descriptive name moveToFront.)
>
> Makes sense?

Yep.

--bb

Bill Baxter wrote:
> On Thu, Sep 11, 2008 at 11:41 AM, Andrei Alexandrescu
> <SeeWebsiteForEmail@erdani.org> wrote:
>> superdan wrote:
>>> like steve i think ranges are cool n all but fraid iterators are
>>> still good at sumthin'. either-way choices ain't a good sign.
>> I think I have an answer. All algorithms supposed to take begin, middle, and
>> end should take range(begin, end) and range(middle, end) and not any other
>> combination. Moreover, whenever a collection can choose to returns a
>> subrange or another, it should return the range to the right.
>>
>> This is because right-open ranges are the most general, e.g. singly-linked
>> lists with range==Node* (or other similar sentinel-terminated collections).
>>
>> Imposing a range of the kind range(begin, middle) would make that algorithm
>> not work for singly-linked list unless they implement a "fat" range
>> containing two Node*.
> 
> 
> Agreed completely.  That's basically what I just got finished sayin'.  :-)
> 
> 
>> So rotate should be:
>>
>> R rotate(R)(R range, R subrange);
>>
>> Description: moves subrange to the front of range, and whatever was in front
>> of the subrange right after it. Preconditions: subrange is a subrange of
>> range (duh). Returns the range after the moved subrange. (In fact I already
>> mentioned I plan to give rotate the more descriptive name moveToFront.)
>>
>> Makes sense?
> 
> Yep.

Sounds great! Thanks Bill. By the way, I am indebted to you for revealing to me that sentinel-terminated collections are not limited to linked lists. Things like zero-terminated arrays are the same deal.

I realized that spanning the characters in a char[] or wchar[] is also a forward iteration case. In that case the thing is not sentinel-terminated per se, but still you're not sure how many elements you'll see before the end. So practically they're still forward-range-prone collections, with the sentinel condition being range.index=hostarray.length.

So a range should exist that spans characters in an array. Fortunately D obviates much need for that via the construct:

foreach (dchar c; chararray) { ... }

(However, things like writing back characters into an array are not solved by foreach.) Such musings make me feel we're on the right track with all this.


Andrei

On Thu, Sep 11, 2008 at 12:06 PM, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:
> Bill Baxter wrote:
>>
> Sounds great! Thanks Bill. By the way, I am indebted to you for revealing to me that sentinel-terminated collections are not limited to linked lists. Things like zero-terminated arrays are the same deal.

I think you might have made that particular leap yourself, but anyway, you're welcome.  Thanks to you too.  I've learned a lot from this discussion about bidirectional iterators and ranges and such.

I'm still not 100% convinced that this is all going to be easier and better than just doing iterators in the end, but I think at this point I can't say without trying it out some.  And you have convinced me that ranges will at least be a sufficient and good way to handle std.algorithm's needs.

--bb