Have anybody written a generic automatically sorted range wrapper for RandomAccessRanges?

I guess

http://dlang.org/library/std/range/assumeSorted.html

should play a key role.

I see two typical variants:

- Direct: Always sorts on write() and modify()
- Lazy: Sorts lazily on read()

read() of course uses binarySearch

On Wednesday, 3 December 2014 at 21:02:05 UTC, Nordlöw wrote:
> Have anybody written a generic automatically sorted range wrapper for RandomAccessRanges?
>
> I guess
>
> http://dlang.org/library/std/range/assumeSorted.html
>
> should play a key role.
>
> I see two typical variants:
>
> - Direct: Always sorts on write() and modify()
> - Lazy: Sorts lazily on read()
>
> read() of course uses binarySearch

There was a relevant discussion about a month ago here:
http://forum.dlang.org/thread/uhfpppdslxdghyconlfr@forum.dlang.org

Otherwise, there's RedBlackTree, but I'm not aware of anything that works over any random-access range.

On Thursday, 4 December 2014 at 04:24:26 UTC, Xinok wrote:
> There was a relevant discussion about a month ago here:
> http://forum.dlang.org/thread/uhfpppdslxdghyconlfr@forum.dlang.org

I can't any reference to code, typically for SortedRange. Has this been implemented somewhere?

On Wednesday, 3 December 2014 at 21:02:05 UTC, Nordlöw wrote:
> Have anybody written a generic automatically sorted range wrapper for RandomAccessRanges?
>
> I guess
>
> http://dlang.org/library/std/range/assumeSorted.html
>
> should play a key role.
>
> I see two typical variants:
>
> - Direct: Always sorts on write() and modify()
> - Lazy: Sorts lazily on read()
>
> read() of course uses binarySearch

You won't be able to grow that range, would you?

On Thursday, 4 December 2014 at 07:58:25 UTC, Tobias Pankrath wrote:
>> I see two typical variants:
>>
>> - Direct: Always sorts on write() and modify()
>> - Lazy: Sorts lazily on read()
>>
>> read() of course uses binarySearch
>
> You won't be able to grow that range, would you?

Why, because of slice invalidation?

On Saturday, 6 December 2014 at 14:10:21 UTC, Nordlöw wrote:
> On Thursday, 4 December 2014 at 07:58:25 UTC, Tobias Pankrath wrote:
>>> I see two typical variants:
>>>
>>> - Direct: Always sorts on write() and modify()
>>> - Lazy: Sorts lazily on read()
>>>
>>> read() of course uses binarySearch
>>
>> You won't be able to grow that range, would you?
>
> Why, because of slice invalidation?

Because a RandomAccessRange has no means to grow in general. Compare your proposed wrapper to http://dlang.org/phobos/std_container.html#.BinaryHeap

On Saturday, 6 December 2014 at 14:14:18 UTC, Tobias Pankrath wrote:
> Because a RandomAccessRange has no means to grow in general. Compare your proposed wrapper to http://dlang.org/phobos/std_container.html#.BinaryHeap

So what should the basic operations in a SortedRange wrapper template be? And how should the wrapped type be restricted?

On Saturday, 6 December 2014 at 14:50:02 UTC, Nordlöw wrote:
> On Saturday, 6 December 2014 at 14:14:18 UTC, Tobias Pankrath wrote:
>> Because a RandomAccessRange has no means to grow in general. Compare your proposed wrapper to http://dlang.org/phobos/std_container.html#.BinaryHeap
>
> So what should the basic operations in a SortedRange wrapper template be? And how should the wrapped type be restricted?

Something like this https://github.com/Panke/phobos/blob/std_container_sorted/std/container/sorted.d

It should additionally support c.remove(r), c.removeKey(k), opIn and insertFront/removeFront if the underlying store supports them.

But that's pretty much it, I'd say.

Sadly, the unittest using an Array!int as store does not compile because of of linker errors. I'm using

rdmd -unittest -main std/container/sorted.d

but that does not work with std/container/array.d as well. So, my setup seems to be broken.

On Sunday, 7 December 2014 at 13:12:06 UTC, Tobias Pankrath wrote:
> Something like this https://github.com/Panke/phobos/blob/std_container_sorted/std/container/sorted.d
>
> It should additionally support c.remove(r), c.removeKey(k), opIn and insertFront/removeFront if the underlying store supports them.
>
> But that's pretty much it, I'd say.
>
> Sadly, the unittest using an Array!int as store does not compile because of of linker errors. I'm using
>
> rdmd -unittest -main std/container/sorted.d
>
> but that does not work with std/container/array.d as well. So, my setup seems to be broken.

Thanks! I don't get any linker errors using dmd git master. I'll try 2.066 later on. I'll do some polishing :)

On Monday, 8 December 2014 at 13:34:33 UTC, Nordlöw wrote:
> On Sunday, 7 December 2014 at 13:12:06 UTC, Tobias Pankrath wrote:
>> Something like this https://github.com/Panke/phobos/blob/std_container_sorted/std/container/sorted.d
>>
>> It should additionally support c.remove(r), c.removeKey(k), opIn and insertFront/removeFront if the underlying store supports them.
>>
>> But that's pretty much it, I'd say.
>>
>> Sadly, the unittest using an Array!int as store does not compile because of of linker errors. I'm using
>>
>> rdmd -unittest -main std/container/sorted.d
>>
>> but that does not work with std/container/array.d as well. So, my setup seems to be broken.
>
> Thanks! I don't get any linker errors using dmd git master. I'll try 2.066 later on. I'll do some polishing :)

Was my fault. The phobos checkout didn't match my dmd version. Here is my current state (has some more unittest, bugs fixed, no assignment via SortedRange views on Sorted.): https://github.com/Panke/phobos/blob/sorted/std/container/sorted.d