The Happy Struct Sorting Accident

[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:

   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.