Sorted Array Wrapper Range
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
Re: Sorted Array Wrapper Range
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/uhfpppdslxdghycon...@forum.dlang.org Otherwise, there's RedBlackTree, but I'm not aware of anything that works over any random-access range.
Re: Sorted Array Wrapper 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/uhfpppdslxdghycon...@forum.dlang.org I can't any reference to code, typically for SortedRange. Has this been implemented somewhere?
Re: Sorted Array Wrapper Range
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?
Re: Sorted Array Wrapper Range
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?
Re: Sorted Array Wrapper Range
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
Re: Sorted Array Wrapper Range
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?
Re: Sorted Array Wrapper Range
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.
Re: Sorted Array Wrapper Range
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 :)
Re: Sorted Array Wrapper Range
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
Re: Sorted Array Wrapper Range
On Monday, 8 December 2014 at 15:43:37 UTC, Tobias Pankrath wrote: 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 Great! You should do a PR when you're satisfied! :) Is there anything you need help with?
Re: Sorted Array Wrapper Range
On Monday, 8 December 2014 at 15:43:37 UTC, Tobias Pankrath wrote: 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 You have an outdated reference to BinaryHeap at line 440 https://github.com/Panke/phobos/blob/sorted/std/container/sorted.d#L440 Should be replaced with Sorted I presume.
Re: Sorted Array Wrapper Range
On Monday, 8 December 2014 at 15:43:37 UTC, Tobias Pankrath wrote: 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 Further it's nicer to use new enum syntax at https://github.com/Panke/phobos/blob/sorted/std/container/sorted.d#L12 as enum isRAContainer(T) = isRandomAccessRange!(typeof(T.init[])) ...
Re: Sorted Array Wrapper Range
On Monday, 8 December 2014 at 20:18:51 UTC, Nordlöw wrote: Great! You should do a PR when you're satisfied! :) https://github.com/D-Programming-Language/phobos/pull/2793
