The RingBuffer trait

[bal-e]

Here's a sketch of what the RingBuffer trait should look like:

pub trait RingBuffer {
    type Item;

    fn is_full(&self) -> bool;
    fn is_empty(&self) -> bool;

    // Peek ahead from elements to be dequeued.
    fn peek(&self, off: usize) -> Option<&Self::Item>;
    fn peek_mut(&mut self, off: usize) -> Option<&mut Self::Item>;

    // Peek behind to elements recently enqueued.
    fn peek_back(&self, off: usize) -> Option<&Self::Item>;
    fn peek_back_mut(&mut self, off: usize) -> Option<&mut Self::Item>;

    fn enqueue(&self, item: Self::Item) -> Option<Self::Item>;
    fn dequeue(&self) -> Option<Self::Item>;
}

I'm still not sure about the peek methods, but they're here to facilitate discussion on better APIs. Are there any other functions or types we want to include here (e.g. for iterators)?

I think a fairly common use case is ring buffers that are always full - let's call them SaturatedRingBuffers. They can have their own trait, and it might look like this:

pub trait SaturatedRingBuffer {
    type Item;

    // Peek ahead from elements to be dequeued.
    fn peek(&self, off: usize) -> &Self::Item;
    fn peek_mut(&mut self, off: usize) -> &mut Self::Item;

    // Peek behind to elements recently enqueued.
    fn peek_back(&self, off: usize) -> &Self::Item;
    fn peek_back_mut(&mut self, off: usize) -> &mut Self::Item;

    fn enqueue(&self, item: Self::Item) -> Self::Item;
}

Note that there are a few shared/similar items here. Can we unify them between the two traits, and how might we do that?

[tertsdiepraam]

I think we should start small, so maybe without peek. For reference: ringbuffer calls the peek things get/get_mut. I associate peek with iteration mostly. In general, matching vecdeque as closely as possible might be nice.

Re: SaturatedRingBuffer, great idea, but I think unifying them is not the best idea. These data structures are fundamentally different.

I like how we're already running into keyword generics territory.

[bal-e]

A ring buffer is a kind of iterator, where enqueue() / dequeue() return the next item. In that sense, peek() is exactly right - you're peeking ahead among the elements that will be dequeued. I've looked around for genuine use cases for ring buffers, and direct access to the elements is very common. I don't want to table it for later.

[tertsdiepraam]

No? Peek on iterators has a very well-defined meaning that's not "get some random element from the collection". If it matched the signature of iterator peek I'd agree with you, but it's not