Make FastBitSet iterable

[ebrensi]

This pull request adds a Symbol.iterator property to FastBitSet, which makes the sets iterable. That means we can do things like

const bs = new BitSet
bs.add(1)
bs.add(2)
bs.add(3)

// Outputs each element of bs (up to max) to the console
const max = 2;
for (const x of bs) {
  console.log(x);
  if (x > max) {
    break;
  }
}
// outputs 1 and 2, but not 3

The above differs from forEach in two major ways.

• we can break out of a for...of loop
• the scope inside the for loop is intuitive

Another thing that cannot be done with a forEach loop is create other iterators

function* gen( func) {
  for (const x of bs) {
    yield func(x)
  }  
}

const squaresGen = gen(x => x**2)

squaresGen.next().value  // 1
squaresGen.next().value  // 4
squaresGen.next().value  // 9 

We can also take advantage of spread operations like

func(...bs)  // executes func(1,2,3)

[lemire]

This looks great. Would you throw a test in https://github.com/lemire/FastBitSet.js/blob/master/unit/basictests.js ?

If you won't or can't, I'll still merge, but I will then add additional tests before releasing.

[ebrensi]

ok. I hope this isn't too much but I added another operation in the form of change, new_change, and change_size methods. These concern the change (XOR) between two sets. Often during some kind of progression we want to know what elements changed from one moment to the next. Say we have a set s1 = {1,2,4} and then later we have a set s2 = {2,4,5}. Then the elements that changed were {1,5} (1 disappeared and 5 appeared).

I have been using this in a geo-visualization that I am developing. A recorded activity track is a sequence of segments in GPS coordinates. I use a BitSet to indicate which segments are currently in view on the screen. As a user pans and zooms around on the map, I update which segments are in view. change allows me to quickly determine which segments are no longer visible and which ones became visible since the last draw. It needs to be fast because there can be a lot of tracks/segments to keep track of.

I will make tests for what I added, but give me a few days to figure out your way of doing it. Also, for my application the BitSets always have the same number of words but I will need to fix it for two sets of different lengths.

oh, one more thing...my text editor runs Prettier with default settings whenever I save the file, and I forgot to disable it, so you will notice a lot of little formatting changes that I did not make intentionally.

Great library, by the way!

[lemire]

I haver reviewed your changes and it looks good. Waiting for the tests!

[ebrensi]

ok, tests for Symbol.iterator property, change, new_change, and change_size methods written and passed.

You may notice I left this line in as a comment: https://github.com/ebrensi/FastBitSet.js/blob/924f577c05ff21a400f6290a39c9d72ef05bf0c3/FastBitSet.js#L362

It is a one-line equivalent to https://github.com/ebrensi/FastBitSet.js/blob/924f577c05ff21a400f6290a39c9d72ef05bf0c3/FastBitSet.js#L363-L366

that should be faster, and was faster sometimes but not enough for me to be sure about it.

[lemire]

Great stuff! Merging.