www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - bug in std.algorithm.sort ??

reply A.M. <AMAMH3 Gmail.com> writes:
import std.string;
import std.array;
import std.algorithm;

void main()
{
	string[] sa = ["TOM","JOE","TOM4","TOM12","TOM6"];
	sort!(comp)(sa);
}
bool comp(string x, string y)
{
	string[] s = [x,y];
	return isSorted(s);
}

this code compiles find, but when run gives the following error:

core.exception.AssertError ./../../src/phobos/std/array.d(210): Attempting to
fetch the front of an empty array

I'm using dmd2.030
same happens with dmd2.029

is that a bug?
Jun 04 2009
next sibling parent reply KennyTM~ <kennytm gmail.com> writes:
A.M. wrote:
 import std.string;
 import std.array;
 import std.algorithm;
 
 void main()
 {
 	string[] sa = ["TOM","JOE","TOM4","TOM12","TOM6"];
 	sort!(comp)(sa);
 }
 bool comp(string x, string y)
 {
 	string[] s = [x,y];
 	return isSorted(s);
 }
 
 this code compiles find, but when run gives the following error:
 
 core.exception.AssertError ./../../src/phobos/std/array.d(210): Attempting to
fetch the front of an empty array
 
 I'm using dmd2.030
 same happens with dmd2.029
 
 is that a bug?

No. Because comp("foo", "foo") == true, but should return false when the two keys are equal. BTW, the following code can reproduce your "bug": import std.algorithm; void main() { sort!("a <= b")( [2,1].dup ); }
Jun 04 2009
parent A.M. <AMAMH3 Gmail.com> writes:
KennyTM~ Wrote:

 No. Because comp("foo", "foo") == true, but should return false when the 
 two keys are equal.
 
 
 BTW, the following code can reproduce your "bug":
 
 import std.algorithm;
 void main() {
     sort!("a <= b")( [2,1].dup );
 }

I guess that's why I should use return x<y and not return x<=y , btw I didn't know that "<" and the like work with strings. I actually don't know why it swaps two elements which are equal. I guess it's something advanced. Thanks for illustrating.
Jun 04 2009
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
A.M. wrote:
 import std.string;
 import std.array;
 import std.algorithm;
 
 void main()
 {
 	string[] sa = ["TOM","JOE","TOM4","TOM12","TOM6"];
 	sort!(comp)(sa);
 }
 bool comp(string x, string y)
 {
 	string[] s = [x,y];
 	return isSorted(s);
 }
 
 this code compiles find, but when run gives the following error:
 
 core.exception.AssertError ./../../src/phobos/std/array.d(210): Attempting to
fetch the front of an empty array
 
 I'm using dmd2.030
 same happens with dmd2.029
 
 is that a bug?

The comp function must be an ordering function of the likes of "<", and yours is a very expensive way to compute x <= y. Sort does not work with "<=", only with "<". Andrei
Jun 04 2009
parent reply A.M. <AMAMH3 Gmail.com> writes:
Andrei Alexandrescu Wrote:

 A.M. wrote:
 import std.string;
 import std.array;
 import std.algorithm;
 
 void main()
 {
 	string[] sa = ["TOM","JOE","TOM4","TOM12","TOM6"];
 	sort!(comp)(sa);
 }
 bool comp(string x, string y)
 {
 	string[] s = [x,y];
 	return isSorted(s);
 }
 
 this code compiles find, but when run gives the following error:
 
 core.exception.AssertError ./../../src/phobos/std/array.d(210): Attempting to
fetch the front of an empty array
 
 I'm using dmd2.030
 same happens with dmd2.029
 
 is that a bug?

The comp function must be an ordering function of the likes of "<", and yours is a very expensive way to compute x <= y. Sort does not work with "<=", only with "<". Andrei

I actually changed it to: return x<y btw, this is not the actual code I'm writing, if it was I'd just use sort(sa) and not make my own comparing function.
Jun 04 2009
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
A.M. wrote:
 Andrei Alexandrescu Wrote:
 
 A.M. wrote:
 import std.string;
 import std.array;
 import std.algorithm;

 void main()
 {
 	string[] sa = ["TOM","JOE","TOM4","TOM12","TOM6"];
 	sort!(comp)(sa);
 }
 bool comp(string x, string y)
 {
 	string[] s = [x,y];
 	return isSorted(s);
 }

 this code compiles find, but when run gives the following error:

 core.exception.AssertError ./../../src/phobos/std/array.d(210): Attempting to
fetch the front of an empty array

 I'm using dmd2.030
 same happens with dmd2.029

 is that a bug?

yours is a very expensive way to compute x <= y. Sort does not work with "<=", only with "<". Andrei

I actually changed it to: return x<y

