www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Circular Buffer

reply "Frustrated" <c1514843 drdrb.com> writes:
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 ;)
Dec 20 2013
next sibling parent reply Orvid King <blah38621 gmail.com> writes:
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 <c1514843 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 ;)
Dec 20 2013
parent reply "Frustrated" <c1514843 drdrb.com> writes:
But does it rely on the GC?
Dec 20 2013
parent Orvid King <blah38621 gmail.com> writes:
On 12/20/13, Frustrated <c1514843 drdrb.com> wrote:
 But does it rely on the GC?
Nope, the template you wanted is vibe.utils.array:FixedRingBuffer.
Dec 20 2013
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Dec 20 2013
prev sibling next sibling parent Timon Gehr <timon.gehr gmx.ch> writes:
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?
Dec 20 2013
prev sibling next sibling parent reply "lomereiter" <lomereiter gmail.com> writes:
Use std.range.cycle with std.container.Array (slice the array to 
get a range).

http://dlang.org/phobos/std_range.html#.cycle
Dec 20 2013
parent reply "Jonathan Dunlap" <jadit2 gmail.com> writes:
(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?
Feb 09 2014
next sibling parent "Chris Cain" <clcain uncg.edu> writes:
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
Feb 09 2014
prev sibling next sibling parent reply "Gary Willoughby" <dev nomad.so> writes:
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]); }
Feb 10 2014
next sibling parent reply Russel Winder <russel winder.org.uk> writes:
On Mon, 2014-02-10 at 09:16 +0000, 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.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Feb 10 2014
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Feb 10 2014
parent Russel Winder <russel winder.org.uk> writes:
On Mon, 2014-02-10 at 11:33 +0000, 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.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Feb 12 2014
prev sibling parent reply "Frustrated" <c1514843 drdrb.com> writes:
On Monday, 10 February 2014 at 10:41:06 UTC, Russel Winder wrote:
 On Mon, 2014-02-10 at 09:16 +0000, 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?
Feb 13 2014
parent "Artem Tarasov" <lomereiter gmail.com> writes:
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!)
Feb 13 2014
prev sibling next sibling parent reply "Jonathan Dunlap" <jadit2 gmail.com> writes:
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]);
 }
Feb 10 2014
next sibling parent "Martijn Pot" <martijnpot52 gmail.com> writes:
 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
Feb 11 2014
prev sibling next sibling parent reply "Andrea Fontana" <nospam example.com> writes:
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.
Feb 11 2014
parent "Andrea Fontana" <nospam example.com> writes:
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.
Feb 11 2014
prev sibling parent reply "Rene Zwanenburg" <renezwanenburg gmail.com> writes:
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
Feb 11 2014
parent reply "Rene Zwanenburg" <renezwanenburg gmail.com> writes:
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
Feb 11 2014
parent reply "Andrea Fontana" <nospam example.com> writes:
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
Feb 11 2014
parent "Jonathan Dunlap" <jadit2 gmail.com> writes:
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
Feb 11 2014
prev sibling parent reply Russel Winder <russel winder.org.uk> writes:
On Mon, 2014-02-10 at 09:16 +0000, 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.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Feb 12 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Feb 13 2014
next sibling parent Russel Winder <russel winder.org.uk> writes:
On Thu, 2014-02-13 at 18:03 +0000, 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.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Feb 13 2014
prev sibling parent Russel Winder <russel winder.org.uk> writes:
On Thu, 2014-02-13 at 18:03 +0000, 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.winder ekiga.net 41 Buckmaster Road m: +44 7770 465 077 xmpp: russel winder.org.uk London SW11 1EN, UK w: www.russel.org.uk skype: russel_winder
Feb 13 2014
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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.
Feb 13 2014
prev sibling parent reply "Tobias Pankrath" <tobias pankrath.net> writes:
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.
Feb 13 2014
parent "Tobias Pankrath" <tobias pankrath.net> writes:
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.
Feb 13 2014
prev sibling next sibling parent "ponce" <contact gam3sfrommars.fr> writes:
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
Dec 21 2013
prev sibling parent "simendsjo" <simendsjo gmail.com> writes:
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
Dec 21 2013