Skip to content

Instantly share code, notes, and snippets.

@weimzh
Last active February 21, 2024 07:23
Show Gist options
  • Save weimzh/d972c188a42f66816559c427881639e0 to your computer and use it in GitHub Desktop.
Save weimzh/d972c188a42f66816559c427881639e0 to your computer and use it in GitHub Desktop.
javascript integer set implemented with bitmap
// Copyright (c) 2021, Wei Mingzhi <whistler_wmz@users.sf.net>.
// SPDX-License-Identifier: BSD-2-Clause
const IntSet = function () {
this.data = [];
this.size = 0;
};
IntSet.prototype.add = function (num) {
const index = num >> 5;
const pos = num & 31;
if (this.data[index] === undefined) {
this.data[index] = 0;
}
if (!(this.data[index] & (1 << pos))) {
this.data[index] |= 1 << pos;
++this.size;
}
};
IntSet.prototype.delete = function (num) {
const index = num >> 5;
const pos = num & 31;
if (this.data[index] !== undefined && (this.data[index] & (1 << pos))) {
this.data[index] &= ~(1 << pos);
--this.size;
}
};
IntSet.prototype.has = function (num) {
const index = num >> 5;
const pos = num & 31;
return !!(this.data[index] && (this.data[index] & (1 << pos)));
};
IntSet.prototype.clear = function () {
this.data = [];
this.size = 0;
};
IntSet.prototype.fill = function (size) {
this.size = size;
this.data = Array((size >> 5) + 1).fill(-1);
for (var i = 31; i > (size & 31); --i) {
this.data[size >> 5] &= ~(1 << i);
}
};
IntSet.prototype.forEach = function (cb) {
this.data.forEach(function (d, idx) {
for (var i = 0; i < 32; ++i) {
if (d & (1 << i)) {
cb(idx << 5 | i);
}
}
});
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment