structurae - npm Package Compare versions

Comparing version 1.0.1 to 1.1.0

index.d.ts

@@ -203,5 +203,14 @@ // Type definitions for structurae
 
-export declare class Pool extends Uint16Array {
-    private nextAvailable: number;
-    constructor(size: number);
+export declare class BitArray extends Uint32Array {
+    size: number;
+    private lastPosition: BitPosition;
+
+    constructor(size: number|ArrayLike<number>|ArrayBuffer, ...args: any);
+    getBit(index: number): Bit;
+    setBit(index: number, value: Bit): this;
+    protected getBitPosition(index: number): void;
+    static getLength(size: number): number;
+}
+
+export declare class Pool extends BitArray {
     get(): number;
@@ -212,2 +221,10 @@ free(index: number): void;
 
+export declare class RankedBitArray extends BitArray {
+    setBit(index: number, value: Bit): this;
+    rank(index: number): number;
+    select(index: number): number;
+    private updateRanks(): void;
+    static getLength(size: number): number;
+}
+
 export declare class StringView extends Uint8Array {
@@ -214,0 +231,0 @@ size: number;

index.js

@@ -6,2 +6,3 @@ const BitField = require('./lib/bit-field');
 const Pool = require('./lib/pool');
+const RankedBitArray = require('./lib/ranked-bit-array');
 const RecordArray = require('./lib/record-array');
@@ -38,2 +39,3 @@ const SortedArray = require('./lib/sorted-array');
   Pool,
+  RankedBitArray,
   RecordArray,
@@ -40,0 +42,0 @@ SortedArray,

lib/pool.js

@@ -0,1 +1,2 @@
+const BitArray = require('./bit-array');
 const utilities = require('./utilities');
@@ -6,5 +7,5 @@
  *
- * @extends Uint16Array
+ * @extends BitArray
  */
-class Pool extends Uint16Array {
+class Pool extends BitArray {
   /**
@@ -14,4 +15,4 @@ * @param {number} size the size of the pool
   constructor(size) {
-    super(Pool.getLength(size));
-    this.fill(65535);
+    super(size);
+    this.fill(4294967295);
     Object.defineProperties(this, {
@@ -45,3 +46,3 @@ nextAvailable: { value: 0, writable: true },
 
-    return (nextAvailable << 4) + index;
+    return (nextAvailable << 5) + index;
   }
@@ -56,19 +57,8 @@
   free(index) {
-    const record = index >> 4;
-    const position = index - (record << 4);
-    this[record] |= 1 << position;
-    this.nextAvailable = record;
+    const { bucket, position } = this.getBitPosition(index);
+    this[bucket] |= 1 << position;
+    this.nextAvailable = bucket;
   }
-
-  /**
-   * Returns the length of underlying TypedArray required to hold the pool.
-   *
-   * @param {number} size
-   * @returns {number}
-   */
-  static getLength(size) {
-    return Math.ceil(size / 16);
-  }
 }
 
 module.exports = Pool;

lib/utilities.js

@@ -18,2 +18,18 @@ const log2 = {
   32768: 15,
+  65536: 16,
+  131072: 17,
+  262144: 18,
+  524288: 19,
+  1048576: 20,
+  2097152: 21,
+  4194304: 22,
+  8388608: 23,
+  16777216: 24,
+  33554432: 25,
+  67108864: 26,
+  134217728: 27,
+  268435456: 28,
+  536870912: 29,
+  1073741824: 30,
+  2147483648: 31,
 };
@@ -36,2 +52,3 @@
 function getLSBIndex(value) {
+  if (value === 2147483648) return 31;
   return log2[value & -value];
@@ -38,0 +55,0 @@ }

package.json

 {
   "name": "structurae",
-  "version": "1.0.1",
+  "version": "1.1.0",
   "description": "Data structures for performance-sensitive modern JavaScript applications.",
@@ -5,0 +5,0 @@ "main": "index.js",

README.md

@@ -9,3 +9,6 @@ # Structurae
 
-- [BitField](https://github.com/zandaqo/structurae#BitField) - stores and operates on data in Numbers and BigInts treating them as bitfields.
+- Bits:
+    - [BitField](https://github.com/zandaqo/structurae#BitField) - stores and operates on data in Numbers and BigInts treating them as bitfields.
+    - BitArray - an array of bits implemented with Uint32Array.
+    - RankedBitArray - extends BitArray with O(1) time rank and O(logN) select methods.
 - [Graphs](https://github.com/zandaqo/structurae#Graphs):
@@ -12,0 +15,0 @@ - [Graph](https://github.com/zandaqo/structurae#Graph) -  extends an adjacency list/matrix structure and provides methods for traversal (BFS, DFS),

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

155622

increased by3.6%

Number of package files

23

increased by9.52%

Lines of code

4356

increased by4.89%

Number of lines in readme file

696

increased by0.43%

No dependency changes