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 { 









#int main(char[][] args)
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 {






 initArg; }



 #int main(char[][] args)












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 {






 initArg; }



 #int main(char[][] args)












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)


<snip>

*** This request has been marked as a duplicate of 
http://www.digitalmars.com/drn-bin/wwwnews?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