Boolean Array (~ 16 kB minified)

The Ultimate JavaScript Module for Memory-Efficient Boolean Management

"From crafting vivid 🎮 1) gaming graphics and compressing 🎞️ 2) media files, to exploring the geometric intricacies of the 🌐 3) digital realm, these tools are the backbone of modern digital artistry. They drive the 💽 4) data compression that fuels our digital conversations, the 📊 5) data mining that unveils hidden patterns, and the 🔍 6) database management that organizes our digital world. They safeguard our networks with robust 🛡️ 7) cryptographic shields, propel the 📡 8) networking channels that connect us, and simulate complex 🧪 9) scientific realities that enhance our understanding of the universe. Lastly, they hold promise in revolutionizing 🩺 10) healthcare, by optimizing medical image processing, promising a future where technology and medicine converge for the betterment of humanity."

• 📚 Introduction
• 💻 Install
• 📤 Import
  • 🌐 Browser
  • 🖥📦 NodeJS
• 🔢 BitArray
• 🔐 SetFixed
• 🔢 BitArray Documentation
  • 🛠️ Constructor: BitArray(s)
    • Number, BitArray, Uint32Array (data)
  • 🔍 Properties
    • length, idealConstructor, data, dataCopy
  • 🔧 Methods
    • readBit, toggleBit, writeBit1, writeBit0, countOnes, countZeros, getMin, getMax, resize, resizeToMax, clear, charge, invert
• 🔐 SetFixed Documentation
  • 🛠️ Constructor: SetFixed(size)
    • Number, BitArray, SetFixed, Array (indexes), Set
  • 🔍 Properties
    • size, length, indexes, idealConstructor, bitArray, bitArrayCopy, bitArrayData, bitArrayDataCopy
  • 🔧 Methods
    • has, hasnt, add, bulkAdd, bulkAddUnsafe, setFromSetFixed, delete, bulkDelete, optimize, resize, resizeUnsafe, clear, charge, invert
  • 🚀 Turbo methods (3000% times faster)
    • addFromSetFixed, addFromSetFixedUnsafe, differentFromSetFixed, differentFromSetFixedUnsafe, sameFromSetFixed, sameFromSetFixedUnsafe, computeSize
• 📝 Example
• 👤 About me

Introduction

🚀 Optimized Efficiency: Leveraging the power of this module, you can ensure unparalleled memory efficiency, especially in applications requiring operations that most other solutions simply can't match. With other systems, you could easily find yourself using up to ten times more system resources. With our solution, you can kiss those inefficiencies goodbye.

🔍 Real-world Applications:

1. Data Compression: When you're compressing data and need to keep track of repeated patterns, our module excels. Register whether patterns are stored in a table swiftly and efficiently.
2. Drawing Apps: For those seeking rapid pixel selection in drawing applications, this module is your go-to. Process pixel selections at lightning speed!

💾 Memory Footprint:

• A staggering 1/4 million entries take up a mere 31kB in memory. 8 millions entries is 1mB and still faaaaster than mad driver in your "homies' hood" tho. (Laugh 2x)
• Engaging with ten 2D pixel selections of 500x500? That's a featherlight 0.3mB for the entire lot.
• Store up to eight thousand boolean values in just 1kB.

🔐 Precision Limitations:

• Designed for a singular purpose: handling boolean values.
• Functions within a fixed index size limited to positive whole numbers.
• Doesn't try to be everything; it just excels at what it's meant to do.

🛠️ Design Efficiency:

• Methods and properties are memory-efficient, with intentional design ensuring that the module remains within its internal state. Only the properties and methods with public "getters" extend beyond.
• Low-level operations are precisely tuned for the JavaScript engine, ensuring minimal computation force. We've rigged numbers to avoid bulky double storage, streamlining memory usage further.

🖋️ Bottom Line: If you're into data compression or drawing applications, this kind of solution is almost indispensable. With its precise focus and memory efficiency, it's time to elevate your operations to the next level with our module.

Install

npm install @asaitama/boolean-array

Import

Browser

// First load `/dist/browser.min.js` (16 kB)
var BitArrayClass = window.BitArray; // Optional
var SetFixedClass = window.SetFixed; // Optional

