www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Using array.sort

reply Heinz <billgates microsoft.com> writes:
What does this sort property do? how can i use it? how do i implement opCmp.
thanks in advance
Jan 24 2007
parent reply torhu <fake address.dude> writes:
Heinz wrote:

 What does this sort property do? how can i use it? how do i implement opCmp.
thanks in advance


.sort sorts an array, using some default sort order.  If you want to 
change the order, you implement opCmp.


opCmp has got these signatures, think.  It doesn't seem to be documented 
much:

class C {
     // the argument is of type Object, not C
     int opCmp(Object other);
}

or:

struct S {
    int opCmp(S other);
}


opCmp() has to return less than zero if it's own object is smaller, more 
than zero if 'other' is smaller, and zero if they are equal.

You can't define opCmp for any other types, if you want to change the 
sort order of ints, you have to write a separate sort function.
Jan 24 2007
parent reply Heinz <billgates microsoft.com> writes:
torhu Wrote:


 Heinz wrote:

 What does this sort property do? how can i use it? how do i implement opCmp.
thanks in advance


 
 .sort sorts an array, using some default sort order.  If you want to 
 change the order, you implement opCmp.
 
 
 opCmp has got these signatures, think.  It doesn't seem to be documented 
 much:
 
 class C {
      // the argument is of type Object, not C
      int opCmp(Object other);
 }
 
 or:
 
 struct S {
     int opCmp(S other);
 }
 
 
 opCmp() has to return less than zero if it's own object is smaller, more 
 than zero if 'other' is smaller, and zero if they are equal.
 
 You can't define opCmp for any other types, if you want to change the 
 sort order of ints, you have to write a separate sort function.


So, lets assume we have the following class:

class myclass
{
        char[] cs;
}

and then we have a dinamic array of myclass, can we sort this array by the cs
property?
Jan 24 2007
parent reply Carlos Santander <csantander619 gmail.com> writes:
Heinz escribió:

 torhu Wrote:
 

 Heinz wrote:

 What does this sort property do? how can i use it? how do i implement opCmp.
thanks in advance


 .sort sorts an array, using some default sort order.  If you want to 
 change the order, you implement opCmp.


 opCmp has got these signatures, think.  It doesn't seem to be documented 
 much:

 class C {
      // the argument is of type Object, not C
      int opCmp(Object other);
 }

 or:

 struct S {
     int opCmp(S other);
 }


 opCmp() has to return less than zero if it's own object is smaller, more 
 than zero if 'other' is smaller, and zero if they are equal.

 You can't define opCmp for any other types, if you want to change the 
 sort order of ints, you have to write a separate sort function.


 
 So, lets assume we have the following class:
 
 class myclass
 {
         char[] cs;
 }
 
 and then we have a dinamic array of myclass, can we sort this array by the cs
property?


Yes, you would have to write an opCmp that does that.

-- 
Carlos Santander Bernal
Jan 24 2007
parent reply Heinz <billgates microsoft.com> writes:
Carlos Santander Wrote:


 Heinz escribió:

 torhu Wrote:
 

 Heinz wrote:

 What does this sort property do? how can i use it? how do i implement opCmp.
thanks in advance


 .sort sorts an array, using some default sort order.  If you want to 
 change the order, you implement opCmp.


 opCmp has got these signatures, think.  It doesn't seem to be documented 
 much:

 class C {
      // the argument is of type Object, not C
      int opCmp(Object other);
 }

 or:

 struct S {
     int opCmp(S other);
 }


 opCmp() has to return less than zero if it's own object is smaller, more 
 than zero if 'other' is smaller, and zero if they are equal.

 You can't define opCmp for any other types, if you want to change the 
 sort order of ints, you have to write a separate sort function.


 
 So, lets assume we have the following class:
 
 class myclass
 {
         char[] cs;
 }
 
 and then we have a dinamic array of myclass, can we sort this array by the cs
