Contents |
A circular array is like a fillable array except values can be added to and removed from the front of the store as well as the back. A consequence of this is the front element of the store may have an associated index other than zero. To avoid shifting elements when adding an element to the front of the store, indices are allowed to roll over. For example, suppose the capacity is 10 and the size is 5, with the first element residing at index 0 (using zero-based counting). Adding a new value to the front should place it at index -1, which does not exist. Since the index is too small (i.e., negative), the capacity is added to the index to make it non-negative. For our example, the new index is -1 plus 10, or 9. Thus the new element is added at index 9, the rightmost slot. Conversely, with the same size and capacity as before, but with the index of the first element being 5, consider adding an element to the back. In this case, the index of the most rightmost element is 9, because the size is 5 (the five values are stored at indices 5, 6, 7, 8, and 9). Adding an element at the back would place it at index 10, which does not exist. Since the index is too large, the proper index is then computed by subtracting off the capacity. The places the to-be-added element at index 0. The tests for indices being too small or too large can be eliminated by the use of modular arithmetic.
As with fillable arrays circular arrays use a normal array as a store.
The typical circular array object has three components plus a set of operators:
class circular-array { var store = ?; //points to an array var capacity = ?; //length of the store var size = 0; //net number of elements added var startIndex = 0; //index of the first/leftmost element var endIndex = 0; //optional: index of the first open slot //operations ... }
The store component points to a normal array and is set by the constructor. The capacity is usually given as an argument to the constructor and is used to allocate the store. Both the start and end indices are set to zero; the only case when these indices are equal is when the circular array is empty.
The terms used in describing a circular array, in addition to those of normal arrays, are:
Circular arrays can be used to implement:
Circular arrays are used as a basis for:
Circular arrays are implemented using arrays, with similarities to fillable arrays.
This operation subracts one from the given index. If the resulting value becomes too small, the value is corrected by adding in the capacity. In any case, the new, perhaps corrected, value is returned.
This operation is generally a private method.
Like decrement-index, except one is added to the given index (with possible correction).
This operation is generally a private method.
The increment and decrement operations can be replaced with this operation which typically uses modular arithmetic to adjust the given index. The calls:
u = decrementIndex(v) x = incrementIndex(y)
would be replaced with:
u = correctIndex(v - 1); x = correctIndex(y + 1);
This operation is generally a private method.
This operation adds a given value to the front of the store. A special case exists if the array is empty. If so, add-to-back is called to handle the addition. Otherwise, the start index is decremented and corrected, if necessary.
function add-to-front(value) { if (size == 0) add-to-back(value) else { startIndex = decrementIndex(startIndex); store[startIndex] = value; size += 1; } }
Adding an element to the front takes Θ(1) time.
This operation adds a given value to the back of the store. Unlike fillable arrays, the next available slot may not have index size. The start index is added to the size to generate the actual index of the next available slot. The generated index is corrected, if necessary.
function add-to-back(value) { store[endIndex] = value; endIndex = incrementIndex(endIndex) size += 1; }
Adding an element to the back takes Θ(1) time.
This operation removes the leftmost value in the store. This can be done simply by incrementing the start index (with correction). The size component is updated accordingly.
Removing the front element takes Θ(1) time.
This operation removes the rightmost value in the store. This can be done simply by decrementing the size, if the end index is not cached. If the end index is cached, it needs to be decremented (with correction) as well.
Removing the back element takes Θ(1) time.
Like fillable arrays, a valid index for get and set lies between 0 and size - 1. However, the value of the start index must be added to the given index and then corrected as necessary. For example, get becomes:
function get(index) { var spot = correctIndex(index + startIndex); return store[spot]; }
The code for set follows a similar pattern.
Find is similar to that of fillable arrays. Assuming the elements are unsorted, a modified linear traversal (see below) is used.
Circular arrays support traversals similar to that of arrays, except that the actual starting (or ending) point is the start index while the actual ending (or starting point) is the end index. However, since the end index may be smaller than the start index, it becomes difficult to write a loop based upon these actual values. By basing the traversal on get (or set), then the starting (or ending) point is zero and the ending (or starting point) is the size - 1 and writing such a traversing loop is greatly simplified:
for (i = 0; i < size; i += 1) println(get(i));
A right-to-left traversal is similar.
Contents |