## digitalmars.D.learn - Proxy sorting

• bearophile (43/43) Feb 18 2011 This is a RosettaCode simple task:
• Steven Schveighoffer (23/71) Feb 18 2011 I think opAssign is incorrect.
• bearophile (44/48) Feb 18 2011 Thank you for your answers. Second try, it doesn't work yet, I'm looking...
• bearophile (41/42) Feb 18 2011 Third try, this seems to work:
bearophile <bearophileHUGS lycos.com> writes:
```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().

Bye,
bearophile
```
Feb 18 2011
"Steven Schveighoffer" <schveiguy yahoo.com> writes:
```On Fri, 18 Feb 2011 08:08:22 -0500, bearophile <bearophileHUGS 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.

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
```
Feb 18 2011
bearophile <bearophileHUGS lycos.com> writes:
```Steven Schveighoffer:

I think opAssign is incorrect.

Silly me :-)

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.

Thank you for your answers. Second try, it doesn't work yet, I'm looking for
the problem:

import std.stdio, std.array, std.algorithm, std.range;

struct IndirectArray(Tdata, Tindexes) {
Tdata[] data;
Tindexes[] indexes;

bool empty() { return indexes.empty(); }
void popFront() { indexes.popFront(); }
Tdata front() { return data[indexes.front()]; }
IndirectArray save() { return this; }
void popBack() { indexes.popBack(); }
Tdata back() { return data[indexes.back()]; }
property size_t length() { return indexes.length; }

Tdata opIndex(size_t i) {
return data[indexes[i]];
}

void opIndexAssign(Tdata value, size_t i) {
data[indexes[i]] = value;
}
}

static assert(isRandomAccessRange!(IndirectArray!(double, int))); // OK

void disjointSort(Tdata, Tindexes)(Tdata[] arr, Tindexes[] idxSet) {
auto proxy = IndirectArray!(Tdata, Tindexes)(arr, idxSet);
sort(proxy);
}

void main() {
auto data = [7, 6, 5, 4, 3, 2, 1, 0];
writeln("orig:     ", [7, 6, 5, 4, 3, 2, 1, 0]);
auto indexes = [1, 6, 7];
disjointSort(data, indexes);
writeln("result:   ", data);
auto expected = [7, 0, 5, 4, 3, 2, 1, 6];
writeln("expected: ", expected);
assert(data == expected);
}

The static assert shows it's a random access range.
But it breaks on the lines of partition():
r.front = t2;
r.back = t1;

So beside being a random access range, it needs some other property...

General comment: to sort an array you need length, opIndex and opIndexAssign
methods only. The need of all other methods looks a bit silly.

Bye,
bearophile
```
Feb 18 2011
bearophile <bearophileHUGS lycos.com> writes:
``` Thank you for your answers. Second try, it doesn't work yet, I'm looking for
the problem:

Third try, this seems to work:

import std.stdio, std.array, std.algorithm, std.range;

struct IndirectArray(Tdata, Tindexes) {
Tdata[] data;
Tindexes[] indexes;

bool empty() { return indexes.empty(); }
void popFront() { indexes.popFront(); }
ref Tdata front() { return data[indexes.front()]; }
IndirectArray save() { return this; }
void popBack() { indexes.popBack(); }
ref Tdata back() { return data[indexes.back()]; }
property size_t length() { return indexes.length; }

Tdata opIndex(size_t i) {
return data[indexes[i]];
}

void opIndexAssign(Tdata value, size_t i) {
data[indexes[i]] = value;
}

IndirectArray opSlice(size_t x, size_t y) {
return IndirectArray(data, indexes[x .. y]);
}
}

static assert(isRandomAccessRange!(IndirectArray!(double, int))); // OK

void disjointSort(Tdata, Tindexes)(Tdata[] arr, Tindexes[] idxSet) {
auto proxy = IndirectArray!(Tdata, Tindexes)(arr, idxSet);
sort(proxy);
}

void main() {
auto data = [7, 6, 5, 4, 3, 2, 1, 0];
writeln("orig:     ", [7, 6, 5, 4, 3, 2, 1, 0]);
auto indexes = [1, 6, 7];
disjointSort(data, indexes);
writeln("result:   ", data);
auto expected = [7, 0, 5, 4, 3, 2, 1, 6];
writeln("expected: ", expected);
assert(data == expected);
}

I don't know yet how much efficient it is, things like opSlice() copy
size_t.sizeof*4 bytes.

front() and back() must return by ref, and opSlice() too is needed. I think
this requirements need to be added to the template constraints of sort().

Bye,
bearophile
```
Feb 18 2011