ch-ch-changes

[Andrei Alexandrescu]

Don wrote:
> Andrei Alexandrescu wrote:
>> Don wrote:
>>> Andrei Alexandrescu wrote:
>>>> I've worked valiantly on defining the range infrastructure and 
>>>> making std.algorithm work with it. I have to say that I'm even more 
>>>> pleased with the result than I'd ever expected when I started. 
>>>> Ranges and concepts really make for beautiful code, and I am sure 
>>>> pretty darn efficient too.
>>>>
>>>> There's a lot to sink one's teeth in, but unfortunately the code 
>>>> hinges on a compiler fix that Walter was kind enough to send me 
>>>> privately. I did document the work, but the documentation doesn't 
>>>> really make justice to the extraordinary possibilities that lay 
>>>> ahead of us. Anyhow, here's a sneak preview into the up-and-coming 
>>>> ranges and their algorithms.
>>>>
>>>> http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
>>>> http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html
>>>>
>>>> Ranges are easy to define and compose efficiently. It was, however, 
>>>> a pig to get a zip(r1, r2, ...) working that can mutate back the 
>>>> ranges it iterates on. With that, it's very easy to e.g. sort 
>>>> multiple arrays in parallel. Similarly, chain(r1, r2, ...) is able 
>>>> to offer e.g. random iteration if all components offer it, which 
>>>> means that you can do crazy things like sorting data that sits 
>>>> partially in one array and partially in another.
>>>>
>>>> Singly-linked list ranges are in, and to my soothing I found an 
>>>> answer to the container/range dichotomy in the form of a topology 
>>>> policy. A range may or may not be able to modify the topology of the 
>>>> data it's iterating over; if it can, it's a free-standing range, 
>>>> much like built-in arrays are. If it can't, it's a limited range 
>>>> tied to a container (of which I defined none so far, but give me 
>>>> time) and it's only the container that can mess with the topology in 
>>>> controlled ways. More on that later.
>>>>
>>>> Feedback welcome.
>>>>
>>>>
>>>> Andrei
>>>
>>> Awesome stuff. Will take some time to adjust my thought processes for 
>>> this.
>>> Some minor comments:
>>> * Is Repeat simply a single-parameter form of Cycle? I can't see any 
>>> difference between them.
>>
>> Cycle takes a range and essentially provides a (potentially mutable!) 
>> way of iterating it. Repeat just gives one element. At the moment that 
>> element is also mutable, so the difference is moot. I'll consider 
>> removing Repeat.
>>
>>> * Uniq docs should at least add one word:  Iterates [[consecutively]] 
>>> unique elements of the given range.
>>> * find:
>>> To find the last element of [[a bidirectional]] haystack satisfying 
>>> pred, call find!(pred)(retro(haystack)).
>>>
>>> (unless Retro also works for forward ranges, which seems unlikely).
>>
>> Thanks (and correct).
>>
>>> * There's no pushHeap. Is it planned?
>>
>> I plan to do something nicer: make Heap an entity of its own instead 
>> of a collection of disparate functions. I'm unsure about the name 
>> because I mean "the computer science heap" as opposed to "the heap for 
>> allocating memory".
> 
> Even better. You might consider including adjustHeap, which is used in 
> eg Dijkstra's algorithm. Stepanov said it was intended to have been 
> public in the STL, but got dropped for political reasons <g>.

(Sorry, this fell through the cracks.) What does adjustHeap do? I have 
heap adjustment as part of pop() and the constructor.

Andrei