Frits van Bommel wrote:
> 
> Try putting them in an array of structs with overloaded opCmp, and then sorting that. For example:  -----
>
.
That worked very well. Thank you.

b.
-- 

Reply to Me,

> Hi all,
> 
> A little advice please. Using D v1.028.
> 
> I have (currently) an array of uints. I need to output these sorted,
> which
> .sort does admirably,
> but I need to know what index is associated with each value. How?
> Springing from my own use of the word "associated", I thought that
> maybe I
> should be using
> and associative array for this. But again the problem is that I would
> need to
> sort the keys
> by their associated values.
> In Perl I'd do
> 
> my @array = ...;
> 
> ## Get the indexes ordered by their values
> my @orderIndexes = sort{
> $array[ $a ] <=> $array[ $b ]
> } 0 .. $#array;
> for my $i ( @orderedIndexes ) {
> printf "%d : %d\n2, $i, $array[ $i ];
> }
> Is there anything built-in or in Phobos that will help me here? Or do
> I need to write my own sort?
> 
> Cheers, b.
> 

pack it in ulongs with the index in the lower bits and the value in the upper bits.

auto tmp = new ulong[](array.length)

foreach(uint i, uint v; array) tmp[i] = (cast(ulong)v)<<32 | i;
tmp.sort;

// get value of item i
cast(uint)(tmp[i]>>32);

// get index of item i;
cast(uint)(tmp[i] & 0xffff_ffff);

Reply to Frits,

> module test;
> import tango.io.Stdout;
> import tango.text.convert.Format;
> struct Pair {
>   int a, b;
>   int opCmp(Pair* other) {
>     if (a != other.a)
>       return typeid(typeof(a)).compare(&a, &other.a);
>     else
>       return typeid(typeof(b)).compare(&b, &other.b);
>   }
>   char[] toString() {
>     return Format("{}:{}", a, b);
>   }
> }


maybe that should be templated.

struct SortSet(K, V...) { ... }

Reply to myself

> pack it in ulongs with the index in the lower bits and the value in
> the upper bits.

My solution is about the same as frits' solution but without the extra type or function calls, but with a big does of WTHuuu...

On Sun, 4 May 2008 13:52:42 +0000 (UTC), Me Here wrote:

> Derek Parnell wrote:
>> The trick I use for this is to have two AAs. When the set is small, performance isn't really an issue.
> 
> Problem: That works fine if the values in the origianl array are unique.

Doh! Of course that's an issue. My bad ... just come off playing a couple of hours of COD4  :-)

I'm still a huge fan of variable-length arrays and AAs ( I also code in the Euphoria language where V/L arrays are the lifeblood). So here is a better solution to this sort of problem using those built-in features of D.

import std.stdio;

void main()
{
    uint[int] SampleData;

    // NB: Has non-sequential indexes and duplicate values.
    SampleData[ 20] = 30;
    SampleData[  1] = 10;
    SampleData[  2] = 30;
    SampleData[243] = 60;
    SampleData[  4] = 90;
    SampleData[ 75] = 90;
    SampleData[  6] = 120;
    SampleData[ 17] = 50;
    SampleData[ -8] = 20;
    SampleData[  9] = 30;
    SampleData[ 10] = 30;
    SampleData[211] = 10;
    SampleData[-12] = 30;
    SampleData[ 13] = 60;
    SampleData[114] = 90;
    SampleData[315] = 90;
    SampleData[126] = 20;
    SampleData[ 17] = 50;
    SampleData[418] = 20;
    SampleData[ 19] = 30;
    SampleData[120] = 30;
    SampleData[ 21] = 10;
    SampleData[-22] = 30;
    SampleData[223] = 60;
    SampleData[ 24] = 90;
    SampleData[425] = 90;
    SampleData[126] = 20;
    SampleData[-27] = 50;
    SampleData[278] = 20;
    SampleData[292] = 30;

    auto SSD = SortVals(SampleData);

   // Publish the results
   writefln("%6s: %s", "Value", "Occurs at ...");
   foreach(i; SSD.keys.sort)
   {
       writef("%6s: ", i);
       auto vals = SSD[i];
       foreach( j, v; vals)
       {
            if (j == vals.length - 1)
            {
                writefln("%s", v);
            }
            else
            {
                writef("%s, ", v);
            }
        }
   }


}

