D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 3199 - sort(chain(...)) doesn't work in some cases
Summary: sort(chain(...)) doesn't work in some cases
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: x86 Linux
: P2 normal
Assignee: Andrei Alexandrescu
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2009-07-21 14:18 UTC by Adolf Mathias
Modified: 2015-06-09 01:28 UTC (History)
1 user (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this issue.
Description Adolf Mathias 2009-07-21 14:18:59 UTC
Having become curious after reading the Dr Dobb's article by Andrei Alexandrescu, I tried:

import std.algorithm, std.random, std.stdio, std.range;

void main() {
  int[] a,b,c;

  auto abc=[a,b,c];

  foreach(ref t;abc) {
    t.length = uniform(8,17);
    foreach(ref v;t) v = uniform(0,100);
  }

  foreach(t;abc) writefln("[%s]",t);
  sort(chain(a,b,c));
  foreach(t;abc) writefln("[%s]",t);
}

which, when run, doesn't print anything different from the first foreach in the second foreach.

Only when I replace the dynamic initialization of a, b, c:

import std.algorithm, std.random, std.stdio, std.range;

void main() {
  int[] a,b,c;

  auto abc=[a,b,c];

  foreach(t;abc) writefln("[%s]",t);
  sort(chain(a,b,c));
  foreach(t;abc) writefln("[%s]",t);
}

things work as expected.

When I overwrite a,b,c in the second example with random values like in the first example:

import std.algorithm, std.random, std.stdio, std.range;

void main() {
  int[] a = [16,80,6,43,43,6,29,16,1,64,75,59,40,5,63], 
        b = [43,11,71,39,32,82,94,42,18],
        c = [17,70,93,96,64,3,24,84,88];

  auto abc=[a,b,c];

  foreach(ref t;abc) {
    t.length = uniform(8,17);
    foreach(ref v;t) v = uniform(0,100);
  }

  foreach(t;abc) writefln("[%s]",t);
  sort(chain(a,b,c));
  foreach(t;abc) writefln("[%s]",t);
}

the data in the arrays is reordered, but the sorting seems to stop somewhere in-between, usually either b or c have not been sorted.
Comment 1 Adolf Mathias 2009-07-21 14:21:54 UTC
I'm very sorry, the second, working example should have been:

import std.algorithm, std.random, std.stdio, std.range;

void main() {
  int[] a = [16,80,6,43,43,6,29,16,1,64,75,59,40,5,63], 
        b = [43,11,71,39,32,82,94,42,18],
        c = [17,70,93,96,64,3,24,84,88];

  auto abc=[a,b,c];


  foreach(t;abc) writefln("[%s]",t);
  sort(chain(a,b,c));
  foreach(t;abc) writefln("[%s]",t);
}
Comment 2 Andrei Alexandrescu 2009-08-28 09:10:41 UTC
The first example creates three empty slices a, b, and c. Then abc is defined as a slice of slices initialized with those empty slices. Subsequently abc is filled but the initial slices a, b, and c remain empty. Therefore sort(chain(a, b, c)) sorts an empty range so it is ineffectual.

The second example (after fixing) works indeed correctly because abc does not undergo modifications independently from a, b, and c.

The third example is subtle. Assigning to the length of a slice, e.g.

t,length = uniform(8, 17);

may or may not spawn a new allocation (and therefore a divergence of what abc holds versus what a, b, and c hold individually). Therefore, the behavior will be erratic depending on what the random number generator yields.

Assigning to length in slices has always had that danger. We have recently decided to prevent assignable length and defining a separate array type that has modifiable length.