Crate framering

A 'deque of deques' all sharing the same contiguous memory space. FramedRing enables creation of multiple deques without needing to allocate a separate heap space for each sequence. As the name implies, FramedRing operates similarly to a ring buffer - items in all frames are stored in the same buffer where deallocated frames on the tail of the buffer free up capacity for new element pushes on the head frame.

Frame creation and element appending likely will not incur a memory allocation unless the ring is full. Operations such as creating a new frame, appending to a frame, random access into a frame, and iterating over a frame are O(1). Operations which may incur a memory allocation such as frame creation or element appending will only incur a O(n) penalty after memory allocation for expansion.

This implementation has flexible capacity behaviors via custom implementations of Capacity - if an application requires unique capacity behaviors, one can be provided.

Examples

Rings (the backing store for frames) can be created using the new method - this creates an empty ring. Memory isn't allocated until the first frame is created.

let ring: FramedRing<i32, Pow2Capacity> = FramedRing::new();

An initial seed frame can be created using the frame method and have items appended to it...

let mut ring = FramedRing::<i32, Pow2Capacity>::new();
let mut frame = ring.frame();
frame.push(1);
frame.push(2);
frame.push(3);

... and other frames can be created after with more elements.

let mut ring = FramedRing::<i32, LinearCapacity>::new();

let mut frame1 = ring.frame();
frame1.push(1);

let (frame1_ro, mut frame2) = frame1.next();
frame2.push(2);

let (frame2_ro, mut frame3) = frame2.next();
frame3.push(3);

A FramedRing may have multiple frames at once, but only one (the head frame) may have items appended to it. Frames (including the head) can be dropped at any time and all objects stored in that frame will be dropped as well. Space is reclaimed when the tail frame is dropped - when that happens, the oldest non-dropped frame will become the new tail and space before then will be reclaimed.

Elements within frames are indexable (with a complexity of O(1)), and appends to the head frame are also O(1) assuming the ring has space (otherwise there is a complexity of O(n)).

Structs

FramedRing	A ring buffer which exposes operations via 'frames'.
LinearCapacity	Implementation of capacity which represents the capacity as usize. Does not support infinite addressing, and will panic if more than usize::MAX elements are inserted in a forward fashion (due to addition overflow).
RingFrame	An immutable frame which does not allow elements to be appended
RingFrameIntoIter	Iterator over elements within a RingFrame
RingFrameIter	Iterator over elements within a RingFrame
RingFrameMut	A mutable frame which allows elements to be appended to the end

Enums

Pow2Capacity

Implementation of capacity which represents the capacity as a power of 2. Supports infinite addressing (will not eventually result in a panic, no matter how many elements are added over the lifetime of the FramedRing).

Traits

Capacity

Defines the capacity behavior of a FramedRing.