www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Problems with sort

reply "Craig Black" <craigblack2 cox.net> writes:
The following code gives me this error:
algorithm.d(5159): Error: template instance SortedRange!(Range,less) does 
not match template declaration SortedRange(Range,alias pred = "a < b") if 
(isRandomAccessRange!(Unqual!(Range)))

import std.stdio;
import std.algorithm;

struct Range(T)
{
public:
 this(T* front, T* back)
 {
  frontPtr = front;
  backPtr = back;
 }
 T* frontPtr, backPtr;
 bool empty() const { return backPtr < frontPtr; }
 void popFront() { frontPtr++; }
 void popBack() { backPtr--; }
 ref T front() { return *frontPtr; }
 ref T back() { return *backPtr; }
}

void main()
{
 int[] a = [9,8,7,6,5,4,3,2,1,0];
 auto r = Range!int(&a[0], &a[9]);
 sort(r);
 writeln(a);
}

Any clue as to what is going on here?

-Craig
Dec 10 2010
next sibling parent Adam D. Ruppe <destructionator gmail.com> writes:
A random access range needs to expose an array like interface.
Specifically, it should implement a length()and an opIndex methods.

If you add them to your range, it should work.

More info here: http://dpldocs.info/isRandomAccessRange
Dec 10 2010
prev sibling next sibling parent Stanislav Blinov <stanislav.blinov gmail.com> writes:
On 12/11/2010 03:48 AM, Craig Black wrote:

 The following code gives me this error:
 algorithm.d(5159): Error: template instance SortedRange!(Range,less)
 does not match template declaration SortedRange(Range,alias pred = "a <
 b") if (isRandomAccessRange!(Unqual!(Range)))

 Any clue as to what is going on here?


My guess is isRandomAccessRange constraint fails, because your range 
does not offer opIndex().
Dec 10 2010
prev sibling parent reply "Craig Black" <craigblack2 cox.net> writes:
Thanks for the help guys.  I implemented length and opIndex and now I get 
the following errors:

C:\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(5341): Error: template 
std.algorithm.swap(T) if (!is(typeof(T.init.proxySwap(T.init)))) does not 
match any function template declaration

C:\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(5341): Error: template 
std.algorithm.swap(T) if (!is(typeof(T.init.proxySwap(T.init)))) cannot 
deduce template function from argument types !()(_error_,Range)

-Craig
Dec 10 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/10/10 6:37 PM, Craig Black wrote:

 Thanks for the help guys. I implemented length and opIndex and now I get
 the following errors:

 C:\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(5341): Error:
 template std.algorithm.swap(T) if
 (!is(typeof(T.init.proxySwap(T.init)))) does not match any function
 template declaration

 C:\dmd2\windows\bin\..\..\src\phobos\std\algorithm.d(5341): Error:
 template std.algorithm.swap(T) if
 (!is(typeof(T.init.proxySwap(T.init)))) cannot deduce template function
 from argument types !()(_error_,Range)

 -Craig


This concerns a decision not yet firmed-up on whether objects should be 
cheap to copy or not.

What happens is that sort wants to swap elements at given indices. Your 
opIndex, I assume, returns by value. (If it returned by reference you'd 
have no problem sorting.) Then sort makes a number of heroic attempts at 
figuring out how to swap elements in your range (e.g. by trying 
moveAt()) before failing in frustration.

If we mandate cheap copy, then swap via two copies should be fine, which 
simplifies implementation a great deal and also your life as a user of 
it. We haven't made that decision yet. There is the concern that things 
would become too inefficient.


Andrei
Dec 10 2010
parent reply "Craig Black" <craigblack2 cox.net> writes:
 This concerns a decision not yet firmed-up on whether objects should be 
 cheap to copy or not.
 
 What happens is that sort wants to swap elements at given indices. Your 
 opIndex, I assume, returns by value. (If it returned by reference you'd 
 have no problem sorting.) Then sort makes a number of heroic attempts at 
 figuring out how to swap elements in your range (e.g. by trying 
 moveAt()) before failing in frustration.
 
 If we mandate cheap copy, then swap via two copies should be fine, which 
 simplifies implementation a great deal and also your life as a user of 
 it. We haven't made that decision yet. There is the concern that things 
 would become too inefficient.
 
 
 Andrei


Thanks for the response.  I appreciate the emphasis on efficiency.

But my opIndex does return a reference:
ref T opIndex(int i) { ... }

-Craig
Dec 10 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 12/10/10 7:04 PM, Craig Black wrote:

 This concerns a decision not yet firmed-up on whether objects should
 be cheap to copy or not.

 What happens is that sort wants to swap elements at given indices.
 Your opIndex, I assume, returns by value. (If it returned by reference
 you'd have no problem sorting.) Then sort makes a number of heroic
 attempts at figuring out how to swap elements in your range (e.g. by
 trying moveAt()) before failing in frustration.

 If we mandate cheap copy, then swap via two copies should be fine,
 which simplifies implementation a great deal and also your life as a
 user of it. We haven't made that decision yet. There is the concern
 that things would become too inefficient.


 Andrei


 Thanks for the response. I appreciate the emphasis on efficiency.

 But my opIndex does return a reference:
 ref T opIndex(int i) { ... }


In that case please send me the code so I can take a look.

Thanks,

Andrei
Dec 10 2010
parent "Craig Black" <craigblack2 cox.net> writes:
Thanks for the help Andrei.  I figured it out.  I needed an opSlice.

-Craig
Dec 10 2010