• nobody (56/56) Aug 24 2007 The Happy Struct Sorting Accident
• 0ffh (6/8) Aug 24 2007 So in a few decades we can say:
• BCS (15/61) Aug 24 2007 thois would be a hair more robust

nobody <nobody mailinator.com> writes:

The Happy Struct Sorting Accident

Sorting with struct overlays

I was somewhat marveled to find a new (to me) device that is
probably fairly unique to the D programming language. It is
possible to sort arrays of structs with interesting results
using "struct overlays" and the sort property of arrays.

All that is required to sort an array of structs using any
field in the struct as the key is an alternate struct whose data
overlays the original struct's data and contains an overloaded
opCmp operator written for that particular field.


A fairly common example are (ID,Name,...) tuples:

   struct IDName
   {
     int id;
     char[] name;
     /*

     Normal struct behavior, maybe another opCmp . . .

     */
   }


You need one struct overlay per unique sort behavior:

   struct IDName_sortID
   {
     int id;
     char[] name;
     int opCmp(IDName_sortID that)
     {
       return (this.id < that.id) ? -1 : (this.id > that.id) ? 1 
: 0;
     }
   }

   struct IDName_sortName
   {
     int id;
     char[] name;
     int opCmp(IDName_sortName that)
     {
       return (this.name < that.name) ? -1 : (this.name > 
that.name) ? 1 : 0;
     }
   }


Now given IDName[] ex is defined, your sort can be keyed either 
field:

   // sort with id as primary key
   (cast(IDName_sortID) ex).sort;

   // sort with name as primary key
   // note id is the secondary key if .sort is stable
   (cast(IDName_sortName) ex).sort;


This all works because of how sort works for structs in D:

   http://digitalmars.com/d/arrays.html
   Array Properties

   For the .sort property to work on arrays of structs or unions,
   the struct or union definition must define the function:
     int opCmp(S) or
     int opCmp(S*).
   The type S is the type of the struct or union. This function
   will determine the sort ordering.

0ffh <spam frankhirsch.net> writes:

nobody wrote:
 The Happy Struct Sorting Accident
 [...]

So in a few decades we can say:
"In the days when we were starting to code in D, sorting
with struct overlays was not yet a common thing.
Nobody found out about it." =)

Regards, Frank

BCS <ao pathlink.com> writes:

Reply to nobody,

 The Happy Struct Sorting Accident
 
 Sorting with struct overlays
 
 I was somewhat marveled to find a new (to me) device that is probably
 fairly unique to the D programming language. It is possible to sort
 arrays of structs with interesting results using "struct overlays" and
 the sort property of arrays.
 
 All that is required to sort an array of structs using any
 field in the struct as the key is an alternate struct whose data
 overlays the original struct's data and contains an overloaded
 opCmp operator written for that particular field.
 A fairly common example are (ID,Name,...) tuples:
 

This was proposed a week or so ago (but for sorting using a different order)

 struct IDName
 {
 int id;
 char[] name;
 /*
 Normal struct behavior, maybe another opCmp . . .
 
 */
 }
 You need one struct overlay per unique sort behavior:
 

thois would be a hair more robust

strutc SortStructBy(T, uint i)
{
  T t;
  int opCmp(T u)
  {
    return this.tupleof[i].opCmp(u.tupleof[i]);
  }
}


alias SortByStruct!(IDName, 0) IDName_sortID;
alias SortByStruct!(IDName, 1) IDName_sortName;


BTW, all of this falls under the heading of "dirty hacks" that should only 
be used when all else fails

 struct IDName_sortID
 {
 int id;
 char[] name;
 int opCmp(IDName_sortID that)
 {
 return (this.id < that.id) ? -1 : (this.id > that.id) ? 1
 : 0;
 }
 }
 struct IDName_sortName
 {
 int id;
 char[] name;
 int opCmp(IDName_sortName that)
 {
 return (this.name < that.name) ? -1 : (this.name >
 that.name) ? 1 : 0;
 }
 }