// Weight around 31 kB in memory for ~ 1/4 million entries
// All instances use Uint32Arrays. A chunck (4 bytes).
// Chuncks contains 32 bits storing as much "potential boolean" as the number of bits
var mySetFixedInstance = new SetFixed(new BitArray(512*512)); 

NodeJS

// You can also use "@asaitama/boolean-array/dist/index.min.js"
import { BitArray, SetFixed } from "@asaitama/boolean-array";

BitArray

BitArray is a useful data structure that allows you to manipulate an array of bits efficiently. This object is perfect for situations where you need to work with bits directly. For instance, it can be useful in coding problems related to bit manipulation or when dealing with binary data. It provides methods to read, write, clear and set individual bits, as well as other utility functions.

SetFixed

SetFixed is a set data structure implemented using the BitArray object. This is an efficient and compact data structure for storing non-repeated elements. SetFixed provides a variety of methods to manipulate the set such as adding, devaring, checking for membership, and iterating over the set.

BitArray Documentation

The BitArray object provides an efficient bit-level manipulation of a typed array. It offers methods for setting, getting and manipulating individual bits within the array.

Constructor

🛠️ BitArray(s)

The constructor function takes a parameter s, which represents the size of the BitArray. This is used to initialize the internal Uint32Array. The function also initializes the M_OR_ and M_AND_ Uint32Arrays, which are used as masks for setting and clearing bits.

var ba = new BitArray(64);
var ba_copy = new BitArray(ba);

Properties

🛠️ length

This getter function returns the length of the BitArray.

var bitArray = new BitArray(64);
var length = bitArray.length;
console.log(length);

🛠️ data & dataCopy

This getter function returns the data used in the inside of the BitArray. It contains bits within uint32, and the last element of the Uint32Array is the length used

var bitArray = new BitArray(64);
var uint32a = bitArray.data || bitArray.dataCopy;
console.log(uint32a);

🛠️ idealConstructor

This getter function returns the ideal TypedArray constructor of the BitArray based on it's given length.

// All positives bit's indexes can fit within a 1 Byte number
var bitArraySmall = new BitArray(22);
var uint8array = new bitArraySmall.idealConstructor(10);

// All positives bit's indexes can fit within a 2 Byte number
var bitArrayMedium = new BitArray(55555);
var uint16array = new bitArrayMedium.idealConstructor(10);

// Fit within a 4 Byte number (it is used by the class named SetFixed...)
var setFixedBig = new SetFixed(7777777+1); // 8 millions entries is OKAY (1 mB)
    setFixedBig.bulkAdd([1, 22, 333, 4444, 55555, 666666, 7777777]);
    setFixedBig.delete(22);

// Indexes are computed "on the fly" (FAAAAAAST)
var uint32array = setFixedBig.indexes;
console.log(uint32array); // // Uint32Array.of(1, 333, 4444, 55555, 666666, 7777777)    

Methods

🛠️ readBit

This getter function returns a function that reads the bit at index i, returning a boolean indicating whether the bit is set.

var result = ba.readBit(4);

🛠️ toggleBit

This getter function returns a function that reads and toggle (invert the value of) the bit at index i, returning a boolean indicating whether the bit has become positive or negative.

// It returns true if the new value is one, and false if it is now zero
var result = ba.toggleBit(4);

🛠️ writeBit1

This getter function returns a function that sets the bit at index i to 1.

ba.writeBit1(4);

🛠️ writeBit0

This getter function returns a function that sets the bit at index i to 0.

ba.writeBit0(4);

🛠️ countOnes & countZeros

Those getter functions returns either function that return the number of positive or nullish values in it.

ba.countOnes();
ba.countZeros();

🛠️ getMin & getMax

Those getter functions returns either function that return the first or latest bit set to one, if none is in it -1 will be returned.

ba.getMax();
ba.getMin();

🛠️ resize & resizeToMax

Those getter functions returns either function that resize the BitArray to a defined length or the last bits set to one.

ba.resize(128);
ba.resizeToMax();

🛠️ clear

This getter function returns a function that clears all bits in the BitArray.

ba.clear();

🛠️ charge

This getter function returns a function that sets all bits in the BitArray to 1.

ba.charge();

🛠️ invert

This getter function returns a function that sets all bits to the opposed value fast (it uses bits level operations on Uint32).

