partition(range, leftsubrange) or partition(range, rightsubrange)

[Andrei Alexandrescu]

Bill Baxter wrote:
> On Thu, Sep 11, 2008 at 11:41 AM, Andrei Alexandrescu
> <SeeWebsiteForEmail at 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