Did things work after that replacement? (Thanks for the bug report too, regardless on whether it unveils an actual bug in std.algorithm.) Andrei
Jun 04 2009
parent reply A.M. <AMAMH3 Gmail.com> writes:
Andrei Alexandrescu Wrote:

 A.M. wrote:
 Andrei Alexandrescu Wrote:
 
 A.M. wrote:
 import std.string;
 import std.array;
 import std.algorithm;

 void main()
 {
 	string[] sa = ["TOM","JOE","TOM4","TOM12","TOM6"];
 	sort!(comp)(sa);
 }
 bool comp(string x, string y)
 {
 	string[] s = [x,y];
 	return isSorted(s);
 }

 this code compiles find, but when run gives the following error:

 core.exception.AssertError ./../../src/phobos/std/array.d(210): Attempting to
fetch the front of an empty array

 I'm using dmd2.030
 same happens with dmd2.029

 is that a bug?

yours is a very expensive way to compute x <= y. Sort does not work with "<=", only with "<". Andrei

I actually changed it to: return x<y

Did things work after that replacement? (Thanks for the bug report too, regardless on whether it unveils an actual bug in std.algorithm.) Andrei

u mean, u don't know if it works or not? well, I don't think I understand ur point, but anyway, of course it works. btw, here is the complete code of my small application: import std.stdio; import std.string; import std.array; import std.conv; import std.algorithm; /* This program works as follows: there is a string[] of users with genders and their answers to a multichoice survey the program takes a user name as input, the user wants to find other users who answered at least a number (called similarity factor) of question as he/she did. the program then outputs a list of users who are ordered by how similar their answers to the user, if two users have the same similarity factor, they are then ordered by name. */ void main() { string[] members= [ "BETTY F M A A C C", "TOM3 M F A D C A", "TOM M F A D C A", "SUE F M D D D D", "ELLEN F M A A C A", "TOM6 M F A D C A", "JOE M F A A C A", "TOM12 M F A D C A", "ED M F A D D A", "SALLY F M C D A B", "MARGE F M A A C C", "TOM4 M F A D C A", ]; // the form is: "NAME G RG X X X .." where G is gender, RG is requested gender, X is the answer to a multichoice question. foreach (string s; bestmatch(members,"BETTY",2)) writefln(s); } string[] bestmatch(string[] ms, string user, int sf) { string[] u,tmp; foreach (string m; ms) if (((u=m.split())[0])==user) break; auto re = appender!(string[]); auto sa = appender!(int[]); int s; foreach (string m; ms) { s = 0; if ((tmp=m.split())[1]==u[2]) { for (int i = 3; i<u.length; i++) if (tmp[i]==u[i]) s++; } if (s>=sf) re.put(join([to!(string)(s),tmp[0]]," ")); } sort!(comp)(re.data); for (int i = 0; i<re.data.length; i++) re.data[i] = re.data[i].split()[1]; return re.data; } bool comp(string x, string y) { writefln("now: %s %s", x, y); string[] a = x.split(); string[] b = y.split(); if (to!(int)(a[0])>to!(int)(b[0])) return 1; else if (a[1]<b[1]) return 1; else return 0; } // END Thanks Andrei for replying Regards, A.M.
Jun 04 2009
parent A.M. <AMAMH3 Gmail.com> writes:
There was an error in my comp function in the code I have just posted, here is
it after modification:

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
/*
   This program works as follows:
   there is a string[] of users with genders and their answers to a multichoice
survey
   the program takes a user name as input, the user wants to find other users
who answered at least a number (called similarity factor)
   of question as he/she did.
   the program then outputs a list of users who are ordered by how similar
their answers to the user, if two users have the same
   similarity factor, they are then ordered by name.
*/
void main()
{
	string[] members=
	[
		"BETTY F M A A C C",
		"TOM3 M F A D C A",
		"TOM M F A D C A",
		"SUE F M D D D D",
		"ELLEN F M A A C A",
		"TOM6 M F A D C A",
		"JOE M F A A C A",
		"TOM12 M F A D C A",
		"ED M F A D D A",
		"SALLY F M C D A B",
		"MARGE F M A A C C",
		"TOM4 M F A D C A",
	];
//	the form is: "NAME G RG X X X .." where G is gender, RG is requested gender,
X is the answer to a multichoice question
	foreach (string s; bestmatch(members,"BETTY",2))
		writefln(s);
}
string[] bestmatch(string[] ms, string user, int sf)
{
	string[] u,tmp;
	foreach (string m; ms)
		if (((u=m.split())[0])==user) break;
	auto re = appender!(string[]);
	auto sa = appender!(int[]);
	int s;
	foreach (string m; ms)
	{
		s = 0;
		if ((tmp=m.split())[1]==u[2])
		{
			for (int i = 3; i<u.length; i++)
				if (tmp[i]==u[i]) s++;
		}
		if (s>=sf)
			re.put(join([to!(string)(s),tmp[0]]," "));
	}
	sort!(comp)(re.data);
	for (int i = 0; i<re.data.length; i++)
		re.data[i] = re.data[i].split()[1];
	return re.data;
}
bool comp(string x, string y)
{
	writefln("now: %s %s", x, y);
	string[] a = x.split(); string[] b = y.split();
	int cmp = (to!(int)(a[0])>to!(int)(b[0]));
	if (cmp>0)
		return 1;
	else if (cmp==0 && a[1]<b[1])
		return 1;
	return 0;
}
Jun 04 2009