ba.invert();

SetFixed Documentation

The SetFixed object provides a set data structure that allows efficient addition, devarion, and checks for membership. It offers methods for setting, getting and manipulating individual elements within the set.

Constructor

🛠️ SetFixed(size)

The constructor function takes a parameter size, which represents the size of the SetFixed. This is used to initialize the internal BitArray. If size is an object (presumably an array-like object), then the SetFixed is initialized with those elements.

// The size is fixed but it will be increased if you use `.add(index)`
var setFixedNew = new SetFixed(64);
// Copy the SetFixed very fast (no indexing needed)
var setFixedCopy = new SetFixed(setFixedNew); 
// It has however the need to count the number of positive values when one is giving a BitArray's instance
var setFixedNew1 = new SetFixed(new BitArray(64)); 
// Do not use float, non positive integer, or bigint 
var setFixedNew2 = new SetFixed([69, 777, 0x09, 666, 22, 57, 333]);
// Without making a copy of bitArrayData (which is a Uint32Array) changes are applied to both
var setFixedNew2Mirror = new SetFixed(new BitArray(setFixedNew2.bitArrayData));
var setFixedNew2Copy = new SetFixed(new BitArray(setFixedNew2.bitArrayDataCopy));

Properties

🛠️ size

This getter function returns the size of the SetFixed set, which is the number of elements in the set.

var setFixed = new SetFixed(64);
    setFixed.add(4);
console.log(setFixed.size); // 1

🛠️ length

This getter function returns the length of the BitArray used internally.

var setFixed = new SetFixed(64);
console.log(setFixed.length); // 64

🛠️ indexes

This getter function returns an array of the indices of the bits that are set within the BitArray.

var setFixed = new SetFixed(64);
console.log(setFixed.indexes); // [] (Uint8Array or Uint16Array or even Uint32Array)

Static Methods

🛠️ import

This static function returns a new SetFixed instance from exported data.

var setFixed = new SetFixed(64);
var copy = true; // Do copy the data
var data = setFixed.export(copy) // Either BitArrayData or BitArrayDataCopy
var setFixed2 = SetFixed.import(data);

Methods

🛠️ export

This getter function returns a function that return the data you need to import/export it.

var setFixed = new SetFixed(64);
var copy = true; // Do copy the data
var data = setFixed.export(copy) // Either BitArrayData or BitArrayDataCopy
var setFixed2 = SetFixed.import(data);

🛠️ has & hasnt

This getter function returns a function that checks if a given index i is set within the BitArray.

var setFixed = new SetFixed(64);
console.log(setFixed.has(4)); // true or false
console.log(setFixed.hasnt(4)); // true or false

🛠️ add & bulkAdd & bulkAddUnsafe& setFromSetFixed

This getter function returns a function that adds a given index i to the SetFixed. If the index given is beyond the capacity of the instance, it will be resized correctly with a margin. Don't worry about resizing or memory consumption, it is far more efficient than a traditional new Set() instance object if you deal with indexes below 1/4 million (indexes from 0 to 250000 will represent only a few 31kB in memory)

However, be careful, if you create a setFixed with a length of 70000 (which is alright) but then add the index 999999, the new length of the setFixed instance will be the max index set to one.

It is as much as 2-3x faster and 4-6x lighter for the JS Engine when used for managing pixel art selection state on canvas of 512x512 pixels than "new Set()" but is limited to entire integer within a range!!!

var setFixed = new SetFixed(64);
var setFixedCopy = new SetFixed(setFixed);
    setFixed.add(100); // It will extend the BitArray used if it is too small (only)
    setFixed.addUnsafe(57); // It will only work if it doesn't overflow it's capacity
    setFixed.bulkAdd([1, 2, 3, 4, 5]);
    setFixedCopy.clearAndBulkAdd(setFixed.indexes);
    setFixed.clearAndBulkAddUnsafe(setFixedCopy.indexes); // Works like if it were replacing it
    setFixed.setFromSetFixed(setFixedCopy); // Replace it (FAST)

🛠️ delete & bulkDelete

This getter function returns a function that deletes a given index i from the SetFixed.

var setFixed = new SetFixed(64);
    setFixed.delete(4);
    setFixed.bulkDelete;([1, 2, 3, 4, 5]);

