www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - How does .sort work?

reply MicroWizard <MicroWizard_member pathlink.com> writes:
I have written to construct an own string class with overloaded opCmp and
opEquals. When I tried to sort it nothing happend. With some wellplaced printf I
figured out that opEquals was called, but opCmp was not, no, never.

Could anybody give me a hint how should .sort work with overloaded operators?

Tamas Nagy
Jan 22 2006
parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"MicroWizard" <MicroWizard_member pathlink.com> wrote in message 
news:dr1365$2k3$1 digitaldaemon.com...

I have written to construct an own string class with overloaded opCmp and
 opEquals. When I tried to sort it nothing happend. With some wellplaced 
 printf I
 figured out that opEquals was called, but opCmp was not, no, never.

 Could anybody give me a hint how should .sort work with overloaded 
 operators?

 Tamas Nagy


You have to overload opCmp to take an Object parameter.  It's tempting to 
just write

class A
{
    int opCmp(A other)
    {
        return this.x - other.x;
    }

    int x;
}

But you have to write

int opCmp(Object o)
{
    A other = cast(A)o;
    assert(other !is null);
    return this.x - other.x;
}

You don't have to overload opEquals to get .sort to work.
Jan 22 2006
parent reply MicroWizard <MicroWizard_member pathlink.com> writes:
Thanks a lot! Now it works. "int opCmp(Object o)" _is_ the solution.
It worth to write about this issue on "D learn"...

Tamás Nagy

In article <dr16cd$529$1 digitaldaemon.com>, Jarrett Billingsley says...

"MicroWizard" <MicroWizard_member pathlink.com> wrote in message 
news:dr1365$2k3$1 digitaldaemon.com...

I have written to construct an own string class with overloaded opCmp and
 opEquals. When I tried to sort it nothing happend. With some wellplaced 
 printf I
 figured out that opEquals was called, but opCmp was not, no, never.

 Could anybody give me a hint how should .sort work with overloaded 
 operators?

 Tamas Nagy


You have to overload opCmp to take an Object parameter.  It's tempting to 
just write

class A
{
    int opCmp(A other)
    {
        return this.x - other.x;
    }

    int x;
}

But you have to write

int opCmp(Object o)
{
    A other = cast(A)o;
    assert(other !is null);
    return this.x - other.x;
}

You don't have to overload opEquals to get .sort to work.
Jan 23 2006
parent Oskar Linde <oskar.lindeREM OVEgmail.com> writes:
MicroWizard wrote:

 Thanks a lot! Now it works. "int opCmp(Object o)" _is_ the solution.
 It worth to write about this issue on "D learn"...


Is there really any real reason it has to work this way? This has always 
felt like a horrible kludge to me.

This is a problem with TypeInfo and the internals in Phobos.

Assume we have a class C and two instances, a and b:

class C {
	int opCmp(Object x) { ... }
	int opCmp(C x) { ... }
}

...

	C a = new C;
	C b = new C;

The call:
	a < b;

Will be correctly identified by the DMD compiler and C.opCmp(C) will be 
called.

.sort on the other hand, is implemented in the internals of Phobos 
(internal/qsort.d) and calls the compare(void *,void*) function defined 
in the TypeInfo class. This code was written long before D had templates 
and working with Object references was probably the only way to do 
generic programming.

----

Today, it is straightforward to write a type aware sort function:

template mySort(D:D[]) {
	void mySort(D[] a) {
		... // implementation left as exercise
	}
}

with the syntax:

mySort!(typeof(arr))(arr);

(Not too nice)...

I really think the built in hash-table and array sorting in 
phobos/internal should be implemented as templates with proper type 
information.

Apart from that, there are two things on my wish list regarding this:

a) In the name of consistency, allow template functions on arrays be 
used as "injected" array methods just as non-template functions are now*.

b) Just one tiny thing: Implicit function template instantiation. :)

a+b would allow any library and user to implement their own sort-functions:

arr.mySort()
arr.stableSort()
...
which would call ElementType!(arr).opCmp(ElementType!(arr)).

The () are still needed since the property-style syntax doesn't work for 
"injected" methods. I'm not sure if this is consistent or not. Is there 
documented anywhere where property syntax may and may not be used?

BTW, is it only I who dislike the property like call the current inplace 
.sort allows? A non-inplace arr.sorted would OK, as is arr.dup, since it 
doesn't have side effects, but unless the intention is to make the 
parentheses in the empty argument list () redundant everywhere, I really 
think it should be called arr.sort(). arr.sort() is not even allowed today!

----

*) Or better yet: improve the language making it possible to inject 
methods into anything via an explicit syntax. Many good syntax 
suggestions have already been posted. This should obsolete the current 
method.


Regards,

Oskar
Jan 23 2006