www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Problem with Sorting

reply Mandeep Singh Brar <mandeep brars.co.in> writes:
Hi,

I am facing the following problems with sorting. .

module testSort;

import std.stdio;
import std.algorithm;

class testcl {
	public string name;
	this(string na) { name=na; }
	public string toString() {
		return name;
	}
	public int opCmp(testcl b) {

		return name < b.name ?  -1: 1;
	}

}

int main(string[] args) {
	testcl a = new testcl(args[1]);
	testcl b = new testcl(args[2]);
	testcl[] arr = [a,b];
	writeln(arr);
	sort!("a>b")(arr);
	writeln(arr);
	return 0;
}

I get the following input when i run this program as:

./testSort te2 test2
[te2, test2]
[test2, te2]


./testSort test1 test2
[test1, test2]
[test2, test1]

which is as desired.. But randomly with a few strings it gives me a range
violation as:


./testSort test2 te1
[test2, te1]
core.exception.RangeError std.algorithm(5293): Range violation
----------------
./testSort() [0x80599d6]
./testSort() [0x8050ca6]
./testSort() [0x8052b26]
./testSort() [0x804d39d]
./testSort() [0x804d2a8]
./testSort() [0x804ce3a]
./testSort() [0x8049919]
./testSort() [0x8050e66]
./testSort() [0x8050dc0]
./testSort() [0x8050eaa]
./testSort() [0x8050dc0]
./testSort() [0x8050d66]
/lib/libc.so.6(__libc_start_main+0xe7) [0x139ce7]
./testSort() [0x8049751]

The problem gets corrected if i write the comparison function as :

	public int opCmp(testcl b) {
		if(name == b.name) return 0;
		return name < b.name ?  -1: 1;
	}

I could not get the problem with the above code.

Thanks
Mandeep
Jan 27 2011
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Thursday 27 January 2011 20:30:47 Mandeep Singh Brar wrote:
 Hi,
 
 I am facing the following problems with sorting. .
 
 module testSort;
 
 import std.stdio;
 import std.algorithm;
 
 class testcl {
 	public string name;
 	this(string na) { name=na; }
 	public string toString() {
 		return name;
 	}
 	public int opCmp(testcl b) {
 
 		return name < b.name ?  -1: 1;
 	}
 
 }
 
 int main(string[] args) {
 	testcl a = new testcl(args[1]);
 	testcl b = new testcl(args[2]);
 	testcl[] arr = [a,b];
 	writeln(arr);
 	sort!("a>b")(arr);
 	writeln(arr);
 	return 0;
 }
 
 I get the following input when i run this program as:
 
 ./testSort te2 test2
 [te2, test2]
 [test2, te2]
 
 
 ./testSort test1 test2
 [test1, test2]
 [test2, test1]
 
 which is as desired.. But randomly with a few strings it gives me a range
 violation as:
 
 
 ./testSort test2 te1
 [test2, te1]
 core.exception.RangeError std.algorithm(5293): Range violation
 ----------------
 ./testSort() [0x80599d6]
 ./testSort() [0x8050ca6]
 ./testSort() [0x8052b26]
 ./testSort() [0x804d39d]
 ./testSort() [0x804d2a8]
 ./testSort() [0x804ce3a]
 ./testSort() [0x8049919]
 ./testSort() [0x8050e66]
 ./testSort() [0x8050dc0]
 ./testSort() [0x8050eaa]
 ./testSort() [0x8050dc0]
 ./testSort() [0x8050d66]
 /lib/libc.so.6(__libc_start_main+0xe7) [0x139ce7]
 ./testSort() [0x8049751]
 
 The problem gets corrected if i write the comparison function as :
 
 	public int opCmp(testcl b) {
 		if(name == b.name) return 0;
 		return name < b.name ?  -1: 1;
 	}
 
 I could not get the problem with the above code.

Well, of course the first version doesn't work. opCmp is supposed to return 0 if the values are equal, and it doesn't do that. opCmp returns a value < 0 if the first value is less than the second, 0 if they're equal, and a value > 0 if the first value is greater than the second value. Also, the signature for opCmp on classes is supposed to be int opCmp(Object o) It's supposed to take Object. I'm surprised that it works at all the way that it is. And since you're comparing strings, your opCmp can just use std.string.cmp to compare them. - Jonathan M Davis
Jan 27 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 28 Jan 2011 00:05:34 -0500, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 Also, the signature for opCmp on classes is supposed to be

 int opCmp(Object o)

 It's supposed to take Object. I'm surprised that it works at all the way  
 that it
 is.

std.algorithm.sort is a template, so it has access to the fully derived class type. The compiler simply rewrites a < b as a.opCmp(b), which calls his function if you are using the derived type. Without defining opCmp as taking object, however, the builtin array sort would fail with a hidden function error. -Steve
Jan 28 2011