Logic Bomb... Retrieving "negative" index, and wrap around an Array?

[badaboom55]

I have an indexed array full of strings.

my_array = new Array("hello", "dear", "goodbye", "cruel", "world", "never", "noticed"); 

I'm generating an integer elsewhere in my code which I want to use to lookup the appropriate index in my_array.
However, the number I'm passing to the [] access operator could be positive or negative, and it could be more or less than my_array.length
For Example:

my_array[lookUpIndex]
my_array[52]
my_array[-2]
my_array[-123] 

So, I need someone to help me with the equation (if possible) that I could use so that if I generate the lookUpIndex out of bounds of the Array, I would be able to "wrap" around the array and get the appropriate element.

For example:

var lookUpIndex:int = 10;
trace(my_array[lookUpIndex]);
// output "cruel", also known as my_array[3] 

The real problem is when you get into negative numbers.

var lookUpIndex:int = -1;
trace(my_array[lookUpIndex]);
// output "noticed", also known as my_array[my_array.length]

var lookUpIndex:int = -7;
trace(my_array[lookUpIndex]);
// output "hello", also known as my_array[0]

var lookUpIndex:int = -10;
trace(my_array[lookUpIndex]);
// output "world", also known as my_array[4] 

I would like 1 equation that could handle both positives and negatives, instead of having to use a conditional.

Basically, I need someone to fill in the equation below:

var lookUpIndex:int = -128;
var i:int = *some equation involving lookUpIndex*
trace(my_array[i]); 

NOTE: Using the modulo (%) operator works fine when dealing with positive numbers...

var lookUpIndex:int = 128;
var i:int = lookUpIndex % my_array.length;
trace(my_array[i]); 

But like I said, I'd like to come up with 1 equation that fits all positive and negative look up number scenarios.

Thanks!

[moagrius]

function cycle(array:Array,position:int):*{
    var len:int = array.length;
    return array[position<0?len-(-position%len):position%len];
}

var my_array:Array = new Array("hello", "dear", "goodbye", "cruel", "world", "never", "noticed");

// passing -2, should give back "never"
trace(cycle(my_array,-2));

// passing -4, should give back "cruel";
trace(cycle(my_array,-4));

// passing 8, should give back "dear"
trace(cycle(my_array,8)); 

[badaboom55]

well, yeah... but like I said, I'm trying to avoid using a conditional.

But, I'm guessing it's not possible.

[moagrius]

missed the thing about the conditional...

probably possible - if you ever find a way, post back - i'd be interested in seeing it...

[Schfifty Five]

Not sure why you don't want to use a conditional, but here's a really ugly method that works (it can probably be simplified some more... I just worked it out right now, there's probably a better way):

var my_array:Array = new Array("hello", "dear", "goodbye", "cruel", "world", "never", "noticed");
var L:int = my_array.length;
var i:int = 0;
trace(my_array[((i*(i-L-(i%L))/Math.abs(i)+i+L+(i%L))>>1)%L]); // traces "hello"
i = 10;
trace(my_array[((i*(i-L-(i%L))/Math.abs(i)+i+L+(i%L))>>1)%L]); // traces "cruel"
i = -1;
trace(my_array[((i*(i-L-(i%L))/Math.abs(i)+i+L+(i%L))>>1)%L]); // traces "noticed"
i = -7;
trace(my_array[((i*(i-L-(i%L))/Math.abs(i)+i+L+(i%L))>>1)%L]); // traces "hello"
i = -10;
trace(my_array[((i*(i-L-(i%L))/Math.abs(i)+i+L+(i%L))>>1)%L]); // traces "world" 

[moagrius]

maybe ugly but i'm impressed you got it figured out

[neznein9]

What's wrong with conditionals?

Additionally - you can use a loop to get everything into the positive:

i %= my_array.length;
while(i < 0) i+= my_array.length;
return(my_array[i]); 

[badaboom55]

I figured it would be some whizz bang with absolute values, I just couldn't get it for the life of me...

The problem with conditionals (only in this specific scenario, obviously) is that it seems like it's a waste of resources to perform an "if" statement... especially IF you don't need to...
If, for example, my conditional tests for a negative value, and I end up passing a bunch of extraneous tests to get to the "else" statement. (And vice versa)
So instead of this:

if(negative){
     // do this
}else{
     // do something slightly different
} 

It just seems to me that it would be faster/smarter/lighter/better/easier/elegant-er to have this:

// do this 

Over simplified, I know, by why test a value with a conditional if you don't have to??

Also, I realize calling an instance of the Math Class object via Math.abs() and the complexity of the resulting equation PROBABLY requires more resources than the simple conditional with 2 simpler equations...

semantics, schmantics =)

