www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Idea: customizable array .sort() property

reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
The built-in .sort property is fine for most things.  It uses qsort() and 
calls the opCmp.  Good enough for most things.

But say you want to sort in more than one way.  There is no way to overload 
opCmp to compare two of the same type.  So instead, we are stuck importing 
std.c.stdlib, declaring an extern(C) int compare(void* a, void* b) function, 
and passing in the array to qsort().

Instead, wouldn't it be cool if we could pass in a custom compare function 
to .sort() that would be used instead of the default opCmp?

class A
{
    int mX, mY;
    int opCmp(A other)
    {
        if(this.mX<other.mX)
            return -1;
        else
            return 1;
    }
}

int mySort(A one, A other)
{
    if(one.mY<other.mY)
        return -1;
    else
        return 1;
}
..

A[] a;
// add some elements
// sort by X
a.sort;

// sort by Y
a.sort(mySort);


What do you think? 
Apr 20 2005
next sibling parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
I've already published it here, but cannot find it in archive, anyway....


// "smart" sort implementation, works 1.3 times faster than D builtin sort

template sort(T)
{
  void sort(T[] arr, int function(in T l, in T r) cmp)
  {
      const int quick_sort_threshold = 9;

      if(arr.length < 2) return;

      void swap_if_less( inout T t1, inout T t2 )
      {
        if( cmp(t1, t2) < 0 ) { T t = t1; t1 = t2; t2 = t; }
      }
      void swap( inout T t1, inout T t2 )
      {
        T t = t1; t1 = t2; t2 = t;
      }

      int  stack[80];
      int* top = stack;
      int  limit = arr.length;
      int  base = 0;

      for(;;)
      {
          int len = limit - base;

          int i;
          int j;
          int pivot;

          if(len > quick_sort_threshold)
          {
              // we use base + len/2 as the pivot
              pivot = base + len / 2;
              swap(arr[base], arr[pivot]);

              i = base + 1;
              j = limit - 1;

              // now ensure that *i <= *base <= *j
              swap_if_less(arr[j], arr[i]);
              swap_if_less(arr[base],arr[i]);
              swap_if_less(arr[j],arr[base]);

              for(;;)
              {
                  do i++; while( arr[i] <  arr[base] );
                  do j--; while( arr[base] <  arr[j] );
                  if( i > j )
                  {
                      break;
                  }
                  swap(arr[i], arr[j]);
              }

              swap(arr[base], arr[j]);

              // now, push the largest sub-array
              if(j - base > limit - i)
              {
                  top[0] = base;
                  top[1] = j;
                  base   = i;
              }
              else
              {
                  top[0] = i;
                  top[1] = limit;
                  limit  = j;
              }
              top += 2;
          }
          else
          {
              // the sub-array is small, perform insertion sort
              j = base;
              i = j + 1;

              for(; i < limit; j = i, i++)
              {
                  for(; cmp(arr[j + 1],arr[j]) < 0; j--)
                  {
                      swap(arr[j + 1],arr[j]);
                      if(j == base)
                          break;
                  }
              }
              if(top > stack)
              {
                  top  -= 2;
                  base  = top[0];
                  limit = top[1];
              }
              else
                  break;
          }
      }
  }
}
Apr 20 2005
parent reply Derek Parnell <derek psych.ward> writes:
On Wed, 20 Apr 2005 17:04:56 -0700, Andrew Fedoniouk wrote:

 I've already published it here, but cannot find it in archive, anyway....

[snip] Hi Andrew, I just tried out your routine but it seems to have a bug for lengths > 9. Here is my code ... <code> import std.stdio; import sorts; // Andrew's template. int mycmp(char a, char b) { // Upper case is always sorted after than lowercase. int res; int simplecmp(char a, char b) { if (a < b) return -1; if (a > b) return 1; return 0; } if (a >= 'A' && a <='Z') { if (b >='A' && b <= 'Z') { // Both uppercase res = simplecmp(a,b); } else { // First is uppercase so it goes high. res = 1; } } else { if (b >='A' && b <= 'Z') { // First is lowercase so it goes low. res = -1; } else { // Both lowercase res = simplecmp(a,b); } } return res; } alias sorts.sort!(char) csort; void main(char[][] pArgs) { char[] a; if (pArgs.length == 1) a = "AbCdEfGhIjKlMnOpQrStUvWxYz".dup; else a = pArgs[1].dup; a.csort(&mycmp); writefln("%s", a); } </code> -- Derek Melbourne, Australia 21/04/2005 12:07:42 PM
Apr 20 2005
next sibling parent "Andrew Fedoniouk" <news terrainformatica.com> writes:
Yep, it was my bug.  And below is fixed version.
Thanks, Derek.

