www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - array.sort(cmp) ?

reply z gg.com writes:
Currently array has a build-in method .sort, which use the default opCmp.

However it often need to sort an array in different ways: e.g. an arry of File
object, we may need to

File[] files;

files.sort(BySize);
files.sort(ByDate);
files.sort(ByName);
files.sort(ByExtention);

so I wonder if we should add another build-in method for array (T):

array.sort(int function(T, T) cmp)

to allow user pass in comparator other than the default opCmp().

Or we should provide a global template function in the standard library:

template(T) {
sort(T[] array, int function(T, T) cmp);
}
Aug 04 2005
next sibling parent "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
<z gg.com> wrote in message news:dctotb$ql5$1 digitaldaemon.com...
 Currently array has a build-in method .sort, which use the default opCmp.

 However it often need to sort an array in different ways: e.g. an arry of 
 File
 object, we may need to

I'd love this. I've run into this a few times, and it's ugly to have to use qsort and write a comparator function (which can't be a nested function or function literal as nested functions don't have C linkage..).
Aug 04 2005
prev sibling next sibling parent "Regan Heath" <regan netwin.co.nz> writes:
On Thu, 4 Aug 2005 19:05:15 +0000 (UTC), <z gg.com> wrote:
 Currently array has a build-in method .sort, which use the default opCmp.

 However it often need to sort an array in different ways: e.g. an arry  
 of File
 object, we may need to

 File[] files;

 files.sort(BySize);
 files.sort(ByDate);
 files.sort(ByName);
 files.sort(ByExtention);

 so I wonder if we should add another build-in method for array (T):

 array.sort(int function(T, T) cmp)

Or a delegate. With a delegate you could pass any addition information required for the sort in the class. Regan
Aug 04 2005
prev sibling next sibling parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Thu, 4 Aug 2005 19:05:15 +0000 (UTC), <z gg.com> wrote:
 Currently array has a build-in method .sort, which use the default opCmp.

 However it often need to sort an array in different ways: e.g. an arry  
 of File
 object, we may need to

 File[] files;

 files.sort(BySize);
 files.sort(ByDate);
 files.sort(ByName);
 files.sort(ByExtention);

 so I wonder if we should add another build-in method for array (T):

 array.sort(int function(T, T) cmp)

 to allow user pass in comparator other than the default opCmp().

 Or we should provide a global template function in the standard library:

 template(T) {
 sort(T[] array, int function(T, T) cmp);
 }

I just had an idea. Could the 'sort' property be a get/set property and thus assignable? eg. int function(File lhs, File rhs) foo; files.sort = foo; //assigns sort function files.sort; //calls sort function ? Regan
Aug 04 2005
parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Fri, 05 Aug 2005 14:09:00 +1200, Regan Heath <regan netwin.co.nz> wrote:
 On Thu, 4 Aug 2005 19:05:15 +0000 (UTC), <z gg.com> wrote:
 Currently array has a build-in method .sort, which use the default  
 opCmp.

 However it often need to sort an array in different ways: e.g. an arry  
 of File
 object, we may need to

 File[] files;

 files.sort(BySize);
 files.sort(ByDate);
 files.sort(ByName);
 files.sort(ByExtention);

 so I wonder if we should add another build-in method for array (T):

 array.sort(int function(T, T) cmp)

 to allow user pass in comparator other than the default opCmp().

 Or we should provide a global template function in the standard library:

 template(T) {
 sort(T[] array, int function(T, T) cmp);
 }

I just had an idea. Could the 'sort' property be a get/set property and thus assignable? eg.

Or rather: int foo(File lhs, File rhs) { .. } files.sort = &foo; //assigns sort function files.sort; //calls sort function Regan
Aug 04 2005
parent reply Shammah Chancellor <Shammah_member pathlink.com> writes:
In article <opsu0iy2a523k2f5 nrage.netwin.co.nz>, Regan Heath says...
On Fri, 05 Aug 2005 14:09:00 +1200, Regan Heath <regan netwin.co.nz> wrote:
 On Thu, 4 Aug 2005 19:05:15 +0000 (UTC), <z gg.com> wrote:
 Currently array has a build-in method .sort, which use the default  
 opCmp.

 However it often need to sort an array in different ways: e.g. an arry  
 of File
 object, we may need to

 File[] files;

 files.sort(BySize);
 files.sort(ByDate);
 files.sort(ByName);
 files.sort(ByExtention);

 so I wonder if we should add another build-in method for array (T):

 array.sort(int function(T, T) cmp)

 to allow user pass in comparator other than the default opCmp().

 Or we should provide a global template function in the standard library:

 template(T) {
 sort(T[] array, int function(T, T) cmp);
 }

