CircularArraysLibrary "CircularArrays"
This library shows how to implement circular arrays. Native arrays in Pine are simple, resizable data structures. If you add or insert another element, the array extends its size. Arrays can grow to 100,000 elements.
🟩 WHY USE A CIRCULAR ARRAY?
The built-in methods that add or remove elements at the beginning of an array can create a performance problem. When `array.shift()` removes and returns the first element, every remaining element moves down one place and receives a new index. The operation is O(n), meaning that its cost scales linearly with the number of elements. For example, shifting an array of 200 elements is roughly twice as expensive as shifting one of 100 elements. Similar considerations apply to `array.unshift()`, which inserts an element at the beginning.
By contrast, `array.push()` and `array.pop()` operate at the end of the array and are generally O(1).
A common requirement is to keep an array at a fixed size. The usual approach is to remove an element from the beginning whenever the script adds one to the end after the array reaches its maximum size. Because removing the first element is O(n), maintaining the fixed-size array this way is also O(n).
A circular array offers an alternative. It has a fixed size and can be imagined as a ring. This implementation uses a normal backing array together with an integer pointer that identifies the element containing the first (oldest) element. The pointer lets us change the apparent order of the elements without actually moving them all.
🟩 EXAMPLE: ADD `Z` TO THE BEGINNING WHEN THE CIRCULAR ARRAY IS NOT FULL
Let's take a "string" array with `A` as element 0. To put `Z` before it, we move the oldest-element pointer back one slot. Because it was at index 0, it wraps around to index 4, the final slot in the backing array. We write `Z` there - to the end of the backing array. The existing values do not move, but reading from the new oldest-element pointer makes the logical order `Z, A, B, C`.
Index: 0 1 2 3 4
Before insertion: A B C - -
^
oldest
int head = 0
Index: 0 1 2 3 4
After insertion: A B C - Z
^
oldest
int head = 4
Logical order: Z A B C
The other beginning-of-array operations use the same pointer:
Remove when not full: Read and clear the value at the oldest-element pointer, move the pointer forward one slot, and decrease the stored size. The next value becomes the oldest without any remaining values moving.
Add when full: Move the oldest-element pointer back one slot. Because every slot is occupied, this is the slot containing the previous newest value. Replace it with the new value. The new value becomes the oldest, the previous newest value is evicted, and the stored size stays the same.
Remove when full: Read and clear the slot identified by the oldest-element pointer, move the pointer forward one slot, and decrease the stored size. The next value becomes the oldest and the cleared slot becomes empty.
🟩 LIMITATIONS
Circular arrays can potentially improve performance when you need to keep an array at a fixed size (see below), but they have some drawbacks:
You cannot use the built-in array methods to alter them. You must use custom methods that manipulate the circular-array object rather than only its backing array.
They require more setup than native arrays.
Their capacity must be chosen in advance. Changing it requires rebuilding the backing array.
Although operations at either end are O(1), inserting or removing elements in the middle remains O(n).
Eviction methods return the displaced value so that your script can react to it if you need. One common use is a ring of drawing objects, where the script additionally deletes the line, box, or label returned as a separate cleanup step.
Pine does not support arrays of a generic type, so this public library stores floats only and serves as a template . Copy it and replace the element type to create a ring of integers, strings, or user-defined objects. Alternatively, for a slight performance increase, you can inline the types and methods you need.
🟩 FUNCTIONAL DEMONSTRATION
The functional demo shows how to keep the last n `close` prices in a fixed-size circular array. It displays the contents of the array in a table on the chart.
🟩 PROFILER DEMONSTRATION
The library also includes a Pine Profiler demonstration of the common fixed-window operation: add one new value and evict the oldest.
It compares four implementations:
The exported circular-array `pushValue()` method.
The same ring operation written directly against a normal backing array, to remove the exported-method overhead.
Native `array.shift()` followed by `array.push()`, which is the usual Pine implementation.
A manual Pine-level linear shift wrapped in a UDT method. This moves every value down one index and is there to compare the circular and linear algorithms when both are written in Pine. It does not reproduce PulseWire's much more optimised native `array.shift()` implementation. It's there so we can compare not the implementations but the principles of both methods.
The main benchmarks run over several bars so that the measured work is much bigger than the Profiler's overhead. The manual linear shift performs 1000x fewer top-level replacements because it is so much sloooower.
Of these options, the emulated Pine linear shift is so much slower it's not even funny.
The native Pine `shift()` and `push()` does the same work but in an optimsed way. You can see that it is ~1000x faster than the emulator.
Our own circular array starts off being much slower than the native version, but as you increase the array size, the native one gets significantly slower, and at some point they cross over and our version "wins". In my tests using this library's demo function the crossover point landed somewhere around ~5,000 elements.
Performance profiling is a tricky business. It depends very much on how your script is written, and even for the same script, it also changes from run to run. YMMV.
My personal conclusions from testing this library are:
Circular arrays *as an operating principle* are great for fixed-size array operations where you are adding new values and removing old ones.
Native optimisations are huge.
This Pine library offers potential performance advantages over the built-in methods only for very large arrays (thousands of elements).
If Pine made native circular arrays they would massively outperform linear arrays for these kinds of tasks.
Find out more about the Pine Profiler: www.pulsewire.com
The functions:
new(_capacity)
Creates an empty circular array with a fixed capacity. The backing array starts at its full length, filled with `na`, so normal operations never need to resize it.
Parameters:
_capacity (int) : The maximum number of elements. Values below 1 or `na` are changed to 1 so the circular array remains usable without a runtime error.
Returns: A new, empty `o_circularFloat` object. Empty in the sense that there are no values in it.
method elementCount(_this)
Gets the number of elements currently stored. This is different from capacity: the backing array always has `capacity` slots, but only `elementCount` of them currently hold logical values. We have kind of split array "size" into two concepts of elementCount and capacity, so to avoid confusion we do not expose a .size() method.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
Returns: The number of stored elements (0..capacity).
method capacity(_this)
Gets the maximum number of elements the circular array can hold. We have kind of split array "size" into two concepts of elementCount and capacity, so to avoid confusion we do not expose a .size() method.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
Returns: The fixed capacity.
method isFull(_this)
Checks whether the circular array is full. When it is, pushValue() or unshiftValue() must evict an element (they always return the element).
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
Returns: `true` when elementCount == capacity.
method isEmpty(_this)
Checks whether the circular array is empty.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
Returns: `true` when elementCount == 0.
method getValue(_this, _index)
Gets the element at a logical index, where 0 is the oldest and elementCount-1 is the newest.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
_index (int) : The logical index.
Returns: The element, or `na` when the index is out of range.
method setValue(_this, _index, _value)
Replaces the element at a logical index without changing the circular array's element count or order. This can update a stored value, or a field when the same pattern is adapted for objects.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
_index (int) : The logical index (0..elementCount-1). An out-of-range index does nothing.
_value (float) : The new value.
method firstValue(_this)
Gets the oldest element (logical index 0) without removing it.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
Returns: The oldest element, or `na` when empty.
method lastValue(_this)
Gets the newest element (logical index elementCount-1) without removing it.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
Returns: The newest element, or `na` when empty.
method pushValue(_this, _value)
Adds a value at the end as the new newest element. If the circular array is full, this replces and returns the oldest element so you can react to it, for example by deleting an evicted drawing.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
_value (float) : The value to add.
Returns: The evicted oldest value when the circular array was full, otherwise `na`.
method unshiftValue(_this, _value)
Adds a value at the beginning as the new oldest element. If the circular array is full, this replaces and returns the newest element. This gives the same result as using array.unshift() with a size limit, but is O(1).
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
_value (float) : The value to add.
Returns: The evicted newest value when the circular array was full, otherwise `na`.
method shiftValue(_this)
Removes and returns the oldest element. Unlike the O(n) array.shift(), this is O(1) because we only clear one slot and move the head pointer. This is therefore the big payoff for all this fussing about.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
Returns: The removed oldest element, or `na` when the circular array was empty.
method popValue(_this)
Removes and returns the newest element.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
Returns: The removed newest element, or `na` when the circular array was empty.
method removeAt(_this, _index)
Removes and returns the element at a logical index. Later elements move down to close the gap, so this is O(n).
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
_index (int) : The logical index to remove (0..elementCount-1). An out-of-range index returns `na` and changes nothing.
Returns: The removed element, or `na` when the index was out of range.
method insertAt(_this, _index, _value)
Inserts a value at a logical index. Elements at and after that index move towards the end, so this is O(n). If the circular array is full, the newest element is removed and returned.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
_index (int) : The logical index at which to insert (0..elementCount). Numeric values outside this range are clamped into it, except that an index past the newest element on a full buffer has nowhere to go, so the value is returned unstored. An `na` index changes nothing and returns `_value`.
_value (float) : The value to insert.
Returns: The evicted newest value when the circular array was full, the supplied value when an `na` index prevented insertion, otherwise `na`.
method containsValue(_this, _value)
Checks whether the circular array contains an exact match, treating a stored `na` as matching an `na` search value. This is O(n). If you adapt this template to an object type, `==` compares references, not contents, so you will likely want to replace the comparison with a field-by-field check.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
_value (float) : The value to look for.
Returns: `true` when found.
method clearValues(_this)
Empties the circular array without changing its capacity. All backing-array slots are reset to `na`, and head and elementCount return to zero.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
method toArray(_this)
Copies the circular array's contents into a normal array, from oldest to newest. This can be useful for iteration or debugging. Changes to the returned array do not affect the circular array.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
Returns: A new array containing the stored values from oldest to newest.
method deepCopy(_this)
Copies the circular array, including a separate backing array, so either copy can be changed without affecting the other.
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
Returns: A new o_circularFloat with the same contents and capacity.
method resize(_this, _newCapacity)
Changes the capacity. Increasing it keeps every element. Decreasing it below the current element count keeps the newest elements and returns the dropped oldest elements, oldest first, so you can react to them as with pushValue().
Namespace types: o_circularFloat
Parameters:
_this (o_circularFloat) : The circular buffer.
_newCapacity (int) : The new capacity. Values below 1 are changed to 1. An `na` value leaves the capacity unchanged.
Returns: An array containing the dropped oldest elements, or an empty array when nothing was dropped.
o_circularFloat
A fixed-capacity circular buffer of floats. Elements are addressed by a LOGICAL index where 0 is the oldest retained element and elementCount-1 is the newest, matching normal array indexing. Internally the data lives in a recycled backing array of length `capacity`; `head` marks where the oldest element physically sits, and the buffer wraps around the end of the backing array as elements are added and removed.
Fields:
a_data (array) : The backing array. Always actually `capacity` elements long; unused slots hold na. Never index this directly - use getValue()/setValue(), which translate logical indices to physical ones.
head (series int) : The physical index in `a_data` of the oldest logical element (logical index 0). Advances on shiftValue(), retreats on unshiftValue(), wrapping modulo capacity. Always kept in 0..capacity-1; the index maths in f_physicalIndex() relies on this.
elementCount (series int) : The number of elements currently stored (0..capacity). This differs from the backing array's size, which always equals capacity.
capacity (series int) : The maximum number of elements the buffer can hold. Fixed at construction; change it only via resize().
Library
