Infinite sliding windows in Javascript
I needed to code a slideshow that should infinitely repeat items when sliding to the left and right. The slide show would always show n slides at the same time. To me that sounded a lot like a sliding window algorithm, only with an added feature of infinitely repeating.
As I needed to have this in Angular.js, I created a simple Javascript function to achieve this "infinite sliding window" algorithm as I call it.
/**
* Returns a sliding window over data
* with lenth len, starting from cur
* repeating data infinitely to fit the window
*/
function infiniteSlidingWindow(data, cur, len) {
var win = [],
num = data.length,
numVisible = len;
// A negative cur is the same as num - abs(cur)
if (cur < 0) {
cur = num + cur;
}
// Now keep adding items until we have enough
while (win.length < numVisible) {
var first = (win.length?0:Math.abs(cur)%num),
missing = numVisible - win.length,
last = Math.min(first + missing, num);
win = win.concat(data.slice(first, last));
}
return win;
}
I actually used a slight modification as you don't want to have duplicates when using ng-repeat.
/**
* Use this slight modification if you need to avoid duplicate items.
* This keeps the window fixed when there are not enough items to fill it.
*/
function infiniteSlidingWindowNoRepeats(data, cur, len) {
if (data.length < len) {
len = data.length;
cur = 0;
}
return infiniteSlidingWindow(data, cur, len);
}
Here are some tests to throw in your console or Node.js interpreter, showing the expected behavior.
/* Tests */
var data = [0,1,2,3,4,5,6,7,8,9];
var result;
result = infiniteSlidingWindow(data, 0, 3);
console.log([0,1,2].join() == result.join());
result = infiniteSlidingWindow(data, 1, 3);
console.log([1,2,3].join() == result.join());
result = infiniteSlidingWindow(data, -1, 3);
console.log([9,0,1].join() == result.join());
result = infiniteSlidingWindow(data, -11, 5);
console.log([1,2,3,4,5].join() == result.join());
result = infiniteSlidingWindow(data, 2, 10);
console.log([2,3,4,5,6,7,8,9,0,1].join() == result.join());
data = [0,1,2,3];
result = infiniteSlidingWindow(data, 0, 5);
console.log([0,1,2,3,0].join() == result.join());
result = infiniteSlidingWindow(data, 2, 5);
console.log([2,3,0,1,2].join() == result.join());
result = infiniteSlidingWindowNoRepeats(data, 2, 5);
console.log(data.join() == result.join());
Have fun with that!
Written by Paul Grau
Related protips
1 Response
Nice approach!
How would you support a finite sliding window as well?
BTW, i think you got a bug when you check the negative curr, i think it should be:
if (curr < 0) {
curr = num + (curr % num);
}
Have a fresh tip? Share with Coderwall community!
JavaScript on a page runs with the privileges of that origin. One altered library, tag manager, or snippet can read inputs, change what people see, and call your APIs as the user.
Security insights from Cside