Class CircularList<T>

A circular list of values, where the next value added overwrites the oldest value. The list is filled in until full, then it overwrites earlier entries in the list.

How CircularList Works

This section describes how the class works internally. This information is not needed for using this class.

Index Numbers, Pointers, and Overflow

Each value added has an index number which starts at zero and increases by one with each new value. The index number keeps increasing even when the list has 'wrapped around' and starts overwriting earlier entries.

Internally we use the term 'pointer' to mean a number in the range from 0 to the list capacity which 'points at' a particular list entry. The pointer and index are related and we can convert between them with the functions pointerToIndex and indexToPointer. The relation between pointer and index is:

pointer = index mod capacity
index = pointer + cycles*capacity      (when pointer < nextPtr)
      = pointer + (cycles-1)*capacity  (when pointer >= nextPtr)
Copy

The index number can have a maximum value of 2^53. When the index number exceeds this maximum, an exception is thrown by methods that calculate the current index number. Because index numbers are visible outside of this class we cannot just reset the index number.

This 2^53 maximum value should be enough capacity for most uses of CircularList. If you add 1000 points per second, it would take 37 million years to run out of capacity.

It might be possible to add a method that the caller can use to reset the index numbers to start at or near zero again, preserving the data in the CircularList and changing the index number associated with each value. Or the caller can simply make a new CircularList when catching the exception.

Example Scenario

We write new entries into the arrays memX and memY until they fill. Then we wrap around and start writing to the beginning again.

nextPtr always points to the next location to write to.
If size > capacity, then we have entries at 0,1,2,...,size-1
If size = capacity, then the order of entries is:
    nextPtr, nextPtr+1, ..., capacity-1, 0, 1, 2, ..., nextPtr-1

Example: Suppose capacity = 10. The list will fill in as shown below.
The numbers are the index number returned by getIndex().
The caret ^ indicates nextPtr -- the next slot to be written to.

                                cycles
.  .  .  .  .  .  .  .  .  .      0
^
0  .  .  .  .  .  .  .  .  .      0
   ^
0  1  .  .  .  .  .  .  .  .      0
      ^
(write of 2 thru 7 omitted)
0  1  2  3  4  5  6  7  8  .      0
                           ^
0  1  2  3  4  5  6  7  8  9      1
^
10 1  2  3  4  5  6  7  8  9      1
   ^
10 11 2  3  4  5  6  7  8  9      1
      ^
(write of 12 thru 16 omitted)
10 11 12 13 14 15 16 17 8  9      1
                        ^
10 11 12 13 14 15 16 17 18 9      1
                           ^
10 11 12 13 14 15 16 17 18 19     2
^
20 11 12 13 14 15 16 17 18 19     2
   ^
20 21 12 13 14 15 16 17 18 19     2
      ^
Copy