🛠️ optimize

This getter function returns a function that resize the data store in the bitArray of the SetFixed to the max element's index. It can be called when you think you have a too large range of possibilities for indexes.

var setFixed = new SetFixed(256);
    setFixed.add(100);
    setFixed.optimize();
    // setFixed.length is now 100, setFixed.size is still one

🛠️ resize & resizeUnsafe

This getter function returns a function that resize the data store in the bitArray of the SetFixed. The unsafe version won't check to update the size (the number of bits set to one).

var setFixed = new SetFixed(64);
    setFixed.resize(128);
    // setFixed.length is now 128

🛠️ clear

This getter function returns a function that clears all elements in the SetFixed.

var setFixed = new SetFixed(64);
    setFixed.clear();

🛠️ charge

This getter function returns a function that sets all bits in the BitArray to 1.

var setFixed = new SetFixed(64);
    setFixed.charge();

🛠️ invert

This getter function returns a function that invert all bits in the BitArray.

var setFixed = new SetFixed(64);
    setFixed.invert();

Turbo methods (3200% times faster)

New in V 4.0.0 & beyond

The subsequent methods execute operations at the "32-bit level" within a single integer action across all 32-bit unsigned integers sequentially. This approach is, though untested, presumed to be 32+ times faster.

Every 32 bits involve one binary operation and one writing action. Binary operations are significantly quicker than additions or multiplications since computers inherently process numbers more efficiently in binary (base 2) format.

It uses setFixed.bitArrayData which uses bitArray.data to perform all the operations. As well as "shared" typed arrays you can also obtain a copy using setFixed.bitArrayDataCopy or bitArray.dataCopy.

The unsafe versions doesn't count the number of bits being positive, you can update the size value of the instance manually if you called unsafe turbo methods. It is feasible by calling setFixed.computeSize() which uses bitArray.countOnes() as well as it could have being using bitArray.countZeros().

🛠️ addFromSetFixed & addFromSetFixedUnsafe

This method is used to add the data from another SetFixed instance.

Parameters:

• sf: The primary SetFixed instance from which data will be added.
• sf2 (optional): An additional SetFixed instance. If provided, its data will be merged alongside sf.
• sf3 (optional): An additional SetFixed instance. If provided, its data will be merged alongside sf2.
• sf4 (optional): An additional SetFixed instance. If provided, its data will be merged alongside sf3.

If you provide more than one SetFixed, you'll need to provide the SetFixed's instance you are using to call this method to include it.

Usage:

var setFixed = new SetFixed(64);
    setFixed.addFromSetFixed(sf, sf2, sf3, sf4);

Behavior:

1. Adds the bit array data from the provided sf (and sf2 if available).
2. Computes the number of bits set to 1.

🛠️ differentFromSetFixed & differentFromSetFixedUnsafe

This method computes the bit difference based on the data from another SetFixed instance.

Parameters:

• sf: The primary SetFixed instance from which difference will be computed.
• sf2 (optional): An additional SetFixed instance. If provided, its data will be used alongside sf.

Usage:

var setFixed = new SetFixed(64);
    setFixed.differentFromSetFixed(sf, sf2);

Behavior:

1. Computes the bit difference from the provided sf (and sf2 if available).
2. Computes the number of bits set to 1.

🛠️ sameFromSetFixed & sameFromSetFixedUnsafe

This method computes the bit intersection based on the data from another SetFixed instance.

Parameters:

• sf: The primary SetFixed instance from which intersection will be computed.
• sf2 (optional): An additional SetFixed instance. If provided, its data will be used alongside sf.

Usage:

var setFixed = new SetFixed(64);
    setFixed.sameFromSetFixed(sf, sf2);

Behavior:

1. Computes the bit intersection from the provided sf (and sf2 if available).
2. Computes the number of bits set to 1.

Example

The SmartRunLengthCompress and SmartRunLengthDecompress functions utilize the SetFixed and BitArray data structures to implement a highly efficient form of run-length encoding. By using a 1-bit matchmaking system, SetFixed in conjunction with BitArray facilitates compression that's almost 8 times more space-efficient for non-repeating values, while only consuming an eighth more space for multiple repetitions. This enables the compression of image data, particularly suitable for pixel art with similar colors, into a much more compact form. The design leverages the concept of a "lazy" run-length algorithm, where lengths are not always mandatory, and values without specific lengths are set to false (0) in the bitarray. Thus, it provides a unique and optimized approach to data compression, which balances space savings with the ability to handle both repeating and non-repeating values.