property?


 
 Yes, you would have to write an opCmp that does that.
 
 -- 
 Carlos Santander Bernal


Hi,

Do i have to declare opCmp(Object) and it'll do it automatically? or
Do i have to write the algorithm to sort the classes by the cs property? if so,
what's the sense of having a sort property if i have to implement a propietary
function, it acts as a link.
Jan 24 2007
parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Heinz wrote:

 Carlos Santander Wrote:
 

 Heinz escribió:

 torhu Wrote:


 Heinz wrote:

 What does this sort property do? how can i use it? how do i implement opCmp.
thanks in advance


 .sort sorts an array, using some default sort order.  If you want to 
 change the order, you implement opCmp.


 opCmp has got these signatures, think.  It doesn't seem to be documented 
 much:

 class C {
      // the argument is of type Object, not C
      int opCmp(Object other);
 }

 or:

 struct S {
     int opCmp(S other);
 }


 opCmp() has to return less than zero if it's own object is smaller, more 
 than zero if 'other' is smaller, and zero if they are equal.

 You can't define opCmp for any other types, if you want to change the 
 sort order of ints, you have to write a separate sort function.


 So, lets assume we have the following class:

 class myclass
 {
         char[] cs;
 }

 and then we have a dinamic array of myclass, can we sort this array by the cs
property?


 Yes, you would have to write an opCmp that does that.

 -- 
 Carlos Santander Bernal


 
 Hi,
 
 Do i have to declare opCmp(Object) and it'll do it automatically? or
 Do i have to write the algorithm to sort the classes by the cs property? if
so, what's the sense of having a sort property if i have to implement a
propietary function, it acts as a link.


opCmp needs only return the sort-order of an object in relation to another
given object. 
Using a simpler example:

class Number {
   int i;

   int opCmp (Object obj) {
     if (auto other = cast(Number) obj) {
       return this.i - other.i;
     }
     else {
       throw new Exception("Can only compare Number with another Number.");
     }
   }
}

Otherwise the .sort property would have no idea how to order the objects (there
really is 
no generic means to do this).  IIRC, there is/was a default Object.opCmp which
compared 
the address of objects, but this is really useless in terms of proper sorting. 
(Although 
it does have the usefulness of making all classes available as associative
array keys.)

-- Chris Nicholson-Sauls
Jan 24 2007
next sibling parent reply Heinz <billgates microsoft.com> writes:
Chris Nicholson-Sauls Wrote:


 Heinz wrote:

 Carlos Santander Wrote:
 

 Heinz escribió:

 torhu Wrote:


 Heinz wrote:

 What does this sort property do? how can i use it? how do i implement opCmp.
thanks in advance


 .sort sorts an array, using some default sort order.  If you want to 
 change the order, you implement opCmp.


 opCmp has got these signatures, think.  It doesn't seem to be documented 
 much:

 class C {
      // the argument is of type Object, not C
      int opCmp(Object other);
 }

 or:

 struct S {
     int opCmp(S other);
 }


 opCmp() has to return less than zero if it's own object is smaller, more 
 than zero if 'other' is smaller, and zero if they are equal.

 You can't define opCmp for any other types, if you want to change the 
 sort order of ints, you have to write a separate sort function.


 So, lets assume we have the following class:

 class myclass
 {
         char[] cs;
 }

 and then we have a dinamic array of myclass, can we sort this array by the cs
property?


 Yes, you would have to write an opCmp that does that.

 -- 
 Carlos Santander Bernal


 
 Hi,
 
 Do i have to declare opCmp(Object) and it'll do it automatically? or
 Do i have to write the algorithm to sort the classes by the cs property? if
so, what's the sense of having a sort property if i have to implement a
propietary function, it acts as a link.


 
 opCmp needs only return the sort-order of an object in relation to another
given object. 
 Using a simpler example:
 
 class Number {
    int i;
 
    int opCmp (Object obj) {
      if (auto other = cast(Number) obj) {
        return this.i - other.i;
      }
      else {
        throw new Exception("Can only compare Number with another Number.");
      }
    }
 }
 
 Otherwise the .sort property would have no idea how to order the objects
