Skip to content

Instantly share code, notes, and snippets.

@NPatch
Last active September 1, 2016 20:30
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save NPatch/264b4f5fef6a8f8432082019e85285e4 to your computer and use it in GitHub Desktop.
Save NPatch/264b4f5fef6a8f8432082019e85285e4 to your computer and use it in GitHub Desktop.
TwoWay Circular Index Traversal in Buffers without IF statements
Lets say we have a one dimensional List with objects/primitives/whatever and inside that one dimensional List
,there are several non fixed length one dimensional Lists.
Say we know the starting index and length of each of the sublists and we want to have circular traversal with wraparound
using the same index for all lists and whenever we want, we change the sublist, we can still traverse without ifs and circular.
Finally, we also want to be able to traverse both forwards and backwards.
An example:
SuperList(0,16) => where first param is start_index and second param is length
SubListA(0,6)
SubListB(6,10)
//Sublist Starting Index
SSI = 6
//Sublist Length
SL = 10
In this setting , you can understand we are trying to traverse the sublist that starts with index 6 and goes on till 15,
10 elements long. We'd like to traverse forward and when at 15 , wrap around to 6. Also we'd like to traverse backwards and
when at 6 , wrap around backwards to 15.
int previous_index = ((current_index - SSI + SL - 1) % SL) + SSI
int next_index = ((current_index - SSI + 1) % SL) + SSI
To test the above, if current_index = 6:
previous_index = ((6 - 6 + 10 - 1) % 10) + 6 = (9 % 10) + 6 = 9 + 6 = 15 (Success)
next_index = ((6 - 6 + 1) % 10) + 6 = (1 % 10) + 6 = 1 + 6 = 7 (Success)
And if current_index = 15:
previous_index = ((15 - 6 + 10 - 1) % 10) + 6 = (18 % 10) + 6 = 8 + 6 = 14 (Success)
next_index = ((15 - 6 + 1) % 10) + 6 = (0 % 10) + 6 = 0 + 6 = 6 (Success)
In order to change the sublist, we simply change SSI and SL and then move the cur_index = SSI.
In case we wanted to use the SuperList as a whole:
SSI = 0
SL = 16
if current_index = 0:
previous_index = ((0 - 0 + 16 - 1) % 16) + 0 = (15 % 16) = 15 (Success)
next_index = ((0 - 0 + 1) % 16) + 0 = (1 % 16) = 1 (Success)
And if current_index = 15:
previous_index = ((15 - 0 + 16 - 1) % 16) + 0 = (30 % 16) = 14 (Success)
next_index = ((15 - 0 + 1) % 16) + 0 = (16 % 16) = 0 (Success)
Will also work even if we change the list sizes, as long as we keep the start_index and length updated.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment