Proxy sorting

[Steven Schveighoffer]

On Fri, 18 Feb 2011 08:08:22 -0500, bearophile <bearophileHUGS at lycos.com>  
wrote:

> This is a RosettaCode simple task:
> http://rosettacode.org/wiki/Sort_disjoint_sublist#D
>
> Given a list of values and a set of integer indices into that value  
> list, sort the values at the given indices, but preserving the values at  
> indices outside the set of those to be sorted.
>
> Example input:
>   values: [7, 6, 5, 4, 3, 2, 1, 0]
>   indices: {6, 1, 7}
>
> Output:
>   [7, 0, 5, 4, 3, 2, 1, 6].
>
>
> I'd like to solve the problem using std.algorithm.sort, creating an  
> array of proxy things, that while they get sorted, sort the original  
> items too. Is it possible? This is a first try, but it doesn't work. I  
> think struct postblits aren't useful here (currently disjointSort can't  
> use a map() because of a map() bug I've added to bugzilla few days ago,  
> so I use just a foreach+append).
>
>
> import std.stdio, std.algorithm, std.array;
>
> struct Proxy(T) {
>     T* item;
>
>     int opCmp(ref const Proxy other) {
>         if (*item < *(other.item))
>             return -1;
>         else
>             return *item > *(other.item);
>     }
>
>     void opAssign(Proxy other) {
>         if (item != null)
>             *item = *(other.item);
>         item = other.item;
>     }
> }
>
> Proxy!T proxy(T)(ref T item) {
>     return Proxy!T(&item);
> }
>
> void disjointSort(T, U)(T[] arr, U[] s) {
>     auto idxSet = array(uniq(s.sort()));
>     auto proxies = new Proxy!T[idxSet.length];
>     foreach (i, idx; idxSet)
>         proxies[i] = proxy(arr[idx]);
>     proxies.sort();
> }
>
> void main() {
>     auto data = [7, 6, 5, 4, 3, 2, 1, 0];
>     auto indexes = [6, 1, 1, 7];
>     disjointSort(data, indexes);
>     writeln(data);
> }
>
>
> Here I think opAssign() is not used by the swap() used by sort().

I think opAssign is incorrect.

Think about a standard swap:

swap(ref Proxy p1, ref Proxy p2)
{
   auto ptmp = p1;
   p1 = p2;
   p2 = ptmp;
}

Let's expand it out to the assignments that happen:

ptmp.item = p1.item;
*p1.item = *p2.item; // at this point, both ptmp.item and p1.item point to  
the *same element*, so you are also effectively assigning *ptmp.item
p1.item = p2.item;
*p2.item = *ptmp.item;
p2.item = ptmp.item;

If you passed in items that point to 1 and 2 respectively, I'd expect the  
pointers to be swapped, but both values set to 2.

My suggestion would be to create a bidirectional proxy range that uses a  
supplemental array to determine where the "next/previous" element is (i.e.  
the index array).  Should be pretty simple.  Then just pass this to sort.

-Steve