www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Proxy sorting

reply 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
parent reply "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.

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
Feb 18 2011
parent reply 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
parent 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