(there really is 
 no generic means to do this).  IIRC, there is/was a default Object.opCmp which
compared 
 the address of objects, but this is really useless in terms of proper sorting.
 (Although 
 it does have the usefulness of making all classes available as associative
array keys.)
 
 -- Chris Nicholson-Sauls



Hi Chris, i still don't get it hahaha. Replace the int in your example by a
char[] str; How the hell opCmp can compare a string, what value of type int
should return? thx
Jan 24 2007
next sibling parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Heinz wrote:

 Chris Nicholson-Sauls Wrote:
 

 Heinz wrote:

 Carlos Santander Wrote:


 Heinz escribió:

 torhu Wrote:


 Heinz wrote:

 What does this sort property do? how can i use it? how do i implement opCmp.
thanks in advance


 .sort sorts an array, using some default sort order.  If you want to 
 change the order, you implement opCmp.


 opCmp has got these signatures, think.  It doesn't seem to be documented 
 much:

 class C {
      // the argument is of type Object, not C
      int opCmp(Object other);
 }

 or:

 struct S {
     int opCmp(S other);
 }


 opCmp() has to return less than zero if it's own object is smaller, more 
 than zero if 'other' is smaller, and zero if they are equal.

 You can't define opCmp for any other types, if you want to change the 
 sort order of ints, you have to write a separate sort function.


 So, lets assume we have the following class:

 class myclass
 {
         char[] cs;
 }

 and then we have a dinamic array of myclass, can we sort this array by the cs
property?


 Yes, you would have to write an opCmp that does that.

 -- 
 Carlos Santander Bernal


 Hi,

 Do i have to declare opCmp(Object) and it'll do it automatically? or
 Do i have to write the algorithm to sort the classes by the cs property? if
so, what's the sense of having a sort property if i have to implement a
propietary function, it acts as a link.


 opCmp needs only return the sort-order of an object in relation to another
given object. 
 Using a simpler example:

 class Number {
    int i;

    int opCmp (Object obj) {
      if (auto other = cast(Number) obj) {
        return this.i - other.i;
      }
      else {
        throw new Exception("Can only compare Number with another Number.");
      }
    }
 }

 Otherwise the .sort property would have no idea how to order the objects
(there really is 
 no generic means to do this).  IIRC, there is/was a default Object.opCmp which
compared 
 the address of objects, but this is really useless in terms of proper sorting.
 (Although 
 it does have the usefulness of making all classes available as associative
array keys.)

 -- Chris Nicholson-Sauls


 
 
 Hi Chris, i still don't get it hahaha. Replace the int in your example by a
char[] str; How the hell opCmp can compare a string, what value of type int
should return? thx


Return any value less than 0 for "less than", 0 for "equal to", and any value
greater than 
zero for "greater than".  (Most people default to -1,0,1.)  For a char[] you'd
have to 
decide how you want to order characters... but one generic means is just to
compare their 
character codes.  So something like:

class myclass {
   char[] cs;

   int opCmp (Object obj) {
     char oc ;

     if (auto other = cast(myclass) obj) {
       foreach (i, c; cs) {
         oc = other.cs[i];
         if (c < oc) {
           return -1;
         }
         else if (c > oc) {
           return 1;
         }
       }
       return 0;
     }
     else {
       throw new Exception("Can only compare myclass with myclass.");
     }
   }
}

-- Chris Nicholson-Sauls
Jan 24 2007
parent reply Heinz <billgates microsoft.com> writes:
Chris Nicholson-Sauls Wrote:


 Heinz wrote:

 Chris Nicholson-Sauls Wrote:
 

 Heinz wrote:

 Carlos Santander Wrote:


 Heinz escribió:

 torhu Wrote:


 Heinz wrote:

 What does this sort property do? how can i use it? how do i implement opCmp.
