www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 3199] New: sort(chain(...)) doesn't work in some cases

reply d-bugmail puremagic.com writes:
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: -------
Jul 21 2009
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3199






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: -------
Jul 21 2009
prev sibling next sibling parent d-bugmail puremagic.com writes:
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: -------
Jul 21 2009
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3199


Andrei Alexandrescu <andrei metalanguage.com> changed:

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





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: -------
Aug 28 2009