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?

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;
          }
      }
  }
}

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?
>
>

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

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

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().
<snip>

*** This request has been marked as a duplicate of http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D/18851 ***

Stewart.

-- 
My e-mail is valid but not my primary mailbox.  Please keep replies on the 'group where everyone may benefit.

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");
}

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...

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