thanks in advance


 .sort sorts an array, using some default sort order.  If you want to 
 change the order, you implement opCmp.


 opCmp has got these signatures, think.  It doesn't seem to be documented 
 much:

 class C {
      // the argument is of type Object, not C
      int opCmp(Object other);
 }

 or:

 struct S {
     int opCmp(S other);
 }


 opCmp() has to return less than zero if it's own object is smaller, more 
 than zero if 'other' is smaller, and zero if they are equal.

 You can't define opCmp for any other types, if you want to change the 
 sort order of ints, you have to write a separate sort function.


 So, lets assume we have the following class:

 class myclass
 {
         char[] cs;
 }

 and then we have a dinamic array of myclass, can we sort this array by the cs
property?


 Yes, you would have to write an opCmp that does that.

 -- 
 Carlos Santander Bernal


 Hi,

 Do i have to declare opCmp(Object) and it'll do it automatically? or
 Do i have to write the algorithm to sort the classes by the cs property? if
so, what's the sense of having a sort property if i have to implement a
propietary function, it acts as a link.


 opCmp needs only return the sort-order of an object in relation to another
given object. 
 Using a simpler example:

 class Number {
    int i;

    int opCmp (Object obj) {
      if (auto other = cast(Number) obj) {
        return this.i - other.i;
      }
      else {
        throw new Exception("Can only compare Number with another Number.");
      }
    }
 }

 Otherwise the .sort property would have no idea how to order the objects
(there really is 
 no generic means to do this).  IIRC, there is/was a default Object.opCmp which
compared 
 the address of objects, but this is really useless in terms of proper sorting.
 (Although 
 it does have the usefulness of making all classes available as associative
array keys.)

 -- Chris Nicholson-Sauls


 
 
 Hi Chris, i still don't get it hahaha. Replace the int in your example by a
char[] str; How the hell opCmp can compare a string, what value of type int
should return? thx


 
 Return any value less than 0 for "less than", 0 for "equal to", and any value
greater than 
 zero for "greater than".  (Most people default to -1,0,1.)  For a char[] you'd
have to 
 decide how you want to order characters... but one generic means is just to
compare their 
 character codes.  So something like:
 
 class myclass {
    char[] cs;
 
    int opCmp (Object obj) {
      char oc ;
 
      if (auto other = cast(myclass) obj) {
        foreach (i, c; cs) {
          oc = other.cs[i];
          if (c < oc) {
            return -1;
          }
          else if (c > oc) {
            return 1;
          }
        }
        return 0;
      }
      else {
        throw new Exception("Can only compare myclass with myclass.");
      }
    }
 }
 
 -- Chris Nicholson-Sauls



Thanks chris, i finally understood. This example is much clearer than the other
one.
We could also use in this case std.string.icmp(), as it returns the same values.

Thanks man, good luck.
Jan 24 2007
parent Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Heinz wrote:

 Chris Nicholson-Sauls Wrote:
 

 Heinz wrote:

 Chris Nicholson-Sauls Wrote:


 Heinz wrote:

 Carlos Santander Wrote:


 Heinz escribió:

 torhu Wrote:


 Heinz wrote:

 What does this sort property do? how can i use it? how do i implement opCmp.
thanks in advance


 .sort sorts an array, using some default sort order.  If you want to 
 change the order, you implement opCmp.


 opCmp has got these signatures, think.  It doesn't seem to be documented 
 much:

 class C {
      // the argument is of type Object, not C
      int opCmp(Object other);
 }

 or:

 struct S {
     int opCmp(S other);
 }


 opCmp() has to return less than zero if it's own object is smaller, more 
 than zero if 'other' is smaller, and zero if they are equal.

 You can't define opCmp for any other types, if you want to change the 
 sort order of ints, you have to write a separate sort function.


 So, lets assume we have the following class:

 class myclass
 {
         char[] cs;
 }

 and then we have a dinamic array of myclass, can we sort this array by the cs