Kt[][Vt] SortVals(Kt, Vt)(Vt[Kt] theArray)
{

    // Reverse index array.
    // nb: The original keys are stored in a V/L array.
    Kt[][Vt] altArray;

    // Setup the reverse index array.
    foreach(i; theArray.keys.sort)
    {
        altArray[ theArray[i] ] ~= i;
    }

    return altArray;
}


This produces the output ...

 Value: Occurs at ...
    10: 1, 21, 211
    20: -8, 126, 278, 418
    30: -22, -12, 2, 9, 10, 19, 20, 120, 292
    50: -27, 17
    60: 13, 223, 243
    90: 4, 24, 75, 114, 315, 425
   120: 6
-- 
Derek Parnell
Melbourne, Australia
skype: derek.j.parnell

bearophile wrote:

> Me Here:
> > How do I write valGetter() ?
> 
> Use the predefined one, my libs are supposed to minimize the work for the programmer ;-)
> 
> Bye,
> bearophile

Oh. I guess I was confused by the implementation:

void valGetter() { } /// ditto

I couldn't for the life of me se how that would work as is, so I assumed it must be some kind of virtual functio or place holder.

Actually, I /still/ don't understand how it can work, but if you say it does I will try it.

What the convention of where to place thrid-party libraries?
The stem (root, path; package?) of the librabry names 'd.*' seems um.. a little
generic?

Cheers, b.

-- 

BCS wrote:

> My solution is about the same as frits' solution but without the extra type or function calls, but with a big does of WTHuuu...

This isn't the first time a request for the permutation computed by the sort routine comes up. Should such be incorprated into the language?

-manfred

Derek Parnell wrote:
> On Sun, 4 May 2008 13:52:42 +0000 (UTC), Me Here wrote:
> 
>> Derek Parnell wrote:
>>> The trick I use for this is to have two AAs. When the set is small,
>>> performance isn't really an issue.
>> Problem: That works fine if the values in the origianl array are unique.
> 
> Doh! Of course that's an issue. My bad ... just come off playing a couple
> of hours of COD4  :-)

COD4 + programming... Is that anything like playing a few hours of GTA, and then immediately driving to the corner store for a soda and some chips?

- Pragma

Me Here:
> Oh. I guess I was confused by the implementation:
> void valGetter() { } /// ditto
> I couldn't for the life of me se how that would work as is, so I assumed it
> must be some kind of virtual functio or place holder.
> Actually, I /still/ don't understand how it can work, but if you say it does I
> will try it.

sortedAA() accepts any callable with key+val arguments, and sorts the keys of the given AA according to the result of that callable, like the key attribute of Python sort()/sorted().
If the callable is the default valGetter, then the result of that callable is meant to be right the value. So it sorts according to the values. That's quite similar to the itemgetter() and similar functions in the operator module of the Python standard library.
If you try the given example, or you look inside the tens of unittests, you can see how and why it works. It's just an empty function, used as flag, to simplify the life of the user.


> What the convention of where to place thrid-party libraries?
> The stem (root, path; package?) of the librabry names 'd.*' seems um.. a little
> generic?

The package is called "d". I know no other package with that name that may collide with it. You can put that directory inside the directory of your modules, libs, etc. Then you have to tell "bud" (or similar tool, there's another more modern one, that I don't use) the path of that directory of your modules.

Then at the top of your code you can use:

import d.func: sortAA;

And bud will find the right module and its dependent modules, and compile them. If you need more compilation speed you can compile the d libs in a library "lib" and maybe create "short" modules, all using the DMD compiler and its tools.

Bye,
bearophile

Manfred Nowak wrote:

> This isn't the first time a request for the permutation computed by the sort routine comes up. Should such be incorprated into the language?
> 
It struck me that the ability to pass a coderef (sorry, delegate :) to the sort
method
that was called back with both the [index, value] or [key,value] of the items
being
compared and returning -1, 0, +1, would allow for custom sorting.

The other notion that crossed my mind was having the ability to locally (scoped) override the opCmp of built-in types, but that would require all opCmps to expect two pairs.

b.
--