http://d.puremagic.com/issues/show_bug.cgi?id=3199

           Summary: sort(chain(...)) doesn't work in some cases
           Product: D
           Version: 2.031
          Platform: x86
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: adolf.mathias@googlemail.com


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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=3199





--- Comment #1 from Adolf Mathias <adolf.mathias@googlemail.com>  2009-07-21 14:21:54 PDT ---
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);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=3199


Andrei Alexandrescu <andrei@metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |andrei@metalanguage.com
         AssignedTo|nobody@puremagic.com        |andrei@metalanguage.com




-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=3199


Andrei Alexandrescu <andrei@metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED




--- Comment #2 from Andrei Alexandrescu <andrei@metalanguage.com>  2009-08-28 09:10:41 PDT ---
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.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------