Last active
January 22, 2025 13:42
-
-
Save binarymax/ab3e917c170ca95268e5 to your computer and use it in GitHub Desktop.
Javascript bitmap data structure
This file contains hidden or 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
//------------------------------------------ | |
//Compact bitmap datastructure | |
//Memory efficient array of bool flags | |
var Bitmap = function(size){ | |
this._cols = 8; | |
this._shift = 3; | |
this._rows = (size>>this._shift)+1; | |
this._buf = new ArrayBuffer(this._rows); | |
this._bin = new Uint8Array(this._buf); | |
}; | |
//Gets the bool at offset | |
Bitmap.prototype.get = function(off){ | |
var row = off>>this._shift; | |
var col = off%this._cols; | |
var bit = 1<<col; | |
return (this._bin[row]&bit)>0; | |
}; | |
//Sets a bit at offset to bool | |
Bitmap.prototype.set = function(off,bool){ | |
var row = off>>this._shift; | |
var col = off%this._cols; | |
var bit = 1<<col; | |
if (bool) { | |
this._bin[row] |= bit; | |
} else { | |
bit = 255 ^ bit; | |
this._bin[row] &= bit; | |
} | |
}; | |
//Flip a single bit at offset | |
Bitmap.prototype.flip = function(off){ | |
var row = Math.floor(off/this._cols); | |
var col = off%this._cols; | |
var bit = 1<<col; | |
this._bin[row] ^= bit; | |
}; | |
//Reset to all 1's | |
Bitmap.prototype.fill = function() { | |
for(var i=0;i<this._rows;i++) { | |
this._bin[i] = 255; | |
} | |
}; | |
//Reset to all 0's | |
Bitmap.prototype.clear = function() { | |
for(var i=0;i<this._rows;i++) { | |
this._bin[i] = 0; | |
} | |
}; |
This file contains hidden or 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
//Example - gets a list of Primes using the Sieve of Eratosthenes | |
//Returns a function to check if a number is prime or not | |
var getSieveOfEratosthenes = function(size) { | |
var bits = new Bitmap(size); | |
bits.fill(); | |
bits.set(0,0); | |
var lim = Math.ceil(Math.sqrt(size)); | |
for(var i=2;i<=lim;i++) { | |
if(bits.get(i)){ | |
for(var j=i*i;j<=size;j+=i) { | |
bits.set(j,0); | |
} | |
} | |
}; | |
return function(n){ return bits.get(n); }; | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment