Streamly.Internal.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.

Show the contents of a RingArray as a list.

>>> showRing rb = RingArray.toList rb >>= return . show

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 at index 0 of the array. Cast fails with Nothing if the array is a slice.

>>> castMutArray = RingArray.castMutArrayWith 0

castMutArray arr index casts a mutable array to a ring array having the ring head at index position in the array.

This operation throws an error if the index is not within the array bounds. It returns Nothing if the array cannot be cast into ring because the array is a slice. In that case clone the array and cast it or stream the array and use createOfLast to create a ring.

Cast a MutArray to a ring sharing the same memory without copying. The ring head is at index 0 of the array. The array must not be a slice.

>>> unsafeCastMutArray = RingArray.unsafeCastMutArrayWith 0

The array must not be a slice, and the index must be within the bounds of the array otherwise unpredictable behavior will occur.

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)

Move the ring head forward or backward by n slots. Moves forward if the argument is positive and backward if it is negative.

Throws an error if the absolute value of count is more than or euqal to the ring size.

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 ring having elements of type a into a ring having elements of type b. The ring size must be a multiple of the size of type b.

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.

Note, this will crash on ring of 0 size.

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.

Apply the given fold on sliding windows of the given size. Note that this could be expensive because each operation goes through the entire window. This should be used only if there is no efficient alternative way possible.

Examples:

>>> windowRange = RingArray.scanFoldRingsBy Fold.range
>>> windowMinimum = RingArray.scanFoldRingsBy Fold.minimum
>>> windowMaximum = RingArray.scanFoldRingsBy Fold.maximum

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.

Fold the buffer starting from ringStart up to the given index using a pure step function. This is useful to fold the items in the ring when the ring is not full. The supplied index is usually the end of the ring.

Unsafe because the supplied index is not checked to be in range.

Like unsafeFoldRing but with a monadic step function.

Fold n items in the ring starting at the ring head. Won't fold more than the length of the ring even if n is larger.

Note, this will crash on ring of 0 size.

slidingWindow collector is an incremental sliding window fold that does not require all the intermediate elements in a computation. This maintains n elements in the window, when a new element comes it slides out the oldest element and the new element along with the old element are supplied to the collector fold.

The Maybe type is for the case when initially the window is filling and there is no old element.

Like slidingWindow but also provides the entire ring contents as an Array. The array reflects the state of the ring after inserting the incoming element.

IMPORTANT NOTE: The ring is mutable, therefore, the result of (m (Array a)) action depends on when it is executed. It does not capture the sanpshot of the ring at a particular time.