Skip to content

Instantly share code, notes, and snippets.

@jdfm
Created October 18, 2016 03:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jdfm/76369fbff63b966ef60b7ba49e6bf865 to your computer and use it in GitHub Desktop.
Save jdfm/76369fbff63b966ef60b7ba49e6bf865 to your computer and use it in GitHub Desktop.
iterative implementation of array flattening in javascript
var flatten_v1 = function(array){
var indices = [array.length - 1];
var arrays = [array];
var output = [];
while(indices.length){
if(indices[0] === -1){
indices.shift();
arrays.shift();
} else if(arrays[0][indices[0]] instanceof Array){
indices[0]--;
arrays.unshift(arrays[0][indices[0] + 1]);
indices.unshift(arrays[1][indices[0] + 1].length - 1);
} else {
output.unshift(arrays[0][indices[0]]);
indices[0]--;
}
}
return output;
}
var flatten_v2 = function(array){
var indices = [];
var arrays = [];
var currentArray = array;
var currentIndex = currentArray.length - 1;
var output = [];
while(currentIndex !== -1 || indices.length > 0){
if(currentIndex === -1){
currentIndex = indices.shift();
currentArray = arrays.shift();
} else if(currentArray[currentIndex] instanceof Array){
arrays.unshift(currentArray);
currentArray = currentArray[currentIndex];
indices.unshift(currentIndex - 1);
currentIndex = currentArray.length - 1;
} else {
output.unshift(currentArray[currentIndex]);
currentIndex--;
}
}
return output;
};
var flatten_v3 = function(array){
var currentArray = array;
var currentIndex = 0;
// these are the indices of the unflattened arrays,
// indices[n] = index state for unflattened array in output[n]
var indices = [];
// output will have the unflattened arrays at the beginning, everything
// afterwards is a result of the flattening process
var output = [];
while(currentIndex !== currentArray.length || indices.length > 0){
if(currentIndex === currentArray.length){
currentIndex = indices.shift();
currentArray = output.shift();
} else if(currentArray[currentIndex] instanceof Array){
output.unshift(currentArray);
currentArray = currentArray[currentIndex];
indices.unshift(currentIndex + 1);
currentIndex = 0;
} else {
output.push(currentArray[currentIndex]);
currentIndex++;
}
}
return output;
};
console.log(flatten_v1([ 1, 2, [ 3, 4, [ 5, 6 ], 7 ], 8, 9, [ 10, 11, [ 12, [ [ 13 ] ]]]]));
console.log(flatten_v2([ 1, 2, [ 3, 4, [ 5, 6 ], 7 ], 8, 9, [ 10, 11, [ 12, [ [ 13 ] ]]]]));
console.log(flatten_v3([ 1, 2, [ 3, 4, [ 5, 6 ], 7 ], 8, 9, [ 10, 11, [ 12, [ [ 13 ] ]]]]));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment