Failed to sort range

[Ali Çehreli]

On 05/28/2013 05:57 AM, Sergei Nosov wrote:
> Hi!
>
> I'm trying to implement an array, which uses malloc to allocate memory.
> Also, I want to implement a random access range interface for it.
>
> That went pretty well, until I tried to sort it. Sorting function
> asserted "Failed to sort range of type Array!(int)."
>
> I've spent quite some time trying to figure out what's going on with no
> success.
>
> The implementation can be found at:
> https://gist.github.com/snosov1/5662471
>
> I used
> DMD64 D Compiler v2.062 and
> LDC - the LLVM D compiler (trunk): based on DMD v2.062 and LLVM 3.2svn
> on Ubuntu. Phobos version was the one that came with the dmd compiler.
>
> Does anyone have any ideas what's wrong with the code I've provided?

1) First, an observation: This Array design conflates the concepts of 
container and range. If there are actual elements that are being stored 
(as opposed to elements being generated), it is better tha a range 
merely provides access to those elements. popFront should consume the 
range, not the container. (Unless it is some special type of range with 
the responsibility of removing elements from the container.)

2) As a minor comment, "back" usually means the last element but your 
back_ has the meaning of one-past-the-last element.

3) You have to rethink the indexing as well. opIndex indexes directly on 
vec_:

     ref T opIndex(size_t idx) {
         return vec_[idx];
     }

However, we may be on a slice which has already been sliced before (as 
is the case in quick sort, which SwapStrategy.unstable uses). So, I 
think opIndex should add front_ to idx:

     ref T opIndex(size_t idx) {
         return vec_[front_ + idx];
     }

It is a start but still not the solution. Sorry... :/

Ali