I just had an idea. Could the 'sort' property be a get/set property and thus assignable? eg.

Or rather: int foo(File lhs, File rhs) { .. } files.sort = &foo; //assigns sort function files.sort; //calls sort function Regan

If a class can be sorted by different properties, it is intuitive that it should be able to be compared by multiple properties. The following example should handle both things. Although, Initially I tried to call my delegate opCmp just to see if operator overloading would work on a delegate. (Since you can have a delegate as a member of the class and it looks like a method to everyone else.) I personally think two things should happen although it's not relevant to this example. That A, delegates should be able to have initializers inside of classes, like in functions. And B, that operator overloading should look for delegates with the same name as the function that would overload it. Example code: #class Foo { # public int value; # public int delegate(in Foo) opCmpDelegate; # # int CompareAlwaysLess(in Foo x) { return -1; }; # int CompareForReal(Foo x) { return this.value - x.value; } # this(int initArg) { opCmpDelegate = &CompareAlwaysLess; value = initArg; } # int opCmp(Foo x) { return opCmpDelegate(x); }; #} # #int main(char[][] args) #{ # Foo a = new Foo(20); # Foo b = new Foo(10); # # writefln( a < b ? "true" : "false" ); # a.opCmpDelegate = &a.CompareForReal; # writefln( a < b ? "true" : "false" ); # # return 0; #}
Aug 04 2005
parent reply "Regan Heath" <regan netwin.co.nz> writes:
On Fri, 5 Aug 2005 03:09:42 +0000 (UTC), Shammah Chancellor  
<Shammah_member pathlink.com> wrote:
 In article <opsu0iy2a523k2f5 nrage.netwin.co.nz>, Regan Heath says...
 On Fri, 05 Aug 2005 14:09:00 +1200, Regan Heath <regan netwin.co.nz>  
 wrote:
 On Thu, 4 Aug 2005 19:05:15 +0000 (UTC), <z gg.com> wrote:
 Currently array has a build-in method .sort, which use the default
 opCmp.

 However it often need to sort an array in different ways: e.g. an arry
 of File
 object, we may need to

 File[] files;

 files.sort(BySize);
 files.sort(ByDate);
 files.sort(ByName);
 files.sort(ByExtention);

 so I wonder if we should add another build-in method for array (T):

 array.sort(int function(T, T) cmp)

 to allow user pass in comparator other than the default opCmp().

 Or we should provide a global template function in the standard  
 library:

 template(T) {
 sort(T[] array, int function(T, T) cmp);
 }

I just had an idea. Could the 'sort' property be a get/set property and thus assignable? eg.

Or rather: int foo(File lhs, File rhs) { .. } files.sort = &foo; //assigns sort function files.sort; //calls sort function Regan

If a class can be sorted by different properties, it is intuitive that it should be able to be compared by multiple properties. The following example should handle both things. Although, Initially I tried to call my delegate opCmp just to see if operator overloading would work on a delegate. (Since you can have a delegate as a member of the class and it looks like a method to everyone else.) I personally think two things should happen although it's not relevant to this example. That A, delegates should be able to have initializers inside of classes, like in functions. And B, that operator overloading should look for delegates with the same name as the function that would overload it. Example code: #class Foo { # public int value; # public int delegate(in Foo) opCmpDelegate; # # int CompareAlwaysLess(in Foo x) { return -1; }; # int CompareForReal(Foo x) { return this.value - x.value; } # this(int initArg) { opCmpDelegate = &CompareAlwaysLess; value = initArg; } # int opCmp(Foo x) { return opCmpDelegate(x); }; #} # #int main(char[][] args) #{ # Foo a = new Foo(20); # Foo b = new Foo(10); # # writefln( a < b ? "true" : "false" ); # a.opCmpDelegate = &a.CompareForReal; # writefln( a < b ? "true" : "false" ); # # return 0; #}

Ok, but how does it work with an array? Foo[] array; foreach(Foo f; array) f.opCmpDelegate = &f.CompareForReal; array.sort; ? This seems wrong, it would allow different items to be sorted differently in the same array or sort operation. IMO the method of sorting should be defined per sort or per array, not per item. Regan
Aug 04 2005
next sibling parent zhou gg.com writes:
In article <opsu0nedtt23k2f5 nrage.netwin.co.nz>, Regan Heath says...
Ok, but how does it work with an array?

Foo[] array;
foreach(Foo f; array) f.opCmpDelegate = &f.CompareForReal;
array.sort;

?

This seems wrong, it would allow different items to be sorted differently  
in the same array or sort operation. IMO the method of sorting should be  
defined per sort or per array, not per item.

Regan

