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

• superdan (2/2) Sep 10 2008 got a question on this range stuff. in stl partition is partition(begin,...
• Sergey Gromov (5/15) Sep 10 2008 Two is too little a number, don't you think? ;) I'd better off with 4.
• Sean Kelly (6/9) Sep 10 2008 To throw another version into the mix, Tango's partition routine is
• Andrei Alexandrescu (6/22) Sep 10 2008 Ours too. I think superdan is making a slight confusion somewhere. But
• Benji Smith (11/27) Sep 10 2008 I was looking at that the other day, and it made me wonder...
• Sean Kelly (6/32) Sep 10 2008 Simply because it's more natural. I don't really like having to store
• Benji Smith (3/19) Sep 10 2008 Gotcha. Thanks for the reply!
• Andrei Alexandrescu (20/31) Sep 10 2008 I think I have an answer. All algorithms supposed to take begin, middle,...
• Bill Baxter (5/25) Sep 10 2008 Agreed completely. That's basically what I just got finished sayin'. :...
• Andrei Alexandrescu (17/50) Sep 10 2008 Sounds great! Thanks Bill. By the way, I am indebted to you for
• Bill Baxter (11/16) Sep 10 2008 I think you might have made that particular leap yourself, but anyway,
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
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
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
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
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
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
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

--benji
```
Sep 10 2008
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
"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
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
"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