I really just thought it would be an interesting exercise, and I just wanted to know if it could be done... I mean there's plenty of times when you deal with both negative and positive numbers similarly, but slightly differently, so I would think it's beneficial to be able to deal with ANY number the same way.

In this specific "wrapping" Array scenario, does anyone think it would be a good feature for AS4.0 to implement a property of a basic array so that if you attempted to access an "out of bounds" index, it would "auto-wrap"?

Something like:

var my_array:Array = new Array("Hello", "Cruel", "World");
my_array.wrappable = true;

trace(my_array[-1]); // output: World
trace(my_array[16]); // output: Cruel 

[Ralgoth]

That would cause more problems. If you use arrays to keep track of objects, especially when using multi-dimensional arrays, you would no longer have the ability to see if an object has been set for a particular cell. Example...

say that I want to get a bitmap from my array that has an index of 16. I would normally retrieve with something like this...

function getBitmap(n:uint):BitmapData
{
   return myArray[n] ||= bitmapLoader(n);
}

var bmp:BitmapData = getBitmap(16);

so the function above would either return the BitmapData that's stored in myArray[n] or load and return a new bitmap. With the index-wrapping feature, that would no longer be the case.

--- edit ---

though, that's not to say that the function itself wouldn't be useful. Just, as a static function either in Math or Array, and not implemented as a default.

[joshstrike]

eh, maybe this is stupidly obvious, but if you know your negative number would never be less than say 100,000 loops around, you could also just add L+=L*100,000 and then use the modulo as usual... as a hack for pure speed, you probably couldn't beat that.

When you're trying to get an arctan based on coordinates, it's kind of generally agreed that conditionals are the most elegant way of getting the quadrant. This seems like a similar problem.

Schfifty five's formula is great, though.

[Ralgoth]

better throw an absolute in there... L+=Math.abs(L*100000);

[joshstrike]

you drinkin the devil's wisky. The absolute screws the rotation. If it's 10 long, then the last index is array[9], so -1 should translate to array[8].

-edit- I'm drinkin the devil's heineken and it told me to say that /edit

[Ralgoth]

maybe I'm reading it wrong... but this is what the whiskey thought you were doing...

var i:int = -123;

i += Math.abs(i*100000); // 12299877

i %= 5; // 2 

without the abs, the final output would be -3

[neznein9]

Calling Math.abs is going to be about an order of magnitude slower than the corresponding inline logic (i > 0) ? i : -1

Id say Moagrius' approach is probably the fastest for your processor but you'd have to be calling this array thousands of times to see any appreciable difference.

[joshstrike]

maybe I'm reading it wrong... but this is what the whiskey thought you were doing...

var i:int = -123;

i += Math.abs(i*100000); // 12299877

i %= 5; // 2 

without the abs, the final output would be -3

naw. that's wasted. Actually, you're right, that's what I wrote. I'm a freakin idiot. Devil hieneken. What a waterslide. What I'm saying is:

var i:int = -123;
var L:int = array.length;
i+=L*100000;
var desiredIndex:int = i%L;

[Ralgoth]

oh yeah, that makes all the more sense... cause mine was definitely faulty the way I wrote it....

Though, if you happen to have an array with a length 21475 or greater, then myArray.length*100000 will exceed int.MAX_VALUE.

[moagrius]

In this specific "wrapping" Array scenario, does anyone think it would be a good feature for AS4.0 to implement a property of a basic array so that if you attempted to access an "out of bounds" index, it would "auto-wrap"?

Something like:

var my_array:Array = new Array("Hello", "Cruel", "World");
my_array.wrappable = true;

trace(my_array[-1]); // output: World
trace(my_array[16]); // output: Cruel 