property?


 Yes, you would have to write an opCmp that does that.

 -- 
 Carlos Santander Bernal


 Hi,

 Do i have to declare opCmp(Object) and it'll do it automatically? or
 Do i have to write the algorithm to sort the classes by the cs property? if
so, what's the sense of having a sort property if i have to implement a
propietary function, it acts as a link.


 opCmp needs only return the sort-order of an object in relation to another
given object. 
 Using a simpler example:

 class Number {
    int i;

    int opCmp (Object obj) {
      if (auto other = cast(Number) obj) {
        return this.i - other.i;
      }
      else {
        throw new Exception("Can only compare Number with another Number.");
      }
    }
 }

 Otherwise the .sort property would have no idea how to order the objects
(there really is 
 no generic means to do this).  IIRC, there is/was a default Object.opCmp which
compared 
 the address of objects, but this is really useless in terms of proper sorting.
 (Although 
 it does have the usefulness of making all classes available as associative
array keys.)

 -- Chris Nicholson-Sauls


 Hi Chris, i still don't get it hahaha. Replace the int in your example by a
char[] str; How the hell opCmp can compare a string, what value of type int
should return? thx


 Return any value less than 0 for "less than", 0 for "equal to", and any value
greater than 
 zero for "greater than".  (Most people default to -1,0,1.)  For a char[] you'd
have to 
 decide how you want to order characters... but one generic means is just to
compare their 
 character codes.  So something like:

 class myclass {
    char[] cs;

    int opCmp (Object obj) {
      char oc ;

      if (auto other = cast(myclass) obj) {
        foreach (i, c; cs) {
          oc = other.cs[i];
          if (c < oc) {
            return -1;
          }
          else if (c > oc) {
            return 1;
          }
        }
        return 0;
      }
      else {
        throw new Exception("Can only compare myclass with myclass.");
      }
    }
 }

 -- Chris Nicholson-Sauls


 
 
 Thanks chris, i finally understood. This example is much clearer than the
other one.
 We could also use in this case std.string.icmp(), as it returns the same
values.
 
 Thanks man, good luck.


You know, I always forget about that function because I use it and its sort
only rarely in 
my own code.  That's most likely the way you want to go.

-- Chris Nicholson-Sauls
Jan 25 2007
prev sibling parent Derek Parnell <derek nomail.afraid.org> writes:
On Wed, 24 Jan 2007 22:55:57 -0500, Heinz wrote:

 

 Hi Chris, i still don't get it hahaha. Replace the int in your
 example by a char[] str; How the hell opCmp can compare a string,
 what value of type int should return? thx


This is a good question. It all depends on how you want to define when one
string is less than another. 

Here is one definition, just for example purposes.

import std.stdio;

 class myclass {
    char[] cs;
    this(char[] d) { cs = d.dup; }

    int opCmp (Object obj)
    {
       // Strings contain unicode code-points.
       // Shorter strings compare "less than" longer strings.
       // Equal length strings compare respective unicode code-points.

       if (cs.length < (cast(myclass)obj).cs.length)
           return -1;
       if (cs.length > (cast(myclass)obj).cs.length)
           return  1;
       if (cs == (cast(myclass)obj).cs)
           return 0;

       // Ok, so they are different. Now we look at each code-point.
       dchar[] temp_self  = std.utf.toUTF32(cs);
       dchar[] temp_other = std.utf.toUTF32((cast(myclass)obj).cs);

       foreach(int i, dchar c; temp_self)
       {
          dchar oc;
          oc = temp_other[i];
          if (c < oc)
             return -1;
          if (c > oc)
             return  1;
       }
       throw new Error("Failed to find difference. Should never happen.");
    }
 }

void show(myclass[] Data, char[] Title)
{
   writefln("\n\n%s\n--------------", Title);
   foreach(myclass x; Data)
   {
        writefln("%s", x.cs);
   }
}

