www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - partition(range, leftsubrange) or partition(range, rightsubrange)

reply superdan <super dan.org> writes:
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.
Sep 10 2008
next sibling parent Sergey Gromov <snake.scaly gmail.com> writes:
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.
Sep 10 2008
prev sibling next sibling parent reply Sean Kelly <sean invisibleduck.org> writes:
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
Sep 10 2008
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Sep 10 2008
prev sibling parent reply Benji Smith <dlanguage benjismith.net> writes:
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
Sep 10 2008
parent reply Sean Kelly <sean invisibleduck.org> writes:
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
Sep 10 2008
parent Benji Smith <dlanguage benjismith.net> writes:
Sean Kelly wrote:
 Benji Smith wrote:
 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

Gotcha. Thanks for the reply! --benji
Sep 10 2008
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Sep 10 2008
next sibling parent reply "Bill Baxter" <wbaxter gmail.com> writes:
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
Sep 10 2008
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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.

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
Sep 10 2008
prev sibling parent "Bill Baxter" <wbaxter gmail.com> writes:
On Thu, Sep 11, 2008 at 12:06 PM, Andrei Alexandrescu
<SeeWebsiteForEmail erdani.org> wrote:
 Bill Baxter wrote:

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
Sep 10 2008