I use custom Array-type class that has a "wrappable" method (and current position pointer, next() and prev() methods like VB Enumerators, etc). I'd say that'd be better than redefining the Array class itself, that is used the same way in a lot of different technologies. just IMO

[moagrius]

just for clarification - the function i gave in the first reply was grabbed out of a .js file from around 2005 and quickly typed to resemble AS3. the logic isn't exactly right - i think it should look like:

function cycle(array:Array,position:int):*{
  var len:int = array.length;
  if(position < 0) position = len + -position;
  return array[position%len];
} 

[Ralgoth]

I just tried both cycle function... they don't match up with the other methods supplied...

function cycle1(len:uint,position:int):uint
{
    return position<0?len-(-position%len):position%len;
}

function cycle2(len:uint,position:int):uint
{
    if(position < 0) position = len + -position;
    return position%len;
}

function cycle3(len:uint,position:int):uint
{
    position%=len;
    return position<0?position+len:position;
}

function modheavy(len:uint,position:int):uint
{
    return ((position*(position-len-(position%len))/Math.abs(position)+position+len+(position%len))>>1)%len;
}

function modplus(len:uint,position:int):uint
{
    return (position+len*100000)%len;
}

function modloop(len:uint,position:int):uint
{
    position %= len;
    while(position < 0) position+= len;
    return position;
}

function onlyloop(len:uint,position:int):uint
{
    // this function is here as a control
    // it's obviously the slowest method possible
    while(position<0){
        position += len;
    }
    while(position>=len){
        position -= len;
    }
    return position;
}

var len:uint; // array.length
var ind:int;  // supplied index

len = 12;
ind = -32;
trace(cycle1(len,ind));        // 4
trace(cycle2(len,ind));        // 8
trace(cycle3(len,ind));        // 4
trace(modheavy(len,ind));    // 4
trace(modplus(len,ind));    // 4
trace(modloop(len,ind));    // 4
trace(onlyloop(len,ind));    // 4

len = 8;
ind = -32;
trace(cycle1(len,ind));        // 8
trace(cycle2(len,ind));        // 0
trace(cycle3(len,ind));        // 0
trace(modheavy(len,ind));    // 0
trace(modplus(len,ind));    // 0
trace(modloop(len,ind));    // 0
trace(onlyloop(len,ind));    // 0

len = 8;
ind = 16;
trace(cycle1(len,ind));        // 0
trace(cycle2(len,ind));        // 0
trace(cycle3(len,ind));        // 0
trace(modheavy(len,ind));    // 0
trace(modplus(len,ind));    // 0
trace(modloop(len,ind));    // 0
trace(onlyloop(len,ind));    // 0

len = 10;
ind = -6843223;
trace(cycle1(len,ind));        // 7
trace(cycle2(len,ind));        // 3
trace(cycle3(len,ind));        // 7
trace(modheavy(len,ind));    // 7
trace(modplus(len,ind));    // 4294967293
trace(modloop(len,ind));    // 7
trace(onlyloop(len,ind));    // 7 

cycle3 is pretty much a mix between nenzein9 and moagrius functions. It checks for a negative after the modulo like nenz, and uses an if statement like moag's.

It's probably the best as far as speed and reliability goes.

[moagrius]

ralgoth's right, my method was broken, and i'd agree that his mod is the best approach. a simple speed test shows it's about twice as fast as modheavy (which i'm calling cycle2):

function cycle(array:Array,position:int):*{
    var len:int = array.length;
    position%=len;
    return array[position<0?position+len:position];
}
function cycle2(array:Array,position:int):*{
    var len:int = array.length;
    return array[((position*(position-len-(position%len))/Math.abs(position)+position+len+(position%len))>>1)%len];
}

var arr:Array = [0,1,2,3,4];
var control:uint;

var start:Number = getTimer();
for(var i:int=0;i<500000;i++){
    //control = cycle(arr,1);
    control = cycle2(arr,i);
}
trace(getTimer()-start); 

even though it's twice as fast, it's still only a matter of a fraction of a second (on my machine, approx 155 for cycle, approx 295 for cycle2 - so about 140ms or one-seventh of a second) when running half a million times.