Skip to main content

One post tagged with "generators"

View All Tags

· 2 min read
Peter Johnson

Javascript Generators are a memory-efficent way of iterating over arbitrary data.

For instance you can store integers as deltas and retrieve values & offsets with an iterator:

function* deltaIterator (deltas) {
  let [v, o] = [0, 0]
  for (const d of deltas) {
    yield [v += d, o++]
  }
}
for (const [v, o] of deltaIterator([1, 3, 12, 2, 72])) {
  console.log(o, v)
}

0 1
1 4
2 16
3 18
4 90

Set Operations​

I wasn't able to find an example online of set operations (intersection, union) using generators so I'm posting an example below:

Intersection​

The intersection generator takes two iterators and yields only values which are members of both sets:

function *intersection (A, B) {
  let a = A.next()
  let b = B.next()
  while (!a.done && !b.done) {
    if (a.value[0] < b.value[0]) { a = A.next(); continue }
    if (a.value[0] > b.value[0]) { b = B.next(); continue }
    yield a.value[0]
    a = A.next()
  }
}
const A = deltaIterator([1, 3, 12, 2, 72])
const B = deltaIterator([1, 12, 2, 72, 3])

for (const v of intersection(A, B)) {
  console.log(v)
}

1
90

Union​

The union generator takes two iterators and yields unique values which are members of either set:

function *union (A, B) {
  let a = A.next()
  let b = B.next()
  let v = 0
  while (!a.done || !b.done) {
    if (!a.done && a.value[0] <= v) { a = A.next(); continue }
    if (!b.done && b.value[0] <= v) { b = B.next(); continue }
    yield v = Math.min(
      a.value ? a.value[0] : Infinity,
      b.value ? b.value[0] : Infinity
    )
  }
}
const A = deltaIterator([1, 3, 12, 2, 72])
const B = deltaIterator([1, 12, 2, 72, 3, 1, 1, 1])

for (const v of union(A, B)) {
  console.log(v)
}

1
4
13
15
16
18
87
90
91
92
93