Any language that supports overriding the index operation should support this. You should be able to do this in C# with a struct with a backing array, for instance. If you're going to do this, use the word "Circular" in it, and I would also insist that if a has 4 elements, then a[0] == a[4] == a[8]. In other words, you always just take the (positive) index modulo the size of the area. Then a[-1] is the same as a[N-1] for an array of size N. This could be useful in a lot of contexts, but should be made explicit.
You'd have to care about the difference between indexing with a literal and indexing with variables of different types/widths, and how indexing with a variable interacts with the size of the area.
For instance if you have an int array that contains the numbers 1-250 and you index with a uint8 variable i,
for (uint8 i = 247; i++;) {
// print circ_arr[i]
}
for the values of i near the overflow points of the circular array and of the uint8 it gets weird:
Right, the calling code needs to handle its own integer overflows, of course. And if your circular array has a size other than a power of 2 you can get only a partial enumeration in the cycle that includes overflow. Sure. But are you really indexing an array of unknown size with a uint8? It's really impossible that there might be more than 255 things you ever care about? No. Everyone who is using a uint8 to index arrays is either doing something extremely low-level and fiddly where abstractions like this simply don't apply, or they're idiots who are doing cargo-cult shotgun "optimization" because they don't know how to write code that works.
If you're indexing with a [u]int32 you need to worry about this once every 4 billion increments, and if an incomplete cycle is a show-stopper for you, you can compute a safe modulo yourself based on the size(s) of your circular array(s), but more likely you just need something else. But really, you don't care if your cache hiccups a little once every 4 billion caches.
You make a good point, of course, I'm just allergic to people poking holes in back-of-the-napkin explanations of things with the trite "but integers can overflow!" It's one of those most common well actuallys written on this site. Of course integers can overflow. They almost never do though, do they? And if they do, a test fails and you add a single line somewhere to fix it.
I really think the vast majority of programmers are too often thinking about bits when they should be thinking about math.
Um, maybe, but then his example is sixteen million times worse than reality! If I argued against some technology by showing how bad it would be if it were sixteen million times worse, that's just not a very good argument, is it?
In a language where arrays are fixed-size, I think the proper solution is to have arrays not indexed by integers, but by a custom modular type that depends on the array with values in [0,n) that allows literals in the range [-n, n-1], with literal ‘-1’ being a different way to write ‘n-1’, etc.
You’d need a way to get that type, for example as
float a[10,20] // two-dimensional array of floats
typeof(a.dims(0)) i = 0 // modular type with values in [0,9]
typeof(a.dims(1)) j = 0 // modular type with values in [0,19]
or, slightly neater:
auto i = a.indextype(0)
auto j = a.indextype(1)
Ugly syntax, but in a modern language, most code would probably do something like
for (i,j,value) in a
where the types are inferred.
Having those modular types means the compiler would do the arithmetic correct for the array, while the negative literals allow programmers to specify “last” and “next to last” correctly.
> you always just take the (positive) index modulo the size of the area.
That's something I'd like in a bunch of languages - a real modulo operator that always returns between 0 and n, even for negative inputs, rather than a remainder operator that's advertised as a modulo operator. Grrrrr!!!!!
It's a little verbose and can probably be reduced, but "((x % m) + m) % m" always works. Although it's probably not better than a check if x < 0 since branch prediction will get that right almost always.
I do think it's quite odd and frustrating that modulo can return negative numbers and I don't really get the reasoning there, but there's probably a good reason I don't know about.
Ecstasy uses % for modulo, and /% for divrem (division and remainder). So "a = b % c" for calculating the modulo, but "(a, r) = b /% c" to get the divisor and remainder.
It's frequently used in signal processing to the point where it's considered one of the defining features of DSPs. One common case is filtering over a fixed size buffer of samples. If you have circular indexing, you can simply overwrite the earliest sample and increment the base reference to the next element.
I'm not sure I'd want it for every list, but there are certain places it's nice.
First of all, it handles the "get me the 2nd to last element" case automatically, but in a way that doesn't feel like a weird edge case: it's more "mathematically sound", basically. I always want mathematical soundness if possible because it leads to serendipity, the opposite of technical debt. Where technical debt is "dammit, this is going to take so much longer than it should!"; serendipity is "oh wow I can implement this cool new feature just by combining these other two things in a new way, in like 2 lines. This is going to be way faster than I thought." Mathematical soundness / purity leads to serendipity.
Directly, it supports caches very well. You just increment the number of things you've ever cached and that's where your next cached value goes; you don't care when it overwrites an old value.
There are other cases where you just need some variant of a thing, but you don't actually care that much about which variant you get. You might want to vary your wording in auto-generated text, for instance, by rotating synonyms. Or rotating the tiles you use in a 2D game. In this case I'd define an interface where you pass in a "seed" integer and it gives you back some deterministic example; a circular array is the simplest implementation of this interface (but there are others).
You could also do simple load balancing by sending work to Worker[workCount++]. While usually you want to track each workers' existing workload (because the work takes unpredictable time), this simple approach could be sufficient if all your work completes in about the same time.
If you're doing fancy math or science computing, you may be working with finite groups or fields, whose elements you could stick in an N-dimensional circular array (based on the characteristics of the field).
Sonic Pi, the live music coding environment, has a circular list structure type called a 'ring'. This proves curiously helpful for a bunch of musical scenarios.
Like:
- you can put a short chord sequence into a ring, and it now functions as a list of as many repetitions of that chord sequence as you like. You can just loop over it forever (which is kind of the essence of how sonic pi live-loop play works)
- you can put the notes that make up a scale into a ring, and use it to extract specific chords - like, take the 1st, 3rd, 5th, 7th and 9th note - from just a seven note scale.
- you can use rings of booleans to capture drum patterns and rings of notes to capture melodies, and loop them forever
