dcsimg
A Flash Developer Resource Site

Page 1 of 2 12 LastLast
Results 1 to 20 of 22

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

Hybrid View

  1. #1
    Senior Member
    Join Date
    Jan 2006
    Posts
    133

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

    I have an indexed array full of strings.

    PHP Code:
    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:

    PHP Code:
    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:
    PHP Code:
    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.
    PHP Code:
    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:
    PHP Code:
    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...
    PHP Code:
    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!

  2. #2
    ___________________
    Join Date
    May 2004
    Posts
    3,174
    PHP Code:
    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)); 

  3. #3
    Senior Member
    Join Date
    Jan 2006
    Posts
    133
    well, yeah... but like I said, I'm trying to avoid using a conditional.

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

  4. #4
    ___________________
    Join Date
    May 2004
    Posts
    3,174
    missed the thing about the conditional...

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

  5. #5
    5+5=55 Schfifty Five's Avatar
    Join Date
    Jun 2006
    Posts
    698
    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):

    PHP Code:
    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"
    10;
    trace(my_array[((i*(i-L-(i%L))/Math.abs(i)+i+L+(i%L))>>1)%L]); // traces "cruel"
    = -1;
    trace(my_array[((i*(i-L-(i%L))/Math.abs(i)+i+L+(i%L))>>1)%L]); // traces "noticed"
    = -7;
    trace(my_array[((i*(i-L-(i%L))/Math.abs(i)+i+L+(i%L))>>1)%L]); // traces "hello"
    = -10;
    trace(my_array[((i*(i-L-(i%L))/Math.abs(i)+i+L+(i%L))>>1)%L]); // traces "world" 
    Last edited by Schfifty Five; 01-14-2010 at 10:30 PM.

  6. #6
    ___________________
    Join Date
    May 2004
    Posts
    3,174
    maybe ugly but i'm impressed you got it figured out

  7. #7
    Ө_ө sleepy mod
    Join Date
    Mar 2003
    Location
    Oregon, USA
    Posts
    2,441
    What's wrong with conditionals?

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

    PHP Code:
    %= my_array.length;
    while(
    0i+= my_array.length;
    return(
    my_array[i]); 
    Please use [php] or [code] tags, and mark your threads resolved 8)

  8. #8
    Senior Member
    Join Date
    Jan 2006
    Posts
    133

    Arrow

    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:

    PHP Code:
    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:

    PHP Code:
    // 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:

    PHP Code:
    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 

  9. #9
    ___________________
    Join Date
    May 2004
    Posts
    3,174
    Quote Originally Posted by badaboom55 View Post
    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:

    PHP Code:
    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

  10. #10
    newb of many sorts Ralgoth's Avatar
    Join Date
    Apr 2002
    Posts
    466
    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...

    Code:
    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.
    Last edited by Ralgoth; 01-17-2010 at 10:59 PM.
    Search first, asked questions later.

  11. #11
    Senior Member joshstrike's Avatar
    Join Date
    Jan 2001
    Location
    Alhama de Granada, España
    Posts
    1,131
    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.

  12. #12
    newb of many sorts Ralgoth's Avatar
    Join Date
    Apr 2002
    Posts
    466
    better throw an absolute in there... L+=Math.abs(L*100000);
    Search first, asked questions later.

  13. #13
    Senior Member joshstrike's Avatar
    Join Date
    Jan 2001
    Location
    Alhama de Granada, España
    Posts
    1,131
    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

  14. #14
    newb of many sorts Ralgoth's Avatar
    Join Date
    Apr 2002
    Posts
    466
    maybe I'm reading it wrong... but this is what the whiskey thought you were doing...

    PHP Code:
    var i:int = -123;

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

    %= 5// 2 
    without the abs, the final output would be -3
    Search first, asked questions later.

  15. #15
    Senior Member joshstrike's Avatar
    Join Date
    Jan 2001
    Location
    Alhama de Granada, España
    Posts
    1,131
    Quote Originally Posted by Ralgoth View Post
    maybe I'm reading it wrong... but this is what the whiskey thought you were doing...

    PHP Code:
    var i:int = -123;

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

    %= 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:
    Code:
    var i:int = -123;
    var L:int = array.length;
    i+=L*100000;
    var desiredIndex:int = i%L;

  16. #16
    Ө_ө sleepy mod
    Join Date
    Mar 2003
    Location
    Oregon, USA
    Posts
    2,441
    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.
    Please use [php] or [code] tags, and mark your threads resolved 8)

  17. #17
    newb of many sorts Ralgoth's Avatar
    Join Date
    Apr 2002
    Posts
    466
    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.
    Search first, asked questions later.

  18. #18
    ___________________
    Join Date
    May 2004
    Posts
    3,174
    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:
    PHP Code:
    function cycle(array:Array,position:int):*{
      var 
    len:int = array.length;
      if(
    position 0position len + -position;
      return array[
    position%len];


  19. #19
    newb of many sorts Ralgoth's Avatar
    Join Date
    Apr 2002
    Posts
    466
    I just tried both cycle function... they don't match up with the other methods supplied...

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

    function 
    cycle2(len:uint,position:int):uint
    {
        if(
    position 0position 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 0position+= 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.
    Last edited by Ralgoth; 01-18-2010 at 08:13 AM. Reason: added Schfifty's method to the mix
    Search first, asked questions later.

  20. #20
    ___________________
    Join Date
    May 2004
    Posts
    3,174
    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):
    PHP Code:
    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.

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center