www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Sorted Array Wrapper Range

reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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
Dec 03 2014
next sibling parent reply "Xinok" <xinok live.com> writes:
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.
Dec 03 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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?
Dec 03 2014
prev sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
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?
Dec 03 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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?
Dec 06 2014
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
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
Dec 06 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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 



So what should the basic operations in a SortedRange wrapper 
template be? And how should the wrapped type be restricted?
Dec 06 2014
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
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 



 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.
Dec 07 2014
parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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 :)
Dec 08 2014
parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
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
Dec 08 2014
next sibling parent reply =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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?
Dec 08 2014
parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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
Dec 10 2014
prev sibling next sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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.
Dec 08 2014
prev sibling parent =?UTF-8?B?Ik5vcmRsw7Z3Ig==?= <per.nordlow gmail.com> writes:
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[])) ...
Dec 10 2014