ch-ch-changes

[Don]

Andrei Alexandrescu wrote:
> 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
adjustHeap is used to restore the heap invariant after the value of a 
single element has been changed.