template sort(T)
{
  void sort(T[] arr, int function(in T l, in T r) cmp)
  {
      const int quick_sort_threshold = 9;

      if(arr.length < 2) return;

      void swap_if_less( inout T t1, inout T t2 )
      {
        if( cmp(t1, t2) < 0 ) { T t = t1; t1 = t2; t2 = t; }
      }
      void swap( inout T t1, inout T t2 )
      {
        T t = t1; t1 = t2; t2 = t;
      }

      int  stack[80];
      int* top = stack.ptr;
      int  limit = arr.length;
      int  base = 0;

      for(;;)
      {
          int len = limit - base;

          int i;
          int j;
          int pivot;

          if(len > quick_sort_threshold)
          {
              // we use base + len/2 as the pivot
              pivot = base + len / 2;
              swap(arr[base], arr[pivot]);

              i = base + 1;
              j = limit - 1;

              // now ensure that *i <= *base <= *j
              swap_if_less(arr[j], arr[i]);
              swap_if_less(arr[base],arr[i]);
              swap_if_less(arr[j],arr[base]);

              for(;;)
              {
                  do i++; while( cmp(arr[i],arr[base]) < 0 );
                  do j--; while( cmp(arr[base],arr[j]) < 0 );
                  if( i > j )
                  {
                      break;
                  }
                  swap(arr[i], arr[j]);
              }

              swap(arr[base], arr[j]);

              // now, push the largest sub-array
              if(j - base > limit - i)
              {
                  top[0] = base;
                  top[1] = j;
                  base   = i;
              }
              else
              {
                  top[0] = i;
                  top[1] = limit;
                  limit  = j;
              }
              top += 2;
          }
          else
          {
              // the sub-array is small, perform insertion sort
              j = base;
              i = j + 1;

              for(; i < limit; j = i, i++)
              {
                  for(; cmp(arr[j + 1],arr[j]) < 0; j--)
                  {
                      swap(arr[j + 1],arr[j]);
                      if(j == base)
                          break;
                  }
              }
              if(top > stack.ptr)
              {
                  top  -= 2;
                  base  = top[0];
                  limit = top[1];
              }
              else
                  break;
          }
      }
  }
}

------------------------------------------

Test:

int less(char a, char b)
{
    // Upper case is always sorted after than lowercase.
    int A = a; if(a >= 'A' && a <='Z') A <<= 8;
    int B = b; if(b >= 'A' && b <='Z') B <<= 8;
    return A - B;
}

int main(char[][] args)
{

  char[] arr = "KlMnOpQrStUvWxYzAbCdEfGhIj".dup;

  writef("%s\n",arr);
  sort!(char)(arr,&less);

  writef("%s\n",arr);
  writef("done\n");
}
Apr 21 2005
prev sibling parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
Derek, your e-mal address at b..p...com. is not working.
Do you have any other addresses out of the psych.ward ?

"Derek Parnell" <derek psych.ward> wrote in message 
news:16zrq2tvts9vz.1ee6p4464fefz.dlg 40tude.net... 
Apr 22 2005
parent Derek Parnell <derek psych.ward> writes:
On Fri, 22 Apr 2005 13:07:40 -0700, Andrew Fedoniouk wrote:

 Derek, your e-mal address at b..p...com. is not working.
 Do you have any other addresses out of the psych.ward ?

Its not?! I'm getting emails from others. Try again. In any case, there are three addresses you could use ... ddparnell using the domain bigpond (ddot) com <-- Main one dpar8777 using the domain bigpond (ddot) net (ddot) au <-- cable one dparnell using the domain admerex (ddot) com <-- My office address -- Derek Parnell Melbourne, Australia http://www.dsource.org/projects/build 23/04/2005 10:25:52 AM
Apr 22 2005
prev sibling next sibling parent "TechnoZeus" <TechnoZeus PeoplePC.com> writes:
Shouldn't casting allow this automatically?

TZ

"Jarrett Billingsley" <kb3ctd2 yahoo.com> wrote in message
news:d46q31$1j2b$1 digitaldaemon.com...
 The built-in .sort property is fine for most things.  It uses qsort() and
 calls the opCmp.  Good enough for most things.

 But say you want to sort in more than one way.  There is no way to overload
 opCmp to compare two of the same type.  So instead, we are stuck importing
 std.c.stdlib, declaring an extern(C) int compare(void* a, void* b) function,
 and passing in the array to qsort().

 Instead, wouldn't it be cool if we could pass in a custom compare function
 to .sort() that would be used instead of the default opCmp?

 class A
 {
     int mX, mY;
     int opCmp(A other)
     {
         if(this.mX<other.mX)
             return -1;
         else
             return 1;
     }
 }

 int mySort(A one, A other)
 {
     if(one.mY<other.mY)
         return -1;
     else
         return 1;
 }
 ..

 A[] a;
 // add some elements
 // sort by X
 a.sort;

 // sort by Y
 a.sort(mySort);


 What do you think?

Apr 20 2005
prev sibling next sibling parent Derek Parnell <derek psych.ward> writes:
On Wed, 20 Apr 2005 19:57:27 -0400, Jarrett Billingsley wrote:

 ... wouldn't it be cool if we could pass in a custom compare function 
 to .sort() that would be used instead of the default opCmp?

Much needed and overdue. I like it. -- Derek Parnell Melbourne, Australia http://www.dsource.org/projects/build/ v2.03 released 20/Apr/2005 http://www.prowiki.org/wiki4d/wiki.cgi?FrontPage 21/04/2005 10:46:23 AM
Apr 20 2005
prev sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
Jarrett Billingsley wrote:
 The built-in .sort property is fine for most things.  It uses qsort() and 
 calls the opCmp.  Good enough for most things.
 
 But say you want to sort in more than one way.  There is no way to overload 
 opCmp to compare two of the same type.  So instead, we are stuck importing 
 std.c.stdlib, declaring an extern(C) int compare(void* a, void* b) function, 
 and passing in the array to qsort().

*** This request has been marked as a duplicate of digitalmars.D/18851 *** Stewart. -- My e-mail is valid but not my primary mailbox. Please keep replies on the 'group where everyone may benefit.
Apr 21 2005