www.digitalmars.com         C & C++   DMDScript  

D - Useful array properties: match(expr) and sort(expr)

reply Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
A couple of days ago, I was (in C++, since I was working on Linux)
sorting through an array of structs, trying to find some that matched a
certain criteria, and then sort the results based on one of the fields.
It was a hideous experience...I ended up using STL in a terrible coding
hack.  It occurred to me that the following two properties of an array
would be useful:

    match(expr)    - returns an array of items that match the expression

    sort(fieldname) - allows you to sort by any field of a struct

For example, take this code:
    struct MyStruct
    {
        int a;
        int b;
    }
    MyStruct[] arr;
    ...
    MyStruct[] arr2 = arr.match(a=b).sort(b);

The code for match(expr) would roughly be this:
    <type>[] match(<type>[] array)
    {
        <type>[] ret;
        for(int i=0; i<array.length; i++)
        {
            with array[i];
            if(<expr>)
                ret ~= array[i];
        }
    }

While sort would be a normal sort (quicksort, presumably), but instead
of comparing the whole value of the struct (or class), it would compare
the field specified.

--
The Villagers are Online! villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]
Jun 17 2002
next sibling parent reply "Matthew Wilson" <mwilson thedjournal.com> writes:
Agree with the match().

Think sort() should be given a predicate, since there are all types of
sorting, including the simple aspect of order: do you want forward, or
reverse?; would you add a boolean parameter for that? What about if you come
up with other aspects you want to handle?


"Russ Lewis" <spamhole-2001-07-16 deming-os.org> wrote in message
news:3D0DF88E.8E290080 deming-os.org...

 A couple of days ago, I was (in C++, since I was working on Linux)
 sorting through an array of structs, trying to find some that matched a
 certain criteria, and then sort the results based on one of the fields.
 It was a hideous experience...I ended up using STL in a terrible coding
 hack.  It occurred to me that the following two properties of an array
 would be useful:

     match(expr)    - returns an array of items that match the expression

     sort(fieldname) - allows you to sort by any field of a struct

 For example, take this code:
     struct MyStruct
     {
         int a;
         int b;
     }
     MyStruct[] arr;
     ...
     MyStruct[] arr2 = arr.match(a=b).sort(b);

 The code for match(expr) would roughly be this:
     <type>[] match(<type>[] array)
     {
         <type>[] ret;
         for(int i=0; i<array.length; i++)
         {
             with array[i];
             if(<expr>)
                 ret ~= array[i];
         }
     }

 While sort would be a normal sort (quicksort, presumably), but instead
 of comparing the whole value of the struct (or class), it would compare
 the field specified.

 --
 The Villagers are Online! villagersonline.com

 .[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
 .[ (a version.of(English).(precise.more)) is(possible) ]
 ?[ you want.to(help(develop(it))) ]
Jun 17 2002
next sibling parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Matthew Wilson wrote:


 Agree with the match().

 Think sort() should be given a predicate, since there are all types of
 sorting, including the simple aspect of order: do you want forward, or
 reverse?; would you add a boolean parameter for that? What about if you come
 up with other aspects you want to handle?


Good points.  As for reverse sorting, you can always do
    array.sort(expr).reverse
but for some things, strings in particular, you may have different manners of
sorting you want to do.  Also, when you have multiple elements with the same key
value, some sorting mechanisms leave them in relative order while others do
not.  All things to consider...

--
The Villagers are Online! http://villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]
Jun 18 2002
prev sibling parent "anderson" <anderson firestar.com.au> writes:
Parhaps you could optionally pass sort, a pointer to a ">" function. That
would solve both reverse order and struct/class problems. Although it'd
require more coding then the other methods it'd be more flexible.
Jun 18 2002
prev sibling parent reply Burton Radons <loth users.sourceforge.net> writes:
Russ Lewis wrote:

 A couple of days ago, I was (in C++, since I was working on Linux)
 sorting through an array of structs, trying to find some that matched a
 certain criteria, and then sort the results based on one of the fields.
 It was a hideous experience...I ended up using STL in a terrible coding
 hack.  It occurred to me that the following two properties of an array
 would be useful:
 
     match(expr)    - returns an array of items that match the expression


I like it, but what about basic type and array arrays?  It may be better 
to offer it a local variable that you can then use, as that only changes 
the namespace slightly, not totally.


     sort(fieldname) - allows you to sort by any field of a struct


I'd prefer sort.fieldname so that sort(expr) is free, handing the 
expression a and b as locals in a pseudolambda.  There's no real call 
for explicitly offering reverse sorting:

     array.sort (b.cmp (a));

Which should work everywhere, even with basic types eventually.
Jun 17 2002
parent Russ Lewis <spamhole-2001-07-16 deming-os.org> writes:
Burton Radons wrote:


 Russ Lewis wrote:

 A couple of days ago, I was (in C++, since I was working on Linux)
 sorting through an array of structs, trying to find some that matched a
 certain criteria, and then sort the results based on one of the fields.
 It was a hideous experience...I ended up using STL in a terrible coding
 hack.  It occurred to me that the following two properties of an array
 would be useful:

     match(expr)    - returns an array of items that match the expression


 I like it, but what about basic type and array arrays?  It may be better
 to offer it a local variable that you can then use, as that only changes
 the namespace slightly, not totally.


Yes, I was hoping that it would soon work for arrays of all types of
things...but I started with the easiest example :)  The "with" statement makes
it much easier to visualize this stuff :)


     sort(fieldname) - allows you to sort by any field of a struct


 I'd prefer sort.fieldname so that sort(expr) is free, handing the
 expression a and b as locals in a pseudolambda.  There's no real call
 for explicitly offering reverse sorting:

      array.sort (b.cmp (a));

 Which should work everywhere, even with basic types eventually.


We can't do the
    array.sort.fieldname
syntax, since
    array.sort
is already legal.

As for the 2nd point, I think you misunderstood me.  I didn't mean that sort
would do an explicit compare, but that sort would have an expression that
returns the value for each array element.  So you would do something like
    array.sort(field1)
which means to sort by field1, or
    array.sort(field2)
which means to sort by field2.  Likewise, if you are comparing arrays of
arrays of structs, you might do:
    array.sort([1].field3)
which sorts by the field3 element of the 2nd element in the array.  Comparing
elements i and j would resolve to:
    if(array[i][1].field3 == array[j][1].field3)
The old syntax still works;
    array.sort
means to sort by doing overall compares of the entire structs.

--
The Villagers are Online! http://villagersonline.com

.[ (the fox.(quick,brown)) jumped.over(the dog.lazy) ]
.[ (a version.of(English).(precise.more)) is(possible) ]
?[ you want.to(help(develop(it))) ]
Jun 18 2002