Re: Circular Buffer
On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote: (disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? Example of some ideal takeBack function: data = cycle([1,2,3][]) take(data, 4) is [1,2,3,1][] takeBack(data, 4) would be [1,3,2,1][] Thoughts? We've had a discussion about this recently with Andrej Mitrovic. The question was basically: Should Cycle (keeping in mind it is an infinite range) be bidirectional? And if yes, what should be the first last? There is fundamentally nothing preventing us from making Cycle bidirection (though maybe as opt-in CycleBidirectional, due to extra costs). We'd just need a use case, and specifications I guess. For example: auto s = cycle([1, 2, 3]); auto last = cycle.back; What's last's value? I think it should be 3. If we can agree and file an ER, it can be done.
Re: Circular Buffer
Russel Winder: I had a quick go at doing a Python 3 version using PyTest: def provide(sourceSequence, resultLength): return (sourceSequence[i % len(sourceSequence)] for i in range(resultLength)) def provideReverse(sourceSequence, resultLength): sourceLength = len(sourceSequence) return (sourceSequence[sourceLength - 1 - i % sourceLength] for i in range(resultLength)) Take also a look at itertools.cycle. Bye, bearophile
Re: Circular Buffer
On Thu, 2014-02-13 at 18:03 +, bearophile wrote: […] Take also a look at itertools.cycle. Indeed. I keep forgetting about itertools when rushed, which is a definite error. -- Russel. = Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.win...@ekiga.net 41 Buckmaster Roadm: +44 7770 465 077 xmpp: rus...@winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Re: Circular Buffer
On Thu, 2014-02-13 at 18:03 +, bearophile wrote: […] Take also a look at itertools.cycle. How about this: #! /usr/bin/env py.test-3.3 from itertools import cycle, islice data = [1, 2, 3] def test_forward(): assert tuple(islice(cycle(data), 5)) == (1,2,3,1,2) def test_reverse(): assert tuple(islice(cycle(reversed(data)), 5)) == (3,2,1,3,2) -- Russel. = Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.win...@ekiga.net 41 Buckmaster Roadm: +44 7770 465 077 xmpp: rus...@winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Re: Circular Buffer
On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote: (disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? Example of some ideal takeBack function: data = cycle([1,2,3][]) take(data, 4) is [1,2,3,1][] takeBack(data, 4) would be [1,3,2,1][] Thoughts? I don't think it is currently possible, but it shouldn't be hard to make retro work with cycle.
Re: Circular Buffer
On Thursday, 13 February 2014 at 20:40:21 UTC, Tobias Pankrath wrote: On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote: (disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? Example of some ideal takeBack function: data = cycle([1,2,3][]) take(data, 4) is [1,2,3,1][] takeBack(data, 4) would be [1,3,2,1][] Thoughts? I don't think it is currently possible, but it shouldn't be hard to make retro work with cycle Yep, I've missed three pages of this discussion. @monarch_dodra I'd say a bidirectional cycle should be a consistent to the random access version, so popBack becomes essentially a index-- and back == front initially.
Re: Circular Buffer
On Monday, 10 February 2014 at 10:41:06 UTC, Russel Winder wrote: On Mon, 2014-02-10 at 09:16 +, Gary Willoughby wrote: On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote: (disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? import std.algorithm; import std.array; import std.range; import std.stdio; void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); } This is why people should be using D instead of C++! This really needs to get onto the D website somewhere. how efficient is ufcs? It seems like it would be very slow in general and way better to manually do the code. I wonder if anyone has done any tests?
Re: Circular Buffer
On Thursday, 13 February 2014 at 20:56:32 UTC, Frustrated wrote: how efficient is ufcs? It seems like it would be very slow in general and way better to manually do the code. I wonder if anyone has done any tests? LDC and GDC are pretty darn good at inlining these UFCS chains, but the yielded machine code might be slightly suboptimal. In any case, you should use a profiler instead of making decisions based on some intuitive feelings which might easily be wrong. (don't underestimate the efforts put into GCC LLVM backends!)
Re: Circular Buffer
On Mon, 2014-02-10 at 09:16 +, Gary Willoughby wrote: On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote: (disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? import std.algorithm; import std.array; import std.range; import std.stdio; void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); } As Gary is aware, I posted this problem to ACCU asking for a C++ version. I think Steve Love has had a go with an added range library not just pure C++14. I'll post when I have looked at his code, and ensured it works. He is using Catch for testing so I suspect it will. I had a quick go at doing a Python 3 version using PyTest: def provide(sourceSequence, resultLength): return (sourceSequence[i % len(sourceSequence)] for i in range(resultLength)) def provideReverse(sourceSequence, resultLength): sourceLength = len(sourceSequence) return (sourceSequence[sourceLength - 1 - i % sourceLength] for i in range(resultLength)) data = [1, 2, 3] def test_forward(): assert tuple(provide(data, 5)) == (1,2,3,1,2) def test_reverse(): assert tuple(provideReverse(data, 5)) == (3,2,1,3,2) -- Russel. = Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.win...@ekiga.net 41 Buckmaster Roadm: +44 7770 465 077 xmpp: rus...@winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Re: Circular Buffer
On Mon, 2014-02-10 at 11:33 +, bearophile wrote: Russel Winder: This really needs to get onto the D website somewhere. retro+cycle is very simple code, you can also combine them: alias retroCycle = compose!(cycle, retro); point-free composition. We like this :-) Ranges and algorithms can be combined together in so many ways :-) For an imperative/OO programmer writing code based on lazy ranges and higher order functions is a new kind of programming that should be learnt patiently, but it's not hard and it doesn't contain many low-level pitfalls :-) Tell me about it. I run training courses trying to get people to do this higher-order stuff, and meta-object protocol stuff, in Python, Java and Groovy (with some Scala) and some get it and some don't. Rule 1: don't mention monads. -- Russel. = Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.win...@ekiga.net 41 Buckmaster Roadm: +44 7770 465 077 xmpp: rus...@winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Re: Circular Buffer
Wow! This is GREAT stuff. My use-case is slightly more complex, and I'm not sure how to best apply this knowledge. The retro reverses the array which is problematic in itself as well as losing the starting index location. I have an array that I'd like to elegantly rotate. Best way I can show this is by example of an imaginary rotate function: auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); Perhaps what I'm doing is too complex requires me making my own iterator or something. In my quest of writing readable efficient code, I'm wondering what's the best route here. Thanks :) On Monday, 10 February 2014 at 09:16:31 UTC, Gary Willoughby wrote: void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); }
Re: Circular Buffer
auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); It's not of immediate help, but it might trigger other answers. Matlab offers this for multi-dimensional arrays: http://www.mathworks.nl/help/matlab/ref/circshift.html
Re: Circular Buffer
On Tuesday, 11 February 2014 at 03:10:02 UTC, Jonathan Dunlap wrote: Wow! This is GREAT stuff. My use-case is slightly more complex, and I'm not sure how to best apply this knowledge. The retro reverses the array which is problematic in itself as well as losing the starting index location. I have an array that I'd like to elegantly rotate. Best way I can show this is by example of an imaginary rotate function: auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); Perhaps what I'm doing is too complex requires me making my own iterator or something. In my quest of writing readable efficient code, I'm wondering what's the best route here. Thanks :) On Monday, 10 February 2014 at 09:16:31 UTC, Gary Willoughby wrote: void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); } data.cycle.rotate(-2) == data.cycle(data.length + (-2 % data.length)) I guess you can implement your rotate function with this in mind.
Re: Circular Buffer
On Tuesday, 11 February 2014 at 09:10:16 UTC, Andrea Fontana wrote: On Tuesday, 11 February 2014 at 03:10:02 UTC, Jonathan Dunlap wrote: Wow! This is GREAT stuff. My use-case is slightly more complex, and I'm not sure how to best apply this knowledge. The retro reverses the array which is problematic in itself as well as losing the starting index location. I have an array that I'd like to elegantly rotate. Best way I can show this is by example of an imaginary rotate function: auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); Perhaps what I'm doing is too complex requires me making my own iterator or something. In my quest of writing readable efficient code, I'm wondering what's the best route here. Thanks :) On Monday, 10 February 2014 at 09:16:31 UTC, Gary Willoughby wrote: void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); } data.cycle.rotate(-2) == data.cycle(data.length + (-2 % data.length)) I guess you can implement your rotate function with this in mind. I missed a .rotate after data.cycle, of course.
Re: Circular Buffer
On Tuesday, 11 February 2014 at 16:26:06 UTC, Rene Zwanenburg wrote: On Tuesday, 11 February 2014 at 03:10:02 UTC, Jonathan Dunlap wrote: Wow! This is GREAT stuff. My use-case is slightly more complex, and I'm not sure how to best apply this knowledge. The retro reverses the array which is problematic in itself as well as losing the starting index location. I have an array that I'd like to elegantly rotate. Best way I can show this is by example of an imaginary rotate function: auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); Perhaps what I'm doing is too complex requires me making my own iterator or something. In my quest of writing readable efficient code, I'm wondering what's the best route here. Thanks :) Perhaps something like this? http://dpaste.dzfl.pl/d4b82b0b5cba Wait, we can avoid creating that closure and eliminate the map. This should be a bit faster and not use the GC: http://dpaste.dzfl.pl/78c65eacfeb1
Re: Circular Buffer
On Tuesday, 11 February 2014 at 03:10:02 UTC, Jonathan Dunlap wrote: Wow! This is GREAT stuff. My use-case is slightly more complex, and I'm not sure how to best apply this knowledge. The retro reverses the array which is problematic in itself as well as losing the starting index location. I have an array that I'd like to elegantly rotate. Best way I can show this is by example of an imaginary rotate function: auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); Perhaps what I'm doing is too complex requires me making my own iterator or something. In my quest of writing readable efficient code, I'm wondering what's the best route here. Thanks :) Perhaps something like this? http://dpaste.dzfl.pl/d4b82b0b5cba
Re: Circular Buffer
On Tuesday, 11 February 2014 at 16:30:42 UTC, Rene Zwanenburg wrote: On Tuesday, 11 February 2014 at 16:26:06 UTC, Rene Zwanenburg wrote: On Tuesday, 11 February 2014 at 03:10:02 UTC, Jonathan Dunlap wrote: Wow! This is GREAT stuff. My use-case is slightly more complex, and I'm not sure how to best apply this knowledge. The retro reverses the array which is problematic in itself as well as losing the starting index location. I have an array that I'd like to elegantly rotate. Best way I can show this is by example of an imaginary rotate function: auto data = [1,2,3]; assert( data.cycle.rotate(2) == [3,1,2] ); assert( data.cycle.rotate(-2) == [2,3,1] ); Perhaps what I'm doing is too complex requires me making my own iterator or something. In my quest of writing readable efficient code, I'm wondering what's the best route here. Thanks :) Perhaps something like this? http://dpaste.dzfl.pl/d4b82b0b5cba Wait, we can avoid creating that closure and eliminate the map. This should be a bit faster and not use the GC: http://dpaste.dzfl.pl/78c65eacfeb1 Why not drop and take? http://dpaste.dzfl.pl/0649b809c81e
Re: Circular Buffer
Ooo.. I like the drop and take approach! I wonder if this could be something that makes it into the standard library (std.range?). What would be the best way to approach in suggesting that? Why not drop and take? http://dpaste.dzfl.pl/0649b809c81e
Re: Circular Buffer
On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote: (disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? import std.algorithm; import std.array; import std.range; import std.stdio; void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); }
Re: Circular Buffer
On Mon, 2014-02-10 at 09:16 +, Gary Willoughby wrote: On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote: (disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? import std.algorithm; import std.array; import std.range; import std.stdio; void main(string[] args) { auto data = [1,2,3]; assert(data.cycle.take(5).array == [1,2,3,1,2]); assert(data.retro.cycle.take(5).array == [3,2,1,3,2]); } This is why people should be using D instead of C++! This really needs to get onto the D website somewhere. -- Russel. = Dr Russel Winder t: +44 20 7585 2200 voip: sip:russel.win...@ekiga.net 41 Buckmaster Roadm: +44 7770 465 077 xmpp: rus...@winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Re: Circular Buffer
Russel Winder: This really needs to get onto the D website somewhere. retro+cycle is very simple code, you can also combine them: alias retroCycle = compose!(cycle, retro); Ranges and algorithms can be combined together in so many ways :-) For an imperative/OO programmer writing code based on lazy ranges and higher order functions is a new kind of programming that should be learnt patiently, but it's not hard and it doesn't contain many low-level pitfalls :-) Bye, bearophile
Re: Circular Buffer
(disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? Example of some ideal takeBack function: data = cycle([1,2,3][]) take(data, 4) is [1,2,3,1][] takeBack(data, 4) would be [1,3,2,1][] Thoughts?
Re: Circular Buffer
On Monday, 10 February 2014 at 03:14:31 UTC, Jonathan Dunlap wrote: (disclaimer: I'm new around here) Is it possible to cycle backwards? If not, what's the best approach? Example of some ideal takeBack function: data = cycle([1,2,3][]) take(data, 4) is [1,2,3,1][] takeBack(data, 4) would be [1,3,2,1][] Thoughts? Probably what you're looking for: http://dlang.org/phobos/std_range.html#.retro
Re: Circular Buffer
On Friday, 20 December 2013 at 15:45:04 UTC, Frustrated wrote: I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC. I suppose I could copy and modify the code but is there any easier way? It looks like it is defined as templates so could I somehow hijack the code and modify only what is needed rather than duplicate a lot of stuff? (or maybe someone could just add it to the library... circular arrays are useful ya know ;) http://p0nce.github.io/gfm/gfm.core.queue.html#RingBuffer and use malloc instead of .length
Re: Circular Buffer
On Friday, 20 December 2013 at 15:45:04 UTC, Frustrated wrote: I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC. I suppose I could copy and modify the code but is there any easier way? It looks like it is defined as templates so could I somehow hijack the code and modify only what is needed rather than duplicate a lot of stuff? (or maybe someone could just add it to the library... circular arrays are useful ya know ;) Writing your own should be quite simple. I see others have already added some implementations, so I'll add mine too. Modifying it to use a static array shouldn't be too difficult, but you're probably better off using some of the others code as this is dynamic and haven't been used in production. https://gist.github.com/simendsjo/3b8a9c60bd92e16691d7
Re: Circular Buffer
There's actually already a circular buffer implemented in vibe.d, and if I remember right it's not dependent on anything from vibe. On 12/20/13, Frustrated c1514...@drdrb.com wrote: I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC. I suppose I could copy and modify the code but is there any easier way? It looks like it is defined as templates so could I somehow hijack the code and modify only what is needed rather than duplicate a lot of stuff? (or maybe someone could just add it to the library... circular arrays are useful ya know ;)
Re: Circular Buffer
But does it rely on the GC?
Circular Buffer
I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC. I suppose I could copy and modify the code but is there any easier way? It looks like it is defined as templates so could I somehow hijack the code and modify only what is needed rather than duplicate a lot of stuff? (or maybe someone could just add it to the library... circular arrays are useful ya know ;)
Re: Circular Buffer
Frustrated: I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC. Why do you need to avoid the GC? Bye, bearophile
Re: Circular Buffer
On 12/20/13, Frustrated c1514...@drdrb.com wrote: But does it rely on the GC? Nope, the template you wanted is vibe.utils.array:FixedRingBuffer.
Re: Circular Buffer
On 12/20/2013 04:45 PM, Frustrated wrote: I'm in need of a circular buffer/array. I am using std.container.array to avoid the GC. I suppose I could copy and modify the code but is there any easier way? ... What prevents you from implementing your buffer using an std.container.Array as the backing store?
Re: Circular Buffer
Use std.range.cycle with std.container.Array (slice the array to get a range). http://dlang.org/phobos/std_range.html#.cycle