void main()
{
   myclass[] A;
   A ~= new myclass("one");
   A ~= new myclass("two");
   A ~= new myclass("three");
   A ~= new myclass("four");
   A ~= new myclass("five");
   A ~= new myclass("six");
   A ~= new myclass("seven");
   A ~= new myclass("eight");
   A ~= new myclass("nine");
   A ~= new myclass("ten");

   show(A, "Before");
   A.sort;
   show(A, "After");

}

 =============

C:\temp>dmd -run test.d


Before
--------------
one
two
three
four
five
six
seven
eight
nine
ten


After
--------------
one
six
ten
two
five
four
nine
eight
seven
three

-- 
Derek
(skype: derek.j.parnell)
Melbourne, Australia
"Down with mediocrity!"
25/01/2007 4:03:16 PM
Jan 24 2007
prev sibling parent reply Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Chris Nicholson-Sauls wrote:

 class Number {
   int i;
 
   int opCmp (Object obj) {
     if (auto other = cast(Number) obj) {
       return this.i - other.i;
     }
     else {
       throw new Exception("Can only compare Number with another Number.");
     }
   }
 }


Broken. (int.max - int.min) doesn't fit in an int...
This is a valid implementation only when the range is less than about 
half that of an int. In practice, that means this is a valid 
implementation if member 'i' is a bool, byte, ubyte, short, ushort, char 
or wchar, but not if it's an int, uint, long or ulong. Nor will it be 
correct for cent and ucent when they get implemented.
Any built-in type not mentioned don't work. (unless I missed any ;) )
Well, theoretically, on a machine with an address space of 31 bits or 
less it would also work for pointers on that machine...

A generic way to do it would be something like
   return typeid(i).compare(&i, &other.i);
That should always return a valid value for built-in types and arrays, 
and call opCmp for user-defined types[1].


[1]: With some wrapping. nulls are always considered 'less than', and 
structs without opCmp members default to calling memcmp instead.
Jan 25 2007
parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
Frits van Bommel wrote:

 Chris Nicholson-Sauls wrote:

 class Number {
   int i;

   int opCmp (Object obj) {
     if (auto other = cast(Number) obj) {
       return this.i - other.i;
     }
     else {
       throw new Exception("Can only compare Number with another 
 Number.");
     }
   }
 }


 
 Broken. (int.max - int.min) doesn't fit in an int...


Granted.  :)  I was really just trying to be illustrative, not neccessarily
thorough. 
(Take a look at the /glaring/ error in my other exmaple... which, in hindsight,
probably 
should've been more complete|correct than this one.  Oh well, that's what I get
for 
posting while half asleep.)

But you make a good point of the sort that belongs in a FAQ somewhere,
actually.  I've 
seen plenty of opCmp's defined along these lines in other code.

-- Chris Nicholson-Sauls
Jan 25 2007
parent Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:
Chris Nicholson-Sauls wrote:

 Frits van Bommel wrote:

 Chris Nicholson-Sauls wrote:

 class Number {
   int i;

   int opCmp (Object obj) {
     if (auto other = cast(Number) obj) {
       return this.i - other.i;
     }
     else {
       throw new Exception("Can only compare Number with another 
 Number.");
     }
   }
 }


 Broken. (int.max - int.min) doesn't fit in an int...


 
 Granted.  :)  I was really just trying to be illustrative, not 
 neccessarily thorough. (Take a look at the /glaring/ error in my other 
 exmaple... which, in hindsight, probably should've been more 
 complete|correct than this one.  Oh well, that's what I get for posting 
 while half asleep.)
 
 But you make a good point of the sort that belongs in a FAQ somewhere, 
 actually.  I've seen plenty of opCmp's defined along these lines in 
 other code.


I usually prefer to write my opCmp in this fashion:
     return typeid(T).compare(&this.member, &other.member);

(replace T by whatever type you're comparing, or even 
"typeof(this.member)" if you're afraid you might forget to change this 
code if you change the type of 'member')

That way I don't make any stupid or annoying mistakes...
Jan 26 2007