Last active
September 1, 2016 20:30
-
-
Save NPatch/264b4f5fef6a8f8432082019e85285e4 to your computer and use it in GitHub Desktop.
TwoWay Circular Index Traversal in Buffers without IF statements
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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