Streamly.Data.RingArray

A ring buffer is a circular buffer. A new element is inserted at a position called the ring head which points to the oldest element in the ring, an insert overwrites the oldest element. After inserting, the head is moved to point to the next element which is now the oldest element.

Elements in the ring are indexed relative to the head. RingArray head is designated as the index 0 of the ring buffer, it points to the oldest or the first element in the buffer. Higher positive indices point to the newer elements in the buffer. Index -1 points to the newest or the last element in the buffer. Higher negative indices point to older elements.

The ring is of fixed size and cannot be expanded or reduced after creation. Creation of zero sized rings is not allowed.

This module provides an unboxed implementation of ring buffers for best performance.

createOfLast n returns the last n elements of the stream in a ring array. n must be non-zero.

Cast a MutArray to a ring sharing the same memory without copying. The ring head is positioned at index 0 of the array. The size of the ring is equal to the MutArray length.

See castMutArrayWith for failure scenarios.

>>> castMutArray = RingArray.castMutArrayWith 0

castMutArrayWith index arr casts a mutable array to a ring array, and positions the ring head at the given index in the array.

A MutArray can be a slice which means its memory starts from some offset in the underlying MutableByteArray, and not from 0 offset. RingArray always uses the memory from offset zero in the MutableByteArray, therefore, it refuses to cast if it finds the array does not start from offset zero i.e. if the array was created from some slicing operation over another array. In such cases it returns Nothing.

To create a RingArray from a sliced MutArray use createOfLast, or clone the MutArray and then cast it.

This operation throws an error if the index is not within the array bounds.

Advance the ring head forward by 1 slot, the ring head will now point to the next (newer) item, and the old ring head position will become the latest or the newest item position.

>>> moveForward = RingArray.moveBy 1

Move the ring head backward by 1 slot, the ring head will now point to the prev (older) item, when the ring head is at the oldest item it will move to the newest item.

>>> moveForward = RingArray.moveBy (-1)

Insert a new element without replacing an old one. Expands the size of the ring. This is similar to the snoc operation for MutArray.

Unimplemented

Replace the oldest item in the ring (the item at the ring head) with a new item and move the ring head to the remaining oldest item.

Throws an error if the ring is empty.

Like replace but does not return the old value of overwritten element.

Same as:

>>> replace_ rb x = RingArray.putIndex 0 rb x >> pure (RingArray.moveForward rb)

O(1) Write the given element at the given index relative to the current position of the ring head. Index starts at 0, could be positive or negative.

Throws an error if the index is more than or equal to the size of the ring.

Performs in-place mutation of the array.

Modify a given index of a ring array using a modifier function.

Unimplemented

O(1) Lookup the element at the given index relative to the ring head. Index starts from 0, could be positive or negative. Returns Nothing if the index is more than or equal to the size of the ring.

Like getIndex but does not check the bounds. Unpredictable behavior occurs if the index is more than or equal to the ring size.

O(1) Lookup the element at the head position.

Prefer this over unsafeGetIndex 0 as it does not have have to perform an index rollover check.

Copy the ring to a list, the first element of the list is the oldest element of the ring (i.e. ring head) and the last is the newest.

>>> toList = Stream.toList . RingArray.read

Copy the ring to a MutArray, the first element of the MutArray is the oldest element of the ring (i.e. ring head) and the last is the newest.

>>> toMutArray rb = Stream.fold (MutArray.createOf (RingArray.length rb)) $ RingArray.read rb

Read the entire ring as a stream, starting at the ring head i.e. from oldest to newest.

Read the entire ring as a stream, starting from newest to oldest elements.

Read the entire ring, starting at the ring head i.e. from oldest to newest.

Read the entire ring in reverse order, starting at the item before the ring head i.e. from newest to oldest

O(1) Get the length of the ring. i.e. the number of elements in the ring.

O(1) Get the byte length of the ring.

Cast a ring having elements of type a into a ring having elements of type b. The length of the ring should be a multiple of the size of the target element otherwise Nothing is returned.

Cast a RingArray a into a RingArray Word8.

Cast the ring to a mutable array. Return the mutable array as well as the current position of the ring head. Note that the array does not start with the current ring head. The array refers to the same memory as the ring.

Fold the entire length of a ring buffer starting at the current ring head.

ringsOf n stream groups the input stream into a stream of ring arrays of size up to n. See scanRingsOf for more details.

scanRingsOf n groups the input stream into a stream of ring arrays of size up to n. The first ring would be of size 1, then 2, and so on up to size n, when size n is reached the ring starts sliding out the oldest elements and keeps the newest n elements.

Note that the ring emitted is a mutable reference, therefore, should not be retained without copying otherwise the contents will change in the next iteration of the stream.

Byte compare the entire length of ringBuffer with the given array, starting at the supplied ring head index. Returns true if the Array and the ring have identical contents. If the array is bigger checks only up to the ring length. If array is shorter than then ring, it is treated as an error.

Like eqArray but compares only N bytes instead of entire length of the ring buffer. If N is bigger than the ring or array size, it is treated as an error.