Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Nested iterator in javascript
/*
Problem: Write a class that implements the following iterator interface:
bool hasNext()
int next()
The iterator is used to sequentially iterate over a collection. Given an implementation of this iterator MyIterator, its usage can be summarized by the following snippet:
input = [1,2,3]
MyIterator it = new MyIterator(input)
while (it.hasNext()) {
println it.next()
}
// output:
// 1
// 2
// 3
The iterator must also handle arbitrarily nested inputs. For example:
input = [1, [2, 3], 4]
// output:
// 1
// 2
// 3
// 4
In the above example, the top-level list has 3 elements, with the second element being a nested list of integers. It can be said that iterator is doing a “lazy flattening” of input.
Restrictions:
1. Assume that the input is large enough that you cannot pre-flatten the entire input as a pre-processing step.
2. hasNext() is idempotent - it doesn't change the state of the iterator, no matter how many times it is called.
3. Two iterators initiated with the same input have no effect on each other.
Feel free to ask questions and talk through your thought process as you go.
*/
class NestedIterator {
constructor(input) {
if (!Array.isArray(input)) {
throw new Error('require input to be of type Array, got ' + (typeof input));
}
this.it = this.nestedIterator(input);
this.nextItem = this.it.next();
}
hasNext() {
return !this.nextItem.done;
}
next() {
const val = this.nextItem.value;
this.nextItem = this.it.next();
return val;
}
*nestedIterator(arr) {
for (let i = 0, len = arr.length; i < len; ++i) {
if (Array.isArray(arr[i])) {
for(const val of this.nestedIterator(arr[i])) {
yield val;
}
} else {
yield arr[i];
}
}
}
}
// Test invalid input
try {
new NestedIterator("blah");
} catch (e) {
console.error(e.message);
}
// Tested nested iterator
const input = [1, [2, 3], 4, [[[5], 6], 7], 8, [[[9]]]]
const it = new NestedIterator(input);
while (it.hasNext()) {
console.log(it.next());
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.