CODEWITHSUNDEEP
javascriptarraysmodulo
Carlo
Carlo

Reputation: 4148

Finding the middle index between any two indexes in a circular array

I have an array and three indexes:

var arr = ['a', 'b', 'c', 'd'];
var f = 0; // first element
var l = arr.length - 1; // last element
var c = 0; // current element

I'm trying to write a function that makes the index c to cycle through the array. The requirement is for it to never reach the index l. So, whenever c reaches a certain value, f and l need to be increased as well.

A reasonable value to work as a limit for c I thought would be the middle point between f and l. The function I wrote is this:

var mod = function(x, m) {
    var r = x%m;
    return r<0 ? r+m : r;
}

while (true) {
    console.log('f', f, 'l', l, 'c', c);
    if (c == l) {
       console.log('error');
    }

    c = mod(c + 1, arr.length);

   if (c > mod(l - f, arr.length) / 2) {
      f = mod(f + 1, arr.length);
      l = mod(l + 1, arr.length);
   }
}

It doesn't work, clearly. Is there a nice simple formula to with the modulo operator to get what I want or the approach is totally wrong?

Here's a fiddle to try it: https://jsfiddle.net/wku37h9e/2/

Edit: Explaining the purpose of this would be a bit long. Let's just say that in the array are stored the positions of external elements which I have to constantly move around. When the c is close to the l, I advance all the indexes. Graphically would be like this:

1. [f|c] [   ] [   ] [ l ]
2. [ f ] [ c ] [   ] [ l ]
3. [ l ] [ f ] [ c ] [   ] // here I start moving things around
4. [   ] [ l ] [ f ] [ c ]
5. [ c ] [   ] [ l ] [ f ]
6. [ f ] [ c ] [   ] [ l ]

And so on. With more elements in the array there would be more distance between the indexes.

I also use a different than normal version of mod to take in account negative numbers.

I hope it's a bit clearer now

Upvotes: 0

Views: 1775

Answers (3)

Nina Scholz
Nina Scholz

Reputation: 386568

I calculate only l with the half of the array length plus c. f is then the next index. All numbers are positve.

                            c   f   l
1. [ c ] [   ] [ l ] [ f ]  0   3   2  l = length / 2 + c, f = l + 1  both mod length
2. [ f ] [ c ] [   ] [ l ]  1   0   3
3. [ l ] [ f ] [ c ] [   ]  2   1   0
4. [   ] [ l ] [ f ] [ c ]  3   2   1
5. [ c ] [   ] [ l ] [ f ]  0   3   2
6. [ f ] [ c ] [   ] [ l ]  1   0   3


var arr = ['a', 'b', 'c', 'd'],
        c, f, l;

for (c = 0; c < arr.length; c++) {
    l = (arr.length / 2 + c) % arr.length;
    f = (l + 1) % arr.length;
    document.write('c:' + c + ' f: ' + f + ' l: ' + l + '<br>');
}

Upvotes: 0

Paul S.
Paul S.

Reputation: 66334

A reasonable value to work as a limit for c I thought would be the middle point between f and l

Finding the mean average between two values, low and high, in mod len

function midPoint(low, high, len) {
    var mid;
    low %= len;
    high %= len;
    while (low < 0) low += len; // these two lines are the
    while (high < low) high += len; // most important for direction
    mid = (low + high) / 2; // mean average
    mid %= len; // convert back to our mod
    return mid;
}

So have

// works as expected beyond range of mod
midPoint( 1, -1, 9); // middle of 1..8 (mod 9) = 4.5
midPoint(-7,  5, 9); // middle of 2..5 (mod 9) = 3.5
midPoint(-6, 12, 9); // middle of 3..3 (mod 9) = 3
// and
midPoint( 2,  5, 9); // middle of 2..5 (mod 9) = 3.5
midPoint( 5,  2, 9); // middle of 5..2 (mod 9) = 8 (we went the other way around)

You don't actually have to force the mod until after the whole calculation, so if you really wanted you could do the following, but you lose direction around the loop

function midPoint(A, B, len) {
    var mid;
    mid = (A + B) / 2; // mean average
    mid %= len; // convert back to our mod
    while (mid < 0) mid += len; // always positive
    return mid;
}

Notice here, however

midPoint(-6, 3, 9); // middle of 3..3 (mod 9) = 7.5
midPoint( 3, 3 + 0 * 9, 9); // middle of 3..3 (mod 9) = 3
midPoint( 3, 3 + 1 * 9, 9); // middle of 3..3 (mod 9) = 7.5
midPoint( 3, 3 + 2 * 9, 9); // middle of 3..3 (mod 9) = 3

i.e. the mid point of 3..3 (mod 9) is both 3 and 7.5, which is true, but which way around we've gone now depends on k (where B - A = k * len + a)

Upvotes: 1

Chris O&#39;Kelly
Chris O&#39;Kelly

Reputation: 1893

I'm not sure I understand - when I define the mod function that all works:

function test() {
    var i=0;
    var arr = ['a', 'b', 'c', 'd'];
    var f = 0; // first element
    var l = arr.length - 1; // last element
    var c = 0; // current element
    while (true && i < 1000) {
        ++i;
        console.log('f', f, 'l', l, 'c', c);
        if (c == l) {
           console.log('error');
           break;
        }

        c = mod(c + 1, arr.length);

        if (c > mod(l - f, arr.length) / 2) {
           f = mod(f + 1, arr.length);
           l = mod(l + 1, arr.length);
        }
    }
}
function mod(a,b) { return a % b;}

Seems to loop c through the possible values, and c is never the same as the (continuously recalculated) value of l... but I don't understand the arithmetic you're trying to apply to f and l there

Upvotes: 0

Related Questions