function SmartRunLengthCompress(data_uintX) {
    var lengths = new Uint8Array(data_uintX.length);
    var lengths_l = 0;
    var values_constructor_bits = data_uintX instanceof Uint32Array ? 32: data_uintX instanceof Uint16Array ? 16: 8;
    var values_constructor = values_constructor_bits === 32 ? Uint32Array: values_constructor_bits === 16 ? Uint16Array: Uint8Array;
    var values = new values_constructor(data_uintX.length);
    var values_l = 0;
    var values_using_compression = new SetFixed(data_uintX.length);

    var current = data_uintX[0], latest = data_uintX[1], repeated = 1;
    var i = 1, l = data_uintX.length;

    for(; (i|0) < (l|0); i = i + 1|0){

        latest = data_uintX[i];

        if((latest|0) != (current|0) || (repeated|0) >= 0xFF){ // The value is new or surpass chunk length
            if((repeated|0) > 1){
                // We set the index of the current value to hold a length
                values_using_compression.add(i-repeated);
                // We add the number of repetition inside the lengths array
                lengths[lengths_l] = repeated|0
                lengths_l = lengths_l+1|0;
                // We add the value inside the values array
                values[values_l] = (current|0)>>>0;
                values_l = values_l+1|0;
            }else {
                // We add the value inside the values array
                values[values_l] = (current|0)>>>0;
                values_l = values_l+1|0;
            }
            repeated = 1;
            current = (latest|0)>>>0;
        }else { // The value is repeated
            repeated = repeated+1|0;
        }
    }

    if((repeated|0) > 1){
        // We set the index of the current value to hold a length
        values_using_compression.add(i-1)
        // We add the number of repetition inside the lengths array
        lengths[lengths_l] = repeated|0
        lengths_l = lengths_l+1|0;
        // We add the value inside the values array
        values[values_l] = (current|0)>>>0;
        values_l = values_l+1|0;
    }else {
        // We add the value inside the values array
        values[values_l] = (current|0)>>>0;
        values_l = values_l+1|0;
    }

    return {
        bits: values_constructor_bits,
        lengths: lengths.slice(0, lengths_l),
        values: values.slice(0, values_l),
        matchmaking: values_using_compression.export()
    };
}

function SmartRunLengthDecompress(object) {
    var constructor = object.bits === 32 ? Uint32Array: object.bits === 16 ? Uint16Array: Uint8Array;
    var lengths = object.lengths;
    var values = object.values;
    var matchmaking = SetFixed.import(object.matchmaking);
    var total_length = values.length - lengths.length; // values that aren't alone
    for(var i = 0, l = lengths.length; (i|0) < (l|0); i = i + 1|0){
        total_length = (total_length+lengths[i]|0)>>>0; // values that are repeated
    }

    var output = new constructor(total_length), v = 0, l = 0;
    for(var i = 0; (i|0) < (total_length|0);){
        if(matchmaking.has(i)){
            output.fill(values[v], i, i+lengths[l]|0);
            i = i + lengths[l] | 0;
            l = l + 1 |0;
        }else {
            output[i] = values[v];
            i = i + 1 |0;
        }

        v = v + 1 |0;
    }

    return output;
}

About me

..................            ..
.......                         
.....                           
.........       ...             
......- .  .#######+.           
....    . .##########+.         
.....-+#++###+++++++#+-         
....-######+--------.++-.       
.. .-#######++++-+++-++##+      
... +######++##+-##+-.-##+.     
.. .#######+--+-----..-###.     
...-########--++++---+####.     
...+########+++##++.-####-      
...##########+++++-.#####.      
...#########++####--#####+.     
..-###########+++++.+######- ...
.-##############-++--#######-. .

"Philosophy is the science of estimating values, yet technology is the value of estimating science. My design is my voice while my code is my weapon of choice..."

I am (sometimes) open to work^^ ==> https://www.linkedin.com/in/matias-affolter/