Exactly. I still think STL-like one-liner is still the best: quickSort(array.start, array.end, cmpFunc); heapSort(array.start, array.end, cmpFunc); .. stableSort(array.start, array.end, cmpFunc); unstableSort(array.start, array.end, cmpFunc); everything is stated on a single line: the [begin,end) of an array, the sorting method, and the comparator. How would you devise something more clear to read, and more flexible to change? We really don't need to re-invent the wheels, especially those square ones.
Aug 04 2005
prev sibling parent reply Shammah Chancellor <Shammah_member pathlink.com> writes:
In article <opsu0nedtt23k2f5 nrage.netwin.co.nz>, Regan Heath says...
On Fri, 5 Aug 2005 03:09:42 +0000 (UTC), Shammah Chancellor  
<Shammah_member pathlink.com> wrote:
 In article <opsu0iy2a523k2f5 nrage.netwin.co.nz>, Regan Heath says...
 On Fri, 05 Aug 2005 14:09:00 +1200, Regan Heath <regan netwin.co.nz>  
 wrote:
 On Thu, 4 Aug 2005 19:05:15 +0000 (UTC), <z gg.com> wrote:
 Currently array has a build-in method .sort, which use the default
 opCmp.

 However it often need to sort an array in different ways: e.g. an arry
 of File
 object, we may need to

 File[] files;

 files.sort(BySize);
 files.sort(ByDate);
 files.sort(ByName);
 files.sort(ByExtention);

 so I wonder if we should add another build-in method for array (T):

 array.sort(int function(T, T) cmp)

 to allow user pass in comparator other than the default opCmp().

 Or we should provide a global template function in the standard  
 library:

 template(T) {
 sort(T[] array, int function(T, T) cmp);
 }

I just had an idea. Could the 'sort' property be a get/set property and thus assignable? eg.

Or rather: int foo(File lhs, File rhs) { .. } files.sort = &foo; //assigns sort function files.sort; //calls sort function Regan

If a class can be sorted by different properties, it is intuitive that it should be able to be compared by multiple properties. The following example should handle both things. Although, Initially I tried to call my delegate opCmp just to see if operator overloading would work on a delegate. (Since you can have a delegate as a member of the class and it looks like a method to everyone else.) I personally think two things should happen although it's not relevant to this example. That A, delegates should be able to have initializers inside of classes, like in functions. And B, that operator overloading should look for delegates with the same name as the function that would overload it. Example code: #class Foo { # public int value; # public int delegate(in Foo) opCmpDelegate; # # int CompareAlwaysLess(in Foo x) { return -1; }; # int CompareForReal(Foo x) { return this.value - x.value; } # this(int initArg) { opCmpDelegate = &CompareAlwaysLess; value = initArg; } # int opCmp(Foo x) { return opCmpDelegate(x); }; #} # #int main(char[][] args) #{ # Foo a = new Foo(20); # Foo b = new Foo(10); # # writefln( a < b ? "true" : "false" ); # a.opCmpDelegate = &a.CompareForReal; # writefln( a < b ? "true" : "false" ); # # return 0; #}

Ok, but how does it work with an array? Foo[] array; foreach(Foo f; array) f.opCmpDelegate = &f.CompareForReal; array.sort; ? This seems wrong, it would allow different items to be sorted differently in the same array or sort operation. IMO the method of sorting should be defined per sort or per array, not per item. Regan

Hadn't thought of that. opCmpDelegate should probably have been static. But that leads to weird behavior when you forget to reset it and some other code calls it. -Sha
Aug 04 2005
parent "Regan Heath" <regan netwin.co.nz> writes:
On Fri, 5 Aug 2005 05:25:42 +0000 (UTC), Shammah Chancellor  
<Shammah_member pathlink.com> wrote:
 This seems wrong, it would allow different items to be sorted  
 differently
 in the same array or sort operation. IMO the method of sorting should be
 defined per sort or per array, not per item.

 Regan

Hadn't thought of that. opCmpDelegate should probably have been static. But that leads to weird behavior when you forget to reset it and some other code calls it.

Yeah.. I followed that same thought pattern :) Regan
Aug 04 2005
prev sibling next sibling parent Niko Korhonen <niktheblak hotmail.com> writes:
z gg.com wrote:
  > so I wonder if we should add another build-in method for array (T):
 
 array.sort(int function(T, T) cmp)
 
 to allow user pass in comparator other than the default opCmp().

