Suggestions for a nanobuffer

I’m looking for a data structure for Motoko that acts like this in behaviour

Basically I can define up front the size of the buffer. Adding items keeps filling it up to the limit. Once at capacity I should be able to discard the oldest item and add the new item. But in a queue so that insertion order is preserved.

The closest data structure I found is a Deque and I was open to writing the max size logic myself. But the deque lacks a size property which I expected it to have. Considering the Deque is derived from a List.

Thoughts?

1 Like

Sounds like a circular buffer to me: Circular buffer - Wikipedia

Is there a data structure here that I could use that serves this purpose?

I’m okay to add some additional logic. I believe Deque would serve this purpose. Is there a way to get the size from a Deque? The methods listed here dont have one

If I have access to size, I can check when pushing items to the end. IF capacity is reached, i’ll pop from the front and push to the end, else i’ll just push to the end

I think you can compute the size of the Deque just by summing the List.size(deque.0) + List.size(deque.1) of its two components. But that is an 0(N) operation and will be expensive.

Another option is wrap the deque and track its size as you push and an pop to the underlying deque.

An array based implementation (as described in the wikipedia page), would be more efficient that either of those approaches, I expect.

1 Like

Curiously, GitHub - aviate-labs/queue.mo: Queues in Motoko seems to implement a size function and circular variant, along the lines you are suggesting…

1 Like

I’ll check. Thank you

1 Like

Someone asked for size() in Queue.mo here a while back so it’s in this one too:
https://github.com/o0x/motoko-queue

Edit: It looks like quint’s variation would handle the circular part for you. Again it uses size so note everything Claudio says above.

1 Like

I was wondering about the “wrap the deque and track its size as you push and an pop to the underlying deque”.

Wouldn’t it make sense to have this functionality as part of the Deque in the base library?

Happy to send a pull request if you think this makes sense.