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