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
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 reply 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.


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


 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



 Sep 10 2008