On Fri, 18 Feb 2011 08:08:22 -0500, bearophile <[email protected]>
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
