Ranges/algorithms for aggregation

[Justin Whear]

On Fri, 21 Mar 2014 15:22:13 +0000, Luís Marques wrote:

> Is there a neat way to do this transformation with ranges and
> std.algorithms?
> 
>      Input:
>      -------
>      B foo B bar C ble B big A begga
> 
>      Output: (aggregated and sorted on length)
>      -------
>      B -> [foo, bar, big]
>      C -> [ble]
>      A -> [begga]
> 
> The most obvious way (to me) to do this without standard algorithms is
> with an AA to the aggregation. The most obvious way (to me) to do this
> with std.algorithms is:
> 
>      B foo B bar C ble B big A begga
> 
>      =>
> 
>      [B, foo]
>      [B, bar]
>      [C, ble]
>      [B, big]
>      [A, begga]
> 
>      =>
> 
>      [B, foo]
>      [B, bar]
>      [B, big]
>      [C, ble]
>      [A, begga]
> 
>      =>
> 
>      B -> [foo, bar, big]
>      C -> [ble]
>      A -> [begga]
> 
> But this seems wasteful on memory. Is there a better way to do this in a
> more algorithmic way?

This pull request[1] for groupBy has been hanging around for a year now, 
driving me to copy-and-paste the implementation into a couple of my 
projects.  Using it, you could do this:

auto tuples = ... // get your list of (B, foo), (B, bar), etc.
auto output = tuples.sort!`a[0] < b[0]`
                    .groupBy!`a[0] == b[0]`;
// output is a range of:
//    [
//     [(A, begga)],
//     [(B, foo), (B, bar), (B, big)],
//     [(C, ble)]
//    ]

The advantage being that output isn't an array at all but a lazy range of 
lazy ranges.

1 https://github.com/D-Programming-Language/phobos/pull/1186