std.string and ranges

[Denis Koroskin]

On Thu, 12 Feb 2009 15:14:34 +0300, Steve Schveighoffer  
<schveiguy at yahoo.com> wrote:

> On Thu, 12 Feb 2009 14:41:26 +0300, Denis Koroskin wrote:
>
>> On Thu, 12 Feb 2009 07:46:31 +0300, Andrei Alexandrescu
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>> Wait, I take that back. I don't know of solid ways to sort into a copy
>>> or shuffle into a copy. For shuffling I'd need auxiliary memory (in
>>> addition to the copy itself), and for sorting I'd be better off copying
>>> and then sorting in place. Could anyone illuminate me about better
>>> ways?
>>>
>>> Andrei
>>
>> That's why I said it /might/ be faster. It doesn't have to, the default
>> implementation may look as follows:
>>
>> typeof(Range.first)[] shuffledCopy(Range)(Range range) {
>>      return shuffle(createCopy(range));
>> }
>>
>> However, it may be implemented quite differently if not inplace. For
>> this to work we need two primitives that I didn't find in std.range (I
>> know names are not good, feel free to rename them as you please):
>>
>> struct RandomNumbers(Rnd = Random)
>> {
>>      // ...
>> }
>>
>> A finite range of length 'max' that generates random numbers in interval
>> [0..max) without repeating. An example:
>
> That's the problem.  How do you do this without remembering all the
> number you have returned so far (i.e. generate an array of N integers)?
> I've done algorithms like this, and generally you have to mutate the
> source array (swapping used items with the item at the location you took
> from).  You may save some time on swapping by building a temporary array
> of pointers or indexes, but you still have to build a temporary array,
> which is what Andrei was saying.
>
> -Steve

Well, I've attached the source code, so take a look at it. I don't  
remember all the values returned so far but I still use O(N) temporary  
storage.

Copying and modifying array of int is often preffered to copying and  
modifying and array of structs (they can be big, have heavyweight  
assignment operators etc).

Even if shuffledCopy won't get into algorithms, RandomNumbers/RandomItems  
are still pretty useful ranges.