That would be great! This is a common scenario and currently we have to roll out our own custom sort routine each time we need to customize anything. This is something that a modern standard library (and considering the C standard library provided a sort with custom comparator, even not so modern) should *definitely* do. Basically I find myself using MinTL most of the time for my container needs since it seems to be a *pretty god damn badass library*, at least when compared to what's available in language level and Phobos. -- Niko Korhonen SW Developer
Aug 05 2005
prev sibling next sibling parent "Ben Hinkle" <ben.hinkle gmail.com> writes:
<z gg.com> wrote in message news:dctotb$ql5$1 digitaldaemon.com...
 Currently array has a build-in method .sort, which use the default opCmp.

 However it often need to sort an array in different ways: e.g. an arry of 
 File
 object, we may need to

 File[] files;

 files.sort(BySize);
 files.sort(ByDate);
 files.sort(ByName);
 files.sort(ByExtention);

 so I wonder if we should add another build-in method for array (T):

 array.sort(int function(T, T) cmp)

 to allow user pass in comparator other than the default opCmp().

 Or we should provide a global template function in the standard library:

 template(T) {
 sort(T[] array, int function(T, T) cmp);
 }

This is slightly off topic but I've added some sorting routines to MinTL. The most directly related to this thread is template(T:T[]) { sort(T[] array, int delegate(T*, T*) cmp = null); } where the default (null) comparison delegate means to sort by the default comparison function for type T (from its TypeInfo). While I was at it I added sorting to ArrayList, Deque, List and HashAA. The first two use quicksort/insertion-sort and the second two use a linked-list merge-sort. Slices are sorted in-place. The HashAA is an associative array ordered by insertion order and so the sort (which is only allowed for the key type) allows for associative arrays in different orders while still maintaining the performance of a hashtable. For more info go to the standard place http://home.comcast.net/~benhinkle/mintl/index.html -Ben
Aug 06 2005
prev sibling next sibling parent Stewart Gordon <smjg_1998 yahoo.com> writes:
z gg.com wrote:
<snip>
 so I wonder if we should add another build-in method for array (T):
 
 array.sort(int function(T, T) cmp)

*** This request has been marked as a duplicate of digitalmars.D/18851 *** We have a wish list here: http://www.wikiservice.at/wiki4d/wiki.cgi?FeatureRequestList Stewart. -- My e-mail is valid but not my primary mailbox. Please keep replies on on the 'group where everyone may benefit.
Aug 08 2005
prev sibling parent Burton Radons <burton-radons smocky.com> writes:
Because I just had need of porting this function again, here you go:

     template QuickSort (T, alias Compare)
     {
         T [] QuickSort (T [] list)
         {
             const size_t maxspan = 7;

             static void swap (T *a, T *b)
             {
                 T c = *a;

                 *a = *b;
                 *b = c;
             }

             T *base;
             T *[40] stack;
             T **sp = stack;
             T *i, j, limit;

             base = list.ptr;
             limit = base + list.length;

             while (1)
             {
                 while (limit - base > maxspan)
                 {
                     swap ((cast (size_t) (limit - base) >> 1) + base, 
base);
                     i = base + 1;
                     j = limit - 1;

                     if (Compare (*i, *j) > 0)
                         swap (i, j);
                     if (Compare (*base, *j) > 0)
                         swap (base, j);
                     if (Compare (*i, *base) > 0)
                         swap (i, base);

                     while (1)
                     {
                         do i ++;
                         while (Compare (*i, *base) < 0);

                         do j --;
                         while (Compare (*j, *base) > 0);

                         if (i > j)
                             break;
                         swap (i, j);
                     }

                     swap (base, j);
                     if (j - base > limit - i)
                     {
                         sp [0] = base;
                         sp [1] = j;
                         base = i;
                     }
                     else
                     {
                         sp [0] = i;
                         sp [1] = limit;
                         limit = j;
                     }

                     sp += 2;
                 }

                 i = base + 1;

                 while (i < limit)
                 {
                     j = i;
                     while (j > base && Compare (*(i - 1), *j) > 0)
                     {
                         swap (j - 1, j);
                         j --;
                     }

                     i ++;
                 }

                 if (sp > stack)
                 {
                     sp -= 2;
                     base = sp [0];
                     limit = sp [1];
                 }
                 else
                     break;
             }

             return list;
         }
     }

     template QuickSort (T)
     {
         T [] QuickSort (T [] list)
         {
             int compare (T a, T b)
             {
                 return a < b ? -1 : +1;
             }

             return .QuickSort! (T, compare) (list);
         }
     }

This is used like:

     int compare (int a, int b)
     {
         return a - b;
     }

     QuickSort! (int, compare) (list);

An apples-to-apples comparison with list.sort shows that this function 
is about 130% faster when sorting random data, all due to the compare 
inlining and compile-time type sizing (this is otherwise just a straight 
port of what's in Phobos).
Aug 21 2005