Proxy sorting
bearophile
bearophileHUGS at lycos.com
Fri Feb 18 16:00:58 PST 2011
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
More information about the Digitalmars-d-learn
mailing list