Created
October 18, 2016 03:39
-
-
Save jdfm/76369fbff63b966ef60b7ba49e6bf865 to your computer and use it in GitHub Desktop.
iterative implementation of array flattening in javascript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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